L'algorithme C++ le plus rapide pour tester des chaînes de caractères par rapport à une liste de graines prédéfinies (insensible à la casse).

Question

J'ai une liste de chaînes de semences, environ 100 chaînes prédéfinies. Toutes les chaînes ne contiennent que des caractères ASCII.

std::list<std::wstring> seeds{ L"google", L"yahoo", L"stackoverflow"};

Mon application reçoit constamment un grand nombre de chaînes de caractères qui peuvent contenir n'importe quels caractères. Je dois vérifier chaque ligne reçue et décider si elle contient une des graines ou non. La comparaison doit être insensible à la casse.

J'ai besoin de l'algorithme le plus rapide possible pour tester la chaîne reçue.

Actuellement, mon application utilise cet algo :

std::wstring testedStr;
for (auto & seed : seeds)
{
    if (boost::icontains(testedStr, seed))
    {
        return true;
    }
}
return false;

Cela fonctionne bien, mais je ne suis pas sûr que ce soit le moyen le plus efficace.

Comment est-il possible d'implémenter l'algorithme afin d'obtenir de meilleures performances ?

Il s'agit d'une application Windows. L'application reçoit des données valides std::wstring ficelles.

---

Mise à jour

Pour cette tâche, j'ai mis en œuvre l'algo Aho-Corasick. Si quelqu'un pouvait revoir mon code, ce serait formidable - je n'ai pas une grande expérience de ces algorithmes. Lien vers l'implémentation : gist.github.com

Answer 1

S'il existe une quantité finie de chaînes de caractères correspondantes, cela signifie que vous pouvez construire un arbre tel que, lu de la racine aux feuilles, des chaînes de caractères similaires occuperont des branches similaires.

C'est aussi ce qu'on appelle un essai ou Arbre Radix .

Par exemple, nous pourrions avoir les chaînes de caractères cat, coach, con, conch ainsi que dark, dad, dank, do . Leur parcours pourrait ressembler à ceci :

La recherche d'un des mots de l'arbre se fait à partir d'une racine. Arriver à une feuille correspondrait à une correspondance avec une graine. Quoi qu'il en soit, chaque caractère de la chaîne doit correspondre à l'un de ses enfants. Si ce n'est pas le cas, vous pouvez mettre fin à la recherche (par exemple, vous ne considérerez aucun mot commençant par "g" ou aucun mot commençant par "cu").

Il existe plusieurs algorithmes pour construire l'arbre, le rechercher et le modifier à la volée, mais j'ai pensé donner un aperçu conceptuel de la solution plutôt qu'une solution spécifique, car je ne connais pas le meilleur algorithme pour cela.

Conceptuellement, un algorithme que vous pourriez utiliser pour rechercher l'arbre serait lié à l'idée derrière tri radix d'un nombre fixe de catégories ou de valeurs qu'un caractère d'une chaîne de caractères peut prendre à un moment donné.

Cela vous permet de vérifier un mot par rapport à votre liste de mots . Puisque vous recherchez cette liste de mots comme sous-chaînes de votre chaîne d'entrée, il y aura plus que cela.

Edit : Comme d'autres réponses l'ont mentionné, l'algorithme d'Aho-Corasick pour la correspondance des chaînes de caractères est un algorithme sophistiqué pour effectuer la correspondance des chaînes de caractères, consistant en un trie avec des liens supplémentaires pour prendre des "raccourcis" dans l'arbre et avoir un modèle de recherche différent pour accompagner cela. (Il est intéressant de noter qu'Alfred Aho a également contribué à l'élaboration d'un manuel populaire sur les compilateurs, Compilateurs : Principes, techniques et outils ainsi que le manuel d'algorithmes, La conception et l'analyse des algorithmes informatiques . Il est également un ancien membre des Laboratoires Bell. Margaret J. Corasick ne semble pas avoir trop d'informations publiques sur elle-même).

Answer 2

Vous pouvez utiliser Algorithme d'Aho-Corasick

Il construit un trie/automate où certains sommets sont marqués comme terminaux, ce qui signifierait que la chaîne a des graines.

Il est construit en O(sum of dictionary word lengths) et donne la réponse en O(test string length)

Avantages :

• Il fonctionne spécifiquement avec plusieurs mots du dictionnaire et le temps de vérification ne dépend pas du nombre de mots (si nous ne considérons pas les cas où il ne tient pas dans la mémoire, etc).
• L'algorithme n'est pas difficile à mettre en œuvre (en comparaison avec les structures de suffixes, du moins).

Vous pouvez le rendre insensible à la casse en abaissant chaque symbole s'il est ASCII (les caractères non ASCII ne correspondent pas de toute façon).

Answer 3

Vous devriez essayer un utilitaire regex préexistant, il peut être plus lent que votre algorithme hand-rolled mais le regex consiste à faire correspondre plusieurs possibilités, il est donc probable qu'il sera déjà plusieurs fois plus rapide qu'un hashmap ou une simple comparaison de toutes les chaînes de caractères. Je crois que les implémentations de regex peuvent déjà utiliser l'algorithme d'Aho-Corasick mentionné par RiaD, donc en gros vous aurez à votre disposition une implémentation rapide et bien testée.

Si vous avez C++11, vous disposez déjà d'une bibliothèque standard pour les expressions rationnelles.

#include <string>
#include <regex>

int main(){
     std::regex self_regex("google|yahoo|stackoverflow");
     regex_match(input_string ,self_regex);
}

Je m'attends à ce qu'il génère le meilleur arbre de correspondance minimum possible, et donc à ce qu'il soit très rapide (et fiable !).

Answer 4

L'une des méthodes les plus rapides consiste à utiliser l'arbre des suffixes. https://en.wikipedia.org/wiki/Suffix_tree mais cette approche présente un énorme inconvénient : il s'agit d'une structure de données difficile à construire. Cet algorithme permet de construire un arbre à partir d'une chaîne de caractères en complexité linéaire. https://en.m.wikipedia.org/wiki/Ukkonen%27s_algorithm

Answer 5

Edit : Comme Matthieu M. l'a fait remarquer, le PO demandait si une chaîne de caractères contenait un mot-clé. Ma réponse ne fonctionne que si la chaîne de caractères est égale au mot-clé ou si vous pouvez diviser la chaîne de caractères, par exemple par le caractère espace.

Surtout avec un nombre élevé de candidats possibles et en les connaissant au moment de la compilation à l'aide d'un fonction de hachage parfaite avec un outil comme gperf vaut la peine d'être essayé. Le principe de base est le suivant : vous ensemencez un générateur avec votre graine et il génère une fonction contenant une fonction de hachage qui ne présente aucune collision pour toutes les valeurs de la graine. Au moment de l'exécution, vous donnez une chaîne à la fonction et elle calcule le hachage, puis elle vérifie si elle est le seul candidat possible correspondant à la valeur de hachage.

Le coût d'exécution consiste à hacher la chaîne et à la comparer au seul candidat possible (O(1) pour la taille de la graine et O(1) pour la longueur de la chaîne).

Pour rendre la comparaison insensible à la casse, il suffit d'utiliser tolower sur la graine et sur votre chaîne.