Lempel-Ziva-Welch-algoritm

Lempel -Ziv-Welch-algoritmen ( Lempel -Ziv-Welch , LZW ) är en universell förlustfri datakomprimeringsalgoritm skapad av Abraham Lempel , Jacob Ziv och Terry Welch ). Den publicerades av Welch 1984 [1] som en förbättrad implementering av LZ78- algoritmen publicerad av Lempel och Ziv 1978 [2] . Algoritmen är designad för att vara ganska enkel att implementera både i mjukvara och hårdvara [1] .

Förkortningen "LZW" hänvisar till namnen på uppfinnarna av algoritmen: Lempel, Ziv och Welch, men många[ vem? ] hävdar att eftersom patentet tillhörde Ziv, borde metoden kallas Ziv-Lempel-Welch-algoritmen .

Beskrivning

När den här algoritmen kodar (komprimerar) ett meddelande skapar den dynamiskt en ordbok med fraser: vissa teckensekvenser (fraser) tilldelas grupper av bitar (koder) med en fast längd (till exempel 12-bitars sådana, som föreslås i originalartikel av Welch [1] ). Ordboken initieras med alla 1-teckens fraser (i fallet med 8-bitars tecken är detta 256 fraser). När den kodas skannar algoritmen texten tecken för tecken från vänster till höger. När algoritmen läser nästa tecken i denna position finns det en sträng W med maximal längd som matchar någon fras från ordboken. Sedan skickas koden för denna fras till utgången, och strängen WK, där K är tecknet efter W i inmatningsmeddelandet, skrivs in i ordboken som en ny fras och någon kod tilldelas den (eftersom W valdes girigt , WK finns ännu inte i ordboken). Tecknet K används som början på nästa fras. Mer formellt kan denna algoritm beskrivas med följande sekvens av steg:

Ordboksinitiering med alla möjliga enkaraktärsfraser. Initiering av inmatningsfrasen W med det första tecknet i meddelandet.
Om END_MESSAGE, utfärda en kod för W och avsluta algoritmen.
Läs nästa tecken K från det kodade meddelandet.
Om frasen WK redan finns i ordboken, ställ in inmatningsfrasen W till WK och gå till steg 2.
Annars, mata ut kod W, lägg till WK i ordboken, ställ in inmatningsfrasen W till värdet K och gå till steg 2.

Avkodningsalgoritmen behöver bara den kodade texten som indata: motsvarande frasordbok återskapas enkelt genom att efterlikna funktionen hos kodningsalgoritmen (men det finns subtila nyanser som diskuteras i exemplet nedan).

Implementering

En anmärkningsvärd egenskap hos LZW-algoritmen är dess enkla implementering, vilket gör den fortfarande mycket populär, trots det ofta sämre kompressionsförhållandet jämfört med analoger som LZ77 [3] . Vanligtvis implementeras LZW med ett prefixträd som innehåller fraser från en ordbok: för att hitta W behöver du bara läsa den längsta möjliga strängen från trädets rot, och för att sedan lägga till en ny fras måste WK läggas till i den hittade noden av den nya sonen med symbolen K, och koden för frasen W kan fungera som index för en nod i en array som innehåller alla noder.

Fraskodning

Användningen av koder med fast längd för fraser (12 bitar i Welch-beskrivningen [1] ) kan negativt påverka komprimeringseffektiviteten, eftersom, för det första, för de initialt kodade tecknen, detta tillvägagångssätt snarare kommer att blåsa upp data snarare än att komprimera (om tecknet tar 8 bitar ), och för det andra är den totala storleken på ordboken (2 12 =4096) inte så stor. Det första problemet löses genom att koda utdatasekvensen med Huffman-algoritmen (eventuellt adaptiv ) eller aritmetisk kodning . För att lösa det andra används andra tillvägagångssätt.

Det första enkla alternativet är att tillämpa någon optimal universell kod som Levenshtein -koden eller Elias-koden . I det här fallet, teoretiskt sett, kan ordboken växa i det oändliga.

