Kompresný algoritmus Lempel-Ziv v Jave

Riešenie úlohy je založené na algoritme Lempel-Ziv, ktorý v sedemdesiatych rokoch vyvinuli Abrahám Lempel a Jacob Ziv.

Ako to funguje

Pri kompresii sa nahrádzajú postupnosti bajtov kódom (index, B), kde index odkazuje na položku v slovníku a B určuje hodnotu bajtu. Na začiatku obsahuje slovník položky 0 až 255 a postupnosť P je prázdna. V každom kroku sa zo vstupu načíta jeden bajt B. Ak slovník obsahuje postupnosť P || B, pokračuje sa načítaním ďalšieho bajtu. V opačnom prípade sa postupnosť P || B pridá do slovníka, na výstup sa zapíše dvojica (index P, B) a P sa nastaví na prázdnu postupnosť. V prípade, že na vstupe zostáva iba jeden bajt, na výstup sa zapíše kód (X, B), kde X je špeciálny index vyhradený pre prázdnu postupnosť.

Pri dekompresiu sa nahrádza kód (index, B) postupnosťami bajtov. V každom kroku sa zo vstupu načíta kód (index, B). Ak je index = X, postupnosť P sa nastaví na prázdnu. V opačnom prípade sa postupnosť P načíta zo slovníka. Postupnosť P || B sa zapíše na výstup a pridá do slovníka.

Pozn .: Symbol || značí zreťazenie. Napr. 01 02 || 04 je 01 02 04.

Spustenie programu

Súbor skomprimuje príkazom:

java -jar silvinios-compression.jar INPUT_FILE OUTPUT_FILE

a dekomprimuje príkazom:

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

INPUT_FILE je vstupný súbor a OUTPUT_FILE je súbor výstupný.

Zdrojové kódy

Zdrojové kódy sú k dispozícii na stiahnutie ako projekt pre Eclipse. Použité kódovanie je UTF-8.

Galéria