English
předchozí hlavní stránka obsah další

Burrows-Wheelerova transformace

Základní informace

  • Hlavní využití má zejména při zpracování obrázků, hudby a textu.
  • Oproti jiným metodám pracuje v blokovém režimu, proto ji lze najít i pod názvem block-sorting.
  • Je použita v kompresním algoritmu bzip2.

Časová a paměťová složitost algoritmu

Časová složitost třídění je O(n.log(n)). Při použití metody Suffix Array O(n).

Historie

Metoda byla navržena Michaelem Burrowsem a Davidem Wheelerem, 1994.

Popis

Burrows-Wheelerova transformace pracuje v blokovém režimu. Čteme tedy ze vstupu bloky textu o předem definované velikosti a každý zpracováváme samostatně.

Nejprve provedeme všechny cyklické rotace vstupního textu (zde vlevo), které očíslujeme. Výsledné fráze potom lexikograficky seřadíme a zapamatujeme si číslo řádku, na kterém je původní řetězec vstupního textu. Ze všech lexikograficky seřazených frází vybereme postupně poslední znak a sestavíme řetězec L, resp. vybereme poslední sloupec (L = Last) máme-li fráze sepsány od sebou.

Při kódování dále aplikujeme na řetězec L postupně metody Move To Front a Huffmanovo kódování. Dále lze ještě aplikovat metodu RLE, apod. Při dekódování použijeme metody v opačném pořadí a získáme zpět řetězec L a hodnotu I.

Dekódování názorně provedeme tak, že řetězec L sepíšeme do sloupce a očíslujeme jednotlivé symboly. Dále vytvoříme sloupce F (First) a T.

Ze sloupce L postupně vybíráme vždy nezpracovaný, lexikograficky nejmenší a v pořadí první symbol L[i]. Umístíme jej na první volnou pozici ve sloupci F a do sloupce T na pozici T[i] zaznamenáme číslo jeho pozice ve sloupci F. To provedeme postupně pro všechny symboly z řetězce L.

V dalším kroku nastavíme index řádku i na hodnotu I. Pak symbol L[i] umístíme na začátek výstupního řetězce a předjdeme na řádek s indexem T[i], to opakujeme dokud je délka výstupního řetězce menší než délka řetězce L, resp. dokud není index řádku i znovu roven hodnotě I.

Pseudokód


 1:  kodovani :
 2:  begin
 3:    provedeme vsechny cyklicke rotace vstupu (fraze zacina zvyraznenym symbolem)
 4:     ziskane fraze ocislujeme
 5:     fraze lexikograficky seradime s vyuzitim suffix array SA a zaznamename koncove 
 6:       symboly jednotlivych frazi L[i]
 7:     zapamatujeme si na kolikate pozici je vstupni fraze I po setrideni
 8:     retezec L nyni zakodujeme metodou Move To Front nad abecedou A
 9:     vystupem metody Move To Front je posloupnost cisel C
10:     urcime cetnosti vyskytu N cisel v posloupnosti C
11:     cislum priradime kodova slova pomoci Huffmanova kodovani
12:     output(vse Fibonacciho kodem radu 2 - hodnotu I)
13:     output(pocet cisel (symbolu) v Huffmanove strome)
14:     output(vsechna kodovana cisla)
15:     output(Huffmanuv strom)
16:     output(posloupnost C)
17:  end
18:
19:  dekodovani :
20:  begin
21:     precteme hodnotu I
22:     cteme pocet kodovanych cisel v Huffmanove strome
23:     cteme kodovana cisla
24:     zrekonstruujeme kodova slova Huffmanova kodovani
25:     dekodujeme puvodni posloupnost C
26:     metodou Move To Front zpetne ziskame retezec L
27:     sepiseme sloupec L (Last) a ocislujeme radky
28:     while (mame nezpracovane symboly v L) do
29:      begin
30:        z L vybereme lexikograficky serazeno v poradi prvni nezpracovany symbol L[i]
31:        vlozime ho na nasledujici volnou pozici ve sloupci F (First) a v T[i] ulozime
32:          jeho index ve sloupci F
33:      end
34:     vybereme radek i = I
35:     while (delka vystupu < delka retezce L) do
36:      begin
37:        symbol L[i] dame na zacatek vystupniho retezce
38:        v dalsim kroku budeme zpracovavat radek s indexem T[i]
39:      end
40:  end

Odkazy

  1. M. Burrows and D. Wheeler: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994.
  2. Burrows-Wheeler Transform. Wikipedia, the free encyclopedia.

Ukázka