J'essaie de goûter une chaîne. J'ai une table de jetons disponibles commandés sous la forme d'un trie . Chaque jeton sait qu'il a des enfants. Une table de jetons simples ressemblera, dans cette table, Maintenant, étant donné une chaîne Pour ce faire, je vais commencer à lire chaque personnage à partir de l'entrée, recherchez le match, si un match trouvé et que le jeton a des enfants, recherchez à nouveau match en incluant le prochain caractère. Faites cela jusqu'à ce que nous trouvions le plus long match. Si aucun match trouvé, essayez de faire correspondre le caractère suivant jusqu'à ce que nous atteignions la fin de la chaîne ou une correspondance réussie. Si nous atteignons la fin de la chaîne sans correspondance, sortie Cet algorithme fonctionne, mais le recul et l'itération sur toutes les combinaisons possibles de l'entrée le rend lent et complexe. Je me demande est une meilleure façon de résoudre ce problème? Toute aide serait appréciée. pile est un enfant de S et débordement est un enfant de sur . En pratique, cette table aura plus de 5000 enregistrements commandés de cette manière. Stackover , il doit indiquer Stack-Valover-Val . L'algorithme est gourmand et il essaiera de trouver le plus long match toujours. ? Symbole et retirez le premier caractère de l'entrée. Répétez le processus entier avec des caractères restants.
5 Réponses :
Pourriez-vous utiliser le Aho-Corasick algorithme? Il crée un automate pour rechercher un arbre de mots-clés (Trie).
Je pense que vous voulez prendre tous vos mots-clés et les trier vers l'inverse alphabétiquement, votre liste deviendrait donc (plus quelques extras) la troisième colonne de cette liste sont des pointeurs vers le jeton parent qui est toujours plus bas sur la liste. Ensuite, vous pouvez prendre votre chaîne cible et votre recherche binaire dans laquelle il convient à cette liste. Si elle atterrit au-dessus d'un jeton qui correspond, vous terminez cette partie et répétez le processus pour le reste. Si cela ne correspond pas, vous n'utilisez pas le pointeur parent pour trouver le prochain jeton correspondant le plus long correspondant potentiel. Si vous voulez être vraiment fantaisiste, vous pouvez également résoudre les chaînes en mots de 64 bits et comparer 8 caractères à la fois Dans la recherche binaire.
Au lieu de revenir en arrière, vous pouvez rester en mémoire tous les résultats possibles, jusqu'à ce que l'on donne un résultat singulant à certains points dans le flux d'entrée. Exemple
jetons: S Pile Stackoverflow Stag sur le trop-plein
String: Sstackoverfun
1 - Trouvé S sur place 0, avez des jetons qui commencent par S, essayez-les tous, seulement s est valide, donc résolution s résultat final: s pile sur le plaisir
2 - S sur 1, ont de tels jetons, essayez-les, possibles valables sont s et pile. Ne résoutez pas, gardez-les juste à l'esprit.
3 - T sur 2, n'a pas de jetons de ce type, SO S pourrait être résolu maintenant, mais nous avons aussi un jeton plus long (pile), donc s n'est pas bon. Fossé S, et la pile n'est laissée que, mais il a des enfants. Essayez la chaîne pour les enfants. Il n'y a pas d'enfants éventuels donc
4 - O On 6, avoir de tels jetons, essayez-les, ne vous trouvez que sur, donc
5 - F sur 10, aucun des jetons de ce type, et rien à résoudre d'avant, il est donc non gênant de
6 et 7 - même que l'étape 5
Je vous suggère d'essayer Ragel , il peut générer des scanners efficaces pouvant faire le plus long match / retour en arrière. Voir le chapitre 6.3 dans le Guide de l'utilisateur Ragel pour plus d'informations.
J'ai créé un essai minuscule que je pense correspond à votre spécification, il ne s'agit que de la description de la machine d'état, sans le code pour alimenter l'entrée:
Le code TOKEN_TREE suivant est basé sur la classe préfixe_tree de Zeromq
La classe Prefix_tree renvoie uniquement "true" lorsque l'un des préfixes de l'arbre correspond au début du texte d'entrée. Cela ne vous dira même pas quel préfixe ou combien de temps le préfixe était.
Ce token_tree recherchera le jeton le plus long qui correspond au début du texte d'entrée. La recherche Fonction token_tree_longest_Token () n'a besoin que de renvoyer la longueur du jeton le plus long correspondant Contre le début du texte d'entrée.
L'algorithme de base est similaire à celui décrit dans la question, mais la implication pourrait être plus rapide.
Il existe également des moyens d'améliorer la mémoire Utilisation, qui pourrait l'avoir plus rapide.
Pourquoi je garde une trace des enfants: si je trouvais un match et cherche le plus long match, je n'ai pas à le faire si le jeton n'a pas d'enfants. Cela améliore l'efficacité.