LZ77 och LZ78

LZ77 och LZ78 är de två förlustfria datakomprimeringsalgoritmerna publicerade i tidningar av Abraham Lempel och Jacob Ziv 1977 och 1978. De är också kända som LZ1 respektive LZ2 . Dessa två algoritmer utgör grunden för många variationer inklusive LZW , LZSS , LZMA och andra. Förutom deras akademiska inflytande, bildade dessa algoritmer grunden för flera allestädes närvarande komprimeringsscheman, inklusive GIF och DEFLATE -algoritmen som används i PNG och ZIP .

De är båda teoretiskt ordbokskodare . LZ77 upprätthåller ett glidfönster under kompression. Detta visades senare vara likvärdigt med den explicita ordboken som konstruerats av LZ78 - de är dock bara likvärdiga när hela data är avsedd att dekomprimeras.

Eftersom LZ77 kodar och avkodar från ett glidande fönster över tidigare sett tecken, måste dekompression alltid starta i början av inmatningen. Konceptuellt kunde LZ78-dekomprimering tillåta slumpmässig åtkomst till indata om hela ordboken var känd i förväg. Men i praktiken skapas ordboken under kodning och avkodning genom att skapa en ny fras när en token matas ut.

Algoritmerna utsågs till en IEEE Milestone 2004. 2021 belönades Jacob Ziv med IEEE Medal of Honor för sitt engagemang i deras utveckling.

Teoretisk effektivitet

I den andra av de två artiklarna som introducerade dessa algoritmer analyseras de som kodare definierade av finita-tillståndsmaskiner. Ett mått analogt med informationsentropi utvecklas för individuella sekvenser (i motsats till probabilistiska ensembler). Detta mått ger en gräns för det datakomprimeringsförhållande som kan uppnås. Det visas sedan att det finns ändliga förlustfria kodare för varje sekvens som uppnår denna gräns när sekvensens längd växer till oändlighet. I denna mening producerar en algoritm baserad på detta schema asymptotiskt optimala kodningar. Detta resultat kan bevisas mer direkt, som till exempel i anteckningar av Peter Shor .

LZ77

LZ77-algoritmer uppnår komprimering genom att ersätta upprepade förekomster av data med referenser till en enda kopia av den data som existerade tidigare i den okomprimerade dataströmmen. En matchning kodas av ett par siffror som kallas ett längd-avståndspar , vilket är ekvivalent med påståendet "vart och ett av nästa längdtecken är lika med tecknen exakt avståndstecken bakom det i den okomprimerade strömmen". ( Avståndet kallas ibland för offset istället.)

För att upptäcka matchningar måste kodaren hålla reda på en viss mängd av den senaste datan, till exempel de senaste 2 KB , 4 KB eller 32 KB. Strukturen i vilken dessa data lagras kallas ett glidande fönster , varför LZ77 ibland kallas för glidfönsterkomprimering . Kodaren behöver behålla dessa data för att leta efter matchningar, och avkodaren behöver behålla dessa data för att tolka de matchningar som kodaren refererar till. Ju större skjutfönstret är, desto längre bakåt kan kodaren söka efter att skapa referenser.

Det är inte bara acceptabelt utan ofta användbart att tillåta längd-distanspar att ange en längd som faktiskt överstiger avståndet. Som ett kopieringskommando är detta förbryllande: "Gå tillbaka fyra tecken och kopiera tio tecken från den positionen till den aktuella positionen". Hur kan tio tecken kopieras över när bara fyra av dem faktiskt finns i bufferten? Att tackla en byte i taget är det inga problem att betjäna denna begäran, eftersom en byte kopieras över kan den matas igen som indata till kopieringskommandot. När kopierings-från-positionen når den ursprungliga destinationspositionen matas den följaktligen data som klistrades in från början av kopierings-från-positionen. Operationen är alltså likvärdig med påståendet "kopiera den data du fick och klistra in den upprepade gånger tills den passar". Eftersom denna typ av par upprepar en enda kopia av data flera gånger, kan den användas för att införliva en flexibel och enkel form av körlängdskodning .

Ett annat sätt att se saker är följande: Under kodning, för att sökpekaren ska fortsätta att hitta matchade par efter slutet av sökfönstret, måste alla tecken från den första matchningen vid offset D och framåt till slutet av sökfönstret ha matchat input, och dessa är de (tidigare sett) tecknen som omfattar en enda enhet med längden L R , som måste vara lika med D . När sedan sökpekaren fortsätter förbi sökfönstret och framåt, så långt som körmönstret upprepas i inmatningen, kommer sök- och inmatningspekarna att vara synkroniserade och matcha tecken tills körningsmönstret avbryts. Då L tecken matchats totalt, L > D , och koden är [ D , L , c ].

