Kompresní algoritmus Lempel-Ziv v Javě

Řešení úlohy je založeno na algoritmu Lempel-Ziv, který v sedmdesátých letech vyvinuli Abraham Lempel a Jacob Ziv.

Jak to funguje

Při kompresi se nahrazují posloupnosti bajtů kódem (index, B), kde index odkazuje na položku ve slovníku a B určuje hodnotu bajtu. Na začátku obsahuje slovník položky 0 až 255 a posloupnost P je prázdná. V každém kroku se ze vstupu načte jeden bajt B. Pokud slovník obsahuje posloupnost P||B, pokračuje se načtením dalšího bajtu. V opačném případě se posloupnost P||B přidá do slovníku, na výstup se zapíše dvojice (index P, B) a P se nastaví na prázdnou posloupnost. V případě, že na vstupu zbývá pouze jeden bajt, na výstup se zapíše kód (X, B), kde X je speciální index vyhrazený pro prázdnou posloupnost.

Při dekompresi se nahrazuje kód (index, B) posloupnostmi bajtů. V každém kroku se ze vstupu načte kód (index, B). Je-li index = X, posloupnost P se nastaví na prázdnou. V opačném případě se posloupnost P načte ze slovníku. Posloupnost P || B se zapíše na výstup a přidá do slovníku.

Pozn.: Symbol || značí zřetězení. Např. 01 02 || 04 je 01 02 04.

Spuštění programu

Soubor zkomprimujete příkazem:

java -jar silvinios-compression.jar INPUT_FILE OUTPUT_FILE

a dekomprimujete příkazem:

java -jar silvinios-compression.jar -d INPUT_FILE OUTPUT_FILE

INPUT_FILE je vstupní soubor a OUTPUT_FILE je soubor výstupní.

Zdrojové kódy

Zdrojové kódy jsou k dispozici ke stažení jako projekt pro Eclipse. Použité kódování je UTF-8.

Galerie