rle-compressie-algoritme. Coderingsmethoden

Gegevens die worden ondersteund door de meeste bestandsformaten voor rasterafbeeldingen: TIFF, BMP en PCX. RLE is geschikt voor het comprimeren van elk type gegevens, ongeacht de informatie-inhoud, maar de inhoud van de gegevens heeft invloed op de compressieverhouding. Hoewel de meeste RLE-algoritmen geen hoge compressieverhoudingen kunnen bereiken complexe methoden, dit hulpmiddel eenvoudig te implementeren en snel te realiseren, waardoor het een goed alternatief is.

Waar is het RLE-compressie-algoritme op gebaseerd?

RLE werkt door te verminderen fysieke grootte herhalende tekenreeks. Deze string, run genaamd, wordt meestal gecodeerd in twee bytes. De eerste byte vertegenwoordigt het aantal tekens in de run en wordt de runteller genoemd. In de praktijk kan een gecodeerde run variëren van 1 tot 128 tot 256 tekens. De teller bevat doorgaans het aantal tekens minus één (een waarde variërend van 0 tot 127 en 255). De tweede byte is de waarde van het teken in de run, die zich in het waardenbereik van 0 tot 255 bevindt en de triggerwaarde wordt genoemd.

Zonder compressie heeft een tekenreeks van 15 tekens doorgaans 15 bytes nodig om op te slaan:

AAAAAAAAAAAAAAA.

Op dezelfde regel zijn na RLE-codering slechts twee bytes vereist: 15A.

15A-codering gegenereerd om aan te geven tekenreeks, wordt een RLE-pakket genoemd. In deze code is de eerste byte, 15, de runteller en bevat deze het vereiste aantal herhalingen. De tweede byte, A, is de runwaarde en bevat de feitelijke herhalende waarde tijdens de run.

Elke keer dat het run-teken verandert, of elke keer dat het aantal tekens in de run groter wordt, wordt er een nieuw pakket gegenereerd maximale hoeveelheid. Laten we aannemen dat een string van 15 tekens volgens de voorwaarden 4 verschillende tekens bevat:

Met behulp van codering op stringlengte kan het worden gecomprimeerd in vier pakketten van twee bytes:

Na codering van de stringlengte zou een string van 15 bytes slechts acht bytes aan gegevens nodig hebben om de string weer te geven, in tegenstelling tot de oorspronkelijke 15 bytes. In dit geval leverde runtime-codering een compressieverhouding op van bijna 2 op 1.

Eigenaardigheden

Lange runs zijn zeldzaam in sommige gegevenstypen. Bijvoorbeeld, leesbare tekst ASCII bevat zelden lange runs. In het vorige voorbeeld was de laatste run (met het teken t) slechts één teken lang. De run van 1 karakter werkt nog steeds. Zowel het aantal runs als de runwaarde moeten voor elke run in 2 tekens worden vastgelegd. Om de kilometerstand te coderen met behulp van het RLE-algoritme, is informatie nodig die uit minimaal twee tekens bestaat. Als gevolg hiervan neemt het uitvoeren van afzonderlijke tekens feitelijk meer ruimte in beslag. Om dezelfde redenen blijven gegevens die volledig bestaan ​​uit runs van twee tekens daarna ongewijzigd RLE-codering.

De RLE-compressie-algoritmeschema's zijn eenvoudig en hoge snelheid uitvoering, maar hun effectiviteit hangt af van het type afbeeldingsgegevens dat wordt gecodeerd. Zwart-wit beeld, dat is meestal wit, bijvoorbeeld de pagina's van een boek, zullen dankzij grote hoeveelheid aangrenzende gegevens die dezelfde kleur hebben. Een afbeelding met veel kleuren, zoals een foto, wordt echter niet zo goed gecodeerd. Dit komt door het feit dat de complexiteit van het beeld wordt uitgedrukt als een groot getal verschillende kleuren. En vanwege deze complexiteit zullen er relatief weinig runs van dezelfde kleur zijn.

Lengtecoderingsopties

Er zijn verschillende runtime-coderingsopties. Beeldgegevens worden doorgaans gecodeerd in een sequentieel proces waarbij visuele inhoud wordt behandeld als een 1D-stream in plaats van als een 2D-gegevenskaart. Tijdens opeenvolgende verwerking rasterafbeelding wordt gecodeerd vanaf de linkerbovenhoek en gaat van links naar rechts langs elke scanlijn naar de rechteronderhoek van de bitmap. Maar alternatieve RLE-schema's kunnen ook worden geschreven om gegevens over de lengte van een bitmap langs kolommen te coderen voor compressie in 2D-tegels, of zelfs om pixels diagonaal op een zigzag-manier te coderen. Vreemde varianten van RLE kunnen worden gebruikt in zeer gespecialiseerde toepassingen, maar zijn over het algemeen vrij zeldzaam.

Coderingsalgoritme met padlengtefout

Een andere zelden geziene optie is het RLE-coderingsalgoritme met runlengtefout. Deze tools voeren doorgaans verliesloze compressie uit, maar negeren gegevens tijdens het coderingsproces, meestal door een of twee kleine bestanden op nul te zetten aanzienlijke stukjes ov in elke pixel, kan de compressieverhoudingen verhogen zonder de kwaliteit van complexe afbeeldingen negatief te beïnvloeden. Dit RLE-algoritmeprogramma werkt alleen goed met afbeeldingen echte wereld, die veel subtiele variaties in pixelwaarden bevatten.

