Perché usare l'ultima colonna di Burrows-Wheeler-Transform

Question

Perché usare l'ultima colonna di Burrows-Wheeler-Transform

#1 da (3 voti)

2

La Trasformazione di Burrows-Wheeler prende una stringa di lunghezza n, crea una matrice con n righe spostando questa stringa di una posizione a sinistra per ogni riga. Quindi le righe vengono ordinate in base alla prima colonna in ordine lessicografico. Quindi verrà inviata l'ultima colonna.

Perché prendere l'ultima colonna? Su Wikipedia c'è un esempio con la stringa "^ BANANA |". Dopo aver ordinato la prima colonna è "AAABNN ^ |" e l'ultima colonna è "BNN ^ AA | A". Usando la codifica run length sarebbe meglio usare la prima colonna a causa di "AAA". Allora, dove sono i vantaggi nel prendere l'ultima colonna?

algorithms compression

posta ooorndtski 03.04.2016 - 22:26

fonte

1 risposta

Leggi altre domande sui tag algorithms compression

Command Pattern - Uso corretto? Eliminazione automatica dell'account utente quando si utilizza OAuth2

score 3 · Accepted Answer

La proprietà chiave di Burrows-Wheeler-Transform che lo rende utile è che è reversibile , senza memorizzare alcun metadato su ciò che ha fatto la trasformazione.

Se scegli semplicemente "AAABNN ^ |" perché comprime meglio delle altre colonne, invece di usare una regola consistente come "seleziona sempre l'ultima colonna", quindi quando arriva il momento di invertire la procedura, non avresti modo di sapere se la stringa originale era "^ BANANA |" o "^ AAABNN |" o "^ BAANAN |" o qualcosa di completamente diverso. In effetti, se tutto ciò che si vuole fare è riorganizzare le lettere per ottenere la massima compressibilità, semplicemente l'ordinamento delle lettere è una soluzione molto più efficace. Ma in realtà stai creando un algoritmo di compressione irreversibile e la compressione è generalmente considerata abbastanza inutile se non c'è modo di decomprimere i dati in seguito.