Lempel-Ziva-Welch algoritme

Lempel -Ziv-Welch-algoritmen ( Lempel -Ziv-Welch , LZW ) er en universel tabsfri datakomprimeringsalgoritme skabt af Abraham Lempel , Jacob Ziv og Terry Welch ). Den blev udgivet af Welch i 1984 [1] som en forbedret implementering af LZ78- algoritmen udgivet af Lempel og Ziv i 1978 [2] . Algoritmen er designet til at være ret nem at implementere både i software og hardware [1] .

Akronymet "LZW" refererer til navnene på opfinderne af algoritmen: Lempel, Ziv og Welch, men mange[ hvem? ] hævder, at da patentet tilhørte Ziv, bør metoden kaldes Ziv-Lempel-Welch-algoritmen .

Beskrivelse

Denne algoritme, når den koder (komprimerer) en meddelelse, skaber dynamisk en ordbog med sætninger: visse sekvenser af tegn (sætninger) tildeles grupper af bits (koder) af en fast længde (f.eks. 12-bit, som foreslået i original artikel af Welch [1] ). Ordbogen initialiseres med alle 1-tegns sætninger (i tilfælde af 8-bit tegn er dette 256 sætninger). Mens den bliver kodet, scanner algoritmen teksten tegn for tegn fra venstre mod højre. Når algoritmen læser det næste tegn i denne position, er der en streng W med maksimal længde, der matcher en eller anden sætning fra ordbogen. Derefter sendes koden for denne sætning til outputtet, og strengen WK, hvor K er tegnet efter W i inputmeddelelsen, indtastes i ordbogen som en ny sætning, og der tildeles en kode til den (da W blev valgt grådigt , WK er endnu ikke indeholdt i ordbogen). Tegnet K bruges som begyndelsen af den næste sætning. Mere formelt kan denne algoritme beskrives ved følgende rækkefølge af trin:

Initialisering af ordbog med alle mulige enkelttegnssætninger. Initialisering af inputsætningen W med det første tegn i beskeden.
Hvis END_MESSAGE, skal du udstede en kode for W og afslutte algoritmen.
Læs det næste tegn K fra den kodede besked.
Hvis sætningen WK allerede er i ordbogen, skal du indstille inputsætningen W til WK og gå til trin 2.
Ellers skal du udlæse kode W, tilføje WK til ordbogen, indstille inputsætningen W til værdien K, og gå til trin 2.

Afkodningsalgoritmen behøver kun den kodede tekst som input: den tilsvarende sætningsordbog genskabes let ved at efterligne funktionen af kodningsalgoritmen (men der er subtile nuancer diskuteret i eksemplet nedenfor).

Implementering

Et bemærkelsesværdigt træk ved LZW-algoritmen er dens lette implementering, hvilket gør den stadig meget populær på trods af det ofte dårligere kompressionsforhold sammenlignet med analoger som LZ77 [3] . Normalt implementeres LZW ved hjælp af et præfikstræ, der indeholder sætninger fra en ordbog: for at finde W, skal du blot læse den længst mulige streng fra træets rod, og derefter for at tilføje en ny sætning, skal WK tilføjes til den fundne node af den nye søn med symbolet K, og koden for sætningen W kan fungere som indekset for en node i en matrix, der indeholder alle noder.

Sætningskodning

Brugen af koder med fast længde til sætninger (12 bit i Welch-beskrivelsen [1] ) kan påvirke komprimeringseffektiviteten negativt, da for det første, for de indledende kodede tegn, vil denne fremgangsmåde snarere puste dataene op i stedet for at komprimere (hvis tegnet tager 8 bit ), og for det andet er den samlede størrelse af ordbogen (2 12 =4096) ikke så stor. Det første problem løses ved at indkode outputsekvensen med Huffman-algoritmen (muligvis adaptiv ) eller aritmetisk kodning . For at løse det andet, bruges andre tilgange.

Den første enkle mulighed er at anvende en optimal universel kode, såsom Levenshtein -koden eller Elias-koden . I dette tilfælde, teoretisk set, kan ordbogen vokse i det uendelige.

