Problema G - The Burrow Wheeler Transform

Autor: Paul Crocker e Simão Sousa (Universidade da Beira Interior)
Tipo de problema: Cifra/Ordenação/Ad-Hoc

A transformação de Burrows-Wheeler, também conhecida como "block-sorting compression" é uma técnica clássica usada em muitos conhecidos algoritmos de compressão. À primeira vista, não parece completamente óbvio que se consiga fazer a transformação inversa, mas tal é perfeitamente possível.

Consideremos o exemplo de input, onde é dado "rdarcaaaabb 2". Se começarmos por ordenar as letras, conseguimos saber a primeira coluna da tabela ordenada de rotações da palavra (a última coluna é o input, e 2 é a posição da palavra, também dada no input). 

0  a.........r
1  a.........d
2  a.........a -> palavra original
3  a.........r
4  a.........c
5  b.........a
6  b.........a
7  c.........a
8  d.........a
9  r.........b
10 r.........b

Seja next[i]=j se i é uma linha da tabela e j é a linha que corresponde à rotação seguinte na palavra original.

Como as entradas da tabela correspondem a rotações da palavra, sabemos a seguir à última letra de uma linha vem a letra do início da mesma linha. Isto permite-nos inferir relações. Por exemplo, como só existe um 'c' na palavra, então next[7]=4, pois 'c' é o primeiro caracter da linha 7 e a única linha que termina em 'c' é a linha 4. Mas o que acontece quando os caracteres não são únicos?

Felizmente, não existe ambiguidade. Mesmo possa não ser muito intuitivo, a verdade é que todas as linhas que terminam com um mesmo caracter estão também ordenadas! Ou seja, a primeira linha que começa com a letra 'a', tem como next a primeira linha que termina em 'a', e por aí adiante. Porquê? Precisamente porque a tabela tem as linhas ordenadas. Para perceber melhor veja a seguinte tabela "completa": 

i               NEXT[i]
0  aabracadabr   2
1  abraabracad   5
2  abracadabra   6
3  acadabraabr   7
4  adabraabrac   8
5  braabracada   9
6  bracadabraa   10
7  cadabraabra   4
8  dabraabraca   1
9  raabracadab   0
10 racadabraab   3

Tendo next[i] calculado, passa a ser trivial reproduzir a palavra original, bastando começar na linha dada no input e seguindo os next[i] respectivos.

Ligações interessantes: