> bwt | trasforma | comprimi <
// Burrows-Wheeler Transform - trasformazione di testo reversibile per migliorare la compressione
>> funzionalità
Completamente reversibile
Trasformazione senza perdita che può essere invertita in modo esatto.
Raggruppamento dei caratteri
Raggruppa caratteri simili per migliorare la compressione nelle fasi successive.
Cuore di bzip2
Base di molti algoritmi di compressione basati su bzip2.
>> informazioni tecniche
Come funziona BWT
La trasformata di Burrows-Wheeler genera tutte le rotazioni cicliche della stringa di input, le ordina lessicograficamente e restituisce l ultima colonna della matrice ordinata insieme all indice della stringa originale. Questa trasformazione tende a raggruppare i caratteri simili, rendendo l output molto comprimibile con RLE, Move-to-Front e altri codificatori entropici.
Esempio BWT
Input: "banana$" Rotations: 0: banana$ 1: anana$b 2: nana$ba 3: ana$ban 4: na$bana 5: a$banan 6: $banana Sorted: 0: $banana 1: a$banan 2: ana$ban 3: anana$b 4: banana$ 5: na$bana 6: nana$ba Last column: annb$aa Original index: 4 Output: annb$aa|4
Perché usare BWT
- Migliora la comprimibilità dei dati
- È completamente reversibile
- Raggruppa contesti simili
- Base dell algoritmo di compressione bzip2
- Preprocessing efficace per altri codificatori
>> domande frequenti
Che cos è la trasformata di Burrows-Wheeler?
La trasformata di Burrows-Wheeler (BWT) è un algoritmo reversibile che riordina una stringa di caratteri per produrre sequenze con molte ripetizioni. Proposta da Michael Burrows e David Wheeler nel 1994, è usata come fase di pre-elaborazione in compressori come bzip2 per ottenere rapporti di compressione migliori.
Perché BWT migliora la compressione?
BWT raggruppa i caratteri che compaiono in contesti simili, così molte occorrenze dello stesso simbolo finiscono vicine nell output. Queste sequenze si comprimono molto bene con codifica run-length, trasformata Move-to-Front e codificatori entropici come Huffman.
Che cos è il marcatore EOF?
Il marcatore EOF (End Of File), di solito il simbolo '$' o un altro carattere univoco, garantisce che tutte le rotazioni siano distinte e permette di recuperare la posizione della stringa originale. Senza questo marcatore alcune stringhe non avrebbero una rappresentazione univoca. Durante la trasformazione inversa il marcatore viene rimosso.
BWT comprime da sola?
No. BWT non è un algoritmo di compressione completo, ma una trasformazione che rende i dati più facili da comprimere. In schemi come bzip2 viene combinata con Move-to-Front, RLE e codifica di Huffman.