Aiguille dans une botte de foin : un didacticiel astucieux sur l'algorithme de recherche de texte à grande échelle

Lorsque l'on rencontre le terme "recherche de texte", on pense généralement à un grand corps de texte qui est indexé de manière à permettre de rechercher rapidement un ou plusieurs termes de recherche lorsqu'ils sont saisis par un utilisateur. C'est un problème classique pour les informaticiens, auquel de nombreuses solutions existent.

Mais que diriez-vous d'un scénario inverse ? Que se passe-t-il si ce qui est disponible pour l'indexation à l'avance est un groupe d'expressions de recherche et qu'un grand corps de texte est présenté pour la recherche uniquement lors de l'exécution ? C'est à ces questions que ce didacticiel sur la structure de données trie cherche à répondre.

Applications

Une application réelle de ce scénario consiste à faire correspondre un certain nombre de thèses médicales à une liste de conditions médicales et à découvrir quelles thèses traitent de quelles conditions. Un autre exemple consiste à parcourir une vaste collection de précédents judiciaires et à extraire les lois auxquelles ils font référence.

Approche directe

L'approche la plus simple consiste à parcourir les phrases de recherche et à parcourir le texte de chaque phrase, une par une. Cette approche ne s'adapte pas bien. La recherche d'une chaîne à l'intérieur d'une autre a la complexité O(n) . Répéter cela pour m expressions de recherche conduit à l'horrible O(m * n) .

Le (probablement le seul) avantage d'une approche directe simple à mettre en œuvre, comme le montre l'extrait de code C# suivant :

 String[] search_phrases = File.ReadAllLines ("terms.txt"); String text_body = File.ReadAllText("body.txt"); int count = 0; foreach (String phrase in search_phrases) if (text_body.IndexOf (phrase) >= 0) ++count;

En exécutant ce code sur ma machine de développement [1] contre un échantillon de test [2], j'ai obtenu une durée d'exécution de 1 heure 14 minutes - bien au-delà du temps dont vous avez besoin pour prendre une tasse de café, vous lever et vous étirer, ou toute autre excuse les développeurs utilisent pour sauter le travail.

Une meilleure approche - L'essai

Le scénario précédent peut être amélioré de plusieurs façons. Par exemple, le processus de recherche peut être partitionné et parallélisé sur plusieurs processeurs/cœurs. Mais la réduction du temps d'exécution obtenue par cette approche (durée d'exécution totale de 20 minutes en supposant une division parfaite sur 4 processeurs/cœurs) ne justifie pas la complexité supplémentaire du codage/débogage.

La meilleure solution possible serait celle qui ne traverse le corps du texte qu'une seule fois. Cela nécessite d'indexer les phrases de recherche dans une structure qui peut être traversée linéairement, parallèlement au corps du texte, en une seule passe, atteignant une complexité finale de O(n) .

Une structure de données particulièrement adaptée à ce scénario est la structure trie . Cette structure de données polyvalente est généralement négligée et n'est pas aussi célèbre que d'autres structures arborescentes lorsqu'il s'agit de problèmes de recherche.

Le précédent tutoriel de Toptal sur les essais fournit une excellente introduction à la façon dont ils sont structurés et utilisés. En bref, un trie est un arbre spécial, capable de stocker une séquence de valeurs de telle sorte que tracer le chemin de la racine à n'importe quel nœud donne un sous-ensemble valide de cette séquence.

Donc, si nous pouvons combiner toutes les phrases de recherche en un seul essai, où chaque nœud contient un mot, nous aurons les phrases disposées dans une structure où le simple fait de tracer de la racine vers le bas, via n'importe quel chemin, donne une phrase de recherche valide.

L'avantage d'un trie est qu'il réduit considérablement le temps de recherche. Pour faciliter la compréhension dans le cadre de ce tutoriel trie, imaginons un arbre binaire. Traverser un arbre binaire a la complexité de O(log 2 n) , puisque chaque nœud se divise en deux, coupant la traversée restante en deux. Ainsi, un arbre ternaire a la complexité de parcours O(log 3 n) . Dans un trie, cependant, le nombre de nœuds enfants est dicté par la séquence qu'il représente, et dans le cas d'un texte lisible/significatif, le nombre d'enfants est généralement élevé.

