rechercher une sous-chaine dans un set de 40 000 noms

[floopi51]

Bonjour,

Je recherche une méthode qui me permette de trouver rapidement une sous chaine ou une chaine dans un set de 40000 noms.

Si je fais une recherche du mot "tu", je veux que mon programme trouve "turquoise", "tortue", "tu" dans un "dictionnaire" figé c'est à dire que les données dans lesquelles la recherche est faite reste inchangées d'une exécution à une autre.

J'ai trouvé des informations sur l'algorithme de Boyer-Moore pour la recherche de sous-chaine.
j'ai aussi trouvé les arbres binaires mais étant donné que ma recherche doit porter sur une sous-chaine qui n'est pas forcément en début de mot, je ne pense pas que cela puisse me servir.
J'ai aussi pensé à une table de hash avec des listes chainées mais je ne vois pas sur quoi calculer ma clé de hash.

Quelqu'un peut-il m'orienter pour choisir une structure de données adaptée pour la recherche ?
Merci

[I_believe_in_code]

Après avoir lu cet article :

http://fr.wikipedia.org/wiki/Algorithme_de_Boyer-Moore

Ainsi que les autres cités dans "articles connexes"

Je crois pouvoir affirmer que tout ceci est très intéressant et répond sans doute à tes questions.

L'Algorithme de Boyer-Moore est basé sur une idée que je trouve géniale. Ne convient-il pas à ce que tu dois faire ?

[kwariz]

Bonsoir,

Une autre approche serait de construire un dictionnaire qui optimise les recherches partielles de lettres consécutives qui renvoient un ensemble de mots correspondants.
Il y a évidemment l'approche naïve (et peu efficace) qui consiste à construire un arbre n-aire qui factorise les préfixes (en anglais un trie). L'étape suivante est de passer en une représentation binaire (fils gauche, frère droit) et de factoriser au possible les suffixes (en anglais un DAWG). Puis tu peux essayer un GADDAG qui prend plus de place mais facilite les «accès en milieu de mots».
Il y a pas mal de doc et d'articles sur ce genre d'approche (citeseer et google scholar par exemple).

[souviron34]

je n'ai pas lu les aticles pointés, mais une idée comme ça, avec ta condition :

Envoyé par floopi51

dans un "dictionnaire" figé c'est à dire que les données dans lesquelles la recherche est faite reste inchangées d'une exécution à une autre.

et si tu disposes d'un tant soit peu de mémoire

Un tableau 2D de 26 cases

• On passe une fois dans l'ensemble du dico
• Pour chaque lettre rencontrée, on stocke dans le tableau à l'indice correspondant la position en 2ième dimension

Ensuite, pour chercher une sous-chaine, on va directement à la première lettre. Puis pour chaque possiiblité, on regarde avec la deuxième (par exemple avec une recherche dichotomique dans son tableau de position). etc...

Non ??

Enfin je sais que c'est un sujet de recherche et de travail courant, donc peut-être mon idée est-elle trop nettement simpliste...

[sologne]

Bonjour,

comme tu a dis que tu recherche une "méthode", si tu peux placer tes mots dans une BDD alors ton problème peut se résoudre facilement avec une requête SQL :
Select * FROM les_mots WHERE mot like "*tu*"

C'est juste une proposition car je ne sais pas si tu as la possibilité d'utiliser une BDD.

[souviron34]

Envoyé par sologne

Bonjour,

comme tu a dis que tu recherche une "méthode", si tu peux placer tes mots dans une BDD alors ton problème peut se résoudre facilement avec une requête SQL :
Select * FROM les_mots WHERE mot like "*tu*"

C'est juste une proposition car je ne sais pas si tu as la possibilité d'utiliser une BDD.

juste pas très efficace, je pense, en termes d'optimisation...

[Trap D]

Bonjour

J'ai eu à faire ce genre de choses il y a une vingtaine d'années, avec une base de plusieurs dizaines de milliers de mots, qui ne changerait pas fréquemment.
J'ai indexé tous les mots de la base sur la premiere lettre, la seconde etc
Ce qui fait que j'ai 24 index et je recherche les chaînes comme je veux à partir de la premiere, la seconde... C'est très rapide.
Evidemment, et j'insiste, il ne faut pas que la base change tous les jours (quoique maintenant, l'indexation totale doit prendre moins d'une heure).

[kwariz]

Envoyé par Trap D

Bonjour

J'ai eu à faire ce genre de choses il y a une vingtaine d'années, avec une base de plusieurs dizaines de milliers de mots, qui ne changerait pas fréquemment.
J'ai indexé tous les mots de la base sur la premiere lettre, la seconde etc
Ce qui fait que j'ai 24 index et je recherche les chaînes comme je veux à partir de la premiere, la seconde... C'est très rapide.
Evidemment, et j'insiste, il ne faut pas que la base change tous les jours (quoique maintenant, l'indexation totale doit prendre moins d'une heure).

Bonjour,

oui, la construction d'un arbre des préfixes pour 40000 mots (je suppose d'après l'exemple du PO) tirés d'un dictionnaire français (longueur moyenne autour de 10) ne doit pas dépasser l'ordre de la minute.

[floopi51]

Merci à tous pour toutes ces pistes !
(NB : c'est bizarre je n'ai reçu aucun mail me disant qu'il y avait des réponses dans la discussions alors que j'avais coché la case.... bref).

@I_believe_in_code : j'ai aussi été très intéressée par Boyer Moore mais le soucis c'est comment gérer les données en entrée : l'algo de Boyer-Moore c'est l'outil de comparaison maintenant ce que je cherche c'est comment parcourir le "dictionnaire" de mots avec lesquels je veux comparer ma sous-chaîne.

@kwariz : effectivement j'ai trouvé des articles très intéressants sur les arbres de tri et notamment les Radix Tree (http://en.wikipedia.org/wiki/Radix_tree). J'ai même un exemple de code ici : https://github.com/agl/critbit. Par contre je ne sais pas si c'est le plus rapide. Il va falloir que je teste.....

@souviron : ta solution s'apparente un peu au Radix tree cité ci-dessus car dans chaque "node" de l'arbre on stocke des informations de position et des informations pour savoir quand les "mots" diffèrent.

@sologne : la solution de bdd semble effectivement la plus simple mais côté performance j'ai peur que ça ne soit pas ça.

@Trap_D : cette solution m'intéresse beaucoup. Ma base de noms dans laquelle va se faire la recherche ne va pas changer souvent. Je ne sais juste pas comment l'implémenter
Je sais que les index sont une solution très rapide de recherche et qu'ils sont utilisés dans les moteurs de recherche du web. J'aimerai beaucoup implémenter cette solution. Pourriez vous me donner des pistes pour comment construire l'index ?

Merci.

[floopi51]

Envoyé par Trap D

Bonjour

J'ai eu à faire ce genre de choses il y a une vingtaine d'années, avec une base de plusieurs dizaines de milliers de mots, qui ne changerait pas fréquemment.
J'ai indexé tous les mots de la base sur la premiere lettre, la seconde etc
Ce qui fait que j'ai 24 index et je recherche les chaînes comme je veux à partir de la premiere, la seconde... C'est très rapide.
Evidemment, et j'insiste, il ne faut pas que la base change tous les jours (quoique maintenant, l'indexation totale doit prendre moins d'une heure).

cette solution m'intéresse beaucoup. Ma base de noms dans laquelle va se faire la recherche ne va pas changer souvent. Je ne sais juste pas comment l'implémenter
Je sais que les index sont une solution très rapide de recherche et qu'ils sont utilisés dans les moteurs de recherche du web. J'aimerai beaucoup implémenter cette solution. Pourriez vous me donner des pistes pour comment construire l'index ?

[floopi51]

Envoyé par kwariz

Bonjour,

oui, la construction d'un arbre des préfixes pour 40000 mots (je suppose d'après l'exemple du PO) tirés d'un dictionnaire français (longueur moyenne autour de 10) ne doit pas dépasser l'ordre de la minute.

Bonjour,

je vais peut être paraître ignorante mais c'est quoi l'exemple du PO ?

Merci.

[kwariz]

Envoyé par floopi51

Bonjour,

je vais peut être paraître ignorante mais c'est quoi l'exemple du PO ?

Merci.

Le PO c'est toi
L'exemple que tu donnes ("tu" -> turquoise, tortue) me laisse penser que tu vas manipuler des noms communs d'un dictionnaire. Ma seconde idée basée sur la taille me laissait penser une liste de communes (40000 ~ le nombre de communes en France).
Dans les deux cas, 40000 mots c'est peanuts (si les mots ont une longueur d'une ou de dizaine de lettres tirées d'un alphabet d'une cinquantaine de symboles).

Par curiosité que contient ton dico ?

[floopi51]

Envoyé par kwariz

Le PO c'est toi
L'exemple que tu donnes ("tu" -> turquoise, tortue) me laisse penser que tu vas manipuler des noms communs d'un dictionnaire. Ma seconde idée basée sur la taille me laissait penser une liste de communes (40000 ~ le nombre de communes en France).
Dans les deux cas, 40000 mots c'est peanuts (si les mots ont une longueur d'une ou de dizaine de lettres tirées d'un alphabet d'une cinquantaine de symboles).

Par curiosité que contient ton dico ?

Gagné c'est bien les communes de France ;o) auquel j'ajoute les noms de régions et département.
Je veux implémenter un outil de recherche qui suggère au fur et à mesure les noms de communes/département/région qui "match" ce que tape l'utilisateur.

Puisque que tu es là : je comprend totalement le principe d'un index pour retrouver rapidement les noms (bien que je ne sache pas comment l'impléméneter ) mais conviendra-t-il si je veux suggérer les noms de communes qui ne contiennent que partiellement ce que l'utilisateur tape ? (ex : l'utilisateur tape Vienne, je donne comme réponse Vienne mais aussi Cenon-sur-Vienne)

[kwariz]

Envoyé par floopi51

Gagné c'est bien les communes de France ;o) auquel j'ajoute les noms de régions et département.
Je veux implémenter un outil de recherche qui suggère au fur et à mesure les noms de communes/département/région qui "match" ce que tape l'utilisateur.

Puisque que tu es là : je comprend totalement le principe d'un index pour retrouver rapidement les noms (bien que je ne sache pas comment l'impléméneter ) mais conviendra-t-il si je veux suggérer les noms de communes qui ne contiennent que partiellement ce que l'utilisateur tape ? (ex : l'utilisateur tape Vienne, je donne comme réponse Vienne mais aussi Cenon-sur-Vienne)

Ça va dépendre de tes utilisateurs, mais si tu veux proposer des suggestions je dirais que la liste doit contenir en premier les matchs exacts suivis des matchs partiels. Mais apparemment tu fais une recherche multi champs.
Quel est le cadre de ton projet ?

[floopi51]

Envoyé par kwariz

Ça va dépendre de tes utilisateurs, mais si tu veux proposer des suggestions je dirais que la liste doit contenir en premier les matchs exacts suivis des matchs partiels. Mais apparemment tu fais une recherche multi champs.
Quel est le cadre de ton projet ?

Non je fais une recherche sur un seul champ dans lequel l'utilisateur peut entrer un nom de commune, département ou région.
Je travaille sur une application mobile (iOS / android).

Saurais-tu m'expliquer ce que TRAP-D entend par indexer les noms sur leur première lettre puis leur deuxième etc ?

[kwariz]

Envoyé par floopi51

Non je fais une recherche sur un seul champ dans lequel l'utilisateur peut entrer un nom de commune, département ou région.

Je suppose que tu as une chaîne du genre : "Vienne, Isère, Rhône-Alpes"
Il s'agit bien de trois données concaténées en une chaîne.
Comment vas-tu gérer les doublons ? Par exemple un user tape Loire, tu commences par toutes les communes contenant "loire", suivies de toutes les communes dont le département contient "loire", suivies de toutes les communes de la région Pays de la Loire ...
Le plus simple est de ne rien faire ... le pourquoi suit :

Envoyé par floopi51

Je travaille sur une application mobile (iOS / android).

OK, cela signifie que tu vas essayer de créer un truc le plus compact possible. Tu pourras utiliser un AutoCompleteTextView pour l'affichage. Tu ne vas pas afficher la liste complète des communes qui matchent, ou alors seulement par morceau, donc une solution qui permet de renvoyer la liste par morceau serait idéale.
Cela m'amène à penser que la solution la plus adaptée à ton cas serait l'utilisation d'une db light (sqlite ?), mais ce serait intéressanr de poser la question sur le forum approprié.

Envoyé par floopi51

Saurais-tu m'expliquer ce que TRAP-D entend par indexer les noms sur leur première lettre puis leur deuxième etc ?

Bah, le plus simple est qu'il t'explique lui-même. Mais j'imagine qu'il s'agit en gros de disposer d'un fichier (ou tableau ou ...) et les index seront d'autres fichiers (ou tableaux ou ...) qui vont lister les positions des mots dans le premier fichier (...) qui correspondent au critère, par exemple INDEX[2]['T'] listera les positions de tous les mots dans le premier fichier qui ont en deuxième position la lettre t. Si la longueur maximum de tes chaînes est L, que ton alphabet contient A caractères alors tu auras A*L listes.
Mais bon attend l'explication de trap-d pour bien comprendre.

[floopi51]

Envoyé par kwariz

Je suppose que tu as une chaîne du genre : "Vienne, Isère, Rhône-Alpes"
Il s'agit bien de trois données concaténées en une chaîne.
Comment vas-tu gérer les doublons ? Par exemple un user tape Loire, tu commences par toutes les communes contenant "loire", suivies de toutes les communes dont le département contient "loire", suivies de toutes les communes de la région Pays de la Loire ...
Le plus simple est de ne rien faire ... le pourquoi suit :

Dans le fichier qui va servir à la recherche, je vais mettre uniquement les noms des départements, les noms des communes et les noms des régions "en vrac", c'est à dire sans relation de cette commune est dans ce département ou ce département est dans cette région. Je vais créer un fichier qui sera un fichier de recherche uniquement pour permettre une recherche très rapide pour un rendu meilleur pour l'utilisateur.

Envoyé par kwariz

OK, cela signifie que tu vas essayer de créer un truc le plus compact possible. Tu pourras utiliser un AutoCompleteTextView pour l'affichage. Tu ne vas pas afficher la liste complète des communes qui matchent, ou alors seulement par morceau, donc une solution qui permet de renvoyer la liste par morceau serait idéale.
Cela m'amène à penser que la solution la plus adaptée à ton cas serait l'utilisation d'une db light (sqlite ?), mais ce serait intéressanr de poser la question sur le forum approprié.

Le résultat sera affiché dans un tableau cliquable en dessous du champ de recherche. L'utilisateur cliquera sur le résultat qui correspond à sa recherche. Je ne vais pas utiliser un AutoCompleteTextView pour renvoyer tous les résultats.
Le problème de la db light c'est que si ma base de données est grosse, j'ai peur que les requêtes soient longues pour la simple recherche de nom : je vais avoir une db bien sûre mais elle contiendra bien plus d'infos que simplement les noms de communes ou départements ou régions. Je veux séparer la recherche pour la suggestion des noms de la base de données qui contient toutes les infos.

Envoyé par kwariz

Bah, le plus simple est qu'il t'explique lui-même. Mais j'imagine qu'il s'agit en gros de disposer d'un fichier (ou tableau ou ...) et les index seront d'autres fichiers (ou tableaux ou ...) qui vont lister les positions des mots dans le premier fichier (...) qui correspondent au critère, par exemple INDEX[2]['T'] listera les positions de tous les mots dans le premier fichier qui ont en deuxième position la lettre t. Si la longueur maximum de tes chaînes est L, que ton alphabet contient A caractères alors tu auras A*L listes.
Mais bon attend l'explication de trap-d pour bien comprendre.

Je vais attendre sa réponse mais déjà tu as éclairci un peu les choses.
Merci !

[kwariz]

Envoyé par floopi51

[...]
Le résultat sera affiché dans un tableau cliquable en dessous du champ de recherche. L'utilisateur cliquera sur le résultat qui correspond à sa recherche. Je ne vais pas utiliser un AutoCompleteTextView pour renvoyer tous les résultats.
Le problème de la db light c'est que si ma base de données est grosse, j'ai peur que les requêtes soient longues pour la simple recherche de nom : je vais avoir une db bien sûre mais elle contiendra bien plus d'infos que simplement les noms de communes ou départements ou régions. Je veux séparer la recherche pour la suggestion des noms de la base de données qui contient toutes les infos.
[...]

Faut voir, mais dupliquer les données est à mon avis à implémenter uniquement si le gain est réel sinon ça complique les choses. Utiliser une db apporte de nombreux avantages, mais bon poser la question dans un un forumeur ayant de l'expérience dans ce genre de dev te sera de meilleur conseil

[floopi51]

Envoyé par kwariz

Faut voir, mais dupliquer les données est à mon avis à implémenter uniquement si le gain est réel sinon ça complique les choses. Utiliser une db apporte de nombreux avantages, mais bon poser la question dans un un forumeur ayant de l'expérience dans ce genre de dev te sera de meilleur conseil

Ca ne complique pas forcément car j'ai des données plutôt statique : les noms des communes, départements et régions. Ca je l'embarque dans l'application dès le départ. Les noms seuls, ça n'est pas très gros.
Et j'ai des infos qui changent dans le temps pour les communes, département ou régions : ça, l'application le charge dans une base de donnée de l'appli depuis internet une première fois au premier démarrage puis quand je lui dis qu'il y a un update à faire.

[Trap D]

Salut

Mes données étaient rangées dans un gros fichier codé, (ça n'a aucune importance pour le traitement).
Je faisais un tri alphabétique à partir de la première lettre, j'obtenais un premier index, puis un tri alphabétique à partir de la deuxième lettre etc. Les index renvoyaient à l'offset du mot dans le fichier. Pour accélérer encore la recherche, pour chaque index, je sauvegardais un tableau où étaient indiqués les offset dans l'index du premier mot débutant par a, par b pac c...
Je trouvais ensuite les mots par une simple recherche dichotomique avec dejà 2 bornes correctes.