LZ77 och LZ78 är förlustfria komprimeringsalgoritmer publicerade i tidningar av de israeliska matematikerna Abraham Lempel och Yaakov Ziv 1977 och 1978 . Dessa algoritmer är de mest kända varianterna i LZ* -familjen , som även inkluderar LZW , LZSS , LZMA och andra algoritmer.
Båda algoritmerna är ordboksmetoder, till skillnad från andra redundansreduktionsmetoder som RLE och aritmetisk komprimering . LZ77 är en "sliding window"-algoritm, vilket är ekvivalent med den implicita användningen av den ordboksmetod som först föreslogs i LZ78.
Vi kan säga att algoritmerna för LZ*-familjen är en mer komplex generalisering av den enkla och intuitiva datakomprimeringsmetoden som används i RLE . För att förstå denna algoritm är det nödvändigt att förstå dess två komponenter: principen för glidfönster och kodningsmekanismen för sammanträffande .
Kodningsmetoden, enligt principen med glidande fönster, tar hänsyn till information som redan har påträffats, det vill säga information som redan är känd för kodaren och avkodaren (den andra och efterföljande förekomsten av en teckensträng i meddelandet ersätts genom länkar till dess första förekomst).
På grund av denna princip kallas LZ*-algoritmer ibland för komprimeringsmetoder för glidfönster. Ett glidande fönster kan ses som en buffert (eller mer komplex dynamisk datastruktur) som är organiserad för att komma ihåg och komma åt tidigare "sagd" information. Således påminner själva processen med komprimeringskodning enligt LZ77 om att skriva ett program vars kommandon låter dig komma åt elementen i det "skjutbara fönstret", och istället för värdena för den komprimerade sekvensen, infoga referenser till dessa värden i det "skjutbara fönstret". Storleken på det skjutbara fönstret kan ändras dynamiskt och vara 2, 4 eller 32 kilobyte. Det bör också noteras att kodarens fönsterstorlek kan vara mindre än eller lika med avkodarens fönsterstorlek, men inte vice versa.
Ovanstående jämförelse av kodningsprocessen med "programmering" kan leda till en för tidig slutsats att LZ77-algoritmen tillhör kontextmodelleringsmetoder . Därför bör det noteras att LZ77-algoritmen vanligtvis klassificeras som en datakomprimeringsmetod för ordbok , när termen "dynamisk ordbok" används istället för konceptet med ett "glidande fönster".
Innan vi går vidare till övervägandet av kodningsmekanismen, låt oss förtydliga begreppet matchning (från engelska match ). Betrakta en sekvens av N element. Om alla element i en sekvens är unika, kommer en sådan sekvens inte att innehålla ett enda upprepande element, eller, med andra ord, det kommer inte att finnas minst två lika eller sammanfallande element i sekvensen.
I standard LZ77-algoritmen kodas matchningar som ett par:
I fortsättningen av den redan givna analogin med programmering noterar vi att i de flesta artiklar som ägnas åt LZ77-algoritmen tolkas det kodade paret exakt som ett kommando för att kopiera tecken från ett glidande fönster från en viss position, eller bokstavligen som: "Återgå till offsetvärdet i teckenbufferten och kopiera teckenlängdsvärdet med början från den aktuella positionen.
Även om denna tolkning kan verka intuitiv för imperativa programmerare , säger den lite om karaktären hos LZ77-algoritmen som en komprimeringsmetod. Det speciella med denna komprimeringsalgoritm är att användningen av ett kodat längdförskjutningspar inte bara är acceptabelt utan också effektivt i fall där längdvärdet överstiger förskjutningsvärdet.
Exemplet med kopieringskommandot är inte helt självklart: "Gå tillbaka 1 tecken i bufferten och kopiera 7 tecken, med start från den aktuella positionen." Hur kan man kopiera 7 tecken från bufferten när det bara finns 1 tecken i bufferten för tillfället? Följande tolkning av kodningsparet kan dock förtydliga situationen: vart sjunde efterföljande tecken är samma (motsvarande) med det 1 tecknet före dem.
Detta innebär att varje tecken entydigt kan bestämmas genom att flytta tillbaka i bufferten - även om det givna tecknet ännu inte finns i bufferten vid den tidpunkt då det aktuella längdoffsetparet avkodas . Ett sådant kodat par skulle vara en multipel (specificerad av offsetvärdet) upprepning av en sekvens (specificerad av längdvärdet) av tecken, vilket är en mer allmän form av RLE .
De valda tecknen finns inte i kodningssekvensen.
Till skillnad från LZ77, som fungerar med redan mottagna data, fokuserar LZ78, som föreslogs 1978 [1] , på data som bara kommer att tas emot (LZ78 använder inte ett "glidande" fönster, det lagrar en ordbok med fraser som redan har visats). Algoritmen läser tecknen i meddelandet tills den ackumulerade delsträngen ingår helt i en av ordboksfraserna. Så snart denna sträng inte längre matchar minst en ordboksfras, genererar algoritmen en kod som består av indexet för strängen i ordboken som innehöll inmatningssträngen tills det sista tecknet angavs, och tecknet som bröt mot matchningen. Sedan läggs den inmatade delsträngen till i ordboken. Om ordboken redan är full, tas den fras som används minst i jämförelser preliminärt bort från den.
Låt strängen ACAGAATAGAGA ges.
| Lexikon | Läs radens innehåll | Koden |
|---|---|---|
| A | <0,A> | |
| A=1 | C | <0,C> |
| A=1 C=2 |
AG | <1,G> |
| A=1, C=2 AG=3 |
AA | <1,A> |
| A=1, C=2 AG=3, AA=4 |
T | <0, T> |
| A=1, C=2, AG=3 AA=4, T=5 |
AGA | <3,A> |
| A=1, C=2, AG=3 AA=4, T=5, AGA=6 |
G | <0,G> |
| A=1, C=2, AG=3, AA=4 T=5, AGA=6, G=7 |
A | <1,EOF> |
Resultatet av arbetet blir sekvensen: <0, A><0, C><1, G><1, A><0, T><3, A><0, G><1, EOF> .
| Kompressionsmetoder _ | |||||||
|---|---|---|---|---|---|---|---|
| Teori |
| ||||||
| Förlust mindre |
| ||||||
| Audio |
| ||||||
| Bilder |
| ||||||
| Video |
| ||||||