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
- David Hoksza: Burrows-Wheelerova transformace. Reboot.cz.
- Arturo San Emeterio Campos: Move to front.