Ett annat vanligare alternativ är att ändra högsta möjliga ordboksstorlek när antalet fraser växer. [4] Till en början är till exempel den maximala storleken på ordboken 2 9 (2 8 koder är redan upptagna av fraser för kodning av 8-bitars enstaka tecken) och 9 bitar är allokerade för fraskoden. När antalet fraser blir 2 9 blir den maximala storleken 2 10 och 10 bitar allokeras för koder. Och så vidare. Således kan en ordbok teoretiskt sett vara godtyckligt stor. Denna metod demonstreras i exemplet nedan (vanligtvis är dock den maximala ordboksstorleken begränsad; till exempel i LZC - en populär modifiering av LZW, diskuterad nedan - växer kodlängder från 9 till 16 bitar.).

I de flesta implementeringar av den senare metoden ökas antalet bitar som allokeras till fraskoden tills en ny fras WK läggs till, vilket svämmar över ordboken, men efter att koden W har skrivits till utgången. returnera fraskoden W och lägg till den nya frasen WK till ordboken; om WK-koden är lika med 2 p (det vill säga WK svämmar över ordboken), så matas p-bitkoden W ut först, och först efter det ökas p med ett så att efterföljande koder upptar p + 1 bitar. Tidiga implementeringar av LZW inkluderar de som ökar p före utmatning av W-koden, dvs. W-kodens utmatning innan WK läggs till i ordboken upptar redan p+1 bitar (vilket inte är nödvändigt eftersom W-koden är mindre än 2p ). Detta beteende kallas "tidig förändring". Denna implementeringsförvirring har lett till att Adobe stöder båda varianterna av LZW i PDF (om "tidiga ändringar" används indikeras av en speciell flagga i rubriken för den data som komprimeras). [5]

Ordbok spill

Eftersom koderna i LZW-algoritmen har en fast längd, är storleken på ordboken begränsad (när man använder koder av icke-fast längd, begränsas storleken på ordboken av mängden tillgängligt minne). Frågan uppstår: vad ska man göra om ordboken rinner över? Flera strategier används.

Det mest uppenbara alternativet är att helt enkelt använda den konstruerade ordboken utan ytterligare ändringar. [1] Det är klart att detta ofta är en dålig strategi.
Författarna till det en gång så populära verktyget compress använder helt enkelt den konstruerade ordboken så länge som komprimeringsförhållandet förblir acceptabelt, och rensar sedan upp det om komprimeringskvaliteten försämras. Denna modifiering av LZW kallas LZC (Lempel-Ziv-Compress, se nedan). [6]
P. Tischer föreslog, innan du infogade en ny fras i den överfulla ordboken, vid nästa steg i algoritmen, att radera den fras från ordlistan som inte har använts under längst tid (LRU, Least Recently Used). Denna modifiering kallas ibland LZT (Lempel-Ziv-Tischer, se nedan). [7]

Exempel

Det här exemplet visar LZW-algoritmen i aktion, och visar tillståndet för utdata och ordförråd vid varje steg, både under kodning och avkodning av meddelandet. För att förenkla presentationen kommer vi att begränsa oss till ett enkelt alfabet - endast versaler, utan skiljetecken och mellanslag. Meddelandet som ska komprimeras ser ut så här:

TOBEORNOTTOBEORTOBEORNOT#

Markören # används för att markera slutet av meddelandet. Det finns alltså 27 tecken i vårt alfabet (26 versaler från A till Ö och #). Datorn representerar detta som grupper av bitar, för att representera varje tecken i alfabetet behöver vi bara en grupp på 5 bitar per tecken. I takt med att ordförrådet växer måste gruppernas storlek växa för att kunna rymma nya element. 5-bitars grupper ger 2 5 = 32 möjliga kombinationer av bitar, så när det 33:e ordet förekommer i ordboken ska algoritmen gå till 6-bitars grupper. Observera att eftersom gruppen av alla nollor 00000 används, har den 33:e gruppen koden 32 . Den första ordboken kommer att innehålla:

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

Kodning

Utan att använda LZW-algoritmen, när meddelandet överförs som det är - 25 tecken med 5 bitar vardera - kommer det att ta 125 bitar. Jämför detta med vad som händer när du använder LZW:

Symbol: Bitcode: Ny ordbokspost: (vid utgången) T20 = 10100 O 15 = 01111 27: TO B 2 = 00010 28: OB E5 = 00101 29: BE O15 = 01111 30: EO R 18 = 10010 31: ELLER <--- börja använda 6-bitars grupper från nästa tecken N 14 = 001110 32: RN O15 = 001111 33: NEJ T 20 = 010100 34: OT TO 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 = 100 000 40: EOR OT 34 = 100010 41: RNO # 0 = 000000 42: OT# Total längd = 6*5 + 11*6 = 96 bitar.

Med LZW reducerade vi alltså meddelandet med 29 bitar av 125 - det är nästan 22%. När meddelandet blir längre kommer ordförrådet att representera längre och längre delar av texten, vilket gör upprepade ord mycket kompakta.

Avkodning

Låt oss nu föreställa oss att vi har fått det kodade meddelandet som visas ovan och att vi måste avkoda det. Först och främst måste vi känna till den första ordboken, och vi kan rekonstruera efterföljande ordboksposter på språng, eftersom de helt enkelt är en sammansättning av tidigare poster.

Data: Utdata: Ny post: Fullständig: Delvis: 10100 = 20 T 27: T? 01111 = 15 O 27: TILL 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? <---- börja använda 6-bitars grupper 001110 = 14 N 32: RN 33: N? 001111 = 15 O 33: NO 34: O? 010100 = 20 T 34: OT 35: T? 011011 = 27 TILL 35: TT 36: TILL? <---- för 37, lägg bara till det första elementet 011101 = 29 BE 36: TOB 37: BE? nästa ordboksord 011111 = 31 ELLER 37: BEO 38: ELLER? 100100 = 36 TOB 38: ORT 39: TOB? 011110 = 30 EO 39: TOBE 40: EO? 100 000 = 32 RN 40: EOR 41: RN? 100010 = 34 OT 41: RNO 42: OT? 000000 = 0 #

Den enda lilla svårigheten kan uppstå om det nya ordboksordet skickas omedelbart. I avkodningsexemplet ovan, när avkodaren stöter på det första tecknet, T , vet den att ord 27 börjar med T, men var slutar det? Låt oss illustrera problemet med följande exempel. Vi avkodar ABABA- meddelandet :

Data: Utdata: Ny post: Fullständig: Delvis: . . . 011101 = 29 AB 46: (ord) 47: AB? 101111 = 47AB? <--- vad ska vi göra åt det?

Vid första anblicken är detta en olöslig situation för dekodern. Vi vet i förväg att ord 47 ska vara ABA , men hur vet avkodaren om det? Observera att ord 47 består av ord 29 plus nästa tecken. Ord 47 slutar alltså med "tecken kommer nästa". Men eftersom detta ord skickas direkt måste det börja med "nästa tecken" och så slutar det med samma tecken som det börjar, i det här fallet A . Detta trick låter avkodaren avgöra att ord 47 är ABA .

I allmänhet uppstår denna situation när en sekvens av formen cScSc är kodad , där c är ett enda tecken och S är en sträng, och ordet cS redan finns i ordboken.

Teoretisk utvärdering av effektivitet

De teoretiska egenskaperna hos obegränsat ordförråd LZW är i allmänhet desamma som för LZ78, och analysen av de två komprimeringsmetoderna är likartad. När man överväger en obegränsad ordbok är det naturligt att anta att de utgående fraserna är kodade med koder med variabel längd, till exempel någon universell kod eller en fast kod, vars storlek växer med ordbokens maximala storlek (se implementeringsavsnittet ).

Asymptotisk optimalitet

För en teoretisk utvärdering av effektiviteten jämförs denna komprimeringsmetod med något referensmått. Tyvärr är det ideala referensdatakomprimeringsmåttet - Kolmogorov-komplexitet - inte ens ungefärligt beräkningsbart , och därför förlorar uppenbarligen alla komprimeringsalgoritmer i jämförelse med den. Lempel och Ziv föreslog en försvagad version av Kolmogorovs komplexitet - komprimering med finita automater [2] . Av tekniska skäl är detta mått definierat för oändliga strängar. Vi fixar ett ändligt alfabet . Låt ett oändligt snöre över . Beteckna med antalet bitar i LZW-kodningen med en obegränsad ordbok för strängen . Därför 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 |),

var är antalet fraser i LZW-kodning för . Ziv visade [8] det $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),

