Trasformatore Burrows-Wheeler senza carattere EOF

Question

Ho bisogno di eseguire una ben nota trasformazione Burrows-Wheeler in tempo lineare. Ho trovato una soluzione con l'ordinamento dei suffissi e il carattere EOF, ma l'aggiunta di EOF modifica la trasformazione. Ad esempio: considerare la stringa bcababa e due rotazioni

• s1 = abababc
• S2 = ababcab

è chiaro che s1 < s2. Ora, con un carattere EOF:

• s1 = Abeba # bc
• s2 = aba # BCAB

e ora s2 < s1. E la trasformazione risultante sarà diversa. Come posso eseguire BWT senza EOF?

Answer 1

È necessario il carattere EOF nella stringa affinché BWT funzioni, altrimenti non è possibile eseguire la trasformazione inversa per ripristinare la stringa originale. Senza EOF, entrambe le stringhe "ba" e "ab" hanno la stessa versione trasformata ("ba"). Con EOF, le trasformazioni sono diverse

ab  ba 

a b |  a | b 
b | a  b a | 
| a b  | b a 

cioè ab si trasforma in "| ab" e ba a "B | a".

EOF è necessario per BWT perché segna il punto in cui inizia il ciclo di caratteri.

Re: farlo senza il carattere EOF, secondo Wikipedia,

Dal momento che ogni rotazione della stringa di input porterà alla stessa stringa trasformato, il BWT non può essere invertita senza l'aggiunta di un 'EOF' marker all'ingresso o, aumentando l'output con informazioni, come come un indice, che consente di identificare la stringa di input da la classe di tutte le sue rotazioni.

Esiste una versione biiettiva della trasformazione, con la quale la stringa trasformata identifica univocamente l'originale. In questa versione, ogni stringa ha un inverso univoco della stessa lunghezza.

La trasformazione biiettiva viene calcolata calcolando innanzitutto l'input in una sequenza non crescente di parole di Lyndon; tale fattorizzazione esiste dal teorema Chen-Fox-Lyndon e può essere trovata in tempo lineare. Quindi, l'algoritmo ordina insieme tutte le rotazioni di tutte queste parole ; come nella consueta trasformazione Burrows-Wheeler, questo produce una sequenza ordinata di n stringhe . La stringa trasformata viene quindi ottenuta selezionando il carattere finale di ciascuna di queste stringhe in questo elenco ordinato .

Answer 2

È possibile eseguire la trasformazione in tempo e spazio lineari senza il carattere EOF calcolando l'array di suffissi della stringa concatenata con se stesso. Quindi scorrere l'array di suffissi.Se il valore dell'array di suffissi corrente è inferiore a n, aggiungere all'array di output l'ultimo carattere della rotazione che inizia alla posizione indicata dal valore corrente nell'array di suffissi. Questo approccio produrrà un risultato di trasformazione BWT leggermente diverso, tuttavia, poiché le rotazioni delle stringhe non sono ordinate come se fosse presente il carattere EOF.

Una descrizione più approfondita può essere trovato qui: http://www.quora.com/Algorithms/How-I-can-optimize-burrows-wheeler-transform-and-inverse-transform-to-work-in-O-n-time-O-n-space

Answer 3

So che questo thread è piuttosto vecchio, ma ho avuto lo stesso problema e si avvicinò con la seguente soluzione:

• Trova la corda minimi lessicografico rotazione e salvataggio dell'offset (necessario per invertire) (utilizzo la fattorizzazione lydon)
• Utilizzare i normali algoritmi di bwt sulla stringa ruotata (questo produce l'output corretto perché tutti gli algos asume che la stringa sia seguita dal carattere lessicograficamente minimo)
• Per invertire: unbwt utilizzando per es. ricerca all'indietro a partire dall'indice 0 e scrivere il carattere corrosivo sull'offset salvato