Algorithme de recherche de texte

À titre d'exemple simple, supposons les expressions de recherche suivantes :

• "même famille"
• "famille différente"
• "existence séparée"
• "membres de la ligue"

N'oubliez pas que nous connaissons nos expressions de recherche à l'avance. Donc, on commence par construire un index, sous la forme d'un trie :

Plus tard, l'utilisateur de notre logiciel lui présente un fichier contenant le texte suivant :

Les langues européennes font partie de la même famille. Leur existence distincte est un mythe.

Le reste est assez simple. Notre algorithme aura deux indicateurs (des pointeurs, si vous préférez), l'un commençant à la racine, ou nœud "start" dans notre structure de trie, et l'autre au premier mot dans le corps du texte. Les deux indicateurs évoluent ensemble, mot par mot. L'indicateur de texte se déplace simplement vers l'avant, tandis que l'indicateur de trie parcourt le trie en profondeur, en suivant une piste de mots correspondants.

L'indicateur trie revient au début dans deux cas : lorsqu'il atteint la fin d'une branche, ce qui signifie qu'une expression de recherche a été trouvée, ou lorsqu'il rencontre un mot non correspondant, auquel cas aucune correspondance n'a été trouvée.

Une exception au mouvement de l'indicateur de texte est lorsqu'une correspondance partielle est trouvée, c'est-à-dire qu'après une série de correspondances, une non-correspondance est rencontrée avant la fin de la branche. Dans ce cas, l'indicateur de texte n'est pas avancé, car le dernier mot pourrait être le début d'une nouvelle branche.

Appliquons cet algorithme à notre exemple de structure de données trie et voyons comment cela se passe :

Comme nous pouvons le voir, le système trouve avec succès les deux phrases correspondantes, "même famille" et "existence séparée" .

Exemple du monde réel

Pour un projet récent, on m'a présenté le problème suivant : une cliente a un grand nombre d'articles et de thèses de doctorat relatifs à son domaine de travail, et a généré sa propre liste de phrases représentant des titres et des règles spécifiques relatifs au même domaine de travailler.

Son dilemme était le suivant : compte tenu de sa liste de phrases, comment relie-t-elle les articles/thèses à ces phrases ? L'objectif final est de pouvoir choisir au hasard un groupe de phrases et d'avoir immédiatement une liste d'articles/thèses qui mentionnent ces phrases particulières prêtes à être saisies.

Comme discuté précédemment, il y a deux parties pour résoudre ce problème : l'indexation des phrases dans un trie et la recherche proprement dite. Les sections suivantes fournissent une implémentation simple en C#. Veuillez noter que la gestion des fichiers, les problèmes d'encodage, le nettoyage du texte et les problèmes similaires ne sont pas traités dans ces extraits, car ils sortent du cadre de cet article.

Indexage

L'opération d'indexation parcourt simplement les phrases une par une et les insère dans le trie, un mot par nœud/niveau. Les nœuds sont représentés avec la classe suivante :

 class Node { int PhraseId = -1; Dictionary<String, Node> Children = new Dictionary<String, Node>(); public Node() { } public Node(int id) { PhraseId = id; } }

Chaque expression est représentée par un identifiant, qui peut être aussi simple qu'un nombre incrémentiel, et transmis à la fonction d'indexation suivante (la racine de la variable est la racine réelle du trie) :

 void addPhrase(ref Node root, String phrase, int phraseId) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // break phrase into words String[] words = phrase.Split (); // start traversal at root for (int i = 0; i < words.Length; ++i) { // if the current word does not exist as a child // to current node, add it if (node.Children.ContainsKey(words[i]) == false) node.Children.Add(words[i], new Node()); // move traversal pointer to current word node = node.Children[words[i]]; // if current word is the last one, mark it with // phrase Id if (i == words.Length - 1) node.PhraseId = phraseId; } }

