Algorithme pour trouver des correspondances de chaînes multiples

comme dans le cas des motifs simples, il existe plusieurs algorithmes pour l'appariement de motifs multiples, et vous devrez trouver celui qui correspond le mieux à votre but. Le papier Un algorithme rapide pour le multi-modèle de recherche (copie archivée) fait une revue de la plupart d'entre eux, y compris Aho-Corasick (qui est en quelque sorte la version multi-motifs de L'algorithme Knuth-Morris-Pratt, avec une complexité linéaire) et Commentz-Walter (une combinaison de Boyer-Moore et Aho-Corasick), et introduit un nouveau, qui utilise des idées de Boyer-Moore pour la tâche de faire correspondre plusieurs modèles.

un autre algorithme basé sur le hachage qui n'est pas mentionné dans cet article est le algorithme Rabin-Karp, qui a une complexité du pire cas plus grande que les autres algorithmes, mais la compense en réduisant le facteur linéaire via le hachage. Qui est mieux dépend en définitive de votre cas d'utilisation. Vous pouvez avoir besoin de mettre en œuvre plusieurs d'entre eux et de les comparer dans votre demande si vous voulez choisir le plus rapide.

en supposant que le gros du texte est du texte anglais statique et que vous avez besoin de faire correspondre des mots entiers, vous pouvez essayer ce qui suit (vous devriez vraiment clarifier ce qu'est exactement un "match", quel type de texte vous regardez etc dans votre question).

tout D'abord, pré-traiter le document entier en un Trie et DAWG.

Trie / Dawg possède la propriété suivante:

étant donné un trie / dawg et un terme de recherche de longueur K, vous pouvez en O (K) temps rechercher les données associées au mot (ou dire s'il n'y a pas de correspondance).

L'utilisation d'un DAWG pourrait vous sauver plus d'espace par rapport à un trie. Tries exploite le fait que de nombreux mots auront un préfixe commun et DAWGs exploite le préfixe commun ainsi que la propriété de suffixe commun.

dans le tri, maintenez aussi exactement la liste des positions du mot. Par exemple, si le texte est

That is that and so it is.

le noeud pour le dernier t en that la liste {1,3} et le nœud s is la liste {2,7} associés.

maintenant, quand vous obtenez un seul terme de recherche de mot, vous pouvez parcourir le trie et obtenir la liste de résultats pour ce mot facilement.

si vous obtenez un terme de recherche de mots multiples, vous pouvez faire ce qui suit.

Marche le trie avec le premier mot dans le terme de recherche. Obtenez la liste des correspondances et insérez dans un hashTable H1.

Maintenant marcher le trie avec le deuxième mot dans le terme de recherche. Obtenir la liste des correspondre. Pour chaque position de correspondance x, vérifiez si x-1 existe dans le HashTable H1. Si c'est le cas, ajoutez x au nouveau hashtable H2.

balader le trie avec le troisième mot, obtenir la liste des correspondances. Pour chaque position de correspondance y, vérifiez si y-1 existe en H3, si c'est le cas, ajoutez le nouveau hashtable H3.

Continuer ainsi de suite.

a la fin vous obtenez une liste de résultats pour la phrase de recherche, qui donne les positions du dernier mot de la phrase.

Vous pourriez potentiellement optimiser la phrase Etape d'appariement en maintenant une liste triée de positions dans la liste et en faisant une recherche binaire: I. e par exemple. pour chaque clé k dans H2, vous binaire rechercher k+1 dans la liste triée pour le terme de recherche 3 et ajouter k+1 à H3 si vous le trouvez etc.

Une solution optimale pour ce problème est d'utiliser un suffix tree (ou tableau de suffixe). C'est essentiellement un tri de tous les suffixes d'une chaîne. Pour un texte de longueur O(N), ce qui peut être construit en O(N).

Puis k les occurrences d'une chaîne de caractères de longueur m peut être répondu de manière optimale dans O(m + k).

les arbres de suffixe peuvent également être utilisés pour trouver efficacement, par exemple, le plus long palindrome, le plus long substrat commun, le plus long substrats répétés, etc.

il s'agit de la structure de données typique à utiliser lors de l'analyse de chaînes D'ADN qui peuvent être des millions/milliards de bases de long.

Voir aussi

• Wikipedia / Suffix tree
• Algorithmes sur des Chaînes, des Arbres et des Séquences: l'Informatique et la Biologie Computationnelle (Dan Gusfield).

donc vous avez beaucoup de termes de recherche et vous voulez voir si l'un d'eux est dans le document?

purement Algorithmique, vous pouvez trier toutes vos possibilités dans l'ordre alphabétique, les joindre avec des pipes, et les utiliser comme une expression régulière, si le moteur regex regarde /ant|ape/ et bien court-circuiter le a dans " ape "s'il ne l'a pas trouvé dans"ant". Si non, vous pouvez faire un "précompile" d'un regex et "squish" les résultats jusqu'à leur chevauchement minimum. I. e. dans le cas ci-dessus /a(nt|pe)/ et ainsi de suite, récursivement pour chaque lettre.

cependant, faire ce qui précède est à peu près comme mettre toutes vos chaînes de recherche dans un arbre 26-ary (26 caractères, plus si aussi des nombres). Poussez vos cordes sur l'arbre, en utilisant un niveau de profondeur par caractère de longueur.

vous pouvez faire cela avec vos termes de recherche pour faire un hyper-rapide "est-ce que ce mot correspond quelque chose dans ma liste de termes de recherche" Si votre nombre de termes de recherche grand.

vous pourriez théoriquement faire le sens inverse -- pack votre document dans l'arbre, et ensuite utiliser les termes de recherche sur -- si votre document est statique et les termes de recherche changer beaucoup de choses.

Cela dépend de l'optimisation dont vous avez besoin...

Sont les termes de recherche de mots que vous recherchez, ou peut-elle être pleine sentances trop ?

si ce ne sont que des mots, alors je suggère de construire un Rouge-Noir Tree à partir de tous les mots, et alors la recherche de chaque mot dans l'arbre.

si cela pouvait être des sentances, alors cela pourrait devenir beaucoup plus complexe... (?)