LZ77 a LZ78 jsou bezeztrátové kompresní algoritmy publikované v dokumentech izraelských matematiků Abrahama Lempela a Yaakova Ziva v letech 1977 a 1978 . Tyto algoritmy jsou nejznámějšími variantami v rodině LZ* , která také zahrnuje LZW , LZSS , LZMA a další algoritmy.
Oba algoritmy jsou slovníkové metody, na rozdíl od jiných metod redundance redundance, jako je RLE a aritmetická komprese . LZ77 je algoritmus "posuvného okna", který je ekvivalentní implicitnímu použití slovníkového přístupu, který byl poprvé navržen v LZ78.
Můžeme říci, že algoritmy rodiny LZ* jsou složitějším zobecněním jednoduché a intuitivní metody komprese dat používané v RLE . Pro pochopení tohoto algoritmu je nutné pochopit jeho dvě složky: princip posuvného okna a mechanismus koincidenčního kódování .
Metoda kódování podle principu posuvného okna bere v úvahu informace, se kterými se již setkali, tedy informace, které jsou již kodéru a dekodéru známé (druhý a další výskyt řetězce znaků ve zprávě je nahrazen pomocí odkazů na jeho první výskyt).
Kvůli tomuto principu jsou algoritmy LZ* někdy označovány jako metody komprese posuvných oken. Posuvné okno si lze představit jako vyrovnávací paměť (nebo složitější dynamickou datovou strukturu), která je organizována tak, aby si pamatovala a zpřístupňovala dříve „uvedené“ informace. Samotný proces kódování komprese podle LZ77 tedy připomíná psaní programu, jehož příkazy umožňují přístup k prvkům „posuvného okna“ a místo hodnot komprimované sekvence vložit odkazy na tyto hodnoty v "posuvném okně". Velikost posuvného okna lze dynamicky měnit a být 2, 4 nebo 32 kilobajtů. Je třeba také poznamenat, že velikost okna kodéru může být menší nebo rovna velikosti okna dekodéru, ale ne naopak.
Výše uvedené srovnání procesu kódování s „programováním“ může vést k předčasnému závěru, že algoritmus LZ77 patří k metodám kontextového modelování . Proto je třeba poznamenat, že algoritmus LZ77 je obvykle klasifikován jako slovníková metoda komprese dat , když se místo pojmu „posuvné okno“ používá termín „dynamický slovník“.
Než přistoupíme k úvahám o mechanismu kódování, ujasněme si pojem shoda (z anglického match ). Uvažujme posloupnost N prvků. Pokud jsou všechny prvky sekvence jedinečné, pak taková sekvence nebude obsahovat jediný opakující se prvek, nebo jinými slovy, v sekvenci nebudou alespoň dva stejné nebo shodné prvky.
Ve standardním algoritmu LZ77 jsou shody kódovány jako pár:
V návaznosti na již uvedenou analogii s programováním podotýkáme, že ve většině článků věnovaných algoritmu LZ77 je zakódovaný pár interpretován přesně jako příkaz ke zkopírování znaků z posuvného okna z určité pozice, nebo doslova jako: „Návrat na hodnotu offsetu ve vyrovnávací paměti znaků a zkopírujte hodnotu délky znaku počínaje aktuální pozicí.
I když se tato interpretace může zdát intuitivním programátorům imperativním , říká jen málo o povaze algoritmu LZ77 jako kompresní metody. Zvláštností tohoto kompresního algoritmu je to, že použití zakódovaného páru délka-offset je nejen přijatelné, ale také účinné v případech, kdy hodnota délky přesahuje hodnotu offsetu.
Příklad s příkazem copy není zcela zřejmý: "Vraťte se o 1 znak zpět do vyrovnávací paměti a zkopírujte 7 znaků, počínaje aktuální pozicí." Jak můžete zkopírovat 7 znaků z vyrovnávací paměti, když je v tuto chvíli ve vyrovnávací paměti pouze 1 znak? Následující výklad kódovacího páru však může situaci objasnit: každých 7 následujících znaků je stejných (ekvivalentních) jako 1 znak před nimi.
To znamená, že každý znak lze jednoznačně určit pohybem zpět ve vyrovnávací paměti – i když daný znak v době dekódování aktuálního páru délky-offset ještě ve vyrovnávací paměti není . Takový kódovaný pár by byl vícenásobným (určeným hodnotou offsetu) opakováním sekvence (určené hodnotou délky) znaků, což je obecnější forma RLE .
Vybrané znaky nejsou v kódovací sekvenci.
Na rozdíl od LZ77, který pracuje s již přijatými daty, LZ78, navržený v roce 1978 [1] , se zaměřuje na data, která budou pouze přijímána (LZ78 nepoužívá „posuvné“ okno, ukládá slovník již prohlížených frází). Algoritmus čte znaky zprávy, dokud není nahromaděný podřetězec zcela zahrnut do jedné z frází slovníku. Jakmile tento řetězec již neodpovídá alespoň jedné frázi ve slovníku, algoritmus vygeneruje kód skládající se z indexu řetězce ve slovníku, který obsahoval vstupní řetězec až do posledního zadaného znaku, a znaku, který shodu porušil. Poté se zadaný podřetězec přidá do slovníku. Pokud je slovník již plný, pak je z něj předběžně odstraněno slovní spojení nejméně používané ve srovnání.
Nechť je dán řetězec ACAGAATAGAGA.
| Slovník | Přečtěte si obsah řádku | Kód |
|---|---|---|
| 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> |
Výsledkem práce bude sekvence: <0, A><0, C><1, G><1, A><0, T><3, A><0, G><1, EOF> .
| Kompresní metody | |||||||
|---|---|---|---|---|---|---|---|
| Teorie |
| ||||||
| Bezztrátový |
| ||||||
| Zvuk |
| ||||||
| snímky |
| ||||||
| Video |
| ||||||