var är komprimeringsmåttet av finita automater, definierat nedan [2] . Således är kompressionsförhållandet LZW (förhållande till - antalet bitar som upptas av den okomprimerade strängen) asymptotiskt begränsat , och i denna mening är LZW optimal. Dessutom, om ordboksstorleken är begränsad och överflödesstrategin är att ta bort de minst använda fraserna, är LZW också asymptotiskt optimal i följande mening: [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),

där anger antalet bitar i LZW-kodning med en ordbok som inte innehåller mer än fraser, varje fras har en längd på högst , och när ordboken svämmar över slängs den minst använda frasen ut (det här alternativet liknar LZT; se modifieringar ). Observera att algoritmerna LZ78 och LZ77 har liknande egenskaper (inklusive liknande varianter, respektive med en ordbok och ett glidfönster av begränsad storlek) [8] . Låt oss definiera nu . $\mathrm {LZW} _{D}(x_{1}x_{2}\cdots x_{n})$ $D$ $\log _{2}^{2}D$ $\mathrm {FS}$

Metriken liknar på många sätt Kolmogorov-komplexiteten, men istället för fullfjädrade Turing-maskiner används Turing - maskiner med ändligt minne, det vill säga ändliga automater, i dess definition. För ett givet nummer betecknar vi med uppsättningen av alla deterministiska Mealy-automater som har tillstånd och omkodar strängar över alfabetet till binära sekvenser, så att utdata från automaten kan återställa den ursprungliga strängen; mer exakt, binära strängar (eventuellt tomma) skrivs på kanterna av automaten, så att för varje ändlig sträng över alfabetet kommer automaten till något tillstånd och producerar i processen en binär sekvens , och den kan återställas unikt från sekvensen och tillståndet (så att den sammandragande automaten skulle kunna ha tomma strängar på kanterna, återställs strängen inte bara av sekvensen utan också av sluttillståndet [9] ). För en given oändlig sträng , definiera: [8] $\mathrm {FS} (x)$ $s$ ${\mathcal {A}}_{s}$ $A,$ $s$ $\Sigma$ $A$ $y$ $\Sigma$ $A$ $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 |}},

där anger antalet bitar i . Representerar således en uppskattning för minsta möjliga kompressionsförhållande som kan uppnås när en sträng komprimeras med finita automater. Observera att på grund av ordbokens obegränsade gräns kan LZW-algoritmen inte modelleras med hjälp av en Mealy-automat, i motsats till den begränsade vokabulär-LZW-algoritmen med högst längdfraser (storleken på en sådan Mealy-automat beror naturligtvis på ). $|A(y)|$ $A(y)$ $\mathrm {FS} (x)$ $x$ $D$ $\log _{2}^{2}D$ $D$

Icke-optimalt antal fraser

Kompressionsmåttet med finita automater är, även om det är naturligt, inte så effektivt som det kan verka vid första anblicken. Så asymptotiskt optimal med avseende på är vilken komprimeringsalgoritm som helst som delar upp den givna strängen i olika fraser (det vill säga när ) och sedan kodar med hjälp av bitar [9] . Det är tydligt att en algoritm som uppfyller så svaga kriterier inte behöver vara effektiv i praktiken. Dessutom återspeglar inte tillståndsmaskinens komprimeringsmått förmågan hos många komprimeringsmetoder att ersätta långa repeterande bitar i data med referenser till platsen där en sådan bit först inträffade (tillståndsmaskinen har helt enkelt inte tillräckligt med minne för att jämföra långa bitar). Det är denna mekanism som ofta är orsaken till effektiviteten i att komprimera stora datamängder i praktiken, och som visas nedan så presterar LZW (och LZ78) ganska dåligt på denna uppgift i värsta fall jämfört med till exempel 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 obegränsad ordboksstorlek bryter ner den givna slutliga strängen i fraser , så att varje fras är antingen ett tecken eller lika med , där är något tal mindre än , och är det första tecknet i frasen . Det finns andra nedbrytningar av formen för en sträng , och frågan uppstår naturligtvis: hur bra är nedbrytningen byggd av den giriga LZW-algoritmen? ${\displaystyle x=x_{1}x_{2}\cdots x_{n))$ ${\displaystyle p_{1}p_{2}\cdots p_{z))$ $p_{k}$ $p_{h}a$ $h$ $k$ $a$ $p_{h+1}$ ${\displaystyle p_{1}p_{2}\cdots p_{z))$ $x$

