Come ordinare i suffissi dell'array nell'ordinamento a blocchi

Question

Sto leggendo l'algoritmo di ordinamento del blocco dalle tane e dalla carta Wheeler. Questo è un passo dell'algoritmo:

Supponiamo S = Abracadabra

Inizializza un array w di n parole w [0, ..., n - 1], tale che W [i] contiene i personaggi s '[i, ..., i + k - 1] disposti in modo che i numeri interi si confrontano Le parole sono d'accordo con i confronti lessicografici sulle corde del personaggio K. L'imballaggio dei caratteri in parole ha due vantaggi: consente di confrontare due prefissi alla volta utilizzando gli accessi alla memoria allineati e consente di eliminare molti casi lenti

(Nota: S' è l'originale S con k EOF I caratteri aggiunti ad esso, K è il numero di caratteri che si adattano a una parola (sono in una macchina da 32 bit, quindi k=4)

EOF = '$'

Correggimi se sbaglio:

S'= abracadabra$$$$  
W= abra brac raca acad cada adab dabr abra bra$ ra$$ a$$$

Quindi, l'algoritmo dice che devi ordinare la matrice di suffissi di S (nominato v), di indicizzazione nell'array W.

Non capisco perfettamente come puoi ordinare i suffissi indicizzandoti W. Ad esempio: ad un certo punto dell'ordinamento, supponiamo di ottenere due suffissi, i e j, e devi confrontarli. Dato che stai indicizzando W, stai controllando 4 caratteri in quel momento.
Supponiamo che abbiano entrambi gli stessi primi 4 caratteri. Quindi, dovresti controllare, per ogni suffisso i loro prossimi 4 caratteri, e lo fai accedendo alla 4a posizione di ogni suffisso in W. È giusto? Questo "imballare i personaggi a parole" accelera davvero le cose?

Answer 1

Il modo in cui lo descrivi nella domanda è del tutto accurato. E sì, accelera le cose perché, come hai detto, confronta quattro personaggi alla volta.

Ci sono due osservazioni da fare, però:

1. Quando confronti i suffissi I e J, come nel tuo esempio, si confrontano davvero le voci w [i] e W [j]. Il risultato di questo è lo stesso che se avessi lessicograficamente il quadruplo dei personaggi S [i..i+3] e S [J..J+3], quindi hai risparmiato il tempo di calcolo equivalente a tre confronti dei caratteri. E sì, se il risultato indica che i due quadrupli sono identici, devi continuare a confrontare W [I+1] e W [J+1], però: Non lo fai subito. Il modo in cui funziona il loro algoritmo è quello di un tipo di radix. Cioè, metti i suffissi in secchi subito dopo il confronto iniziale (forse entrambi nello stesso secchio), quindi ordina internamente i secchi, in modo ricorsivo.
2. L'algoritmo descritto nel documento originale da Burrows e Wheeler (da cui si cita; c'è una copia qui Ad esempio), che è del 1994, non è l'algoritmo di costruzione dell'array suffisso ottimale. In primo luogo, nel 2003 sono stati scoperti diversi metodi di costruzione di O (N); In secondo luogo, da allora, sono stati apportati molti ulteriori miglioramenti all'implementazione. Il nucleo del documento del 1994 è l'idea di usare la trasformazione di Burrows-Wheeler come base per la compressione delle stringhe, non nel modo esatto in cui viene generata la trasformazione stessa.

Answer 2

The array V is not a suffix array, but an array of indices into W. Once the sorting is complete, V should hold indices into W such that if

V[i] <= V[j]

poi

 W[V[i]] <= W[V[j]].

Spero di averlo detto bene :) Avere esattamente la corrispondenza non è un problema e uno dei due ordini va bene. Il punto è che quando si applica la trasformazione inversa è necessario essere in grado di recuperare W per recuperare la stringa originale e elementi identici di W non causano un problema.