Vid avkodning av [ D , L , c ] , återigen, D = LR . När de första L R- tecknen läses till utgången, motsvarar detta en enda körningsenhet som läggs till utgångsbufferten. Vid denna tidpunkt kan läspekaren tänkas bara behöva returnera int( L / L R ) + (1 om L mod L R ≠ 0) gånger till början av den enda buffrade körningsenheten, läs L R -tecken ( eller kanske färre vid den senaste returen), och upprepa tills totalt L tecken har lästs. Men för att spegla kodningsprocessen, eftersom mönstret är repetitivt, behöver läspekaren bara följa synkroniserad med skrivpekaren med ett fast avstånd lika med körlängden L R tills L tecken har kopierats till utdata totalt.

Med tanke på ovanstående, särskilt om komprimeringen av datakörningar förväntas dominera, bör fönstersökningen börja i slutet av fönstret och fortsätta bakåt, eftersom körmönster, om de finns, kommer att hittas först och tillåta sökningen att avslutas, absolut om den aktuella maximala matchande sekvenslängden är uppfylld, eller klokt, om en tillräcklig längd är uppfylld, och slutligen för den enkla möjligheten att data är nyare och kan korrelera bättre med nästa ingång.

Pseudokod

Pseudokoden är en reproduktion av LZ77-kompressionsalgoritmens glidfönster.

    
     medan inmatningen   inte  är tom,  matcha := längsta upprepade förekomsten av inmatning som börjar i fönstret  om  matchning finns  då  d := avstånd till matchens början l := matchens längd c := char efter matchning i ingången  annars  d := 0 l := 0 c := första tecknet i ingångsänden  om  utgång  (d, l, c) kassera  l  + 1 tecken från framsidan av fönster s := pop  l  + 1 tecken från framsidan av ingången lägg till s till baksidan av fönstret  upprepa

Genomföranden

Även om alla LZ77-algoritmer per definition fungerar enligt samma grundläggande princip, kan de variera mycket i hur de kodar sina komprimerade data för att variera de numeriska områdena för ett längd-avståndspar, ändra antalet bitar som konsumeras för ett längd-avståndspar, och särskilj deras längd-avstånd-par från literaler (rådata kodad som sig själv, snarare än som en del av ett längd-distans-par). Några exempel:

  • Algoritmen som illustreras i Lempel och Zivs ursprungliga artikel från 1977 matar ut alla sina data tre värden åt gången: längden och avståndet för den längsta matchningen som finns i bufferten, och den bokstavliga som följde den matchningen. Om två på varandra följande tecken i inmatningsströmmen endast kunde kodas som bokstaver, skulle längden på längd-avståndsparet vara 0.
  • LZSS förbättrar på LZ77 genom att använda en 1-bitars flagga för att indikera om nästa databit är ett bokstavligt eller ett längd-avståndspar, och använda bokstaver om ett längd-avståndspar skulle vara längre.
  • I PalmDoc-formatet kodas alltid ett längd-avståndspar av en tvåbytesekvens. Av de 16 bitarna som utgör dessa två byte går 11 bitar till att koda avståndet, 3 går till att koda längden och de återstående två används för att se till att avkodaren kan identifiera den första byten som början på en sådan två- bytesekvens.
  • I implementeringen som används för många spel av Electronic Arts , kan storleken i byte för ett längd-avståndspar specificeras inuti den första byten av själva längd-avståndsparet; beroende på om den första byten börjar med en 0, 10, 110 eller 111 (när den läses i big-endian bitorientering), kan längden på hela längd-avståndsparet vara 1 till 4 byte.
  • Från och med 2008 är den mest populära LZ77-baserade komprimeringsmetoden DEFLATE ; den kombinerar LZSS med Huffman-kodning . Bokstaver, längder och en symbol för att indikera slutet av det aktuella datablocket placeras alla tillsammans i ett alfabet. Avstånd kan säkert placeras i ett separat alfabet; eftersom ett avstånd bara inträffar strax efter en längd, kan det inte misstas för en annan typ av symbol eller vice versa.

LZ78

