algorithme efficace pour trouver un ensemble de correspondances dans un court texte

Question

Entrée:

1. Un texte relativement court (100-1000 caractères, le plus souvent).
2. Une liste fixe d'environ 5000 expressions données à l'avance, la plupart d'entre elles ayant entre 10 et 20 caractères, certaines d'entre elles en contenant d'autres en tant que sous-expressions (par exemple "Try" et "Try Again").

Remarque - Seuls les premiers changements d'entrée, la seconde est considérée comme une constante, et est disponible pour pré-traitement.

sortie souhaitée:

Identifier tous les matchs des expressions de l'article 2 à l'intérieur du texte. S'il y a des ambiguïtés de correspondance, prenez le match glouton si possible.

Le temps d'exécution devrait être relativement rapide, mais aucune exigence de performance stricte. Une tentative de force brute pourrait suffire ici.

Qu'est-ce qu'un bon algorithme pour cela? Les arbres de suffixe sont-ils utiles ici? Que diriez-vous de passer en revue toutes les expressions et de les mettre dans une table de hachage? Notez également que je suis intéressé par solutions pratiques, donc la facilité de mise en œuvre peut être plus utile qu'un algorithme super efficace ...

Answer 1

Jetez un oeil à l'algorithme Aho–Corasick.

Answer 2

L '"algorithme" général supposant un stockage illimité, pour optimiser cela consiste à construire un arbre sur les données basées sur les caractères vous permettant de rechercher votre modèle récursivement. Dans l'index de l'arbre que vous construisez, vous allez vers le bas jusqu'à ce que vous atteigniez un point "unique" et la "feuille" indique l'emplacement de cette occurrence unique.

Dans le paragraphe ci-dessus par exemple le mot "index" apparaît une fois. Si l'arbre est construit un caractère à la fois, alors le chemin de l'arbre que nous suivons commencerait par le caractère "i" puis "in". Si elle est sensible à la casse, il n'y a que 3 occurrences (en supposant, en optimisant et en indexant). Lorsque nous recherchons ensuite 'd', nous atteignons notre résultat unique. Bien sûr, nous pourrions commencer notre recherche d'abord avec l'espace, puis le i puis le n et nous suivrions un chemin différent.

Vous pouvez également rendre l'arbre insensible à la casse, et vous pouvez utiliser un "nybble" plutôt qu'un octet à chaque point de branchement.