Compressie met behulp van seriecoderingsmethode: RLE-algoritme. Coderingsmethoden

PROFIEL Bij het comprimeren met behulp van het RLE-algoritme wordt eerst het aantal herhalingen van het eerste teken geregistreerd, vervolgens het eerste teken zelf, vervolgens het aantal herhalingen van het tweede teken, enz. IN in dit geval het gehele gecodeerde bestand neemt 4 bytes in beslag: 0 11 00100 2 11 000000 2 011 00100 2 11 000001 2 100 A (code 192) 100 B (code 193) We hebben het bestand dus 50 keer gecomprimeerd vanwege het feit dat het opnieuw redundantie had: ketens van identieke karakters. Dit is verliesvrije compressie omdat u, als u het verpakkingsalgoritme kent, de originele gegevens uit de code kunt herstellen. Het is duidelijk dat deze aanpak zal leiden tot een toename (met 2 keer) van de hoeveelheid gegevens in het geval dat er geen aangrenzende identieke tekens in het bestand voorkomen. Om de RLE-coderingsresultaten zelfs in dit ergste geval te verbeteren, werd het algoritme als volgt gewijzigd. De ingepakte reeks bevat besturingsbytes, waarbij elke besturingsbyte wordt gevolgd door een of meer gegevensbytes. Als de meest significante bit van de besturingsbyte 1 is, moet de databyte die tijdens het uitpakken op de besturingsbyte volgt, net zo vaak worden herhaald als in de resterende 7 bits van de besturingsbyte is geschreven. Als het meest significante bit van de besturingsbyte 0 is, moeten de volgende paar bytes aan gegevens ongewijzigd worden overgenomen. Hoeveel precies wordt er in de resterende 7 bits van de besturingsbyte geschreven. Bijvoorbeeld controlebyte 10000 11 1 2 betekent dat de volgende byte 7 keer moet worden herhaald, en de controlebyte 00000100 2 betekent dat de volgende 4 bytes zonder wijzigingen moeten worden overgenomen. De rij is dus 1000 11 11 2 11 000000 2 00000010 2 11 000001 2 11 000010 2 herhaling 15 A (code 192) 2 B (code 193) B (code 194) wordt uitgepakt in 17 tekens: AAAAAAAAAAAAAAAABV. Het RLE-algoritme is met succes gebruikt om tekeningen te comprimeren waarin grote gebieden zijn gevuld met dezelfde kleur en enkele audiogegevens. Tegenwoordig worden in plaats daarvan geavanceerdere, maar geavanceerdere versies gebruikt. complexe methoden. We zullen hieronder een van hen bekijken (Huffman-codering). Het RLE-algoritme wordt bijvoorbeeld gebruikt in een van de fasen van het coderen van afbeeldingen in JPEG-formaat. RLE-compressie is ook mogelijk in BMP-formaat(voor tekeningen met een palet van 16 of 256 kleuren). De beste manier begrijp het werkingsprincipe van het algoritme - oefen met het gebruik ervan. Van de website van de auteur (http://kpolyakov.narod.ru/prog/compress.htm) kunt u een gratis simulatorprogramma downloaden, dat is ontworpen om het RLE-algoritme te bestuderen: Aan de linkerkant van het programmavenster staat teksteditor. Wanneer u op de knop klikt, wordt de ingevoerde tekst gecomprimeerd met behulp van het RLE-algoritme. De gecomprimeerde gegevens worden weergegeven als hexadecimale codes aan de rechterkant van het venster. Het venster aan de rechterkant is tevens een editor, zodat de codes kunnen worden gewijzigd en de omgekeerde handeling (uitpakken, decomprimeren) kan worden uitgevoerd door op de knop te klikken. Met de knoppen bovenaan het venster kunt u bestanden op de schijf comprimeren en herstellen. U hoeft er alleen maar rekening mee te houden dat het programma zijn eigen programma gebruikt eigen formaat gegevensopslag. 6 december 2012 / INFORMATICA Beveiligingsvragen 1) Schat de maximaal haalbare compressieverhouding met behulp van de beschouwde versie van het RLE-algoritme. In welk geval zal het mogelijk zijn dit te verwezenlijken? 2) Schat de compressieverhouding in het slechtste geval met behulp van het RLE-algoritme. Beschrijf dit worstcasescenario. 3) Bedenk drie reeksen die niet kunnen worden gecomprimeerd met behulp van het RLE-algoritme. 4) Construeer reeksen die door het RLE-algoritme precies 2 keer, 4 keer, 5 keer worden gecomprimeerd. Workshop 1) Gebruiken RLE-algoritme, codeer de tekenreeks BBBBBBACCCABBBBBB Schrijf het resultaat als hexadecimale codes (elk teken wordt gecodeerd als een byte, die wordt weergegeven door twee hexadecimale cijfers). Controleer het resultaat met behulp van het RLE-programma.

2) Decodeer de reeks die is verpakt met behulp van het RLE-algoritme (er zijn hexadecimale codes gegeven): 01 4D 8E 41 01 4D 8E 41 16. Om karakters te identificeren aan de hand van hun hexadecimale codes gebruik ASCII-tabel. Bepaal het aantal bytes in de originele en gedecomprimeerde reeks en bereken de compressieverhouding. Controleer het resultaat met behulp van het RLE-programma. Stel twee verificatiemethoden voor. 3) Gebruik het RLE-programma om RLE-compressie toe te passen de volgende bestanden 1 en zoek de compressieverhouding voor elk ervan. grad_vert.bmp grad_horz.bmp grad_diag.jpg Leg uw resultaten uit: waarom voor twee cijfers in BMP-formaat dezelfde maat RLE-compressieverhoudingen zijn zo verschillend; Waarom kan ik afbeeldingen die zijn opgeslagen in JPEG-indeling niet comprimeren? Voorvoegselcodes Denk aan morsecode, die gebruik maakt van een ongelijke code om de berichtlengte te verkorten: veel voorkomende letters (A, E, M, H, T) worden in korte reeksen gecodeerd, en zelden voorkomende letters worden in langere reeksen gecodeerd. Zo'n code kan worden weergegeven in de vorm van een structuur die een boom wordt genoemd: Root Dit toont een onvolledige morsecodeboom, alleen gebouwd voor karakters waarvan de codes uit één en twee karakters bestaan ​​(punten en streepjes). De boom bestaat uit knooppunten (zwarte stip en cirkels met alfabetsymbolen) en gerichte randen die ze verbinden, pijlen geven de bewegingsrichting aan. Het bovenste knooppunt (dat geen pijlen bevat) wordt de ‘wortel’ van de boom genoemd. Twee pijlen komen uit de wortel en uit alle tussenliggende knooppunten (behalve de laatste knooppunten - "bladeren"), de linker is gemarkeerd met een punt en de rechter is gemarkeerd met een streepje. Om de symboolcode te vinden, moet je de pijlen volgen van de "wortel" van de boom naar het gewenste "blad", waarbij je de labels opschrijft van de pijlen waarlangs we bewegen. Er zijn geen cycli (gesloten paden) in de boom, dus de code voor elke 1 Deze en andere bestanden die bij de workshoptaken worden gebruikt, bevinden zich op de supplementschijf bij deze uitgave van het tijdschrift. karakter wordt op unieke wijze bepaald. Met behulp van deze boom kunt u de volgende codes construeren: E I A – T – N – M – – Dit is een oneven code, waarbij de tekens codes van verschillende lengte hebben. In dit geval doet zich altijd het probleem voor van het verdelen van de reeks in afzonderlijke codewoorden. In morsecode wordt dit opgelost met behulp van een scheidingsteken: een pauze. U kunt echter geen extra teken invoeren als aan de Fano-voorwaarde is voldaan: geen van de codewoorden is het begin van een ander codewoord. Hierdoor kunt u het bericht ondubbelzinnig in realtime decoderen, zodra de volgende tekens worden ontvangen. Een prefixcode is een code waarin geen enkel codewoord het begin is van een ander codewoord (Fano-voorwaarde). Robert Fano (geb. 1917) (nytimes.com) Claude Shannon (1916–2001) Om dit idee te gebruiken bij de verwerking van computergegevens, was het noodzakelijk een algoritme te ontwikkelen voor het construeren van een prefixcode. Dit probleem werd voor het eerst, onafhankelijk van elkaar, opgelost door de Amerikaanse wiskundigen en ingenieurs Claude Shannon (in 1948) en Robert Fano (in 1949). Ze gebruikten berichtredundantie, wat erin bestaat dat de karakters in de tekst dat wel hebben verschillende frequenties voorkomen. In dit geval moet u de gegevens lezen bronbestand tweemaal: bij de eerste doorgang wordt de frequentie van voorkomen van elk teken bepaald, vervolgens wordt een code gebouwd waarbij rekening wordt gehouden met deze gegevens, en bij de tweede doorgang worden de teksttekens vervangen door hun codes. Het door Shannon en Fano voorgestelde coderingsalgoritme werd de Shannon-Fano-code genoemd. Voorbeeld 3. Laat de tekst alleen bestaan ​​uit de letters O, E, N, T en een spatie. Het is bekend hoe vaak ze in de tekst verschenen: spatie - 179, O - 89, E - 72, N - 53 en T - 50 keer. Volgens de Shannon-Fano-methode verdelen we de karakters in twee groepen, zodat het totale aantal karakters in de eerste groep in de tekst ongeveer gelijk is aan het totale aantal karakters in de tweede groep. In ons geval beste optie- dit is om de spatie en de letter T te combineren in de eerste groep (som 179+50 = 229), en de overige tekens in de tweede (som 89+72+53 = 214). De tekens in de eerste groep hebben codes die beginnen met 0, en de rest - met 1. Er zijn slechts twee tekens in de eerste groep, een daarvan, bijvoorbeeld een spatie, heeft een tweede codecijfer van 0 (en volledige code 00), en de tweede - 1 (lettercode T - 01). 7 december 2012 / INFORMATICA

