J'ai beaucoup de cordes contenant du texte dans de nombreuses orthographes différentes. Je tikenisez ces chaînes en recherchant des mots-clés et si un mot clé est trouvé, j'utilise un texte assoqué pour ce mot clé.
Disons que la chaîne de recherche peut contenir le texte "schw" "," Schwa ". et "schwarz". J'ai trois mots clés qui résolvent tous au texte "schwarz".
Je cherche un moyen efficace de trouver tous les mots-clés sans effectuer une chaîne.Contains (mot-clé) pour chaque mot-clé. < / p>
échantillons de données: échantillon de mots-clés (clé, valeur): résultat de l'échantillon:
5 Réponses :
Ceci semble convenir à " algorithmes à l'aide d'un jeu de motifs finis "
the String Aho-Corasick Assortiment L'algorithme est une recherche de chaîne algorithme inventé par Alfred V. Aho et Margaret J. Corasick. C'est une sorte d'algorithme correspondant au dictionnaire qui Localise des éléments d'un ensemble fini de chaînes (le "dictionnaire") dans un Texte de saisie. Il correspond à tous les modèles "A la fois", donc la complexité de la l'algorithme est linéaire dans la longueur de les motifs plus la longueur de la texte recherché plus le nombre de correspondance de sortie. Notez que parce que tout Les matchs sont trouvés, il peut y avoir un Nombre quadratique de matchs si chaque Correspondances de sous-chaînes (par exemple Dictionnaire = A, AA, AAA, AAAA et String String sont AAAA).
the algorithme de rabin-karp est une chaîne Algorithme de recherche créée par Michael O. Rabin et Richard M. Karp en 1987 qui utilise hachage pour trouver l'un des Ensemble de chaînes de motifs dans un texte. Pour Texte de longueur N et P Motifs de longueur combinée m, sa moyenne et Le meilleur cas de fonctionnement est O (n + m) dans espace o (p), mais son pire temps est O (nm). En revanche, l'Aho-Corasick algorithme de correspondance de chaîne a complexité des mauvais temps asymptotique O (n + m) dans l'espace O (m).
L'algorithme Aho-Crasick semble vraiment prometteur. Je suis actuellement à la recherche d'un projet CodeProject implémentant l'algorithme: codeProject.com/kb/recipes /ahocorasick.aspx
Aho-Corasick est exactement ce que vous voulez. Une autre solution que je suggère est simplement d'utiliser une bibliothèque de regex qui construit également une DFA, telle que quelque chose basé sur RE2 code.google.com/p/re2
Récemment, j'ai porté de Java Mise en œuvre très efficace d'Aho-Corasick: Github.com/nreco/ahocorasickDoueRayRieRie C'est vraiment rapide et approprié pour une utilisation de la production.
Je suggère d'approcher:
1) TOKENISE en utilisant 2) Mettre en œuvre Tokeniser vous-même un lecteur avec string.split et correspond à un dictionnaire de clés que vous avez
ReadTokoken () Méthode qui ajoute les caractères à un tampon jusqu'à ce qu'il trouve (Split pourrait le faire) un caractère divisé et des sorties que comme jeton. Ensuite, vous vérifiez contre votre dictionnaire.
La tokénisation n'est pas possible car certains des caractères pouvant être utilisés comme séparateurs font partie des mots-clés. Même si je hommage à la chaîne en mots, le mot clé peut toujours se produire quelque part avec le mot.
Vos exemples n'ont pas transé ça. VRAI, ils sont utilisés pour la fin du mot (par exemple "schw") mais pas au milieu de la Parole - à moins que des cas, vous n'avez pas partagé.
Peut-être que c'est un peu maîtrisé mais vous devriez certainement jeter un coup d'œil à antlr .
J'utiliserais des expressions régulières précompilées pour chaque groupe de mots-clés pour correspondre. En arrière-plan, ils sont "compilés" aux automates finis, ils sont donc assez rapides pour reconnaître le motif de votre chaîne et beaucoup plus rapidement qu'un Utilisation: Dans votre exemple:
Documentation supplémentaire disponible ici: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regexoptions (v = vs.90) .aspx contient pour chacune des chaînes possibles.
system.text.regularexpressions .
nouvelle regex (@ "schw (a? \. | ArZ)", Regexoptions.Compiled)
C'est une correspondance de regex par mot clé (ou groupe) qui n'est pas trop grande. Ou une regexplesse vraiment horrible avec alternance sur chaque groupe. Aho-Crasick fait fondamentalement la même chose que la compilation hte horrible dans une DFA, mais sans la complexité complète de Regexps, il est plus facile de mettre en œuvre.