Tableau de suffixe complet

Question

Un tableau de suffixe indexera tous les suffixes pour une liste donnée de chaînes, mais que se passe-t-il si vous essayez d'indexer toutes les sous-chaînes uniques possibles? Je suis un peu nouveau à ce sujet, alors voici un exemple de ce que je veux dire:

Étant donné la chaîne

abcd

Un suffixe index de tableau (au moins à ma compréhension)

(abcd,bcd,cd,d)

Je voudrais indexer (toutes les sous-chaînes)

(abcd,bcd,cd,d,abc,bc,c,ab,b,a)

Un tableau de suffixe est-il ce que je recherche? Si oui, que dois-je faire pour que toutes les sous-chaînes soient indexées? Sinon, où devrais-je chercher? Aussi à quoi serais-je Google pour contraster "toutes les sous-détrages" vs "Suffix Substrations"?

Answer 1

Le tableau de suffixe fait déjà ce dont vous avez besoin, car chaque sous-chaîne est un préfixe de l'un des suffixes. Plus précisément, compte tenu de votre tableau de suffixe

ABCD BCD CD D

Et supposons que vous recherchez une sous-chaîne "BC", alors vous pouvez le constater en recherchant tous les suffixes qui commencent par "BC" (il n'y en a qu'un dans ce cas, "BCD"). Étant donné qu'un tableau de suffixe est trié lexicographiquement, trouver tous les suffixes qui partagent un certain préfixe correspond à une recherche binaire à travers le tableau de suffixe, et le résultat sera une gamme continue d'entrées du tableau de suffixe.

Cependant, il existe des méthodes de recherche optimisées en utilisant le tableau de suffixe combiné avec des structures de données auxiliaires, telles que le tableau LCP (préfixe le plus long-commun) ou les arbres en ondelettes. Voir le sondage de Navarro 2007 pour une description de ces méthodes (doi 10.1145 / 1216370.1216372).

Pour prendre en compte les commentaires faits ci-dessous, je suggère de combiner chaque suffixe avec le nombre de substations qu'il représente. Dans un exemple simple comme ce qui précède

4 abcd
3 bcd
2 bc
1 d

Parce que, par exemple, le premier suffixe "ABCD" représente les 4 sous-chaînes "A", "AB", "ABC", "ABCD". Cependant, dans un exemple plus complexe, par exemple pour la chaîne "Abcabxdabe", les deux premières entrées du tableau de suffixe seraient

10 abcabxdabe
1 abe

Parce que la deuxième entrée représente les sous-chaînes "a", "ab" et "abe", mais "a" et "ab" sont également représentés par la première entrée.

Comment calculer le nombre de sous-chaînes qu'une entrée représente? -> la longueur du suffixe moins la longueur du préfixe le plus long qu'il a en commun avec le suffixe précédent. Par exemple, dans l'exemple "Abe", c'est-à-dire 3 (sa longueur) moins 2 (la longueur de "AB", le préfixe le plus long qu'il partage avec l'entrée précédente). Ainsi, ces nombres peuvent être générés en un seul passage sur le tableau de suffixe, et encore plus rapidement si vous avez également généré le tableau LCP (préfixe le plus long-commun).

L'étape suivante serait de générer des comptes accumulés:

10 abcabxdabe
11 abe
16 abxdabe
...

puis trouver un moyen efficace d'utiliser les dénombrements accumulés. Par exemple, si vous voulez obtenir le 13e sous-chaîne lexicogramme, vous devez trouver la première entrée qui a un nombre accumulé supérieur ou égal à 13. Ce serait "16 abxdabe" ci-dessus. Retirez ensuite le préfixe qu'il partage avec l'entrée précédente (donne "XDABE"), puis sautez à la position après le 2ème caractère (car l'entrée précédente a accumulé le comte 11 et 13-11 == 2), donc vous obtenez " ABXD "comme la 13e sous-chaîne lexicographique.

Answer 2

Comme il a déjà été répondu, les sous-chaînes sont des préfixes de suffixes. Parfois, vous aimeriez peut-être aller dans l'autre sens et obtenir des suffixes de préfixes.

Au-delà de cela, on ne sait pas ce que vous recherchez avec des «sous-chaînes uniques». Je vous suggère de rechercher les mots: type, jeton, maximal, supermaximal. Vous ne devriez avoir aucun mal à les trouver dans la littérature sur le tableau du suffixe.

Answer 3

Vous devez utiliser une variation de «Trie». Essentiellement, si vous avez ABCD, créez une arbre qui est une fusion de chemins: root-> a-> b-> c-> d, root-> b-> c-> d, root-> c-> d et root -> d. Maintenant, à chaque nœud, gardez une liste d'emplacements où la corde racine -> .-> .-> Le nœud a été observé.