Recherche

Le processus de recherche est une implémentation directe de l'algorithme trie décrit dans le tutoriel ci-dessus :

 void findPhrases(ref Node root, String textBody) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // a list of found ids List<int> foundPhrases = new List<int>(); // break text body into words String[] words = textBody.Split (); // starting traversal at trie root and first // word in text body for (int i = 0; i < words.Length;) { // if current node has current word as a child // move both node and words pointer forward if (node.Children.ContainsKey(words[i])) { // move trie pointer forward node = node.Children[words[i]]; // move words pointer forward ++i; } else { // current node does not have current // word in its children // if there is a phrase Id, then the previous // sequence of words matched a phrase, add Id to // found list if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); if (node == root) { // if trie pointer is already at root, increment // words pointer ++i; } else { // if not, leave words pointer at current word // and return trie pointer to root node = root; } } } // one case remains, word pointer as reached the end // and the loop is over but the trie pointer is pointing to // a phrase Id if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); }

Performance

Le code présenté ici est extrait du projet réel et a été simplifié pour les besoins de ce document. Exécuter à nouveau ce code sur la même machine [1] et sur le même échantillon de test [2] a entraîné un temps d'exécution de 2,5 secondes pour la construction du trie et de 0,3 seconde pour la recherche. Tant pis pour la pause, hein ?

Variantes

Il est important de reconnaître que l'algorithme tel que décrit dans ce didacticiel peut échouer dans certains cas extrêmes, et est donc conçu avec des termes de recherche prédéfinis déjà à l'esprit.

Par exemple, si le début d'un terme de recherche est identique à une partie d'un autre terme de recherche, comme dans :

• « à partager et à déguster entre amis »
• "J'ai deux billets à partager avec quelqu'un"

et le corps du texte contient une phrase qui fait démarrer le pointeur trie sur le mauvais chemin, comme :

J'ai deux billets à partager et à apprécier avec des amis.

alors l'algorithme ne parviendra pas à faire correspondre un terme, car l'indicateur trie ne reviendra pas au nœud de départ tant que l'indicateur de texte n'aura pas déjà dépassé le début du terme correspondant dans le corps du texte.

Il est important de déterminer si ce type de cas limite est une possibilité pour votre application avant d'implémenter l'algorithme. Si tel est le cas, l'algorithme peut être modifié avec des indicateurs de tri supplémentaires pour suivre toutes les correspondances à un moment donné, au lieu d'une seule correspondance à la fois.

Conclusion

La recherche de texte est un domaine profond de l'informatique ; un domaine riche en problèmes comme en solutions. Le type de données que j'ai dû traiter (23 Mo de texte représentent une tonne de livres dans la vraie vie) peut sembler être un événement rare ou un problème spécialisé, mais les développeurs qui travaillent avec la recherche linguistique, l'archivage ou tout autre type de manipulation de données , rencontrez régulièrement de plus grandes quantités de données.

Comme le montre le didacticiel sur la structure de données trie ci-dessus, il est très important de choisir avec soin l'algorithme correct pour le problème à résoudre. Dans ce cas particulier, l'approche trie a réduit le temps d'exécution de 99,93 %, passant de plus d'une heure à moins de 3 secondes.

Ce n'est en aucun cas la seule approche efficace, mais c'est assez simple et ça marche. J'espère que vous avez trouvé cet algorithme intéressant et je vous souhaite bonne chance dans vos efforts de codage.

[1] La machine utilisée pour ce test a les caractéristiques suivantes :

• Intel i7 4700HQ
• 16 Go de RAM

Les tests ont été effectués sur Windows 8.1 en utilisant .NET 4.5.1 et également Kubuntu 14.04 en utilisant la dernière version de mono et les résultats étaient très similaires.

[2] L'échantillon de test se compose de 280 000 expressions de recherche d'une taille totale de 23,5 Mo et d'un corps de texte de 1,5 Mo.