> 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.