En anden mere almindelig mulighed er at ændre den maksimalt mulige ordbogsstørrelse, efterhånden som antallet af sætninger vokser. [4] Indledningsvis er ordbogens maksimale størrelse f.eks. 2 9 (2 8 koder er allerede optaget af sætninger til kodning af 8-bit enkelttegn), og 9 bits er allokeret til sætningskoden. Når antallet af sætninger bliver 2 9 , bliver den maksimale størrelse 2 10 og der tildeles 10 bit til koder. Og så videre. Således kan en ordbog teoretisk set være vilkårligt stor. Denne metode er demonstreret i eksemplet nedenfor (normalt er den maksimale ordbogsstørrelse dog begrænset; for eksempel i LZC - en populær modifikation af LZW, diskuteret nedenfor - vokser kodelængder fra 9 til 16 bit.).

I de fleste implementeringer af sidstnævnte metode øges antallet af bits allokeret til sætningskoden, indtil der tilføjes en ny sætning WK, som løber over ordbogen, men efter at koden W er skrevet til outputtet. returner sætningskoden W og tilføj den nye sætning WK til ordbogen; hvis WK-koden er lig med 2 p (det vil sige, at WK løber over ordbogen), så udlæses p-bit-koden W først, og først derefter øges p med én, så efterfølgende koder optager p + 1 bit. Tidlige implementeringer af LZW indbefatter dem, der øger p før udlæsning af W-koden, dvs. W-kodeoutputtet, før WK tilføjes til ordbogen, optager allerede p+1 bit (hvilket ikke er nødvendigt, da W-koden er mindre end 2 p ). Denne adfærd kaldes "tidlig forandring". Denne implementeringsforvirring har fået Adobe til at understøtte begge varianter af LZW i PDF (om "tidlige ændringer" bruges, er angivet med et særligt flag i overskriften på de data, der komprimeres). [5]

Ordbogsoverløb

Da koderne i LZW-algoritmen har en fast længde, er størrelsen af ordbogen begrænset (ved brug af koder af ikke-fast længde, er størrelsen af ordbogen begrænset af mængden af tilgængelig hukommelse). Spørgsmålet opstår: hvad skal man gøre i tilfælde af ordbogsoverløb? Der anvendes flere strategier.

Den mest oplagte mulighed er blot at bruge den konstruerede ordbog uden yderligere ændringer. [1] Det er klart, at dette ofte er en dårlig strategi.
Forfatterne af det engang så populære compress -værktøj bruger simpelthen den konstruerede ordbog, så længe komprimeringsforholdet forbliver acceptabelt, og rydder derefter op, hvis komprimeringskvaliteten forringes. Denne modifikation af LZW kaldes LZC (Lempel-Ziv-Compress, se nedenfor). [6]
P. Tischer foreslog, inden du indsatte en ny sætning i den overfyldte ordbog, ved næste trin i algoritmen at slette den sætning fra ordbogen, der ikke har været brugt i længst tid (LRU, Least Recently Used). Denne modifikation kaldes undertiden LZT (Lempel-Ziv-Tischer, se nedenfor). [7]

Eksempel

Dette eksempel viser LZW-algoritmen i aktion, og viser status for output og ordforråd på hvert trin, både under indkodning og afkodning af meddelelsen. For at forenkle præsentationen vil vi begrænse os til et simpelt alfabet - kun store bogstaver, uden tegnsætningstegn og mellemrum. Den besked, der skal komprimeres, ser sådan ud:

TOBEORNOTTOBEORTOBEORNOT#

# -markøren bruges til at markere slutningen af beskeden. Der er således 27 tegn i vores alfabet (26 store bogstaver fra A til Z og #). Computeren repræsenterer dette som grupper af bits, for at repræsentere hvert tegn i alfabetet behøver vi kun en gruppe på 5 bits pr. tegn. I takt med at ordforrådet vokser, skal gruppernes størrelse vokse for at kunne rumme nye elementer. 5-bit grupper giver 2 5 = 32 mulige kombinationer af bit, så når det 33. ord optræder i ordbogen, skal algoritmen gå til 6-bit grupper. Bemærk, at da gruppen af alle nuller 00000 bruges, har den 33. gruppe koden 32 . Den indledende ordbog vil indeholde:

# = 00000 A=00001 B=00010 C=00011 . . . Z = 11010

Kodning

Uden at bruge LZW-algoritmen vil det tage 125 bit, når meddelelsen transmitteres, som den er - 25 tegn á 5 bit hver. Sammenlign dette med, hvad der sker, når du bruger LZW:

Symbol: Bitcode: Ny ordbogspost: (ved udgangen) T20 = 10100 O 15 = 01111 27: TO B 2 = 00010 28: OB E 5 = 00101 29: BE O 15 = 01111 30: EO R 18 = 10010 31: ELLER <--- begynd at bruge 6-bit grupper fra næste tegn N 14 = 001110 32: RN O 15 = 001111 33: NEJ T 20 = 010100 34: OT TIL 27 = 011011 35: TT BE 29 = 011101 36: TOB ELLER 31 = 011111 37: BEO TOB 36 = 100100 38:ORT EO 30 = 011110 39: TOBE RN 32 = 100000 40: EOR OT 34 = 100010 41: RNO # 0 = 000000 42: OT# Samlet længde = 6*5 + 11*6 = 96 bit.

Ved at bruge LZW reducerede vi således beskeden med 29 bit ud af 125 - det er næsten 22%. Efterhånden som beskeden bliver længere, vil ordforrådet repræsentere længere og længere dele af teksten, hvilket gør gentagne ord meget kompakte.

Afkodning

Lad os nu forestille os, at vi har modtaget den kodede meddelelse vist ovenfor, og vi skal afkode den. Først og fremmest skal vi kende den indledende ordbog, og vi kan rekonstruere efterfølgende ordbogsposter på farten, da de blot er en sammenkædning af tidligere opslag.

Data: Output: Ny post: Fuld: Delvis: 10100 = 20 T 27: T? 01111 = 15 O 27: TIL 28: O? 00010 = 2 B 28: OB 29: B? 00101 = 5 E 29: BE 30: E? 01111 = 15 O 30: EO 31: O? 10010 = 18 R 31: ELLER 32: R? <---- begynd at bruge 6-bit grupper 001110 = 14 N 32: RN 33: N? 001111 = 15 O 33: NO 34: O? 010100 = 20 T 34: OT 35: T? 011011 = 27 TIL 35: TT 36: TIL? <---- for 37 skal du kun tilføje det første element 011101 = 29 BE 36: TOB 37: BE? næste ordbogsord 011111 = 31 ELLER 37: BEO 38: ELLER? 100100 = 36 TOB 38: ORT 39: TOB? 011110 = 30 EO 39: TOBE 40: EO? 100000 = 32 RN 40: EOR 41: RN? 100010 = 34 OT 41: RNO 42: OT? 000000 = 0 #

Den eneste lille vanskelighed kan opstå, hvis det nye ordbogsord sendes med det samme. I afkodningseksemplet ovenfor, når dekoderen støder på det første tegn, T , ved den, at ord 27 starter med T, men hvor ender det? Lad os illustrere problemet med følgende eksempel. Vi afkoder ABABA- meddelelsen :

Data: Output: Ny post: Fuld: Delvis: . . . 011101 = 29 AB 46: (ord) 47: AB? 101111 = 47AB? <--- hvad skal vi gøre ved det?

Ved første øjekast er dette en uløselig situation for dekoderen. Vi ved på forhånd, at ord 47 skal være ABA , men hvordan ved dekoderen om det? Bemærk, at ord 47 består af ord 29 plus det næste tegn. Ord 47 ender således med "tegn kommer næste". Men da dette ord sendes med det samme, skal det begynde med "det næste tegn", og så slutter det med det samme tegn, som det begynder, i dette tilfælde A . Dette trick gør det muligt for dekoderen at bestemme, at ord 47 er ABA .

Generelt opstår denne situation, når en sekvens af formen cScSc er kodet , hvor c er et enkelt tegn og S er en streng, og ordet cS allerede er i ordbogen.

Teoretisk evaluering af effektivitet

De teoretiske egenskaber af ubegrænset ordforråd LZW er generelt de samme som for LZ78, og analysen af de to komprimeringsmetoder er ens. Når man overvejer en ubegrænset ordbog, er det naturligt at antage, at outputsætningerne er kodet med koder med variabel længde, for eksempel en universel kode eller en fast kode, hvis størrelse vokser med den maksimale størrelse af ordbogen (se implementeringsafsnittet ).

Asymptotisk optimalitet