Låt beteckna det minsta antalet så att strängen kan representeras som en nedbrytning där varje sträng är antingen ett tecken eller lika med , där är något tal mindre än , och är det första tecknet i strängen . Sergio De Agostino och Ricardo Silvestri [10] bevisade att det i värsta fall kan vara mer än en faktor 1, även om alfabetet bara innehåller två tecken (de visade också att denna uppskattning är optimal). Med andra ord ger den giriga strategin i det här fallet resultat som är väldigt långt ifrån optimala. En del av motiveringen för LZW-tillvägagångssättet är att att konstruera en optimal frasnedbrytning är ett NP-komplett problem , vilket visas av De Agostino och Storer [11] . ${\displaystyle z_{o))$ $x$ $p'_{1}p'_{2}\cdots p'_{z_{o))$ ${\displaystyle p'_{k))$ $p'_{h}a$ $h$ $k$ $a$ $p'_{h+1}$ $z$ ${\displaystyle z_{o))$ $\Omega (n^{1/4})$ $z\leq z_{o}\cdot O(n^{1/4}),$ ${\displaystyle z_{o))$

En annan naturlig fråga är hur bra LZW är jämfört med LZ77 ? LZ77 är känd för att girigt dekomponera en sträng i fraser , så att varje fras är antingen ett tecken eller en delsträng av strängen . Hooke, Laurie, Re [12] och Charikar et al [13] har visat att den i värsta fall kan vara flera gånger större än . Å andra sidan är det känt att det alltid inte är mindre än , och ännu mer, alltid inte mindre än . [13] Med andra ord, LZW, och till och med den "optimala" versionen av LZW som innehåller fraser, kan inte vara bättre än LZ77 (åtminstone väsentligt - observera att antalet fraser diskuteras här, inte hur de är kodade), och i vissa patologiska fall kan det vara 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))$

Applikation

Vid tiden för introduktionen gav LZW-algoritmen ett bättre kompressionsförhållande för de flesta applikationer än någon annan välkänd metod på den tiden. Det blev den första datakomprimeringsmetoden som användes i stor utsträckning på datorer.

Algoritmen (eller snarare dess modifiering, LZC, se nedan) implementerades i programmet compress , som blev mer eller mindre ett standardverktyg på Unix-system runt 1986. Flera andra populära arkiveringsverktyg använder också denna metod, eller de som ligger nära den.

1987 blev algoritmen en del av standarden för GIF -bildformat . Den kan också (valfritt) användas i TIFF -format . Dessutom används algoritmen i modemets kommunikationsprotokoll v.42bis och PDF -standarden [14] (även om det mesta av text och visuell data i PDF som standard komprimeras med hjälp av Deflate-algoritmen ).

Patent

Ett antal patent har utfärdats för LZW-algoritmen och dess variationer, både i USA och i andra länder. LZ78 utfärdades US Patent 4,464,650 av Sperry Corporation , senare en del av Unisys Corporation . Två amerikanska patent har utfärdats för LZW: US patent 4 814 746 ägt av IBM och Welchs amerikanska patent 4 558 302 (utfärdat 20 juni 1983 ) ägt av Sperry Corporation, senare övertaget av Unisys Corporation. Vid det här laget har alla patent gått ut.

Unisys GIF och PNG

När CompuServe utvecklade GIF - formatet var CompuServe omedveten om existensen av US Patent 4 558 302 . I december 1994, när Unisys blev medveten om användningen av LZW i ett brett använt grafiskt format, offentliggjorde företaget sina planer på att samla in royalties från kommersiella program med möjlighet att skapa GIF-filer. Då var formatet redan så utbrett att de flesta mjukvaruföretag inte hade något annat val än att betala. Denna situation var en av anledningarna till utvecklingen av PNG -grafikformatet (inofficiell transkription: "PNG's Not GIF" [15] ), som blev det tredje vanligaste på WWW , efter GIF och JPEG . I slutet av augusti 1999 avslutade Unisys royaltyfria licenser för LZW för fri och icke-kommersiell programvara [16] och för användare av olicensierade program, vilket fick League for Programming Freedom att lansera en "bränn alla GIFs"-kampanj [17] och informera allmänheten om tillgängliga alternativ. Många patenträttsexperter har påpekat att patentet inte omfattar enheter som bara kan dekomprimera LZW-data, men inte komprimera dem; av denna anledning kan det populära gzip -verktyget läsa .Z-filer men inte skriva dem.

