algorithme efficace pour la recherche l'un de plusieurs chaînes dans un texte?

StackOverflow https://stackoverflow.com/questions/3560234

Question

Je dois rechercher des morceaux entrants non très longs textes pour les occurrences de chaînes données. Les chaînes sont constantes pour toute la session et ne sont pas beaucoup (~ 10). simplification supplémentaire est qu'aucune des chaînes est contenue dans une autre.

Je suis actuellement en utilisant boost regex correspondant à str1 | str2 | .... La performance de cette tâche est importante, alors je me demande si je peux l'améliorer. Non pas que je peux programmer mieux que les gars de stimuler, mais peut-être une mise en œuvre spécifique est plus efficace que d'ordre général.

Comme les chaînes restent constantes dans le temps, je peux me permettre la construction d'une structure de données, comme une table de transition d'état, dès le départ.

par exemple., Si les chaînes sont abcx, bcy et cz, et je l'ai lu jusqu'à présent abc, je serais dans un état combiné que des moyens you're either 3 chars into string 1, 2 chars into string 2 or 1 char into string 1. Puis la lecture x suivant me déplacer à l'état string 1 matched etc., et tout autre que ombles xyz se déplacera à l'état initial, et je ne vais pas besoin de revenir à rétractent b.

Toutes les idées ou les références sont appréciées.

Était-ce utile?

La solution

Regardez ceci: http://www.boost.org/doc/libs/1_44_0/libs/regex/doc/html/boost_regex/configuration/algorithm.html

L'existence d'une récursive / distinction non récurrente est une suggestion assez forte que BOOST est pas nécessairement un temps linéaire discret machine à état fini. Par conséquent, il y a une bonne chance que vous pouvez faire mieux pour votre problème particulier.

La meilleure réponse dépend tout à fait un peu le nombre de meules de foin que vous avez et la taille minimale d'une aiguille. Si la plus petite aiguille est plus longue que quelques caractères, vous pourrez peut-être faire un peu mieux qu'une bibliothèque regex généralisée.

En fait toutes les recherches de chaîne fonctionne en testant pour un match à la position actuelle (curseur), et si aucune est trouvée, d'essayer à nouveau avec le curseur a glissé plus loin vers la droite.

Rabin-Karp construit une DFSM de la chaîne (ou chaînes) pour lesquelles vous êtes à la recherche de telle sorte que le test et le mouvement du curseur sont combinés en une seule opération. Cependant, Rabin-Karp a été conçu à l'origine pour une seule aiguille, de sorte que vous auriez besoin pour soutenir un match si retours en arrière pourrait jamais être le préfixe d'un autre. (Rappelez-vous que lorsque vous voulez réutiliser votre code.)

Une autre tactique consiste à faire glisser le curseur plus d'un caractère à droite si possible. Boyer-Moore fait cela. Il est normalement construit pour une seule aiguille. Construire une table de tous les personnages et la position la plus à droite dans lequel elles apparaissent dans l'aiguille (le cas échéant). Or, la position du curseur à len (aiguille) -1. L'entrée de la table vous dira (a) ce leftward décalé par rapport au curseur que l'aiguille peut être trouvée, ou (b) que vous pouvez déplacer le curseur len (aiguille) plus à droite.

Lorsque vous avez plus d'une aiguille, la construction et l'utilisation de votre table devient plus compliqué, mais il peut encore éventuellement vous faire économiser un ordre de grandeur sur les sondes. Vous pourriez encore vouloir faire un DFSM mais au lieu d'appeler une méthode de recherche générale, vous appelez does_this_DFSM_match_at_this_offset ().

Une autre tactique consiste à tester plus de 8 bits à la fois. Il y a un outil tueur de spam qui se penche sur les mots machine 32 bits à la fois. Il fait alors un code de hachage simple pour adapter le résultat en 12 bits, et regarde alors dans une table pour voir s'il y a un coup. Vous disposez de quatre entrées pour chaque motif (décalages de 0, 1, 2, et 3 depuis le début du motif) et de cette façon, malgré des milliers de modèles dans la table ils ne d'un test ou deux par mot de 32 bits dans le sujet ligne.

Donc, en général, oui, vous pouvez aller plus vite que regexes QUAND LES AIGUILLES SONT CONSTANT.

Autres conseils

Jetez un oeil à Suffixe Arbre .

J'ai regardé les réponses, mais aucun ne semble tout à fait explicite ... et surtout bouillie jusqu'à quelques liens.

Ce qui intrigue me est ici le caractère unique de votre problème, les solutions exposons à ce jour ne capitalise pas du tout sur le fait que nous recherchons plusieurs aiguilles à la fois dans la botte de foin.

Je jeter un oeil à KMP / Boyer Moore, bien sûr, mais je ne les appliquer aveuglément (au moins si vous avez un peu de temps sur votre main), parce qu'ils sont conçus pour une seule aiguille, et je suis assez convaincu que nous pouvions capitaliser sur le fait que nous avons plusieurs cordes et vérifier tous à la fois, avec une machine d'état personnalisé (ou tableaux personnalisés pour BM).

Bien sûr, il est peu probable d'améliorer le grand O (Boyer Moore fonctionne en 3n pour chaque chaîne, il sera de toute façon linéaire), mais vous pourriez probablement gagner sur le facteur constant.

Regex initialisation du moteur devrait avoir certains frais généraux, donc s'il n'y a pas de A expressions régulières en cause, C - memcmp () devrait faire bien.

Si vous pouvez dire la taille des fichiers et donner quelques cas d'utilisation spécifiques, nous pourrions construire une référence (Je considère cela très intéressant).

Intéressant: explorations memcmp et différences temporelles

Cordialement

RBO

Il y a toujours Boyer Moore

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top