Czestina TNT's HomePage Algoritmy komprese dat

Block Sorting

Klíčová slova: lossless compression, block sorting, Burrows-Wheeler

Reference:

Jinak řečeno Burrows--Wheelerova transformace. Jde o metodu popsanou v článku A block-sorting lossless data compression algorithm z roku 1994. Na této kompresní metodě je založen i populární bzip2.

Komprese

Mějme nějaký blok dat, například řetězec abracadabra, nejprve vytvoříme čtvercovou matici obsahující všechna cyklická posunutí daného řetězce a její jednotlivé řádky lexikograficky setřídíme, tedy:
   0   a a b r a c a d a b r
   1   a b r a a b r a c a d
   2   a b r a c a d a b r a   <-
   3   a c a d a b r a a b r
   4   a d a b r a a b r a c
   5   b r a a b r a c a d a
   6   b r a c a d a b r a a
   7   c a d a b r a a b r a
   8   d a b r a a b r a c a
   9   r a a b r a c a d a b
  10   r a c a d a b r a a b
Alespoň jeden řádek této matice obsahuje původní řetězec, zapamatujeme si tedy číslo řádku jeho prvního výskytu (zde 2) a také celý poslední sloupec. Výsledkem transformace tedy je dvojice < I, L>, v našem příkladě < 2, "rdarcaaaabb" >.

Dekomprese

Postup dekomprese lze snadno odhadnout z pustupu komprese. Máme tedy řetězec L a číslo řádku I v původní matici. Víme také, že jednotlivé řádky matice jsou setříděny. Tedy:
   0   a . . . . . . . . . r
   1   a . . . . . . . . . d
   2   a . . . . . . . . . a   <-
   3   a . . . . . . . . . r
   4   a . . . . . . . . . c
   5   b . . . . . . . . . a
   6   b . . . . . . . . . a
   7   c . . . . . . . . . a
   8   d . . . . . . . . . a
   9   r . . . . . . . . . b
  10   r . . . . . . . . . b
Např. z 2. řádku vidíme, že po d následuje a, z 1. a 4. řádku pak, že po r následuje a nebo a apod. Máme tedy všechny dvouznakové podřetězce, tzn. po jejich setřídění první dva znaky všech řádků:
   0   a a . . . . . . . . r
   1   a b . . . . . . . . d
   2   a b . . . . . . . . a   <-
   3   a c . . . . . . . . r
   4   a d . . . . . . . . c
   5   b r . . . . . . . . a
   6   b r . . . . . . . . a
   7   c a . . . . . . . . a
   8   d a . . . . . . . . a
   9   r a . . . . . . . . b
  10   r a . . . . . . . . b
Nyní např. z 1. řádku vidíme, že po da následuje b, takto vidíme všechny trojice znaků původního řetězce, jejich setříděním dostáváme další sloupec atd. Takto můžeme snadno rekonstruovat původní matici a na I. tém řádku přečíst původní text.

Proč to dělat

Uvedenou transformací dostáváme z původního řetězce délky n jiný řetězec stejné délky a navíc ještě číslo z množiny Zn. V našem příkladě tedy "rdarcaaaabb" a číslo 2. Takový řetězec pak můžeme úspěšně kódovat algoritmem MFR, protože často obsahuje stejné znaky blízko sebe:
       abcdr
   r   rabcd   4
   d   drabc   4
   a   adrbc   2
   r   radbc   2
   c   cradb   4
   a   acrdb   2
   a   acrdb   0
   a   acrdb   0
   a   acrdb   0
   b   bacrd   4
   b   bacrd   0
Tedy speciálně pro abecedu {a, b, c, d, r} dostaneme kód 44224200040. Výhoda transformace se podstatně projeví pro větší bloky textu, na kterých se již projevují statistické vlastnosti jazyka. V praxi se používají bloky o velikosti několika set kilobytů (100-900 KB pro bzip2).
Last change Mon Dec 2 2002 by TNT