LZW komprese

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, http://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, http://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, http://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, http://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: 17 (nové: 0)

Diskuse

Šedě jsou podbarveny příspěvky, které jste už viděli.

Navigace

PHP triky

• Archiv (597)
• Stažení celého webu
• RSS, Atom, Atom diskusí
• O autorovi, o webu, Twitter

Kupte si mou knihu

Nabídka pracovních pozic

• Přidejte vlastní pracovní nabídku

Reklama

• Hledáte-li programátora nebo naopak sami programujete a nemáte do čeho píchnout, využijte služeb portálu nezávislých profesionálů Na volné noze.
• Český hosting
• HostMonster – neomezený hosting

Články podle skupin

• Dobře míněné rady (94)
• Řešení problému (142)
• Výuka (94)
• Seznámení s oblastí (84)
• Ze zákulisí (69)
• Školení (29)
• Verze PHP (8)
• Osobní (38)
• Adminer (39)

Výběr článků

• Traverzování kolem stromu prakticky
• Vlastní pořadí řádků v tabulce
• Ukázka použití indexů
• Struktura stránek
• Unikátnost návštěvníka
• Vyhledávání v JavaScriptu
• Kontrola e-mailové adresy
• Vytvoření přátelského URL
• HTTP cachování
• Atomicita operací
• Vypnutí magic_quotes_gpc
• Ukládání souborů od uživatele
• Cross Site Scripting
• AJAX
• Přihlašování uživatelů
• MySQL 4.1 – kódování
• Vzájemné propojení souborů
• Diskuse s reakcemi
• Šablony
• HTTP metody GET a POST
• Escapování
• Ukládání hesel
• Využití unikátních klíčů v databázi
• Obrana proti SQL Injection

Nejnovější články

• Common Mistakes in Securing Web Applications
• Představuji nové školitele
• WebExpo 2011
• Transakce v reálném světě
• Záměna proměnných v řetězci

Normy a manuály

• PHP
• MySQL
• HTTP
• Apache
• HTML, XHTML
• JavaScript

Další projekty

• Adminer
• NotORM
• JavaScript Syntax Highlighter
• php-initialized
• Ve Facebooku
• Čtyřka