For en teoretisk evaluering af effektiviteten sammenlignes denne komprimeringsmetode med en referencemetrik. Desværre er den ideelle referencedatakomprimeringsmetrik - Kolmogorov-kompleksitet - ikke engang tilnærmelsesvis beregnelig , og derfor taber enhver komprimeringsalgoritme naturligvis i sammenligning med den. Lempel og Ziv foreslog en svækket version af Kolmogorov-kompleksitet - komprimering af endelige automater [2] . Af tekniske årsager er denne metrik defineret for uendelige strenge. Vi fikser et endeligt alfabet . Lad en uendelig streng over . Angiv med antallet af bits i LZW-kodningen med en ubegrænset ordbog for strengen . Derfor har vi $\Sigma$ $x=x_{1}x_{2}\cdots$ $\Sigma$ $\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})$ ${\displaystyle x_{1}x_{2}\cdots x_{n))$

\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})\leq z\log _{2}z+O(z\log _{2}|\Sigma |),

hvor er antallet af sætninger i LZW-kodning for . Det viste Ziv [8] $z$ ${\displaystyle x_{1}x_{2}\cdots x_{n))$

\limsup \limits _{n\to \infty }{\frac {\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})}{n\log _{2}| \Sigma |}}\leq \mathrm {FS} (x),

hvor er komprimeringsmetrikken ved endelige automater, defineret nedenfor [2] . Således er kompressionsforholdet LZW (forhold til - antallet af bit optaget af den ukomprimerede streng) asymptotisk afgrænset , og i denne forstand er LZW optimal. Desuden, hvis ordbogsstørrelsen er begrænset, og overløbsstrategien er at fjerne de mindst brugte sætninger, er LZW også asymptotisk optimal i følgende forstand: [8] $\mathrm {FS} (x)$ $\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})$ $n\log _{2}|\Sigma |$ $\mathrm {FS}$

\lim _{D\to \infty }\limsup \limits _{n\to \infty }{\frac {\mathrm {LZW} _{D}(x_{1}x_{2}\cdots x_ {n})}{n\log _{2}|\Sigma |}}\leq \mathrm {FS} (x),

hvor angiver antallet af bits i LZW-kodning med en ordbog, der ikke indeholder mere end sætninger, hver sætning har en længde på højst , og når ordbogen løber over, bliver den mindst brugte sætning smidt ud (denne mulighed ligner LZT; se ændringer ). Bemærk, at algoritmerne LZ78 og LZ77 har lignende egenskaber (herunder tilsvarende varianter, henholdsvis med en ordbog og et glidende vindue af begrænset størrelse) [8] . Lad os definere nu . $\mathrm {LZW} _{D}(x_{1}x_{2}\cdots x_{n})$ $D$ $\log _{2}^{2}D$ $\mathrm {FS}$

Metrikken ligner på mange måder Kolmogorov-kompleksiteten, men i stedet for fuldgyldige Turing-maskiner bruges Turing - maskiner med endelig hukommelse, det vil sige endelige automater, i dens definition. For et givet tal betegner vi ved sættet af alle deterministiske Mealy-automater , der har tilstande og omkoder strenge over alfabetet til binære sekvenser, så outputtet fra automaten kan gendanne den oprindelige streng; mere præcist skrives binære strenge (eventuelt tomme) på kanterne af automaten, så for enhver finit streng over alfabetet kommer automaten i en eller anden tilstand og producerer i processen en binær sekvens , og den kan gendannes unikt fra sekvensen og tilstanden (så at den kontraherende automat kan have tomme strenge på kanterne, gendannes strengen ikke kun af sekvensen, men også af den endelige tilstand [9] ). For en given uendelig streng skal du definere: [8] $\mathrm {FS} (x)$ $s$ ${\mathcal {A}}_{s}$ $EN,$ $s$ $\Sigma$ $EN$ $y$ $\Sigma$ $EN$ $v$ $A(y)$ $A(y)$ $v$ $y$ $y$ $A(y)$ $v$ $x=x_{1}x_{2}\cdots$

\mathrm {FS} (x)=\lim _{s\to \infty }\limsup \limits _{n\to \infty }\min \limits _{A\in {\mathcal {A)) _{s}}{\frac {|A(x_{1}x_{2}\cdots x_{n})|}{n\log _{2}|\Sigma |}},

