LZ77 og LZ78 er tabsfri komprimeringsalgoritmer udgivet i artikler af de israelske matematikere Abraham Lempel og Yaakov Ziv i 1977 og 1978 . Disse algoritmer er de bedst kendte varianter i LZ* -familien , som også omfatter LZW , LZSS , LZMA og andre algoritmer.
Begge algoritmer er ordbogsmetoder, i modsætning til andre redundansreduktionsmetoder såsom RLE og aritmetisk komprimering . LZ77 er en "sliding window"-algoritme, som svarer til den implicitte brug af den ordbogstilgang, der først blev foreslået i LZ78.
Vi kan sige, at algoritmerne i LZ* -familien er en mere kompleks generalisering af den enkle og intuitive datakomprimeringsmetode, der bruges i RLE . For at forstå denne algoritme er det nødvendigt at forstå dens to komponenter: glidende vinduesprincippet og tilfældighedskodningsmekanismen .
Kodningsmetoden, ifølge glidende vinduesprincippet, tager højde for information, der allerede er stødt på, det vil sige information, der allerede er kendt af koderen og dekoderen (den anden og efterfølgende forekomst af en streng af tegn i meddelelsen erstattes ved links til dens første forekomst).
På grund af dette princip omtales LZ*-algoritmer nogle gange som sliding window-komprimeringsmetoder. Et glidende vindue kan opfattes som en buffer (eller mere kompleks dynamisk datastruktur), der er organiseret til at huske og få adgang til tidligere "sagte" informationer. Således minder selve processen med komprimeringskodning i henhold til LZ77 om at skrive et program, hvis kommandoer giver dig adgang til elementerne i "glidende vindue", og i stedet for værdierne af den komprimerede sekvens, indsæt referencer til disse værdier i "skydevinduet". Størrelsen på det glidende vindue kan ændres dynamisk og være 2, 4 eller 32 kilobyte. Det skal også bemærkes, at kodervinduets størrelse kan være mindre end eller lig med dekodervinduets størrelse, men ikke omvendt.
Ovenstående sammenligning af kodningsprocessen med "programmering" kan føre til en for tidlig konklusion om, at LZ77-algoritmen tilhører kontekstmodelleringsmetoder . Derfor skal det bemærkes, at LZ77-algoritmen normalt klassificeres som en ordbogsdatakomprimeringsmetode , når udtrykket "dynamisk ordbog" bruges i stedet for begrebet "glidende vindue".
Før vi går videre til overvejelserne om indkodningsmekanismen, lad os præcisere begrebet match (fra det engelske match ). Overvej en sekvens af N elementer. Hvis alle elementer i en sekvens er unikke, vil en sådan sekvens ikke indeholde et enkelt gentagende element, eller med andre ord, der vil ikke være mindst to lige store eller sammenfaldende elementer i sekvensen.
I standard LZ77-algoritmen er kampe kodet som et par:
I forlængelse af den allerede givne analogi med programmering bemærker vi, at i de fleste artikler om LZ77-algoritmen tolkes det kodede par præcist som en kommando til at kopiere tegn fra et glidende vindue fra en bestemt position, eller bogstaveligt som: "Vend tilbage til forskydningsværdien i tegnbufferen og kopier tegnlængdeværdien startende fra den aktuelle position.
Selvom denne fortolkning kan virke intuitiv for imperative programmører , siger den lidt om karakteren af LZ77-algoritmen som en komprimeringsmetode. Det særlige ved denne kompressionsalgoritme er, at brugen af et kodet længde-offset- par ikke kun er acceptabelt, men også effektiv i tilfælde, hvor længdeværdien overstiger offset-værdien.
Eksemplet med kopieringskommandoen er ikke helt indlysende: "Gå 1 tegn tilbage i bufferen og kopier 7 tegn, startende fra den aktuelle position." Hvordan kan du kopiere 7 tegn fra bufferen, når der kun er 1 tegn i bufferen i øjeblikket? Den følgende fortolkning af kodningsparret kan dog afklare situationen: Hvert 7 efterfølgende tegn er det samme (svarende til) det 1 tegn før dem.
Det betyder, at hvert tegn entydigt kan bestemmes ved at flytte tilbage i bufferen - også selvom det givne tegn endnu ikke er i bufferen på det tidspunkt, hvor det aktuelle længde-offset- par afkodes . Et sådant kodet par ville være en multipel (specificeret af offsetværdien) gentagelse af en sekvens (specificeret ved længdeværdien) af tegn, som er en mere generel form for RLE .
De valgte tegn er ikke i kodningssekvensen.
I modsætning til LZ77, som arbejder med allerede modtagede data, fokuserer LZ78, foreslået i 1978 [1] , på data, der kun vil blive modtaget (LZ78 bruger ikke et "glidende" vindue, det gemmer en ordbog med sætninger, der allerede er set). Algoritmen læser meddelelsens tegn, indtil den akkumulerede delstreng er inkluderet helt i en af ordbogssætningerne. Så snart denne streng ikke længere matcher mindst én ordbogssætning, genererer algoritmen en kode, der består af indekset for strengen i ordbogen, der indeholdt inputstrengen indtil det sidste tegn, der blev indtastet, og det tegn, der overtrådte matchningen. Derefter tilføjes den indtastede understreng til ordbogen. Hvis ordbogen allerede er fuld, er den sætning, der er mindst brugt i sammenligninger, foreløbig fjernet fra den.
Lad strengen ACAGAATAGAGA være givet.
| Ordbog | Læs linjeindhold | Koden |
|---|---|---|
| EN | <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 |
EN | <1,EOF> |
Resultatet af arbejdet vil være sekvensen: <0, A><0, C><1, G><1, A><0, T><3, A><0, G><1, EOF> .
| Kompressionsmetoder _ | |||||||
|---|---|---|---|---|---|---|---|
| Teori |
| ||||||
| Tabsfri |
| ||||||
| Lyd |
| ||||||
| Billeder |
| ||||||
| Video |
| ||||||