Den 20 juni 2003 gick det ursprungliga amerikanska patentet ut, vilket innebär att Unisys inte längre kan ta ut royalties på det. Liknande patent i Europa, Japan och Kanada gick ut 2004.

Ändringar

LZC (1985, Thomas SW, McKie J., Davies S., Turkowski K., Woods JA och Orost JW) [6] är en av de mest kända praktiska implementeringarna av LZW, tillhandahållen i komprimeringsverktyget (Lempel- Ziv-Compress). LZC använder 9 till 16 bitar för fraskoder (antalet bitar ökar med ordbokens storlek, se implementeringsavsnittet ); när ordboken svämmar över fortsätter LZC helt enkelt att använda den utan ytterligare modifiering, men algoritmen övervakar graden av datakomprimering och, när komprimeringen med den aktuella ordboken blir oacceptabelt dålig, rensar LZC ordlistan och fortsätter att fungera. LZC komprimerar sämre än LZW, men kompressionshastigheten är högre.
LZT (1985, Tischer P.) [7] är en annan känd variant av LZW. När ordboken svämmar över fortsätter LZT, men varje gång innan en ny fras infogas i ordboken tar den bort den fras som motsvarar det längsta oanvända bladet i prefixträdet som innehåller alla fraser. I LZT-implementeringen placeras alla blad i en länkad lista, och varje gång bladen används under komprimering flyttas bladen till listans huvud; således ligger de blad som inte har använts längst längst ner på listan (ytterligare detaljer är uppenbara).
LZMW (1985, Victor Miller och Mark Wegman ) [18] - hittar i ingångsströmmen den längsta strängen som redan finns i ordboken (låt oss beteckna den W), matar ut koden W och lägger sedan till den till ordboken strängen VW, där V är strängen från ordboken vars kod returnerades i föregående steg (initialt är V en tom sträng). Således växer strängarna i ordboken snabbare än i den ursprungliga LZW, och i praktiken går det ofta att få bättre komprimeringskvalitet. Miller och Wegman föreslog också att vid bristande minne skulle fraser som sällan används tas bort från ordboken, precis som man gör i LZT.
LZAP (1988, James Storer) [19] är en modifiering av LZMW, som skiljer sig genom att vid varje steg läggs inte bara strängen VW till i ordboken utan även strängarna VW 1 , VW 2 , …, VW |W |-1 , där Wi är ett prefix W med längden i . ("AP" i "LZAP" betyder "alla prefix", det vill säga "alla prefix.") Till exempel, om V = wiki och W = pedia - det vill säga i föregående steg, hittade algoritmen strängen wiki i ordboken , och på den här hittade den pedia - då kommer algoritmen att lägga till strängen wikipedia till ordboken , som LZMW skulle göra, men också lägga till strängarna wikip , wikipe , wikiped , wikipedi . LZAP-algoritmen är lättare att implementera än LZMW, men samtidigt behåller den de flesta fördelarna med LZMW, förutom att ordbokssträngskoder tar mer plats eftersom ordboken är mer uppsvälld.

Se även

Anteckningar

↑ 1 2 3 4 5 Welch, 1984 .
↑ 1 2 3 Lempel, Ziv, 1978 .
↑ Arnold, Bell, 1997 .
↑ Bell, Witten, Cleary, 1989 , avsnitt 3.4.6.
↑ PDF 1.7-specifikation , avsnitt 7.4.4.3.
↑ 1 2 Bell, Witten, Cleary, 1989 , avsnitt 3.4.8.
↑ 1 2 Bell, Witten, Cleary, 1989 , avsnitt 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 , avsnitt 7.4.4.
↑ Webbrecension: PNG är INTE GIF! . Hämtad 18 oktober 2018. Arkiverad från originalet 30 mars 2022. (obestämd)
↑ Unisys LZW-patent och GIF-filer . Hämtad 18 oktober 2018. Arkiverad från originalet 19 oktober 2018. (obestämd)
↑ Unisys upprätthåller GIF-patent - Slashdot . Hämtad 18 oktober 2018. Arkiverad från originalet 18 oktober 2018. (obestämd)
↑ Miller, Wegman, 1985 .
↑ Storer, 1988 .