hvor angiver antallet af bits i . Repræsenterer således et estimat for det mindst mulige kompressionsforhold, der kan opnås ved komprimering af en streng med endelige automater. Bemærk, at på grund af ordbogens ubegrænsede grænser, kan LZW-algoritmen ikke modelleres ved hjælp af en Mealy-automat, i modsætning til LZW-algoritmen med begrænset ordforråd med højst længdesætninger (størrelsen af en sådan Mealy-automat afhænger naturligvis af ). $|A(y)|$ $A(y)$ $\mathrm {FS} (x)$ $x$ $D$ $\log _{2}^{2}D$ $D$

Ikke-optimalt antal sætninger

Kompressionsmetrikken ved finite automater er, selvom den er naturlig, ikke så effektiv, som den kan se ud ved første øjekast. Så asymptotisk optimal med hensyn til er enhver komprimeringsalgoritme, der opdeler den givne streng i forskellige sætninger (det vil sige når ) og derefter koder ved hjælp af bits [9] . Det er klart, at en algoritme, der opfylder så svage kriterier, ikke behøver at være effektiv i praksis. Derudover afspejler tilstandsmaskinens komprimeringsmetrik ikke mange komprimeringsmetoders evne til at erstatte lange gentagne bidder i dataene med referencer til det sted, hvor en sådan chunk først fandt sted (tilstandsmaskinen har simpelthen ikke nok hukommelse til at sammenligne lange bidder). Det er denne mekanisme, der ofte er årsagen til effektiviteten ved at komprimere store mængder data i praksis, og som vist nedenfor klarer LZW (og LZ78) sig i værste fald ret dårligt til denne opgave sammenlignet med eksempelvis LZ77. $\mathrm {FS}$ ${\displaystyle x=x_{1}x_{2}\cdots x_{n))$ ${\displaystyle f_{1}f_{2}\cdots f_{k))$ ${\displaystyle f_{i}\neq f_{j))$ $i<j<k$ $x$ $k\log _{2}k+O(k\log _{2}|\Sigma |)$

LZW-algoritmen med ubegrænset ordbogsstørrelse dekomponerer den givne endelige streng i sætninger , så hver sætning enten er et tegn eller lig med , hvor er et tal mindre end , og er det første tegn i sætningen . Der er andre dekomponeringer af formen for en streng , og spørgsmålet opstår naturligvis: hvor god er nedbrydningen bygget af den grådige LZW-algoritme? ${\displaystyle x=x_{1}x_{2}\cdots x_{n))$ ${\displaystyle p_{1}p_{2}\cdots p_{z))$ $p_{k}$ $p_{h}a$ $h$ $k$ $-en$ $p_{h+1}$ ${\displaystyle p_{1}p_{2}\cdots p_{z))$ $x$

Lad betegne det mindste antal, således at strengen kan repræsenteres som en dekomponering , hvor hver streng enten er et tegn eller lig med , hvor er et tal mindre end , og er det første tegn i strengen . Sergio De Agostino og Ricardo Silvestri [10] beviste, at det i værste fald kan være mere end en faktor 1, selvom alfabetet kun indeholder to tegn (de viste også, at dette skøn er optimalt). Med andre ord giver den grådige strategi i dette tilfælde resultater, der er meget langt fra optimale. En del af begrundelsen for LZW-tilgangen er, at konstruering af en optimal sætningsnedbrydning er et NP-komplet problem , som vist af De Agostino og Storer [11] . ${\displaystyle z_{o))$ $x$ $p'_{1}p'_{2}\cdots p'_{z_{o))$ ${\displaystyle p'_{k))$ $p'_{h}a$ $h$ $k$ $-en$ $p'_{h+1}$ $z$ ${\displaystyle z_{o))$ $\Omega (n^{1/4})$ $z\leq z_{o}\cdot O(n^{1/4}),$ ${\displaystyle z_{o))$

Et andet naturligt spørgsmål er, hvor god LZW er sammenlignet med LZ77 ? LZ77 er kendt for grådigt at dekomponere en streng i sætninger , sådan at hver sætning enten er et tegn eller en understreng af strengen . Hooke, Laurie, Re [12] og Charikar et al. [13] har vist, at den i værste fald kan være flere gange større end . På den anden side er det kendt, at det altid ikke er mindre end , og endnu mere, altid ikke mindre end . [13] Med andre ord kan LZW, og selv den "optimale" version af LZW, der indeholder sætninger, ikke være bedre end LZ77 (i det mindste væsentligt - bemærk at antallet af sætninger diskuteres her, ikke måden de er kodet på), og i nogle patologiske tilfælde kunne det være katastrofalt værre. $x$ ${\displaystyle f_{1}f_{2}\cdots f_{w))$ $f_{h}$ ${\displaystyle f_{1}f_{2}\cdots f_{h-1))$ $z$ $\Omega ((n/\log n)^{1/2})$ $w$ $z$ $w$ ${\displaystyle z_{o))$ $w$ ${\displaystyle z_{o))$