Cross-codering

Cross-encoding is het samenvoegen van scanlijnen die optreedt wanneer het compressieproces het onderscheid tussen de originele lijnen verliest. Als individuele lijngegevens worden gecombineerd door het RLE-herhalingscoderingsalgoritme, is het punt waar de ene scanlijn vastloopt en de andere verloren gaat kwetsbaar en moeilijk te detecteren.

Soms vindt kruiscodering plaats, wat het decoderingsproces bemoeilijkt en tijd kost. Voor ris deze methode bedoeld om de rasterafbeelding langs scanlijnen te ordenen. Hoewel veel specificaties voor bestandsformaten expliciet aangeven dat lijngegevens individueel moeten worden gecodeerd, coderen veel toepassingen deze afbeeldingen als een continue stroom, waarbij lijngrenzen worden genegeerd.

Hoe codeer je een afbeelding met behulp van het RLE-algoritme?

Individuele codering van scanlijnen is voordelig in gevallen waarin de toepassing slechts een deel van het beeld moet gebruiken. Laten we zeggen dat een foto 512 scanlijnen bevat en alleen de lijnen 100 tot en met 110 hoeft weer te geven. Als we niet wisten waar de scanlijnen begonnen en eindigden met de gecodeerde beeldgegevens, zou onze applicatie de lijnen 1 tot en met 100 moeten decoderen voordat ze de tien regels die nodig zijn. Als de overgangen tussen scanlijnen gemarkeerd zouden zijn met een gemakkelijk herkenbare scheidingsteken, zou de applicatie eenvoudig de gecodeerde gegevens kunnen lezen en de markeringen tellen totdat de benodigde lijnen bereikt werden. Maar deze aanpak zou tamelijk ineffectief zijn.

Alternatieve optie

Een andere optie voor het bepalen van het startpunt van een bepaalde scanlijn in een blok gecodeerde gegevens is het construeren van een scanlijntabel. Dit tafel structuur bevat doorgaans één element voor elke scanlijn in de afbeelding, en elk element bevat de offsetwaarde van de overeenkomstige scanlijn. Om het eerste RLE-pakket van scanlijn 10 te vinden, hoeft de decoder alleen maar de offsetpositiewaarden op te zoeken die zijn opgeslagen in het tiende element van de scanlijnopzoektabel. De scanlinetabel kan ook het aantal bytes bevatten dat wordt gebruikt om elke lijn te coderen. Met behulp van deze methode om het eerste RLE-pakket van scanline 10 te vinden, zal uw decoder de waarden van de eerste 9 scanline-tabelelementen samenvoegen. Het eerste pakket voor scanlijn 10 zal beginnen bij deze byte-offset vanaf het begin van de RLE-gecodeerde beeldgegevens.

Meeteenheden

De onderdelen van lengtecoderingsalgoritmen die verschillen, zijn de beslissingen die worden genomen op basis van het type gegevens dat wordt gedecodeerd (bijvoorbeeld de lengte van de gegevensrun). RLE-circuits gebruikt voor compressie rasterafbeeldingen, worden gewoonlijk onderverdeeld in klassen op basis van het type atomaire (d.w.z. meest fundamentele) elementen dat ze coderen. De drie klassen die door de meeste grafische bestandsformaten worden gebruikt, zijn bit, byte en pixel RLE.

Compressiekwaliteit

De bitniveaus van RLE-schema's coderen reeksen van meerdere bits in een scanlijn en negeren byte- en woordgrenzen. Alleen monochrome (zwart-wit), 1-bit afbeeldingen bevatten voldoende hoeveelheid bits om deze RLE-coderingsklasse efficiënt te maken. Een typisch RLE-schema op bitniveau codeert van één tot 128 bits in een pakket van één byte. De minst significante zeven bits bevatten het aantal runs minus één, en het meest significante bit bevat de bitrunwaarde van 0 of 1. Een run langer dan 128 pixels wordt opgesplitst in meerdere RLE-gecodeerde pakketten.

Uitzonderingen

RLE-schema's op byteniveau coderen reeksen van identieke bytewaarden, waarbij enkele bits en woordgrenzen in de scanlijn worden genegeerd. Het meest gebruikelijke RLE-schema op byteniveau codeert byteruns in pakketten van 2 bytes. De eerste byte bevat een teller van 0 tot 255, en de tweede byte bevat de byte-triggerwaarde. Het is ook gebruikelijk om het coderingsschema van twee bytes aan te vullen met de mogelijkheid om letterlijke, ongeschreven byteruns in de gecodeerde datastroom op te slaan.

In een dergelijk ontwerp bevatten de minst significante zeven bits van de eerste byte het aantal runs minus één, en het meest significante bit van het eerste byte is de triggertype-indicator die volgt op het aantal runs. Als de meest significante bit is ingesteld op 1, duidt dit op een gecodeerde run. Gecodeerde runs worden gedecodeerd door de runwaarde te lezen en deze het aantal keren te herhalen dat wordt aangegeven door het aantal cycli. Als de meest significante bit is ingesteld op 0, wordt een letterlijke run in kaart gebracht, wat betekent dat de bytes voor de volgende runtelling letterlijk worden gelezen uit de gecodeerde beeldgegevens. De runcounterbyte bevat dan een waarde in het bereik van 0 tot 127 (runcounter minus één). RLE-schema's op byteniveau zijn goed voor afbeeldingsgegevens die zijn opgeslagen als één byte per pixel.

