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

Move-to-front

Základní informace

  • metoda použitá v Burrowsově-Wheelerově transformaci
  • data nekomprimuje, ale pomáhá snižovat redundanci
  • využívá zásobník

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

Časová složitost algoritmu: O(n)
Paměťová složitost algoritmu: O(|Σ|)

Popis

Metoda spočívá v uložení vstupní abecedy na zásobník a využití indexů jednotlivých položek. Při každém použití položky, je tato přesunuta na začátek zásobníku (bude mít index 0) a ostatní indexy se přepočítají tak, aby byla zachována souvislost řady indexů.

Pseudokód


 1:  begin 
 2:     vlož všechny symboly abecedy na zásobník 
 3:     while (!EOF) do
 4:      begin
 5:        output(pozice symbolu v zásobníku)
 6:        přesuň symbol na začátek zásobníku
 7:      end
 8:  end

Odkazy

  1. David Hoksza: Burrows-Wheelerova transformace. Reboot.cz.
  2. Arturo San Emeterio Campos: Move to front.

Ukázka