Algoritme RLE(Run Length Encoding, packing, run length encoding) is het snelste, eenvoudigste en meest begrijpelijke algoritme voor datacompressie en blijkt soms zeer effectief te zijn. Het is een soortgelijk algoritme dat wordt gebruikt om afbeeldingen in bestanden te comprimeren. PCX.

Het werkt als volgt: elke reeks herhaalde invoersymbolen wordt geassocieerd met een set van drie uitvoersymbolen: de eerste is een prefixbyte, die aangeeft dat een herhaalde invoerreeks is aangetroffen, de tweede is een byte die de lengte van de invoer bepaalt. reeks, de derde is het invoersymbool zelf. . Het is het beste om de werking van het algoritme uit te leggen aan de hand van een specifiek voorbeeld.

Bijvoorbeeld: stel dat er een (hexadecimale) tekst is van 20 bytes:

05 05 05 05 05 05 01 01 03 03 03 03 03 03 05 03 FF FF FF FF

Laten we de FF-byte als voorvoegsel kiezen. Vervolgens krijgen we aan de uitvoer van de archiver de reeks

FF 06 05 FF 02 01 FF 06 03 FF 01 05 FF 01 03 FF 04 FF

De lengte is 18 bytes, dat wil zeggen dat er enige compressie is bereikt. Het is echter gemakkelijk op te merken dat bij het coderen van sommige tekens de grootte van de uitvoercode toeneemt (bijvoorbeeld in plaats van 01 01 - FF 02 01). Het is duidelijk dat het geen zin heeft om enkele of tweemaal (driedubbele) herhaalde tekens te coderen; ze moeten expliciet worden opgeschreven. We krijgen een nieuwe reeks:

FF 06 05 01 01 FF 06 03 05 03 FF 04 FF

13 bytes lang. Behaalde compressieverhouding: 13/20*100 = 65%.

Het is gemakkelijk te zien dat het voorvoegsel mogelijk overeenkomt met een van de invoertekens. In dit geval kan het invoersymbool worden vervangen door de “prefix”-weergave, bijvoorbeeld:

FF is hetzelfde als FF 01 FF (drie bytes in plaats van één).

Daarom vanaf de juiste keuze voorvoegsel hangt af van de kwaliteit van het compressie-algoritme zelf, want als er vaak enkele FF-tekens in onze brontekst zouden voorkomen, zou de grootte van de uitvoertekst zelfs groter kunnen zijn dan de invoer. Over het algemeen moet het zeldzaamste teken in het invoeralfabet als voorvoegsel worden gekozen.

U kunt de compressieverhouding nog een stap verder brengen door het voorvoegsel en de lengte in één byte te combineren. Laat het voorvoegsel een getal F0...FF zijn, waarbij het tweede cijfer de lengte bepaalt lengte van 0 tot 15. In dit geval zal de uitvoercode twee bytes zijn, maar we beperken het bereik van de lengteweergave van 255 tot 15 tekens en beperken ons verder in de keuze van het voorvoegsel. De uitvoertekst voor ons voorbeeld ziet er als volgt uit:

F6 05 F2 01 F6 03 05 03 F4 FF

Lengte - 10 bytes, compressieverhouding - 50%.

Verder, aangezien we hebben afgesproken om een ​​reeks met een lengte van 0 tot 3 niet te coderen, wordt de code lengte Het is handig om te gebruiken met een offset van drie, dat wil zeggen 00=3, 0F=18, FF=258, waarbij langere kettingen tegelijk worden verpakt.

Als afzonderlijke tekens zeldzaam genoeg zijn, kan het goed zijn om het RLE-algoritme aan te passen zonder een voorvoegsel . In dit geval zijn afzonderlijke tekens dat ook Noodzakelijkerwijs moeten in voorvoegselvorm worden gecodeerd, zodat de decoder ze in de uitvoerstroom kan onderscheiden:

06 05 02 01 06 03 01 05 01 03 04 FF

Lengte - 12 bytes, compressieverhouding - 60%.

Een variant van het algoritme is mogelijk in plaats van lengte lengte positie wordt gecodeerd ten opzichte van het begin van de tekst afstand het eerste teken verschilt van het vorige. Voor ons voorbeeld zal dit een uitvoerregel zijn zoals:

01 05 07 01 09 03 0F 05 10 03 11 FF

• 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 deze leek toen gemakkelijk te begrijpen - de codelijsten leken op Chinees schrift, 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, met behulp van dit voorbeeld van invoergegevens, kregen we 18 bytes van de 32 bytes. Geen slecht resultaat, vooral gezien het feit 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 gecodeerd hebben.

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 raam, maar we zullen het erover eens zijn groter formaat gecodeerde tekenreeks. Laten we proberen alle herhalende tekenreeksen te vinden. We beschouwen een keten 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 het om kleine teksten gaat, 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. Het mag duidelijk zijn dat de link dat wel heeft 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 over. 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 dingen te gaan kijken.

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<счетчик повторений, значение>vermindert gegevensredundantie.

Algoritme decompressie het ziet er zo uit:

Initialisatie(...);
Doen(
if(is een teller(byte)) (
teller = Low6bits(byte)+1;
voor(i=1 om tegen te gaan)
De
}
anders(
GedecomprimeerdBestand.WriteByte(byte)
) while(ImageFile.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 twee bytes, d.w.z. Laten we het 32 ​​keer comprimeren.

Oefening: Maak een algoritme compressie voor de eerste versie van het RLE-algoritme.

Vraag voor zelfbeheersing: Geef twee of drie voorbeelden van ‘slechte’ afbeeldingen voor het RLE-algoritme. Leg uit waarom het gecomprimeerde bestand groter is dan het originele bestand.

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.

Het decompressie-algoritme ervoor ziet er als volgt uit:

Initialisatie(...);
Doen(
byte = Beeldbestand.ReadNextByte();
teller = Low7bits(byte)+1;
if(if herhaal vlag(byte)) (
waarde = ImageFile.ReadNextByte();
voor (i=1 om tegen te gaan)
GecomprimeerdBestand.WriteByte(waarde)
}
anders(
for(i=1 om tegen te gaan)(
waarde = ImageFile.ReadNextByte();
GecomprimeerdBestand.WriteByte(waarde)
}
GecomprimeerdBestand.WriteByte(byte)
) while(ImageFile.EOF());

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

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.

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 klein aantal kleuren: zakelijke en wetenschappelijke afbeeldingen.

Symmetrie: Ongeveer één.

Kenmerken: K 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.

Het algoritme is vernoemd naar de eerste letters van de achternamen van de ontwikkelaars: Lempel, Ziv en Welch. Compressie daarin wordt, in tegenstelling tot RLE, uitgevoerd met behulp van identieke byteketens.

LZ-algoritme

Er bestaat een vrij grote familie van LZ-achtige algoritmen, die bijvoorbeeld verschillen in de manier waarop naar zich herhalende ketens wordt gezocht. Eén van de genoeg eenvoudige opties Dit algoritme gaat er bijvoorbeeld van uit dat de invoerstroom een ​​paar bevat<счетчик, смещение относительно текущей позиции>, of gewoon<счетчик>“overgeslagen” bytes en de bytewaarden zelf (zoals in de tweede versie van het RLE-algoritme). Bij het uitpakken voor een stel<счетчик, смещение>gekopieerd<счетчик>byte uit de uitvoerarray die is verkregen als gevolg van het uitpakken, naar<смещение>byte ervoor<счетчик>(d.w.z. een getal gelijk aan de teller) van de “skip” bytewaarden worden eenvoudig vanuit de invoerstroom naar de uitvoerarray gekopieerd. Dit algoritme is asymmetrisch in de tijd, omdat het een volledige doorzoeking van de buffer vereist bij het zoeken naar identieke substrings. Als gevolg hiervan is het voor ons moeilijk om een ​​grote buffer te specificeren vanwege de sterke toename van de compressietijd. Mogelijk wordt er echter een algoritme gebouwd waarin<счетчик>en aan<смещение>Er worden 2 bytes toegewezen (het meest significante bit van de hoge byte van de teller is een teken van lijnherhaling / streamkopie), wat ons de mogelijkheid geeft om alle herhaalde substrings tot een grootte van 32 Kb te comprimeren in een buffer van 64 Kb.

In dit geval krijgen we in het ergste geval een toename van de bestandsgrootte met 32770/32768 (in twee bytes staat geschreven dat de volgende 2 15 bytes moeten worden herschreven naar de uitvoerstroom), wat helemaal niet slecht is . De maximale compressieverhouding zal 8192 keer zijn. Binnen de limiet, aangezien we maximale compressie bereiken door een buffer van 32 KB om te zetten in 4 bytes, en we een buffer van deze omvang niet meteen zullen accumuleren. De minimale substring waarvoor het voor ons voordelig is om compressie uit te voeren, zou echter wel moeten zijn algemeen geval minimaal 5 bytes, wat de lage waarde van dit algoritme bepaalt. De voordelen van LZ omvatten de extreme eenvoud van het decompressie-algoritme.

Oefening: Stel een andere versie van het LZ-algoritme voor, waarin voor een stel<счетчик, смещение>Er worden 3 bytes toegewezen en de belangrijkste kenmerken van uw algoritme worden berekend.

De variant van het algoritme dat we hieronder bespreken, gebruikt een boom om ketens weer te geven en op te slaan. Het is duidelijk dat dit een vrij sterke beperking is voor het type ketens, en niet alle identieke subketens in onze afbeelding zullen tijdens de compressie worden gebruikt. In het voorgestelde algoritme is het echter voordelig om even ketens bestaande uit 2 bytes te comprimeren.

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.

De functie InitTable() maakt de tabel leeg en plaatst alle rijen met eenheidslengte erin.

InitTabel();
GecomprimeerdBestand.WriteCode(ClearCode);
CurStr=lege tekenreeks;
while(niet ImageFile.EOF())( //Tot het einde van het bestand
C=ImageFile.ReadNextByte();
if(CurStr+C staat in de tabel)
CurStr=CurStr+C;//Lijm een ​​teken aan een string
anders(
code=CodeForString(CurStr);//code is geen byte!
AddStringToTable(CurStr+C);
CurStr=С; // Tekenreeks van één teken
}
}
code=CodeForString(CurStr);
GecomprimeerdBestand.WriteCode(code);
GecomprimeerdBestand.WriteCode(CodeEndOfInformation);

Zoals hierboven besproken, initialiseert de functie InitTable() de rijtabel zodat deze alles bevat mogelijke snaren, bestaande uit één karakter. Als we bijvoorbeeld bytegegevens comprimeren, zullen er 256 van dergelijke rijen in de tabel staan ​​("0", "1", ..., "255"). De waarden 256 en 257 zijn gereserveerd voor de clearingcode (ClearCode) en de einde-informatiecode (CodeEndOfInformation). In de beschouwde versie van het algoritme wordt een 12-bits code gebruikt, en dienovereenkomstig blijven we over waarden van 258 tot 4095 voor codes voor rijen. De toegevoegde rijen worden opeenvolgend naar de tabel geschreven, waarbij de rij-index in de tabel de code wordt.

De functie ReadNextByte() leest een teken uit een bestand. De functie WriteCode() schrijft code (niet even groot als een byte) naar het uitvoerbestand. De functie AddStringToTable() voegt toe nieuwe lijn in de tabel en wijs er een code aan toe. Bovendien verwerkt deze functie situaties waarin tabellen overlopen. In dit geval worden de code van de eerder gevonden rij en de opschooncode naar de stream geschreven, waarna de tabel wordt gewist door de functie InitTable(). De functie CodeForString() vindt een string in een tabel en drukt de code voor die string af.

Voorbeeld:

Laten we de reeks 45, 55, 55, 151, 55, 55, 55 comprimeren. Vervolgens plaatsen we, volgens het hierboven geschetste algoritme, eerst de opruimcode in de uitvoerstroom<256>, voeg vervolgens “45” toe aan de aanvankelijk lege regel en controleer of de regel “45” in de tabel staat. Omdat we tijdens de initialisatie alle regels van één teken in de tabel hebben ingevoerd, staat de regel “45” in de tabel. Vervolgens lezen we het volgende teken 55 uit de invoerstroom en controleren of de string “45, 55” in de tabel staat. Een dergelijke rij bestaat nog niet in de tabel. We voeren de regel "45, 55" in de tabel in (met de eerste vrije code 258) en schrijven de code naar de stream<45>. U kunt archivering in het kort als volgt voorstellen:

• "45" - staat in de tabel;
• "45, 55" - nee. Voeg toe aan de tabel<258>“45, 55.” Streamen:<45>;
• "55, 55" - nee. Naar de tafel:<259>“55, 55.” Streamen:<55>;
• "55, 151" - nee. Naar de tafel:<260>“55, 151.” Streamen:<55>;
• "151, 55" - nee. Naar de tafel:<261>“151, 55.” Streamen:<151>;
• "55, 55" - staat in de tabel;
• "55, 55, 55" - nee. Naar de tafel: “55, 55, 55”<262>. Streamen:<259>;

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

We weten dat we voor elke code een regel aan de tabel moeten toevoegen, bestaande uit de regel die daar al aanwezig is en het teken waarmee deze begint volgende regel in de stroom.

Het decompressiealgoritme dat deze bewerking uitvoert, is als volgt:

code=Bestand.ReadCode();
while(code != CodeEndOfInformation)(
if(code = ClearCode) (
InitTabel();
code=Bestand.ReadCode();
if(code = CodeEndOfInformatie)
(afmaken werk);
ImageFile.WriteString(StrFromTable(code));
oude_code=code;
}
anders(
if(InTabel(code)) (
ImageFile.WriteString(FromTable(code));
AddStringToTable(StrFromTable(oude_code)+
FirstChar(StrFromTable(code)));
oude_code=code;
}
anders(
OutString= StrFromTable(oude_code)+
FirstChar(StrFromTable(oude_code));
ImageFile.WriteString(OutString);
AddStringToTable(OutString);
oude_code=code;
}
}
}

Hier leest de functie ReadCode() de volgende code uit het gedecomprimeerde bestand. De functie InitTable() voert dezelfde acties uit als tijdens compressie, d.w.z. maakt de tabel leeg en schrijft alle rijen met hetzelfde teken erin. De functie FirstChar() geeft ons het eerste teken van de string. De functie StrFromTable() retourneert een rij uit een tabel met behulp van code. De functie AddStringToTable() voegt een nieuwe rij toe aan de tabel (waardoor deze de eerste vrije code krijgt). De functie WriteString() schrijft een tekenreeks naar een bestand.

Opmerking 1. Zoals je misschien hebt gemerkt, nemen de codes die naar de stream worden geschreven geleidelijk toe. Totdat code 512 bijvoorbeeld voor de eerste keer in de tabel verschijnt, zullen alle codes kleiner zijn dan 512. Bovendien worden tijdens compressie en decompressie codes in de tabel toegevoegd bij het verwerken van hetzelfde teken, d.w.z. het gebeurt “synchroon”. We kunnen deze eigenschap van het algoritme gebruiken om de mate van compressie te verhogen. Totdat het 512e teken aan de tabel is toegevoegd, schrijven we 9-bits codes in de uitvoerbitstroom, en onmiddellijk na het toevoegen van 512 - 10-bits codes. Dienovereenkomstig zal de decompressor ook alle invoerstroomcodes als 9-bits moeten waarnemen totdat code 512 aan de tabel wordt toegevoegd, waarna hij alle invoercodes als 10-bits zal waarnemen. We zullen hetzelfde doen als we de codes 1024 en 2048 aan de tabel toevoegen. Deze techniek Hiermee kunt u de compressieverhouding met ongeveer 15% verhogen:

Opmerking 2. Bij het comprimeren van een afbeelding is het belangrijk dat we de snelheid van het zoeken naar rijen in de tabel garanderen. We kunnen profiteren van het feit dat elke volgende substring één teken langer is dan de vorige. Bovendien hebben we de vorige regel al in de tabel gevonden. Daarom volstaat het om een ​​lijst met verwijzingen naar rijen te maken, beginnend met een bepaalde subtekenreeks, en het hele zoekproces in de tabel wordt teruggebracht tot een zoekopdracht in de rijen in de lijst voor de vorige rij. Het is duidelijk dat een dergelijke operatie zeer snel kan worden uitgevoerd.

Merk ook op dat het in werkelijkheid voldoende is om er maar een paar in de tafel op te slaan<код предыдущей подстроки, добавленный символ>. Deze informatie is voldoende om het algoritme te laten werken. Dus een array van 0 tot 4095 met elementen<код предыдущей подстроки; добавленный символ; список ссылок на строки, начинающиеся с этой строки>lost het gegeven zoekprobleem op, zij het zeer langzaam.

In de praktijk wordt voor het opslaan van een tabel een hashtabeloplossing gebruikt die net zo snel is als bij lijsten, maar compacter in geheugen. De tafel bestaat uit 8192 (2 13) elementen. Elk element bevat<код предыдущей подстроки; добавленный символ; код этой строки>. De 20-bits zoeksleutel wordt gevormd met behulp van de eerste twee elementen die in de tabel zijn opgeslagen als een enkel getal (sleutel). De onderste 12 bits van dit getal worden aan de code gegeven en de volgende 8 bits aan de symboolwaarde.

Het volgende wordt gebruikt als hashfunctie:

Index(sleutel)= ((sleutel >> 12) ^ sleutel) & 8191;

Waar >> een bitsgewijze verschuiving naar rechts is (sleutel >> 12 - we krijgen de waarde van het teken), ^ - logische werking bitgewijs exclusieve OR, & logische bitgewijze AND.

Zo ontvangen we bij een paar vergelijkingen de vereiste code of een bericht dat een dergelijke code niet in de tabel voorkomt.

Laten we de beste en slechtste compressieverhoudingen voor dit algoritme berekenen. De beste coëfficiënt wordt uiteraard verkregen voor een lange keten van identieke bytes (dat wil zeggen voor een 8-bits beeld, waarvan alle pixels met zekerheid de kleur 0 hebben). In dit geval schrijven we in de 258e rij van de tabel de string “0, 0”, in 259 - “0, 0, 0”, ... in 4095 - een string van 3839 (=4095-256) nullen . In dit geval bevat de stream (controleer het algoritme!) 3840 codes, inclusief de clearingcode. Door de som van de rekenkundige progressie van 2 tot 3839 (dat wil zeggen de lengte van de gecomprimeerde keten) te berekenen en deze te delen door 3840*12/8 (12-bits codes worden naar de stream geschreven), krijgen we de beste compressie verhouding.

Oefening: Bereken de exacte waarde van de beste compressieverhouding. Een moeilijkere opgave: bereken dezelfde coëfficiënt, rekening houdend met opmerking 1.

Oefening: Creëer een algoritme voor het genereren van dergelijke ketens. Probeer het resulterende bestand te comprimeren met behulp van standaard archiveringsprogramma's (zip, arj, gz). Als u compressie krijgt, wordt het generatie-algoritme onjuist geschreven.

LZW geïmplementeerd GIF-formaten en TIFF.

Kenmerken van algoritmen LZW:

Compressieverhoudingen: Ongeveer 1000, 4, 5/7 (beste, gemiddelde, slechtste verhoudingen). 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, mits de zoekactie naar een rij in een tabel optimaal wordt uitgevoerd.

Functies: De situatie waarin het algoritme het beeld vergroot, is uiterst zeldzaam. LZW is universeel - het zijn de varianten die in conventionele archiveringssystemen worden gebruikt.

Klassiek Huffman-algoritme

Een van de klassieke algoritmen die bekend zijn sinds de jaren 60. Gebruikt alleen de frequentie waarmee identieke bytes in de afbeelding voorkomen. Komt overeen met tekens in de invoerstroom die voorkomen groter aantal keer, een bitketting van kortere lengte. En, integendeel, zeldzaam - een ketting van grotere lengte. Om statistieken te verzamelen, zijn twee passages over de afbeelding nodig.

Laten we eerst een paar definities introduceren.

Definitie. Laat het alfabet Y =( A 1, ..., een r ), bestaande uit een eindig aantal letters. Een eindige reeks karakters uit Y

wij bellen in één woord in het alfabet Y, en het nummer N - woord lengte A. De lengte van een woord wordt aangegeven als la).

Laat het alfabet W gegeven worden, W =( B 1 , ..., B Q ). Door B duiden een woord aan in het alfabet W en door S (W)is de verzameling van alle niet-lege woorden in het alfabet W.

Laten S =S(Y) -de verzameling van alle niet-lege woorden in het alfabet Y, en S"- een deelverzameling van de verzameling S. Laten we ook de mapping krijgen F, waarvan elk woord Een, een? S(Y)

, komt overeen met het woord B=F(A), B .

? Z(W) Woord IN wij bellen A berichtcode A, en de overgang van het woord.

Definitie. naar zijn code -

codering 1 - B 1 ,
codering 2 - B 2 ,
. . .
codering Beschouw de correspondentie tussen letters van het alfabet Y en enkele woorden van het alfabet W: B A

R- R Deze correspondentie heet S" (W)=S (W)schema en aangeduid met S. Het definieert de codering als volgt: elk woord uit komt overeen met het woord dat wordt genoemd B 1 ... B woordcode A. Woorden R. worden genoemd elementaire codes Dit soort

Definitie. codering wordt genoemd Z(W) alfabetische codering.

Laat het woord

lijkt op B=B" B" Dan het woord B" genaamd het begin of B=B" B" - voorvoegsel van het woord B, een B het einde van het woord B .

B. Bovendien het lege woord L en het woord zelf worden beschouwd als het begin en einde van woorden Definitie. Schema Sheeft de eigenschap van een voorvoegsel, als dat nodig is i(1? heeft de eigenschap van een voorvoegsel, En J B , J? r, ik?J B ) woord

i is geen woordvoorvoegsel J.

Stelling 1. A 1 ,..., A Als het schema S} (de eigenschap heeft van een voorvoegsel, dan zal de alfabetische codering één-op-één zijn. >1 Laten we aannemen dat het alfabet Y =( R 1 , . . . , R woordcode R A 1 ,..., A Als het schema S) en een reeks waarschijnlijkheden B 1 , ..., B P} (verschijning van karakters >1 . Laten we verder het alfabet W , W =(

Q - B 1 ,
. . .
codering Beschouw de correspondentie tussen letters van het alfabet Y en enkele woorden van het alfabet W: B A

Q

). Dan is het mogelijk om een ​​hele reeks alfabetische coderingsschema’s S te construeren een 1 het bezit van één-op-één eigendom. Bij ieder patroon kunt u de gemiddelde lengte invoeren

l

wo een 1, gedefinieerd als de wiskundige verwachting van de lengte van de elementaire code: - lengte van woorden.

Lengte een 1 het bezit van één-op-één eigendom. wo een 1 * laat zien hoe vaak de gemiddelde woordlengte toeneemt bij het coderen met schema S.

B. Bovendien het lege woord L en het woord zelf Dat kan worden aangetoondzijn minimumwaarde bereikt op sommige S en wordt gedefinieerd als een 1 * Codes gedefinieerd door circuit S met l gemiddelde =

, worden genoemd

codes met minimale redundantie A 1 ,..., A Als het schema S, of Huffman-codes.

Codes met minimale redundantie geven gemiddeld een minimale toename van de woordlengte als ze op de juiste manier worden gecodeerd.

In ons geval alfabet Y =( We rangschikken alle letters van het invoeralfabet in afnemende volgorde van waarschijnlijkheid. We tellen alle overeenkomende woorden B , J? r, ik?uit het alfabet W =(0,1) zijn leeg.

Stap 2. Twee symbolen combineren een ik r-1 En een ik Rminst waarschijnlijk p ik r-1 En p ik Rtot pseudokarakter A"{een ik r-1 lucht ) met waarschijnlijkheid p ik r-1+p ik R. Voeg 0 toe aan het begin van woord B i r-1(B i r-1=0B i r-1 ), en 1 tot het begin van woord B i R(B i R=1B i R).

Stap 3. Verwijderen uit de lijst met geordende tekens een ik r-1 En een ik R, plaats daar een pseudo-symbool A"{een ik r-1 lucht ). Voer stap 2 uit en voeg indien nodig 1 of nul toe voor alle woorden B , J? r, ik?, overeenkomend met pseudo-tekens, totdat er 1 pseudo-teken in de lijst overblijft.

Voorbeeld: Laten we 4 letters in het alfabet hebben Y =( A 1 ,..., A 4 } (de eigenschap heeft van een voorvoegsel, dan zal de alfabetische codering één-op-één zijn. =4 ), R 1 =0.5, R 2 =0.24,P 3 =0.15,P 4 =0,11. Vervolgens kan het proces van het construeren van een diagram als volgt worden weergegeven:

Door de acties uit te voeren die overeenkomen met de tweede stap, verkrijgen we een pseudo-symbool met waarschijnlijkheid 0,26 (en kennen we 0 en 1 toe aan de overeenkomstige woorden). Door deze stappen voor de gewijzigde lijst te herhalen, verkrijgen we een pseudo-symbool met waarschijnlijkheid 0,5. En ten slotte krijgen we in de laatste fase een totale waarschijnlijkheid van 1.

Om de codeerwoorden te herstellen, moeten we de pijlen volgen vanaf de beginsymbolen tot het einde van de resulterende binaire boom. Dus voor een symbool met waarschijnlijkheid R 4, we krijgen B 4 =101, voor R 3 krijgen we B 3 =100, voor R 2 krijgen we B 2 =11, voor R 1 krijgen we B1 =0. Wat betekent het diagram: codering 1 - 0,
codering 2 - 11
codering 3 - 100
codering 4 - 101 Dit diagram vertegenwoordigt voorvoegselcode, wat een Huffman-code is. Het meest voorkomende personage in de stream A 1 we coderen het kortste woord als 0, en het zeldzaamste woord A 4 lang woord 101.

Voor een reeks van 100 tekens waarin het teken A 1 zal 50 keer voorkomen, symbool A 2 - 24 keer, symbool A 3 - 15 keer, en het symbool A 4 - 11 keer, deze code kunt u een reeks van 176 bits krijgen ( ). Die. gemiddeld besteden we 1,76 bits per streamsymbool.

Voor bewijs van de stelling, evenals het feit dat het geconstrueerde circuit feitelijk de Huffman-code definieert, zie.

Zoals uit het bovenstaande duidelijk werd, vereist het klassieke Huffman-algoritme het vastleggen van een tabel met correspondentie tussen gecodeerde karakters en coderingsketens in een bestand.

In de praktijk worden de variëteiten ervan gebruikt. In sommige gevallen is het dus redelijk om een ​​constante tabel te gebruiken of deze ‘adaptief’ te bouwen, d.w.z. tijdens het archiveren/dearchiveren. Deze technieken zorgen ervoor dat we de afbeelding niet twee keer moeten doorlopen en de tabel samen met het bestand moeten opslaan. Coderen met vaste tafel gebruikt als de laatste fase van archivering in JPEG en in het CCITT Groep 3-algoritme dat hieronder wordt besproken.

Kenmerken van het klassieke Huffman-algoritme:

Compressieverhoudingen: 8, 1,5, 1 (beste, gemiddelde, slechtste kansen).

Afbeeldingsklasse: Praktisch niet toegepast op beelden in hun pure vorm. Meestal gebruikt als een van de compressietrappen in complexere circuits.

Symmetrie: 2 (vanwege het feit dat er twee passages door de gecomprimeerde data-array nodig zijn).

Functies: Het enige algoritme dat in het ergste geval de omvang van de brongegevens niet vergroot (behalve als de conversietabel samen met het bestand moet worden opgeslagen).

Een soortgelijke aanpassing van het algoritme wordt gebruikt bij het comprimeren van zwart-witafbeeldingen (één bit per pixel). De volledige naam van dit algoritme is CCITT Group 3. Dit betekent dat dit algoritme werd voorgesteld door de derde standaardisatiegroep van de International Telegraph and Telephone Advisory Committee. Reeksen van opeenvolgende zwarte en witte stippen daarin worden vervangen door een getal dat gelijk is aan hun getal. En deze serie is op zijn beurt volgens Huffman gecomprimeerd met een vaste tafel.

Definitie: Er wordt een reeks opeenvolgende beeldpixels van dezelfde kleur opgeroepen serie.De lengte van deze set punten wordt genoemd serie lengte.

De onderstaande tabel bevat twee soorten codes:

• Voltooiingscodes van series- instellen van 0 tot 63 in stappen van 1.
• Samengestelde (aanvullende) codes- instellen van 64 tot 2560 in stappen van 64.

In de praktijk keren we, in gevallen waarin de afbeelding overwegend zwart is, de afbeelding vóór de compressie om en schrijven we informatie hierover in de bestandskop.

Het compressie-algoritme ziet er als volgt uit:

for(over alle lijnen van de afbeelding) (
Laten we de string transformeren in een reeks runlengtes;
voor (over alle series) (
if(serie wit) (
L= looplengte;
terwijl(L > 2623) ( // 2623=2560+63
L=L-2560;
WriteWhiteCodeFor(2560);
}
als(L > 63) (
L2=MaximumConstCodeLessL(L);
L=L-L2;
WriteWhiteCodeFor(L2);
}
WriteWhiteCodeFor(L);
//Dit is altijd de exitcode
}
anders(
[De code is vergelijkbaar met de witte serie,
met het verschil dat ze worden geregistreerd
zwarte codes]
}
}
// Einde van beeldregel
}

Omdat de zwarte en witte serie elkaar afwisselen, zullen de code voor de witte serie en de code voor de zwarte serie feitelijk afwisselend werken.

In termen reguliere expressies we krijgen voor elke regel van onze afbeelding (lang genoeg, beginnend met een wit punt) een uitvoerbitstream van de vorm:

((<Б-2560>)*[<Б-сст.>]<Б-зв.>(<Ч-2560>)*[<Ч-сст.>]<Ч-зв.>) +

[(<Б-2560>)*[<Б-сст.>]<Б-зв.>]

Waar ()* - 0 of meer keer herhalen, () + .- 1 of meer keer herhalen, - 1 of 0 keer inschakelen.

Voor het eerder gegeven voorbeeld: 0, 3, 556, 10... genereert het algoritme de volgende code:<Б-0><Ч-3><Б-512><Б-44><Ч-10>, of, volgens de tabel, 00110101 10 0110010100101101 0000100 (verschillende codes in de draad zijn voor het gemak gemarkeerd). Deze code heeft de eigenschap van prefixcodes en kan eenvoudig worden teruggevouwen tot een reeks runlengtes. Het is eenvoudig te berekenen dat we voor de gegeven reeks van 569 bits een code van 33 bits lang hebben ontvangen, d.w.z. de compressieverhouding is ongeveer 17 keer.

Vraag: Hoe vaak zal de bestandsgrootte in het ergste geval toenemen? Waarom? (Het antwoord dat wordt gegeven in de kenmerken van het algoritme is niet compleet, omdat grotere waarden van de slechtste compressieverhouding mogelijk zijn. Vind ze.)

Oefening: Gegeven een afbeeldingsreeks, geschreven als runlengtes - 442, 2, 56, 3, 23, 3, 104, 1, 94, 1, 231, 120 bytes groot ((442+2+..+231)/8) . Bereken de compressieverhouding van deze string met behulp van het CCITT Group 3-algoritme.

Voltooiingscodetabel:

Tabel met samengestelde codes:

Dit algoritme is geïmplementeerd in TIFF-formaat.

Kenmerken van algoritmen CCITT-groep 3

Run-length-codering (RLE) of Repeat Coding is een eenvoudig algoritme voor datacompressie 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 klein 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 het geen extra geheugen nodig heeft bij het archiveren en uitpakken, en ook snel werkt. Een interessant kenmerk van batchcodering is dat de archiveringsgraad van sommige afbeeldingen aanzienlijk kan worden vergroot door eenvoudigweg 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 kleuren. 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 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 drukken extra karakters

, kunnen we de opnamelengte verkorten.Compressieverhoudingen Kenmerken van het LZW-algoritme: Afbeeldingsklasse: 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. : LZW is gericht op 8-bits afbeeldingen die op een computer zijn gebouwd. Comprimeert vanwege identieke subketens in de stroom. Symmetrie

Functies: Bijna symmetrisch, op voorwaarde dat de zoekactie voor een rij in een tabel optimaal wordt uitgevoerd.

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

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