Aho-Corasick recherche paires de mots-clés

Question

Supposons que nous avons un dictionnaire de mots-clés

Dictionary A: {A1, A2, A3} 

Et supposons que nous avons un second dictionnaire de mots-clés (distincte de la première)

Dictionary B: {B1, B2, B3, B4} 

Je voudrais trouver toutes les correspondances possibles de paires de mots-clés non ordonnées dans une séquence (c.-à-d. séparées uniquement par des espaces) des deux dictionnaires dans un texte d'entrée. Par exemple, considérez ce qui suit comme un texte d'entrée

We are not looking for single words from either dictionary on their own, like 
A2 or B4, nor are we looking for sequences of words from only one dictionary, 
like A1 A3 or B4 B2. We are looking for tuples of words from both dictionaries 
in a sequence together, like B1 A3 and A2 B4 and B4 A2. 

L'algorithme Aho-Corasick est une solution traditionnelle pour trouver efficacement tous les matches d'un seul dictionnaire de mots-clés dans un texte d'entrée en construisant un automate comme Trie et numériser le texte caractère par caractère.

Existe-t-il un moyen efficace d'étendre Aho-Corasick pour le cas plusieurs dictionnaires?

Answer 1

Oui, vous pourriez construire un automate général Aho-Corasick et une personne pour chaque document: Using Aho-Corasick, can strings be added after the initial tree is built?