Trouver tous les noms correspondant à une requête : comment utiliser un arbre de suffixes ?

Question

Question : Vous avez un smartphone et vous avez ouvert l'application contact. Vous voulez rechercher un contact. Disons que manmohan . mais vous ne vous souvenez pas de son nom complet. vous vous souvenez seulement mohan Vous avez donc commencé à taper. Au moment où vous tapez m L'application contact commencera à chercher le contact qui a la lettre ' m Supposons que vous ayez enregistré des noms dans votre liste de contacts. ("manmohan", "manoj", "raghav","dinesh", "aman") maintenant le contact va montrer manmohan,manoj and aman en conséquence. Maintenant, le prochain caractère que vous tapez est ' o (jusqu'à présent, vous avez tapé " mo ") maintenant le résultat devrait être "man mo han". Comment implémenteriez-vous une telle structure de données ?

Mon approche consistait à appliquer KMP en recherchant le motif "m" puis "mo" dans tous les contacts disponibles, puis en affichant la chaîne qui correspond. Mais mon interlocuteur m'a dit que ce n'était pas efficace. (Je ne pouvais pas penser à une meilleure approche.) Avant de partir, il a dit qu'il y avait un algorithme qui aiderait. Si vous le connaissez, vous pouvez le résoudre. Je n'ai pas pu le faire. (Avant de partir, j'ai demandé quel était cet algorithme standard. L'interviewer a répondu : arbre de suffixes). Quelqu'un peut-il m'expliquer s'il vous plaît en quoi il est meilleur ? ou quel est le meilleur algorithme pour implémenter cette structure de données.

Answer 1

Le problème que vous essayez de résoudre se résume essentiellement à ceci : étant donné une collection fixe de chaînes de caractères et une chaîne de caractères qui ne change que via les ajouts, comment trouver efficacement toutes les chaînes de caractères qui contiennent ce motif comme sous-chaîne ?

Il existe un petit résultat sur les chaînes de caractères qui est souvent utile pour résoudre des problèmes impliquant la recherche de sous-chaînes : une chaîne P est une sous-chaîne d'une chaîne T si et seulement si P est un préfixe d'au moins un suffixe de T. (Vous voyez pourquoi ?)

Imaginez donc que vous prenez tous les noms de votre banque de mots et que vous construisez un tableau de tous les suffixes de tous les mots de cette banque. Si vous tombez du trie, c'est que la chaîne P ne doit pas être une sous-chaîne de la banque de noms (sinon, elle aurait été un préfixe d'au moins un suffixe de l'une des chaînes de T). Sinon, on se trouve à un nœud de trie. Dans ce cas, tous les suffixes du sous-arbre dont la racine se trouve au nœud que vous visitez actuellement correspondent à toutes les correspondances de votre sous-chaîne dans tous les noms de T, que vous pouvez trouver en effectuant un DFS sur le sous-arbre et en enregistrant tous les suffixes que vous trouvez.

Un arbre de suffixes est essentiellement une structure de données efficace en termes de temps et d'espace pour représenter un tri de tous les suffixes d'une collection de chaînes de caractères. Il peut être construit en un temps proportionnel au nombre total de caractères de T (bien que les algorithmes pour ce faire soient réputés pour être difficiles à comprendre et à coder) et est conçu de manière à ce que vous puissiez trouver toutes les correspondances de la chaîne de texte en question enracinée à un nœud donné en un temps O(k), où k est le nombre de correspondances.

Pour récapituler, l'idée de base ici est de créer un tableau de tous les suffixes des chaînes de caractères dans T, puis de le parcourir en utilisant le motif P. Pour des raisons de temps et d'espace, vous ferez cela avec un suffixe arbre plutôt qu'un suffixe essai .