LZ-77
Základní informace
- slovníková kompresní metoda
- jednoprůchodová kompresní metoda
- adaptivní kompresní metoda
- asymetrická kompresní metoda
- vhodná pro jednorázové zakódování a četná dekódování
- použití v gzip, zip, pkzip
Historie
Původní metoda posuvného okna navržená v roce 1977 Abrahamem Lempelem a Jacobem Zivem pro bezztrátovou kompresi dat. Stala se základem pro ostatní LZ metody.
Popis
Tato metoda používá okno, rozdělené na zakódovanou a nezakódovanou část - výhled. Velikost zakódované části bývá 8 192 bitů a velikost výhledu bývá 10 až 20 bitů, ve vizualizaci je možné tyto hodnoty nastavit.
Algoritmus pracuje tak, že vyhledá nejdelší předponu výhledu, která začíná v zakódované části a zakóduje ji pak pomocí trojice (i,j,X), kde i je vzdálenost předpony od hranice mezi nezakódovanou a zakódovanou částí, j je délka nalezené předpony a X je první znak za předponou v nezakódované části. Vizualizace tohoto algoritmu je v následujícím appletu. Počet výstupních bitů vychází ze zakódování čísel.
Pseudokód
1: begin
2: naplň nezakódovanou část okna ze vstupu
3: while (nezakódovaná část není prázdná) do
4: begin
5: najdi v okně předponu p nezakódované části začínající v zakódované části
6: i := pozice předpony p v okně
7: j := délka předpony p
8: X := první znak za p v nezakódované části
9: output(i,j,X)
10: přidej do okna zprava i+1 znaků
11: end
12: end
Odkazy
- LZ77. Wikipedia, the free encyclopedia.
- Aplikace využívající LZ77
- Humorně podaný příběh komprimovacích algoritmů, zejména pak algoritmů rodiny LZ a jejich patentů
- Michael Dipperstein: LZSS (LZ77) Discussion and Implementation.