Litteratur

Arnold R., Bell T. En korpus för utvärdering av förlustfria komprimeringsalgoritmer // IEEE Data Compression Conference. - 1997. - S. 201-210 . - doi : 10.1109/DCC.1997.582019 .
Bell T. , Witten IH , Cleary JG Modellering för textkomprimering // 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 minsta grammatikproblemet // 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 värsta tänkbar analys av 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 kontra off-line beräkning i dynamisk textkomprimering // 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 minsta grammatikproblemet återbesökt // 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. Komprimering av individuella sekvenser via kodning med variabel hastighet // 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 på ett tema av Ziv och Lempel // Kombinatoriska algoritmer på ord. - 1985. -T. 12. —S. 131–140. -doi:10.1007/978-3-642-82456-2_9.
Sheinwald D. Om Ziv-Lempel-beviset och relaterade ämnen // Proceedings of the IEEE . - 1994. - T. 82 , nr 6 . — S. 866–871 . - doi : 10.1109/5.286190 .
Storer JA Datakompression: Metoder och teori. - New York, USA: Computer Science Press, 1988. - 413 sid. - ISBN 0-7167-8156-5 .
Welch TA En teknik för högpresterande datakomprimering // Dator. - 1984. - V. 6 , nr 17 . — S. 8–19 . - doi : 10.1109/MC.1984.1659158 .
Ziv J. En version av LZ78 med begränsad ordbok uppnår asymptotiskt komprimerbarheten i finita tillstånd med ett distorsionsmått // IEEE Information Theory Workshop. - 2015. - S. 1–4 . - doi : 10.1109/ITW.2015.7133077 .
Adobe Systems Inc. Dokumenthantering - Portabelt dokumentformat - Del 1: PDF 1.7 . PDF 1.7-specifikation . Adobe (1 juli 2008). Tillträdesdatum: 26 januari 2018.

Kompressionsmetoder _

Teori

Information	Egen Ömsesidig Entropi Villkorlig entropi Komplexitet Redundans
Enheter	Bit Nat Knapra Hartley Hartley formel

Förlust mindre

Entropikompression	Asymmetriska talsystem Huffman algoritm Adaptiv Huffman-algoritm Shannon-Fano algoritm Shannons algoritm Aritmetisk kodning ( intervall ) Golomb-koder Delta Universell kod Elias fibonacci
Ordboksmetoder	RLE Töm luften LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Övrig	RLE CTW BWT MTF PPM DMC

Audio

Teori	Veck PCM Aliasing Provtagning Kotelnikovs teorem
Metoder	LPC LAR LSP WLPC CELP ACELP En lag μ-lag ADPCM MDCT Fouriertransform Psykoakustisk modell
Övrig	Ljudkompressor Talkompression Bandkodning

Bilder

Villkor	färg rymd Pixel Mättnad delsampling Kompressionsartefakter
Metoder	RLE DPCM fraktal vågkomponent EZW SPIHT LP PrEP PCL
Övrig	Bithastighet Standard testbild PSNR Kvantisering

Video

Villkor	Videoegenskaper Ram Ramtyper Videokvalitét
Metoder	Rörelsekompensation PrEP Kvantisering vågkomponent
Övrig	Video codec Rate distortion theory CBR ABR VBR

Arkivformat _
Endast arkivering	ar cpio DAR shar tjära LBR
Endast kompression	bzip2 komprimera gzip LZMA LZW lzop rzip S.Q. XZ
Arkivering och komprimering	7z ACB ESS BÅGE ALZip ARJ Skåp cpt dd DGCA dmg GCA kgb LHA LZX PAQ PRS RAR qda sitta SQX xar Zoo blixtlås
Programvarupaketering och distribution	apk deb pkg pärla RPM MSI BURK KRIG RAR (Java) ÖRA