Comment faire pour trier suffixes tableau dans le tri des blocs

Question

Je lis l'algorithme de tri de blocs de Burrows et du papier Wheeler. Cette étape de l'algorithme:

Supposons que S = abracadabra

Initialiser une matrice W de N mots de P [0, ..., N - 1], de telle sorte que W [i] contient les caractères S '[i, ..., i + k - 1] agencés de sorte que les comparaisons entières sur les mots sont d'accord avec des comparaisons lexicographiques sur les chaînes k caractères. caractères d'emballage en mots a deux avantages: Il permet à deux préfixes à comparer k octets à la fois en utilisant des accès mémoire alignés, et il permet de nombreux cas lents à éliminer

(Note: S' est le S d'origine avec des caractères k EOF annexée, k étant le nombre de caractères qui correspondent à un mot de la machine (je suis dans une machine 32 bits, donc k=4)

EOF = '$'

moi si je me trompe:

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

Ensuite, l'algorithme dit que vous devez trier le tableau de suffixe S (nommé V), par indexation en le tableau W .

Je ne comprends pas bien comment pouvez-vous trier par l'indexation suffixes dans W. Par exemple: à un moment donné du tri, supposons que vous obtenez deux suffixes, i et j, et vous devez les comparer. Puisque vous indexez dans W, vous vérifiez 4 caractères à l'époque.
Supposons qu'ils ont tous deux les mêmes 4 premiers caractères. Ensuite, vous devez vérifier, pour chaque suffixe leurs 4 caractères suivants, et vous le faites en accédant à partir de la 4ème position de chaque suffixe dans W. Est-ce correct? Est-ce « caractères d'emballage en mots » choses vraiment à accélérer?

Answer 1

La façon dont vous décrivez la question est tout à fait exact. Et oui, il accélère les choses parce que, comme vous l'avez dit, il compare quatre caractères à la fois.

Il y a deux remarques à faire, bien que:

1. Lorsque vous comparez i et j suffixes, comme dans votre exemple, vous comparez les entrées W [i] et W [j] En effet. Le résultat de ceci est le même que si vous aviez lexicographique comparé le quadruple des personnages [de i..i + 3] et S [j..j + 3], de sorte que vous avez enregistré le temps de calcul équivalent à trois comparaisons de caractères. Et oui, si le résultat indique que les deux quadruplets sont identiques, vous devez continuer à comparer W [i + 1] et W [j + 1], mais : Vous ne le faites pas tout de suite . La façon dont leur algorithme fonctionne est celui d'une sorte de radix. Autrement dit, vous mettez les suffixes dans des seaux à droite après la première comparaison (peut-être à la fois dans le même seau), puis en interne sorte les seaux, récursive.
2. L'algorithme décrit dans le document original par Burrows et Wheeler (à partir de laquelle vous citez, il y a une copie par exemple), qui est de 1994, n'est pas l'algorithme de construction de tableau de suffixe optimal. Tout d'abord, en 2003, plusieurs O (N), ont été découverts les méthodes de construction directe; d'autre part, depuis lors, de nombreuses autres améliorations à la mise en œuvre ont été faites. Le cœur du document de 1994 est l'idée d'utiliser les Burrows-Wheeler transformer comme base pour la compression de chaîne, pas la manière exacte est généré lui-même transformée.

Answer 2

Le tableau V n'est pas un tableau de suffixe, mais un tableau d'indices en W. Une fois le tri terminé, V devrait tenir des indices en W de telle sorte que si

V[i] <= V[j]

puis

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

J'espère que je l'ai dit ce droit :) Après les avoir EXACTEMENT match pas un problème et un ordre est très bien. Le point est que lorsque vous appliquez la transformation inverse vous devez être en mesure de récupérer W afin de récupérer la chaîne d'origine, et des éléments identiques de W ne va causer un problème.