Ansøgning

På tidspunktet for dens introduktion gav LZW-algoritmen et bedre kompressionsforhold for de fleste applikationer end nogen anden velkendt metode på den tid. Det blev den første datakomprimeringsmetode, der blev brugt i vid udstrækning på computere.

Algoritmen (eller rettere dens modifikation, LZC, se nedenfor) blev implementeret i compress -programmet , som blev mere eller mindre et standardværktøj på Unix-systemer omkring 1986. Flere andre populære arkiveringsværktøjer bruger også denne metode, eller dem tæt på den.

I 1987 blev algoritmen en del af GIF -billedformatstandarden . Det kan også (valgfrit) bruges i TIFF -format . Derudover bruges algoritmen i modemkommunikationsprotokollen v.42bis og PDF -standarden [14] (selvom som standard er det meste af tekst og visuelle data i PDF komprimeret ved hjælp af Deflate-algoritmen ).

Patenter

Der er udstedt en række patenter for LZW-algoritmen og dens variationer, både i USA og i andre lande. LZ78 blev udstedt US Patent 4.464.650 af Sperry Corporation , senere en del af Unisys Corporation . To amerikanske patenter er blevet udstedt for LZW: US Patent 4.814.746 ejet af IBM og Welchs US Patent 4.558.302 (udstedt 20. juni 1983 ) ejet af Sperry Corporation, senere overtaget af Unisys Corporation. Alle patenter er nu udløbet.

Unisys GIF'er og PNG'er

Da CompuServe udviklede GIF - formatet , var CompuServe uvidende om eksistensen af US Patent 4.558.302 . I december 1994, da Unisys blev opmærksom på brugen af LZW i et meget brugt grafisk format, offentliggjorde virksomheden sine planer om at indsamle royalties fra kommercielle programmer med mulighed for at oprette GIF-filer. På det tidspunkt var formatet allerede så udbredt, at de fleste softwarevirksomheder ikke havde andet valg end at betale. Denne situation var en af årsagerne til udviklingen af PNG -grafikformatet (uofficielt udskrift: "PNG's Not GIF" [15] ), som blev det tredje mest almindelige på WWW , efter GIF og JPEG . I slutningen af august 1999 opsagde Unisys royaltyfrie licenser til LZW til gratis og ikke-kommerciel software [16] og for brugere af ulicenserede programmer, hvilket fik League for Programming Freedom til at lancere en "brænd alle GIF'er"-kampagne [17] og informere offentligheden om tilgængelige alternativer. Mange patentretseksperter har påpeget, at patentet ikke dækker enheder, der kun kan dekomprimere LZW-data, men ikke komprimere dem; af denne grund kan det populære gzip -værktøj læse .Z-filer, men ikke skrive dem.

Den 20. juni 2003 udløb det originale amerikanske patent, hvilket betyder, at Unisys ikke længere kan opkræve royalties på det. Lignende patenter i Europa, Japan og Canada udløb i 2004.

Ændringer

LZC (1985, Thomas SW, McKie J., Davies S., Turkowski K., Woods JA og Orost JW) [6] er en af de bedst kendte praktiske implementeringer af LZW, leveret i komprimeringsværktøjet (Lempel- Ziv-Compress). LZC bruger 9 til 16 bit til sætningskoder (antallet af bit stiger med ordbogens størrelse, se implementeringsafsnittet ); når ordbogen løber over, fortsætter LZC simpelthen med at bruge den uden yderligere ændringer, men algoritmen overvåger graden af datakomprimering, og når komprimeringen med den aktuelle ordbog bliver uacceptabelt dårlig, rydder LZC ordbogen og fortsætter med at arbejde. LZC komprimerer dårligere end LZW, men kompressionshastigheden er højere.
LZT (1985, Tischer P.) [7] er en anden kendt variant af LZW. Når ordbogen løber over, fortsætter LZT, men hver gang, før den indsætter en ny sætning i ordbogen, fjerner den den sætning, der svarer til det længste ubrugte blad i præfikstræet, der indeholder alle sætninger. I LZT-implementeringen placeres alle blade i en sammenkædet liste, og hver gang bladene bruges under komprimering, flyttes bladene til listens hoved; således er de blade, der ikke har været brugt længst, i halen på listen (yderligere detaljer er indlysende).
LZMW (1985, Victor Miller og Mark Wegman ) [18] - finder i inputstrømmen den længste streng, der allerede er i ordbogen (lad os betegne det W), udsender koden W og tilføjer den derefter til ordbogen strengen VW, hvor V er strengen fra ordbogen, hvis kode blev returneret i det foregående trin (i første omgang er V en tom streng). Således vokser strengene i ordbogen hurtigere end i den originale LZW, og i praksis er det ofte muligt at opnå bedre kompressionskvalitet. Miller og Wegman foreslog også, at i tilfælde af manglende hukommelse, skulle sætninger, der sjældent bruges, fjernes fra ordbogen, ligesom det gøres i LZT.
LZAP (1988, James Storer) [19] er en modifikation af LZMW, som adskiller sig ved, at ved hvert trin tilføjes ikke kun strengen VW til ordbogen, men også strengene VW 1 , VW 2 , …, VW |W |-1 , hvor W i er et præfiks W med længden i. ("AP" i "LZAP" betyder "alle præfikser", det vil sige "alle præfikser.") For eksempel, hvis V = wiki og W = pedia - det vil sige i det foregående trin, fandt algoritmen strengen wiki i ordbogen , og på denne fandt den pedia - så vil algoritmen tilføje strengen wikipedia til ordbogen , som LZMW ville gøre, men også tilføje strengene wikip , wikipe , wikiped , wikipedi . LZAP-algoritmen er lettere at implementere end LZMW, men den bevarer samtidig de fleste fordele ved LZMW, bortset fra at ordbogsstrengkoder fylder mere, fordi ordbogen er mere oppustet.

Se også

Noter

↑ 1 2 3 4 5 Welch, 1984 .
↑ 1 2 3 Lempel, Ziv, 1978 .
↑ Arnold, Bell, 1997 .
↑ Bell, Witten, Cleary, 1989 , afsnit 3.4.6.
↑ PDF 1.7 specifikation , afsnit 7.4.4.3.
↑ 1 2 Bell, Witten, Cleary, 1989 , afsnit 3.4.8.
↑ 1 2 Bell, Witten, Cleary, 1989 , afsnit 3.4.9.
↑ 1 2 3 4 Ziv, 2015 .
↑ 12 Sheinwald , 1994 .
↑ De Agostino, Silvestri, 1997 .
↑ De Agostino, Storer, 1996 .
↑ Hucke, Lohrey, Reh, 2016 .
↑ 12 Charikar et al., 2005 .
↑ PDF 1.7 specifikation , afsnit 7.4.4.
↑ Webanmeldelse: PNG's NOT GIF! . Hentet 18. oktober 2018. Arkiveret fra originalen 30. marts 2022. (ubestemt)
↑ Unisys LZW-patent- og GIF-filer . Hentet 18. oktober 2018. Arkiveret fra originalen 19. oktober 2018. (ubestemt)
↑ Unisys håndhæver GIF-patenter - Slashdot . Hentet 18. oktober 2018. Arkiveret fra originalen 18. oktober 2018. (ubestemt)
↑ Miller, Wegman, 1985 .
↑ Storer, 1988 .

Litteratur