LZ78-algoritmerna komprimerar sekventiell data genom att bygga en ordbok med tokensekvenser från ingången och sedan ersätta den andra och efterföljande förekomsten av sekvensen i dataströmmen med en referens till ordboksposten. Observationen är att antalet upprepade sekvenser är ett bra mått på en sekvenss icke slumpmässiga natur. Algoritmerna representerar ordboken som ett n-ärt träd där n är antalet tokens som används för att bilda tokensekvenser. Varje ordbokspost har formen dictionary[...] = {index, token} , där index är indexet till en ordbokspost som representerar en tidigare sett sekvens, och token är nästa token från inmatningen som gör denna post unik i ordboken. Notera hur algoritmen är girig, så ingenting läggs till i tabellen förrän en unik tillverkningstoken hittas. Algoritmen ska initiera sista matchande index = 0 och nästa tillgängliga index = 1 och sedan, för varje token i inmatningsströmmen, sökte ordboken efter en matchning: { last matching index, token} . Om en matchning hittas, ställs det sista matchande indexet till indexet för den matchande posten, ingenting matas ut och det sista matchande indexet finns kvar som representerar indata hittills. Indata bearbetas tills en matchning inte hittas. Sedan skapas en ny ordbokspost, dictionary[next available index] = {senast matchande index, token}, och algoritmen matar ut senaste matchande index, följt av token, återställer sedan senaste matchande index = 0 och ökar nästa tillgängliga index. Som ett exempel betrakta sekvensen av tokens AABBA som skulle sammanställa ordboken; 

0 {0,_} 1 {0,A} 2 {1,B} 3 {0,B}

och utgångssekvensen för den komprimerade datan skulle vara 0A1B0B . Observera att det sista A:et inte är representerat ännu eftersom algoritmen inte kan veta vad som kommer härnäst. I praktiken läggs en EOF-markör till ingången - AABBA$ till exempel. Observera också att i det här fallet är utdata 0A1B0B1$ längre än den ursprungliga ingången men komprimeringsförhållandet förbättras avsevärt när ordboken växer, och i binärt behöver indexen inte representeras av mer än det minsta antalet bitar.

Dekomprimering består av att bygga om ordboken från den komprimerade sekvensen. Från sekvensen 0A1B0B1$ är den första posten alltid terminatorn 0 {...} , och den första från sekvensen skulle vara 1 {0,A} . A: et läggs till utgången. Det andra paret från ingången är 1B och resulterar i post nummer 2 i ordboken, {1,B} . Token "B" matas ut, föregås av sekvensen som representeras av ordbokspost 1. Post 1 är ett 'A' (följt av "inmatning 0" - ingenting) så AB läggs till i utgången. Nästa 0B läggs till i ordboken när nästa post, 3 {0,B} och B (föregås av ingenting) läggs till i utdata. Slutligen skapas en ordbokspost för 1$ och A$ matas ut vilket resulterar i att A AB BA$ eller AABBA tar bort mellanslagen och EOF-markören.

LZW

LZW är en LZ78-baserad algoritm som använder en ordbok som är förinitierad med alla möjliga tecken (symboler) eller emulering av en förinitierad ordbok. Den huvudsakliga förbättringen av LZW är att när en matchning inte hittas, antas det aktuella indataströmstecknet vara det första tecknet i en befintlig sträng i ordboken (eftersom ordboken initieras med alla möjliga tecken), så endast den sista matchningen index utmatas (vilket kan vara det förinitierade ordboksindexet som motsvarar det föregående (eller det initiala) inmatade tecknet). Se LZW- artikeln för implementeringsdetaljer.

BTLZ är en LZ78-baserad algoritm som utvecklades för användning i realtidskommunikationssystem (ursprungligen modem) och standardiserad av CCITT/ITU som V.42bis . När den trie -strukturerade ordboken är full, används en enkel återanvändnings-/återställningsalgoritm för att säkerställa att ordboken kan fortsätta att anpassa sig till ändrade data. En räknare cyklar genom ordboken. När en ny post behövs, stegar räknaren genom ordboken tills en bladnod hittas (en nod utan beroenden). Detta raderas och utrymmet återanvänds för den nya posten. Detta är enklare att implementera än LRU eller LFU och uppnår motsvarande prestanda.

Se även

externa länkar

  • "LZ78-algoritmen" . Referenscenter för datakomprimering: RASIP-arbetsgruppen . Fakulteten för elektroteknik och databehandling, universitetet i Zagreb. 1997. Arkiverad från originalet den 7 januari 2013 . Hämtad 22 juni 2012 .
  • "LZW-algoritmen" . Referenscenter för datakomprimering: RASIP-arbetsgruppen . Fakulteten för elektroteknik och databehandling, universitetet i Zagreb. 1997. Arkiverad från originalet den 7 januari 2013 . Hämtad 22 juni 2012 .
Hämtad från " https://en.wikipedia.org/w/index.php?title=LZ77_and_LZ78&oldid=1134943903 "