LZW komprese

Školení, která pořádám

Pro kompresi textů je velmi účinná komprese LZW. Spočívá v tom, že si postupně budujeme slovník opakujících se posloupností bajtů. Algoritmus komprese bohužel není přímo součástí PHP, i když ho využívá třeba formát GIF, se kterým PHP extenze pracovat umí. Komprese je nicméně jednoduchá, takže si ji můžeme napsat sami:

<?php
/** LZW komprese
* @param string data ke komprimaci
* @return array kódy ze slovníku
* @copyright Jakub Vrána, https://php.vrana.cz/
*/
function lzw_encode($string) {
    $dictionary = array_flip(range("\0", "\xFF"));
    $word = "";
    $return = array();
    for ($i=0; $i <= strlen($string); $i++) {
        $x = $string[$i];
        if (strlen($x) && isset($dictionary[$word . $x])) {
            $word .= $x;
        } elseif ($i) {
            $return[] = $dictionary[$word];
            $dictionary[$word . $x] = count($dictionary);
            $word = $x;
        }
    }
    return $return;
}
?>

Funkce vrací pole kódů z průběžně budovaného slovníku. Při dekompresi si tento slovník budeme také průběžně budovat a zároveň vrátíme v něm nalezené kódy. Jediné úskalí spočívá v situaci, kdy je na vstupu kód, který zrovna přidáváme do slovníku – ten bude končit svým prvním bajtem.

<?php
/** LZW dekomprese
* @param array kódy ze slovníku
* @return string dekomprimovaná data
* @copyright Jakub Vrána, https://php.vrana.cz/
*/
function lzw_decode($codes) {
    $dictionary = range("\0", "\xFF");
    $return = "";
    foreach ($codes as $i => $code) {
        $element = $dictionary[$code];
        if (!isset($element)) {
            $element = $word . $word[0];
        }
        $return .= $element;
        if ($i) {
            $dictionary[] = $word . $element[0];
        }
        $word = $element;
    }
    return $return;
}
?>

Aby komprese skutečně komprimovala, je potřeba převést posloupnost kódů na binární řetězec. Čistší je udělat to oddělenou funkcí, než to míchat přímo do komprimace. Jednoduchý způsob spočívá v tom, že se ukládá nejmenší možný počet bitů pro uložení slovníkového kódu, efektivnější způsob by využil např. Huffmanův algoritmus.

<?php
/** Převod LZW kódů na binární řetězec
* @param array výstup funkce lzw_encode()
* @return string komprimovaná data
* @copyright Jakub Vrána, https://php.vrana.cz/
*/
function lzw_binary($codes) {
    $dictionary_count = 256;
    $bits = 8; // ceil(log($dictionary_count, 2))
    $return = "";
    $rest = 0;
    $rest_length = 0;
    foreach ($codes as $code) {
        $rest = ($rest << $bits) + $code;
        $rest_length += $bits;
        $dictionary_count++;
        if ($dictionary_count >> $bits) {
            $bits++;
        }
        while ($rest_length > 7) {
            $rest_length -= 8;
            $return .= chr($rest >> $rest_length);
            $rest &= (1 << $rest_length) - 1;
        }
    }
    return $return . ($rest_length ? chr($rest << (8 - $rest_length)) : "");
}
?>

Obdobně se z binárního řetězce sestaví kódy:

<?php
/** Získání LZW kódů z binárních dat
* @param string komprimovaná data
* @return array vstup pro funkci lzw_decode()
* @copyright Jakub Vrána, https://php.vrana.cz/
*/
function lzw_codes($binary) {
    $dictionary_count = 256;
    $bits = 8; // ceil(log($dictionary_count, 2))
    $return = array();
    $rest = 0;
    $rest_length = 0;
    for ($i=0; $i < strlen($binary); $i++) {
        $rest = ($rest << 8) + ord($binary[$i]);
        $rest_length += 8;
        if ($rest_length >= $bits) {
            $rest_length -= $bits;
            $return[] = $rest >> $rest_length;
            $rest &= (1 << $rest_length) - 1;
            $dictionary_count++;
            if ($dictionary_count >> $bits) {
                $bits++;
            }
        }
    }
    return $return;
}
?>

Ukázka použití

<?php
$data = "";
$compressed = lzw_binary(lzw_encode($data));
var_dump($data === lzw_decode(lzw_codes($compressed)));
?>

Funkce jsem sdružil do projektu php-lzw.

Jakub Vrána, Seznámení s oblastí, 11.9.2009, diskuse: 19 (nové: 0)

Diskuse

Vojtěch Semecký:

Jako studijní materiál pěkný, ale v praxi bych použil raději kompresi Gzip, právě kvůli tomu, že v PHP implementována je a tudíž poskytuje vyšší výkon, než řešení napsané v jazyce PHP.

ikona Jakub Vrána OpenID:

Hrál jsem si s tím v Admineru, kde jsem potřeboval řešení nezávislé na PHP extenzi a výkon mě netrápil (protože komprese se provádí jen jednou za vydání verze a dekomprese jen jednou za sezení – rozbalený text se kešuje). Nakonec jsem to ale nepoužil (vyjde o tom článek).

Michal Illich:

Huffmann by nebyl dobry - jednak by to uz nebylo LZW, ale on by tam ten huffmann nenadelal tolik dobroty jako v jinych svych pouzitich (napriklad v gzipu, raru a podobnych pakovacich). To proto, ze LZW samo o sobe usiluje o to, aby vsechny znaky byly priblizne stejne caste (protoze k tem castejsim generuje jejich potomky, cimz se snizuje potreba rodicu v budoucnu).

ikona Jakub Vrána OpenID:

Já myslím, že adaptivní Huffman by mohl pomoct u dat, jejichž charakter se mění (jako jsou třeba texty v různých jazycích nebo třeba TAR ze souborů různého druhu). Tam bych viděl problém v tom, že se slovník zaseká frázemi, které už se nadále nepoužívají a na všechny (tedy i ty nové) kódy se vypotřebuje hodně bitů. Adaptivní Huffman by těmto naposledy používaným kódům přiřadil kratší bitovou délku.

Leo:

Kdyz uz si hrajeme tak co prevest text na obrazova data, ulozit do GIFu (a vyuzit tak LZW kompresi) a pak to prevest zpatky na text :-) Jeste zajimavejsi by pak mohlo byt pouzit tento postup se ztratovou kompresi JPEG, jak by se text zmenil :-) Leo

Marek Hrabě:

Zajímavej přístup, Leo :D bylo by to dost zajímavý :)

pojízdná kočka:

Bude mít Adminer export/import .sql souboru ve zpakované formě?

ikona Jakub Vrána OpenID:

Ano, už je hotový.

kozotoč:

if ($dictionary_count > (1 << $bits)) {

-->

if($dictionary_count >> $bits) {

ikona Jakub Vrána OpenID:

Díky, změnil jsem to.

Říkal jsem si, jak se do komentáře dostal ten neuzavřený HTML komentář a ona to je šipka :-).

koko:

zkusím taky dát návrh na vylepšení:
místo...
<?php
$dictionary_count
= 256;
$bits = 8; // ceil(log($dictionary_count, 2))
?>
...dát:
<?php
$bits
= 8;
$dictionary_count = 1 << $bits;
?>
- Místo dvou závislých konstant jedna
- o ždibíček více rezistentní proti změně $bits bez změny $dictionary_count
(chápu, že to je víceméně jedno)

ikona Jakub Vrána OpenID:

Nezdá se mi to jako dobrý nápad, protože $dictionary_count může být třeba 257 (pokud bychom použili kódování, které jeden kód uloží do méně než jednoho bajtu, tak bychom potřebovali ještě symbol pro End-of-stream).

Nána:

Co kdybych to chtěla použít na data, jejichž velikost přesahuje přidělenou paměť pro skript? Jsou tam nějaká úskalí? Předpokládám, že tady asi asociativita nebude fungovat... Jak by třeba vypadala upravená lzw funkce, která zpracovává soubor?

Megaloman:

Co místo Huffmana použít před samotným LZW Burrows-Wheelerovu transformaci? Tím by se dosáhlo lepšího kompresního poměru a implementace BWT v PHP není nijak složitá.

ikona PeTaX:

Trochu mi, Jakube, uniká smysl ekvivalence v řádku použití dekompresní fce
<?php
var_dump
($data = lzw_decode(lzw_codes($compressed)));
?>
Asi tam má být přiřazení, ne?

ikona Jakub Vrána OpenID:

Ne. Ekvivalence v příkladu ověřuje, zda jsme dostali stejná data, která jsme komprimovali.

V normálním kódu by samozřejmě přiřazení bylo.

ikona PeTaX:

Jasně, true jako výstup ověření je OK. Já to pochopil jako podivně napsaný produkční výstup.

Jirka:

Zkouším zkomprimovat UTF-8 text a hlásí mi to:
Notice: Uninitialized string offset: 12 in C:\xampp\htdocs\cskr\tridy\lzw.php on line 19

Notice: Uninitialized string offset: 32 in C:\xampp\htdocs\cskr\tridy\lzw.php on line 19

Notice: Uninitialized string offset: 50 in C:\xampp\htdocs\cskr\tridy\lzw.php on line 19

Notice: Uninitialized string offset: 0 in C:\xampp\htdocs\cskr\tridy\lzw.php on line 19

Dá se to nějak vyřešit?

ikona Jakub Vrána OpenID:

Ano, vypnutím E_NOTICE nebo úpravou funkce. Příklady na tomto blogu jsou psané s vypnutými E_NOTICE, protože je to zpřehledňuje.

Používejte diakritiku. Vstup se chápe jako čistý text, ale URL budou převedeny na odkazy a PHP kód uzavřený do <?php ?> bude zvýrazněn. Pokud máte dotaz, který nesouvisí s článkem, zkuste raději diskusi o PHP, zde se odpovědi pravděpodobně nedočkáte.

Jméno: URL: Reakce na: Jakub Vrána

avatar © 2005-2018 Jakub Vrána. Publikované texty můžete přetiskovat pouze se svolením autora. Ukázky kódu smíte používat s uvedením autora a URL tohoto webu bez dalších omezení Creative Commons. Můžeme si tykat. Skripty předpokládají nastavení: magic_quotes_gpc=Off, magic_quotes_runtime=Off, error_reporting=E_ALL & ~E_NOTICE a očekávají předchozí zavolání mysql_set_charset. Skripty by měly být funkční v PHP >= 4.3 a PHP >= 5.0.