Arnold R., Bell T. Et korpus til evaluering af tabsfri komprimeringsalgoritmer // IEEE Data Compression Conference. - 1997. - S. 201-210 . - doi : 10.1109/DCC.1997.582019 .
Bell T. , Witten IH , Cleary JG Modellering til tekstkomprimering // ACM Computing Surveys . - 1989. -T. 21,nr. 4. —S. 557–591. doi:/76894.76896.
Charikar M., Lehman E., Lehman A., Liu D., Panigrahy R., Prabhakaran M., Sahai A., shelat a. Det mindste grammatikproblem // IEEE Transactions on Information Theory . - 2005. - T. 51 , nr. 7 . - S. 2554-2576 . - doi : 10.1109/TIT.2005.850116 .
De Agostino S., Silvestri R. En worst-case-analyse af LZ2-komprimeringsalgoritmen // Information and Computation . - 1997. - T. 139 , nr. 2 . — S. 258–268 . - doi : 10.1006/inco.1997.2668 .
De Agostino S., Storer JA On-line versus offline-beregning i dynamisk tekstkomprimering // Information Processing Letters . - 1996. - T. 59 , nr. 3 . — S. 169–174 . - doi : 10.1016/0020-0190(96)00068-3 .
Hucke D., Lohrey M., Reh CP Det mindste grammatikproblem genbesøgt // String Processing and Information Retrieval (SPIRE). - 2016. - T. 9954 . — s. 35–49 . - doi : 10.1007/978-3-319-46049-9_4 .
Lempel A. , Ziv J. Kompression af individuelle sekvenser via variabel hastighedskodning // IEEE Transactions on Information Theory . - 1978. - T. 24 , nr. 5 . — S. 530–536 . - doi : 10.1109/TIT.1978.1055934 .
Miller V. S , Wegman MN Variationer over et tema af Ziv og Lempel // Kombinatoriske algoritmer på ord. - 1985. -T. 12. —S. 131–140. -doi:10.1007/978-3-642-82456-2_9.
Sheinwald D. Om Ziv-Lempel-beviset og relaterede emner // Proceedings of the IEEE . - 1994. - T. 82 , nr. 6 . — S. 866–871 . - doi : 10.1109/5.286190 .
Storer JA Datakomprimering: Metoder og teori. - New York, USA: Computer Science Press, 1988. - 413 s. - ISBN 0-7167-8156-5 .
Welch TA En teknik til højtydende datakomprimering // Computer. - 1984. - V. 6 , nr. 17 . — S. 8–19 . - doi : 10.1109/MC.1984.1659158 .
Ziv J. En begrænset ordbogsversion af LZ78 opnår asymptotisk finite-state kompressibilitet med et forvrængningsmål // IEEE Information Theory Workshop. - 2015. - S. 1–4 . - doi : 10.1109/ITW.2015.7133077 .
Adobe Systems Inc. Dokumenthåndtering - Bærbart dokumentformat - Del 1: PDF 1.7 . PDF 1.7 specifikation . Adobe (1. juli 2008). Dato for adgang: 26. januar 2018.

Kompressionsmetoder _

Teori

Information	Egen Gensidig Entropi Betinget entropi Kompleksitet Redundans
Enheder	Bit Nat Nappe Hartley Hartley formel

Tabsfri

Entropi kompression	Asymmetriske talsystemer Huffman algoritme Adaptiv Huffman-algoritme Shannon-Fano algoritme Shannons algoritme Aritmetisk kodning ( interval ) Golomb koder Delta Universel kode Elias fibonacci
Ordbogsmetoder	RLE Tøm luften ud LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Andet	RLE CTW BWT MTF PPM DMC

Lyd

Teori	Konvolution PCM Aliasing Prøveudtagning Kotelnikovs teorem
Metoder	LPC LAR LSP WLPC CELP ACELP En lov μ-lov ADPCM MDCT Fourier transformation Psykoakustisk model
Andet	Audio kompressor Talekompression Båndkodning

Billeder

Vilkår	farverum Pixel Mætningsundersampling Kompressionsartefakter
Metoder	RLE DPCM fraktal wavelet EZW SPIHT LP Forbered PCL
Andet	Bitrate Standard testbillede PSNR Kvantisering

Video

Vilkår	Video egenskaber Ramme Rammetyper Videokvalitet
Metoder	Bevægelseskompensation Forbered Kvantisering wavelet
Andet	Video codec Teori om prisforvrængning CBR ABR VBR

Arkivformater _
Kun arkivering	ar cpio DAR dele tjære LBR
Kun kompression	bzip2 komprimere gzip LZMA LZW lzop rzip S.Q. XZ
Arkivering og komprimering	7z ACB ES BUE ALZip ARJ Skab cpt dd DGCA dmg GCA kgb LHA LZX PAQ PRS RAR qda sidde SQX xar Zoo ZIP
Softwarepakning og distribution	apk deb pkg perle RPM MSI KRUKKE KRIG RAR (Java) ØRE