> mtf | move | front <
// Move-to-Front - Riordino dinamico della lista per una migliore compressione
Auto-adattivo
Si adatta automaticamente ai pattern locali nei dati.
Sfrutta la località
I simboli recenti ricevono indici più piccoli per una migliore compressione.
Parte di bzip2
Usato dopo BWT nella pipeline di compressione di bzip2.
>> informazioni tecniche
Come funziona MTF:
MTF mantiene una lista di tutti i simboli possibili. Quando si codifica un simbolo, si emette la sua posizione corrente nella lista e poi lo si sposta in testa. In questo modo i simboli usati spesso hanno indici piccoli, che si comprimono meglio con la codifica entropica successiva.
Esempio di codifica:
Testo: "banana" Lista iniziale: [a,b,c,d,...] "b": indice 1, sposta b→fronte [b,a,c,d,...] "a": indice 1, sposta a→fronte [a,b,c,d,...] "n": indice 13, sposta n→fronte [n,a,b,c,...] "a": indice 1, sposta a→fronte [a,n,b,c,...] "n": indice 1, sposta n→fronte [n,a,b,c,...] "a": indice 1, sposta a→fronte [a,n,b,c,...] Output: [1,1,13,1,1,1]
Perché usare MTF:
- >Migliora la ridondanza locale
- >Funziona con BWT
- >Implementazione semplice
- >Trasformazione reversibile
- >Si adatta ai pattern
>> domande frequenti
Che cos’è la codifica Move-to-Front?
MTF è un algoritmo di trasformazione dei dati che codifica ogni simbolo come il suo indice in una lista aggiornata dinamicamente. Dopo la codifica, il simbolo viene spostato in testa alla lista, così i simboli usati di frequente hanno indici più piccoli.
Perché usare MTF insieme a BWT?
BWT raggruppa contesti simili e crea ripetizioni locali. MTF trasforma queste ripetizioni in numeri piccoli (molti 0 e 1), che si comprimono molto bene con codifica run-length o Huffman.
Come funziona la lista in MTF?
La lista inizia con tutti i 256 possibili valori di byte in ordine. Man mano che i simboli vengono codificati, quelli usati vengono spostati in testa. I simboli usati di recente rimangono vicino al fronte con indici piccoli, mentre quelli non usati migrano verso indici maggiori.
MTF rispetto ad altre trasformazioni?
MTF è progettato specificamente per essere usato dopo BWT. Da solo non è molto efficace, ma è ottimo per trasformare l’output di BWT in una forma che si comprime facilmente. È più semplice della codifica aritmetica ma meno ottimale.
// Esempio svolto
| # | Symbol | Index | List |
|---|---|---|---|
| 1 | b | 1 | abcdefg… |
| 2 | a | 1 | bacdefg… |
| 3 | n | 13 | abcdefg… |
| 4 | a | 1 | nabcdef… |
| 5 | n | 1 | anbcdef… |
| 6 | a | 1 | nabcdef… |
// Esempi di codice
Input banana initial list: a b c d ... z (index from 0)
Output 1 1 13 1 1 1
Encode output the index of the symbol, then move it to the front
Decode read index, output list[index], move it to the front
Use after BWT: runs of equal symbols become runs of 0s,
which RLE and Huffman/arithmetic coding then compress well (bzip2)
>> Altre domande
D: A cosa serve Move-to-Front?
R: MTF non è compressione in sé ma una trasformazione: i simboli recenti ricevono indici piccoli. Ne risultano molti 0 e 1, che un codificatore entropico (Huffman, aritmetico) comprime bene.
D: Che rapporto ha con la trasformata di Burrows-Wheeler?
R: La BWT raggruppa i caratteri uguali in sequenze. MTF le trasforma in numeri piccoli, soprattutto 0. La catena BWT → MTF → RLE → Huffman è quella di bzip2.
D: MTF è senza perdita e reversibile?
R: Sì. Il decodificatore parte dalla stessa lista iniziale e segue gli stessi spostamenti. La lista iniziale (alfabeto e ordine) deve essere identica su entrambi i lati.