RLE-circuits op pixelniveau worden gebruikt wanneer twee of meer opeenvolgende bytes aan beeldgegevens worden gebruikt om de waarden van een enkele pixel op te slaan. Op pixelniveau worden bits genegeerd en worden bytes alleen geteld om elke pixelwaarde te identificeren. De grootte van de gecodeerde pakketten hangt af van de grootte van de gecodeerde pixelwaarden. Het aantal bits of bytes per pixel wordt opgeslagen in de header van het afbeeldingsbestand. Een reeks beeldgegevens, opgeslagen als pixelwaarden van 3 bytes, wordt gecodeerd in een pakket van 4 bytes, waarbij één byte van het aantal bewerkingen wordt gevolgd door drie bytes aan bytes. De coderingsmethode blijft hetzelfde als bij byte RLE.

Run-length-codering (RLE) of Repeat Coding is een eenvoudig datacompressie-algoritme dat werkt op dataruns, dat wil zeggen reeksen waarin hetzelfde teken meerdere keren achter elkaar voorkomt. Bij het coderen wordt een reeks identieke tekens waaruit een reeks bestaat vervangen door een reeks die het herhalende teken zelf en het aantal herhalingen ervan bevat.

Kenmerken van het RLE-algoritme:

Compressieverhoudingen: Eerste optie: 32, 2, 0,5. Tweede optie: 64, 3, 128/129. (Beste, gemiddelde, slechtste kansen). Afbeeldingsklasse: Het algoritme is gericht op afbeeldingen met een groot aantal kleuren: zakelijke en wetenschappelijke afbeeldingen. Symmetrie: Ongeveer één.

Functies: NAAR positieve aspecten algoritme kan misschien alleen worden toegeschreven aan het feit dat het niet nodig is extra geheugen bij het archiveren en uitpakken, en werkt bovendien snel. Interessante functie groepscodering houdt in dat de archiveringsgraad van sommige afbeeldingen aanzienlijk kan worden vergroot door simpelweg de volgorde van de kleuren in het afbeeldingspalet te wijzigen.

Eerste versie van het algoritme

Dit algoritme is uiterst eenvoudig te implementeren.<Groepscodering - van het Engelse Run Length Encoding (RLE) - is een van de oudste en eenvoudigste algoritmen voor grafische archivering. De afbeelding daarin (zoals in verschillende hieronder beschreven algoritmen) wordt langs rasterlijnen in een keten van bytes getekend. De compressie zelf in RLE vindt plaats vanwege het feit dat de bronafbeelding ketens van identieke bytes bevat. Vervang ze door paren

herhalingsteller, waarde > vermindert gegevensredundantie. Het algoritme is ontworpen voor

zakelijke afbeeldingen

- afbeeldingen met grote herhalende kleurvlakken. De situatie waarin het bestand groeit, is niet zo zeldzaam voor dit eenvoudige algoritme. Dit kan eenvoudig worden verkregen door groepscodering toe te passen op verwerkte kleurenfoto's. Om een ​​afbeelding te verdubbelen, moet deze worden toegepast op een afbeelding waarin de waarden van alle pixels groter zijn dan binair 11000000 en niet in paren achter elkaar worden herhaald.

Tweede versie van het algoritme

De tweede versie van dit algoritme heeft een grotere maximale archiveringsratio en vergroot de grootte van het originele bestand minder. 29. lzw-compressie-algoritme, Het algoritme is vernoemd naar de eerste letters van de achternamen van de ontwikkelaars: Lempel Ziv.

En Wel Het LZW-algoritme is gebaseerd op het idee om het alfabet uit te breiden, waardoor extra tekens kunnen worden gebruikt om reeksen reguliere tekens weer te geven. Als u bijvoorbeeld 9-bits ASCII-codes gebruikt in plaats van 8-bits, krijgt u 256 extra tekens. Het werk van de compressor komt neer op het bouwen van een tabel bestaande uit rijen en de bijbehorende codes. Het compressie-algoritme komt op het volgende neer: het programma leest het volgende teken en voegt dit toe aan de string. Als de rij al in de tabel staat, gaat het lezen verder. Zo niet, gegeven lijn wordt toegevoegd aan de tekenreekstabel. Hoe meer dubbele regels er zijn, hoe meer de gegevens worden gecomprimeerd.

Terugkerend naar het voorbeeld met de telefoon, kunnen we, met behulp van een zeer vereenvoudigde analogie, zeggen dat door de invoer 233 34 44 te comprimeren met behulp van de LZW-methode, we tot de introductie van nieuwe regels zullen komen - 333 en 444 en deze uit te drukkenCompressieverhoudingen: Ongeveer 1000, 4, 5/7 (beste, gemiddelde, slechtste kansen). Een compressie van 1000 keer wordt alleen bereikt bij afbeeldingen met één kleur die veelvouden zijn van ongeveer 7 MB groot. Afbeeldingsklasse: LZW richt zich op 8-bits afbeeldingen die op een computer zijn gebouwd. Comprimeert vanwege identieke subketens in de stroom. Symmetrie: Bijna symmetrisch, op voorwaarde dat de zoekactie voor een rij in een tabel optimaal wordt uitgevoerd.

Functies: De situatie waarin het algoritme de afbeelding vergroot, is uiterst zeldzaam.

LZW is universeel - het zijn de varianten die in conventionele archiveringssystemen worden gebruikt.

Het compressieproces ziet er vrij eenvoudig uit. We lezen de karakters van de invoerstroom opeenvolgend en controleren of een dergelijke string bestaat in de stringtabel die we hebben gemaakt. Als er een regel is, lezen we het volgende teken, en als er geen regel is, voeren we de code voor de vorige gevonden regel in de stream in, voeren de regel in de tabel in en starten het zoeken opnieuw.

Het bijzondere van LZW is dat je voor decompressie de tabel met tekenreeksen niet in een bestand hoeft op te slaan om te decomprimeren. Het algoritme is zo ontworpen dat we de stringtabel kunnen herstellen met slechts een stroom codes.

Eerste versie van het algoritme Dit algoritme is uiterst eenvoudig te implementeren. Het coderen van herhalingslengtes - van English Run Length Encoding (RLE) - is een van de oudste en eenvoudigste algoritmen voor grafische archivering. De afbeelding daarin (zoals in verschillende hieronder beschreven algoritmen) wordt langs rasterlijnen in een keten van bytes getekend. De compressie zelf in RLE vindt plaats vanwege het feit dat de bronafbeelding ketens van identieke bytes bevat.<счетчик повторений, значение>Vervang ze door paren

vermindert gegevensredundantie. Algoritme decompressie

het ziet er zo uit:

Initialisatie(...); Doen( byte

= Beeldbestand.ReadNextByte(); if(is een teller(byte)) ( counter = Low6bits(byte)+1; waarde = ImageFile.ReadNextByte(); for(i=l om te counteren)

GedecomprimeerdBestand.WriteByte(waarde))

DecompressionFile.WriteByte(byte)) while (UmageFile.EOF ()) ;

In dit algoritme is het teken van een teller het teken in de twee bovenste bits van het leesbestand:

Dienovereenkomstig worden de resterende 6 bits besteed aan een teller, die waarden van 1 tot 64 kan aannemen. We zetten een reeks van 64 herhalende bytes om in 2 bytes, dat wil zeggen, we comprimeren deze 32 keer. Oefening. Maak een algoritme compressie

voor de eerste versie van het RLE-algoritme. Het algoritme is ontworpen voor zakelijke afbeeldingen: afbeeldingen met grote herhalende kleuren. De situatie waarin het bestand groeit, hiervoor niet zo zeldzaam. Dit kan eenvoudig worden verkregen door groepscodering toe te passen op verwerkte kleurenfoto's. Om een ​​afbeelding 2 keer te vergroten, moet deze worden toegepast op een afbeelding waarin de waarden van alle pixels groter zijn dan binair 11000000 en niet paarsgewijs achter elkaar worden herhaald.

Oefening. Stel 2-3 voorbeelden van ‘slechte’ afbeeldingen voor voor het RLE-algoritme. Leg uit waarom de maat gecomprimeerd bestand groter formaat bronbestand.

Dit algoritme is geïmplementeerd in PCX-formaat. Zie voorbeeld in bijlage 2.

Tweede versie van het algoritme

De tweede versie van dit algoritme heeft een hogere maximale compressieverhouding en wordt minder groot bronbestand. Het decompressie-algoritme ervoor ziet er als volgt uit:

het ziet er zo uit:

byte = Beeldbestand.ReadNextByte(); teller = Low7bits(byte)+1; if (if herhaal teken (byte)) ( waarde = ImageFile.ReadNextByte(); for (i=l om te counteren)

GecomprimeerdBestand.WriteByte(waarde)

for(i«=l om tegen te gaan) (

waarde = ImageFile.ReadNextByte(); GecomprimeerdBestand.WriteByte(waarde) } ) while (! ImageFile.EOFO) ;

Het teken van herhaling in dit algoritme is een één in het meest significante bit van de overeenkomstige byte:

J 0 7 bit___ I Wat ik moet overslaan I ... Wat ik moet overslaan I

^1 7 bits I Wat te herhalen I

Hoe kun je eenvoudig berekenen beste scenario dit algoritme comprimeert het bestand 64 keer (en niet 32 ​​keer, zoals in de vorige versie), in het slechtste geval vergroot het het met 1/128. De gemiddelde compressieverhouding van dit algoritme ligt op het niveau van de eerste optie.

(Oefening. Maak een compressie-algoritme voor de tweede versie van het RLE-algoritme.

Soortgelijke compressieschema's worden gebruikt als een van de ondersteunde algoritmen TIFF-formaat, evenals in TGA-formaat.

Kenmerken van het RLE-algoritme:

Compressieniveaus: eerste optie: 32, 2, 0,5. Tweede optie: 64, 3, I 128/129. (Beste, gemiddelde, slechtste graad).

Afbeeldingsklasse: Het algoritme is gericht op afbeeldingen met niet-ik groot aantal kleuren: zakelijke en wetenschappelijke afbeeldingen.

Symmetrie: ongeveer één.

Functies: De positieve aspecten van het algoritme kunnen misschien alleen worden toegeschreven aan het feit dat er geen extra geheugen voor nodig is \ bij het archiveren en uitpakken, en werkt bovendien snel. Interessant bijzonder! Het voordeel van groepscodering is dat de mate van archivering voor niet-! welke afbeeldingen aanzienlijk kunnen worden verbeterd door simpelweg de volgorde van de kleuren in het afbeeldingenpalet te wijzigen.

• Handleiding

Lang geleden, toen ik nog een naïeve schooljongen was, werd ik plotseling vreselijk nieuwsgierig: hoe nemen gegevens in archieven op magische wijze minder ruimte in beslag? Nadat ik mijn vertrouwde inbelverbinding had geïnstalleerd, begon ik op internet te surfen op zoek naar een antwoord, en vond veel artikelen met een vrij gedetailleerde presentatie van de informatie die mij interesseerde. Maar geen van hen leek toen gemakkelijk te begrijpen - de codelijsten leken op Chinese geletterdheid, en pogingen om de ongebruikelijke terminologie en verschillende formules te begrijpen werden niet met succes bekroond.

Daarom is het doel van dit artikel om een ​​idee te geven van de eenvoudigste compressie-algoritmen voor degenen wier kennis en ervaring hen nog niet in staat stellen om onmiddellijk meer professionele literatuur te begrijpen, of wier profiel helemaal ver verwijderd is van dergelijke onderwerpen. Die. Ik zal je in één oogopslag vertellen over enkele van de eenvoudigste algoritmen en voorbeelden geven van hun implementatie zonder kilometerslange codelijsten.

Ik waarschuw je meteen dat ik de details van de implementatie van het coderingsproces en dergelijke nuances niet zal overwegen efficiënt zoeken voorkomens van de string. Het artikel zal alleen betrekking hebben op de algoritmen zelf en de manieren om de resultaten van hun werk te presenteren.

RLE - compactheid van uniformiteit

Implementatie voorbeeld

Voor velen zal het veel gebruikelijker zijn om deze gegevens in de vorm van een hex-dump te zien:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF FF 00 00

Nadat we erover hadden nagedacht, besloten we dat het goed zou zijn om dergelijke sets op de een of andere manier te comprimeren om ruimte te besparen. Om dit te doen, hebben we ze geanalyseerd en een patroon geïdentificeerd: heel vaak komen we deelreeksen tegen die uit identieke elementen bestaan. Natuurlijk is RLE hier perfect voor!

Laten we onze gegevens coderen met behulp van de nieuw verworven kennis: 6x0, 4, 2, 0, 7x4, 4x80, 0, 4x2, 5x255, 2x0.

Het is tijd om ons resultaat op de een of andere manier te presenteren in een vorm die begrijpelijk is voor een computer. Om dit te doen, moeten we in de datastroom op de een of andere manier enkele bytes scheiden van de gecodeerde strings. Omdat het volledige bereik van bytewaarden door onze gegevens wordt gebruikt, zal het niet mogelijk zijn om voor onze doeleinden eenvoudigweg een bereik van waarden te selecteren.

Er zijn minstens twee manieren om uit deze situatie te komen:

1. Selecteer één bytewaarde als indicator voor een gecomprimeerde keten en ontsnap eraan in geval van een botsing met echte gegevens. Als we bijvoorbeeld de waarde 255 gebruiken voor “officiële” doeleinden, zullen we, wanneer we deze waarde tegenkomen in de invoergegevens, gedwongen worden om “255, 255” te schrijven en een maximum van 254 na de indicator te gebruiken.
2. Structureer de gecodeerde gegevens en geef de hoeveelheid aan, niet alleen voor herhaalde, maar ook voor daaropvolgende afzonderlijke elementen. Dan weten wij vooraf waar welke gegevens zich bevinden.

Nu hebben we dus twee soorten reeksen: ketens van afzonderlijke elementen (zoals “4, 2, 0”) en ketens van identieke elementen (zoals “0, 0, 0, 0, 0, 0”). Laten we één bit in de “service” bytes selecteren voor het type reeks: 0 - enkele elementen, 1 - identiek. Laten we hiervoor bijvoorbeeld het meest significante bit van de byte nemen.

In de resterende 7 bits slaan we de lengte van de reeksen op, d.w.z. de maximale lengte van de gecodeerde reeks is 127 bytes. We zouden bijvoorbeeld twee bytes kunnen toewijzen voor servicebehoeften, maar in ons geval zijn zulke lange reeksen uiterst zeldzaam, dus het is gemakkelijker en economischer om ze eenvoudigweg in kortere reeksen op te delen.

Het blijkt dat we eerst de lengte van de reeks naar de uitvoerstroom zullen schrijven, en vervolgens één herhaalbare waarde of een reeks niet-herhaalbare elementen van de opgegeven lengte.

Het eerste dat opvalt, is dat we in deze situatie een aantal ongebruikte waarden hebben. Er kunnen geen reeksen zijn met een lengte van nul, dus we kunnen de maximale lengte verhogen tot 128 bytes door er één af te trekken van de lengte bij het coderen en één toe te voegen bij het decoderen. Op deze manier kunnen we lengtes van 1 tot 128 coderen in plaats van lengtes van 0 tot 127.

Het tweede wat je opvalt is dat er geen reeksen van identieke elementen met een eenheidslengte zijn. Daarom zullen we bij het coderen een andere aftrekken van de lengte van dergelijke reeksen, waardoor hun maximale lengte wordt vergroot tot 129 (de maximale lengte van een keten van afzonderlijke elementen is nog steeds 128). Die. Onze kettingen van identieke elementen kunnen een lengte hebben van 2 tot 129.

Laten we onze gegevens opnieuw coderen, maar nu in een vorm die begrijpelijk is voor een computer. We zullen servicebytes schrijven als , waarbij T het reekstype is en L de lengte. Laten we er meteen rekening mee houden dat we de lengtes in een gewijzigde vorm schrijven: voor T=0 trekken we één af van L, en voor T=1 trekken we er twee af.

0, , 4, 2, 0, , 4, , 80, , 0, , 2, , 255, , 0

Laten we proberen ons resultaat te decoderen:

• . T=1, wat betekent dat de volgende byte L+2 (4+2) keer wordt herhaald: 0, 0, 0, 0, 0, 0.
• . T=0, wat betekent dat we eenvoudigweg L+1 (2+1) bytes lezen: 4, 2, 0.
• . T=1, herhaal de volgende byte 5+2 keer: 4, 4, 4, 4, 4, 4, 4.
• . T=1, herhaal de volgende byte 2+2 keer: 80, 80, 80, 80.
• . T=0, lees 0+1 bytes: 0.
• . T=1, herhaal byte 2+2 keer: 2, 2, 2, 2.
• . T=1, herhaal byte 3+2 keer: 255, 255, 255, 255, 255.
• . T=1, herhaal byte 0+2 keer: 0, 0.

En nu laatste stap: sla het resultaat op als een byte-array. Een paar dat in een byte is verpakt, ziet er bijvoorbeeld als volgt uit:

Als resultaat krijgen we het volgende:
0000: 84 00 02 04 02 00 85 04 82 80 00 00 82 02 83 FF
0010: 80 00

Op deze eenvoudige manier in dit voorbeeld We hebben 18 bytes uit 32 bytes aan invoergegevens gehaald. Geen slecht resultaat, vooral als je bedenkt dat het bij langere ketens veel beter kan zijn.

Mogelijke verbeteringen

Extra efficiëntie kan worden bereikt door gebruik te maken van heuristische methoden codering. Laten we bijvoorbeeld de volgende keten coderen met behulp van onze methode: “ABBA”. We krijgen " , A, , B, , A" - d.w.z. We hebben 4 bytes omgezet in 6, waardoor de oorspronkelijke gegevens maar liefst anderhalf keer zijn opgeblazen! En hoe meer van zulke korte, afwisselende reeksen van verschillende typen, hoe meer redundante gegevens er zijn. Als we hiermee rekening houden, kunnen we het resultaat coderen als “, A, B, B, A” - we zouden slechts één extra byte verspillen.

LZ77 - beknoptheid in herhaling

Het basisidee is om identieke reeksen elementen te coderen. Dat wil zeggen, als een bepaalde keten van elementen meer dan eens voorkomt in de invoergegevens, dan kunnen alle volgende exemplaren ervan worden vervangen door “links” naar de eerste instantie ervan.

Net als andere algoritmen in deze familie gebruikt LZ77 een woordenboek waarin eerder aangetroffen reeksen worden opgeslagen. Om dit te doen, past hij het principe van de zogenaamde toe. "schuifvenster": een gebied altijd vóór de huidige coderingspositie waarbinnen we referenties kunnen adresseren. Dit venster is een dynamisch woordenboek voor dit algoritme - elk element daarin komt overeen met twee attributen: positie in het venster en lengte. Hoewel binnen fysieke zin het is gewoon een stukje geheugen dat we al hebben gecodeerd.

Implementatie voorbeeld

“De compressie en de decompressie laten een indruk achter. Hahahaha!”

Zo ziet het er in het geheugen uit (ANSI-codering):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20 De compressie
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65 en de decompre
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69 ssion laat een i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 onderdrukking. Haha
0040: 61 68 61 68 61 21 ahaha!

We hebben nog geen beslissing genomen over de grootte van het venster, maar we zullen het erover eens zijn dat het groter is dan de grootte van de gecodeerde string. Laten we proberen alle herhalende tekenreeksen te vinden. Een keten wordt beschouwd als een reeks tekens langer dan één. Als de keten deel uitmaakt van een langere zich herhalende keten, zullen we deze negeren.

“De compressie en t de leave[ an] i . Haha!

Laten we voor meer duidelijkheid naar het diagram kijken, waar we de overeenkomst kunnen zien tussen de herhaalde reeksen en hun eerste optreden:

Misschien is het enige onduidelijke punt hier de reeks “Hahahahaha!”, omdat de reeks karakters “ahahaha” overeenkomt met een korte reeks “ah”. Maar er is hier niets ongewoons, we hebben een truc gebruikt waarmee het algoritme soms kan werken zoals de eerder beschreven RLE.

Feit is dat we bij het uitpakken uit het woordenboek zullen lezen gespecificeerde hoeveelheid karakters. En aangezien de hele reeks periodiek is, d.w.z. de gegevens daarin worden met een bepaalde periode herhaald, en de symbolen van de eerste periode bevinden zich vlak voor de uitpakpositie, en van daaruit kunnen we de hele keten opnieuw creëren door simpelweg de symbolen van de vorige periode naar de volgende te kopiëren.

Dat is geregeld. Laten we nu de gevonden herhalingen vervangen door links naar het woordenboek. We zullen de link in het formaat schrijven, waarbij P de positie is van de eerste keer dat de ketting in de regel voorkomt, L de lengte ervan.

“De compressie en t de laat i. Haha!

Maar vergeet niet dat we te maken hebben met een schuifraam. Voor een beter begrip, zodat de links niet afhankelijk zijn van de venstergrootte, vervangen we de absolute posities door het verschil tussen deze posities en de huidige coderingspositie.

“De compressie en t de laat i. Haha!

Nu hoeven we alleen maar P af te trekken van de huidige coderingspositie om de absolute positie in de string te krijgen.

Het is tijd om te beslissen over de grootte van het venster en maximale lengte gecodeerde zin. Omdat we met tekst te maken hebben, zullen er zelden bijzonder lange herhalende reeksen in voorkomen. Laten we dus bijvoorbeeld 4 bits toewijzen voor hun lengte - een limiet van 15 tekens per keer is voor ons voldoende.

Maar de grootte van het venster bepaalt hoe diep we naar identieke ketens zullen zoeken. Omdat we met kleine teksten te maken hebben, is het goed om het aantal bits dat we gebruiken aan te vullen tot twee bytes: we zullen links in het bereik van 4096 bytes behandelen, waarbij we hiervoor 12 bits gebruiken.

Uit ervaring met RLE weten we dat niet alle waarden gebruikt kunnen worden. Uiteraard kan de link dat wel hebben minimale waarde Om terug te keren naar het bereik 1..4096 moeten we daarom één van de referentie aftrekken bij het coderen, en deze weer toevoegen bij het decoderen. Hetzelfde geldt voor reekslengtes: in plaats van 0..15 zullen we het bereik 2..17 gebruiken, omdat we niet met nullengtes werken en individuele tekens geen reeksen zijn.

Laten we dus onze gecodeerde tekst presenteren, rekening houdend met deze amendementen:

“De compressie en t de laat i. Haha!

Nu moeten we de gecomprimeerde ketens op de een of andere manier scheiden van de rest van de gegevens. De meest gebruikelijke manier is om de structuur opnieuw te gebruiken en expliciet aan te geven waar de gegevens zijn gecomprimeerd en waar niet. Om dit te doen, verdelen we de gecodeerde gegevens in groepen van acht elementen (symbolen of links), en vóór elk van deze groepen voegen we een byte in, waarbij elke bit overeenkomt met het type element: 0 voor een symbool en 1 voor een koppeling.

Wij verdelen in groepen:

• "De comp"
• "reactie"
• "en t de"
• "vertrekken"
• "i. Haha"

"(0,0,0,0,0,0,0,0) De comp(0,0,0,0,0,0,0,0) ressie (0,0,0,0,0,1 ,0,0) en t de(1,0,0,0,0,0,1,0) laten (0,1,0,0,0,0,0,1) i achter. Ha (0)!”

Dus als we tijdens het uitpakken bit 0 tegenkomen, lezen we eenvoudigweg het teken in de uitvoerstroom, als we bit 1 lezen, lezen we de link, en uit de link lezen we de reeks uit het woordenboek.

Nu hoeven we alleen nog maar het resultaat in een byte-array te groeperen. Laten we afspreken dat we bits en bytes in volgorde van hoog naar laag gebruiken. Laten we eens kijken hoe links in bytes worden verpakt met behulp van een voorbeeld:

Als gevolg hiervan zal onze gecomprimeerde stream er als volgt uitzien:

0000: 00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f #De comp#ressio
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #en t##de###l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 dakrand## #i##. Haha
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00 ###!

Mogelijke verbeteringen

“De lange goooooong. De loooooower gebonden."

Laten we alleen reeksen zoeken voor het woord “loooooower”:

“De lange goooooong. De beste grens."

Om een ​​dergelijk resultaat te coderen, hebben we vier bytes per referentie nodig. Het zou echter economischer zijn om dit te doen:

“De lange goooooong. De ik was gebonden.'

Dan zouden we een byte minder uitgeven.

In plaats van een conclusie

Hun voordeel is eenvoud en snelheid, en complexere en effectievere algoritmen kunnen gebaseerd zijn op hun principes en hun combinaties.

Ik hoop dat de essentie van deze op deze manier gepresenteerde algoritmen iemand zal helpen de basisprincipes te begrijpen en naar serieuzere zaken te gaan kijken.

Een typisch beeld gemaakt door een digitale camera heeft een resolutie van ongeveer 3000x2000, d.w.z. ongeveer 6 megapixels; Meestal worden 24 bits per pixel gebruikt om kleur over te brengen. Het volume van de originele gegevens is dus ongeveer 17 megabytes. Voor professionele apparaten Bij het invoeren van afbeeldingen kan de grootte van het resulterende raster aanzienlijk groter zijn en kan de kleurdiepte 48 bits per pixel bereiken (“Moderne raster grafische hardware”). Dienovereenkomstig kan de grootte van één afbeelding meer dan 200 megabytes zijn. Daarom zijn algoritmen zeer relevant compressie afbeeldingen, of, met andere woorden, algoritmen die de hoeveelheid gegevens die een afbeelding vertegenwoordigen, verminderen.

Er zijn twee hoofdklassen van algoritmen:

1. A wordt een algoritme genoemd verliesloze compressie(Engelse verliesloze compressie), als er een algoritme A -1 is (invers ten opzichte van A), zodat voor elk beeld I A(I) = I 1 en A -1 (I 1) = I. Afbeelding I wordt gedefinieerd als een reeks pixelattribuutwaarden; Na het toepassen van algoritme A op I verkrijgen we dataset I 1 . Hierbij wordt verliesloze compressie gebruikt grafische formaten afbeeldingsrepresentaties zoals: GIF, PCX, PNG, TGA, TIFF 1 Over het algemeen gesproken, dit formaat ondersteunt ook verliesgevende compressie., veel eigen formaten van fabrikanten van digitale camera's, enz.);
2. A wordt een algoritme genoemd verliesgevende compressie(eng. lossy compressie), als dit niet de mogelijkheid biedt om de originele afbeelding nauwkeurig te herstellen. Een algoritme gekoppeld aan A dat een geschatte restauratie oplevert, wordt aangeduid als A *: voor een afbeelding I A(I) = I 1, A * (I 1) = I 2 en het resulterende herstelde beeld I 2 valt niet noodzakelijkerwijs precies samen met I. Het paar A, A* is geselecteerd om hoge compressieverhoudingen te bieden en toch de visuele kwaliteit te behouden, d.w.z. een minimaal verschil in perceptie bereiken tussen I en I 2. Compressie met verlies wordt gebruikt in de volgende beeldformaten: JPEG, JPEG2000, enz.

Deze lezing richt zich op verliesvrije compressie, die nodig is in gevallen waarin de informatie tegen hoge kosten is verkregen (bijvoorbeeld medische beelden of satellietbeelden), of in andere gevallen waarin zelfs de geringste vervorming ongewenst is.

13.2. Het niet bestaan ​​van een ideaal algoritme

Zoals al vermeld in de vorige paragraaf, wordt afbeelding I beschouwd als een set (reeks) pixelattribuutwaarden. In de rest van deze lezing zijn alle algoritmen en uitspraken van toepassing op zowel afbeeldingen als willekeurige reeksen, waarvan de elementen een eindig aantal waarden kunnen aannemen.

Verklaring 13.2.1. Er bestaat geen algoritme dat een dataset zonder verlies kan comprimeren.

Er zijn 2 N reeksen van grootte N bits (we zullen een bit beschouwen als een minimale informatiedrager). Laat er een algoritme A zijn zodat , waarbij |I|< N . Существует 2 1 + 2 2 + ... + 2 M последовательностей длины, меньшей или равной M . Но - datavolume (reekslengte). Zij M = max M k , dan is M< 2 N 2 1 +2 2 +...+2 M = 2 M+1 -2

. Tegenspraak.

Uit de verklaring volgt dat het zinvol is om algoritmen te ontwikkelen die een bepaalde klasse afbeeldingen effectief kunnen comprimeren; Tegelijkertijd zullen er voor deze algoritmen altijd afbeeldingen zijn waarvoor ze geen compressie bieden.

13.3. Herhaallengtecoderingsalgoritmen (RLE). Dit type algoritmen (her2 Een andere naam die vaak in de literatuur voorkomt is groepscodering. (RLE 3 Engels Runlengtecodering

)) is gebaseerd op het eenvoudigste principe: we zullen herhalende groepen elementen van de oorspronkelijke reeks vervangen door een paar (hoeveelheid, element), of alleen door hoeveelheid.

RLE - bitniveau We zullen de brongegevens op bitreeksniveau beschouwen; vertegenwoordigen bijvoorbeeld zwart-wit beeld . Er zijn meestal meerdere nullen of enen op een rij, en je kunt alleen het aantal identieke cijfers op een rij onthouden. Die. de reeks 0000 11111 000 11111111111 komt overeen met een reeks herhalingen 4 5 3 11 . Ontstaat volgende nuance 111 000 111 000 111 111 000 111 000 111 011 111 : Getallen die het aantal herhalingen aangeven, moeten ook in bits worden gecodeerd. We kunnen aannemen dat elk aantal herhalingen varieert van 0 tot 7 (d.w.z. kan worden gecodeerd met precies drie bits), waarna de reeksen 11111111111 kunnen worden gekoppeld aan de getallen 7 0 4, d.w.z. 7 enen, 0 nullen, 4 enen. Een reeks bestaande uit 21 enen, 21 nullen, 3 enen en 7 nullen wordt bijvoorbeeld als volgt gecodeerd:

, d.w.z. uit de oorspronkelijke reeks, die 51 bits lang is, werd een reeks van 36 bits verkregen.

Het idee achter deze methode wordt gebruikt bij faxverzending.

Laten we aannemen dat de invoer een halftoonafbeelding is, waarbij 1 byte is toegewezen voor de pixelintensiteitswaarde. Het is duidelijk dat vergeleken met een zwart-witraster de verwachting van een lange keten van identieke bits aanzienlijk wordt verminderd.

We splitsen de invoerstroom in bytes (letters) en coderen herhalende letters met een paar (hoeveelheid, letter).

Die. AABBCDAA-gecodeerd (2A) (3B) (1C) (1D) (2A) . Er kunnen echter lange gegevensreeksen zijn waarin niets wordt herhaald, en we coderen elke letter als een paar (cijfer, letter).

Laten we een vast nummer (letter) M hebben (van 0 tot 255). Dan kan een enkele letter op zichzelf worden gecodeerd, - output = S, en als er meerdere letters zijn, of, dan output = CS, waarbij C > M, en C - M het aantal opeenvolgende letters S is. We presenteren bijvoorbeeld alleen het decoderingsalgoritme.

// M - vaste grens // lees tekens opeenvolgend uit de invoerstroom // in - invoer - gecomprimeerde reeks // out - uitvoer - gedecomprimeerde reeks while(in.Read(c)) ( if(c > M) ( // gevalteller n = c - M; Read(c);< n; i++) out.Write(c); } else // случай просто символа out.Write(c); } Lijst 13.1.

RLE-decoderingsalgoritme - byteniveau

Het getal M is meestal 127. Een wijziging van dit algoritme wordt vaker gebruikt, waarbij het teken van een teller de aanwezigheid is van enen in de 2 meest significante bits van het gelezen symbool. De overige 6 bits zijn de tellerwaarde. Deze wijziging van dit algoritme wordt gebruikt in het PCX-formaat. Wijzigingen van dit algoritme worden echter zelden op zichzelf gebruikt, omdat subklasse van reeksen waarop dit algoritme