Optimiser la recherche dans un dico de 25k/mots

**Maf77** · 02/08/2011, 17h11

Bonjour,

avec un amis, on est à la recherche d'optimisation pour requeter un dictionnaire de 25.000 mots.
Bon, ce qu'on a fait:
-On charge le dico à l'initialisation de notre jeu XNA dans une List<string>
-On va requeter le dico à l'aide de LINQ très souvent pour trouver si un mot a matché de la sorte:
t.ListOfWord est notre List<string> de 25k mots

Code C# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
var chars = t.ListOfWord.Where(o => o.ToUpper()
                                     .StartsWith(word) && o.Length > word.Length)
                                     .Select(o => 
                                             o.Substring(word.Length, 1))
                                     .Distinct()
                                     .ToList();

Cette requète étant horriblement long à effectuer, nous vous demandons si il y a une autre manière pour faire une recherche bien plus optimisée sur une liste ou toute autre structure adaptée?

Cordialement,
Maf77

ps1: List.Find n'existe pas en WP7
ps2: Google fait ca avec plusieurs millions de mot en AJAX!

**tomlev** · 02/08/2011, 17h26

Déjà tu peux utiliser StringComparison.CurrentCultureIgnoreCase plutôt que ToUpper.

Remplace :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

o.ToUpper().StartsWith(word)

Par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

o.StartsWith(word, StringComparison.CurrentCultureIgnoreCase)

ça fera pas une différence radicale mais bon...

En fait, si tu veux vraiment optimiser, le mieux est d'utiliser une base de données avec un index sur la colonne. Ce sera nettement plus efficace qu'une recherche linéaire.

Sinon il y a aussi des moteurs de recherche textuelle, genre Lucene.NET, mais j'ai jamais utilisé donc je sais pas trop comment ça marche

**SaumonAgile** · 02/08/2011, 18h15

Un Dictionary sera plus efficace pour la recherche d'une clé.

Plus généralement, toute structure basée sur un arbre plutot qu'une liste sera plus efficace en termes de recherche. Plus précisement un trie sera adapté dans ton cas: http://fr.wikipedia.org/wiki/Trie_(informatique)

**Skyounet** · 02/08/2011, 18h28

Je suis d'accord avec l'utilise du Dictionnaire.

Sinon tu aurais la methode FirstOrDefault qui ferait en sorte que la requete s'arreterait au premier resultat trouve (alors que Where parcours tout).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

t.ListOfWord.FirstOrDefault(w => w.Equals(word, StringComparison.CurrentCultureIgnoreCase)

Parce que si je me trompe pas

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

.StartsWith(word) && o.Length > word.Length)

Ca equivaut a un == non ?

**Immobilis** · 02/08/2011, 19h10

Salut,

Cette recherche se fait sur le téléphone? Tu prends en compte les accents? Tu cherches toujours à partir du début du mot? Y aura-t-il plus de mots?

A+

**SaumonAgile** · 02/08/2011, 19h52

Envoyé par Skyounet

Parce que si je me trompe pas

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

.StartsWith(word) && o.Length > word.Length)

Ca equivaut a un == non ?

Ca équivaut à "commence par word mais n'est pas égal à word" à mon avis

**Skyounet** · 02/08/2011, 20h15

Envoyé par SaumonAgile

Ca équivaut à "commence par word mais n'est pas égal à word" à mon avis

Pfiou j'avais vu ...Length == ...Length

Oublie ce que j'ai ecrit Maf77.

**Maf77** · 02/08/2011, 20h35

Merci pour vos réponses aussi rapide!!! C'est un réel plaisir d'avoir cette communauté!!!
Alors, commençons:
Merci pour le

Code C# :

Sélectionner tout - Visualiser dans une fenêtre à part

o.StartsWith(word, StringComparison.CurrentCultureIgnoreCase)

Et oui, ca n'a pas amélioré grandement, mais c'est toujours ça!

Ensuite, une BDD n'est possible que sous Mango avec SQLite =( ça me pose problème vu le peu qui y sont.
le

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

StartsWith("toto")

équivaut à l'expression régulière

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

^toto

donc oui, seulement débutant par.

J'ai vu que Lucene à fait du LINQ avec sa librairie, mais cela augmenterait les recherches sur une liste?

Pour l'utilisation du dictionnaire je ne vois pas l'utilité.
Je m'explique, je recherche à trouver les occurences matchant le peu de lettres que j'ai. Ensuite, faire un Random sur ces occurrences afin de prendre la lettre suivante: Cela servira à l'utilisateur pour compléter le mot!
Donc avoir une clé correspondante à chaque mot.... Je vois pas le but.

Ce code est exécuté sur un WP7.
Je ne prends pas en compte les accents car (je ne l'avais pas dit, excusez moi) j'utilise un dictonnaire anglophone.
Oui, je cherche à partir du début du mot :-)
Plus de mot dans le dico? Je ne pense pas, non.

Très cordialement, et merci bcp pour votre aide,
Maf77

Invité · 02/08/2011, 21h08

Pourquoi ne pas faire une liste triée par ordre alphabétique.
Tu peux ainsi faire une recherche dichotomique (ou par interpolation).

**Maf77** · 02/08/2011, 21h12

Envoyé par meziantou

Tu peux ainsi faire une recherche dichotomique (ou par interpolation).

Oui, mais ce n'est pas ce que Linq fait? voir même Atomique il me semble.

C'est une liste triée par ordre alphabétique le dictionnaire chargé en mémoire.

Invité · 02/08/2011, 21h24

Envoyé par Maf77

"Tu peux ainsi faire une recherche dichotomique (ou par interpolation)."
Oui, mais ce n'est pas ce que Linq fait? voir même Atomique il me semble.

C'est une liste triée par ordre alphabétique le dictionnaire chargé en mémoire.

Linq ne peut pas deviner que ta liste est triée. Il ne peut donc pas faire de recherche optimisée.
Il faut que tu fasses la recherche toi même. Ce n'est tout de même pas trop compliqué.

**Maf77** · 02/08/2011, 21h34

Envoyé par meziantou

Linq ne peut pas deviner que ta liste est triée. Il ne peut donc pas faire de recherche optimisée.
Il faut que tu fasses la recherche toi même. Ce n'est tout de même pas trop compliqué.

J'ai pensé à faire 26 listes et un switch... Ca aiderait peut-être?

Invité · 02/08/2011, 21h41

par rapport à une recherche par interpolation sur une seule liste, je ne pense pas que cela fasse une grosse différence

**tomlev** · 02/08/2011, 22h09

Envoyé par Maf77

Ensuite, une BDD n'est possible que sous Mango avec SQLite =( ça me pose problème vu le peu qui y sont.

Ah oui, j'oubliais ce "détail"... pas de BDD sous WP7, j'espère qu'ils vont remédier à ça vite fait

Envoyé par Maf77

J'ai vu que Lucene à fait du LINQ avec sa librairie, mais cela augmenterait les recherches sur une liste?

Non, pas sur une liste. Je suppose que Lucene utilise une structure de données spécifique. Mais je sais pas si c'est compatible avec WP7...

Envoyé par Maf77

Je ne prends pas en compte les accents car (je ne l'avais pas dit, excusez moi) j'utilise un dictonnaire anglophone.

Il y a des mots accentués dans le dictionnaire anglophone, par exemple des mots importés du français comme "café".

Envoyé par Maf77

"Tu peux ainsi faire une recherche dichotomique (ou par interpolation)."
Oui, mais ce n'est pas ce que Linq fait? voir même Atomique il me semble.

Non, parce que Linq ne peut pas savoir que la liste est triée... il fait donc une recherche linéaire. A priori c'est le point que tu peux optimiser le plus efficacement : en utilisant une recherche dichotomique, tu peux passer d'une complexité de O(n) à une complexité de O(log n).

Sinon, SaumonAgile a mentionné l'utilisation d'un trie, c'est effectivement une bonne idée pour ce genre d'utilisation. Le temps d'accès à un noeud ne dépend que de la longueur du préfixe recherché, pas du nombre d'éléments dans le trie. Donc que tu aies un élément ou un million, ça ne change rien.

Comme je trouvais l'idée intéressante, j'ai essayé d'implémenter un Trie... J'ai fait ça un peu à l'arrache, donc je pensais que les perfs seraient pourries, mais sans même chercher à optimiser, c'est déjà beaucoup plus rapide que la recherche linéaire dans une liste (en moyenne 2000 fois plus rapide, pour un dictionnaire de 130000 mots. La recherche d'un mot prend environ 2ms au lieu de 4s

Mon implémentation est ici si ça t'intéresse
Attention, c'est pas tout à fait "sec", donc il doit rester quelques bugs... et il y a sûrement moyen d'optimiser plus

EDIT: après test, c'est aussi plus rapide que la recherche dichotomique (environ 2.2 fois pour cette masse de données)

Par contre, c'est probablement assez couteux en mémoire (pas vérifié), ce qui peut être gênant sur WP7... à tester. Si c'est trop lourd, tu peux utiliser la recherche dichotomique, c'est presque aussi rapide et ça ne coute rien en mémoire.

**Maf77** · 02/08/2011, 22h32

Nan??? Tu es sérieux? Ta fais un arbre binaire en 2min à l'arrache? Oh my god, j'ai vraiment pas le niveau!
Je vais tester ta solutions 2000fois mieux! Merci beaucoup Tomlev!

EDIT: je vois toujours pas l’intérêt d'un dictonnary

**tomlev** · 02/08/2011, 22h47

Envoyé par Maf77

Nan??? Tu es sérieux? Ta fais un arbre binaire en 2min à l'arrache?

C'est pas un arbre binaire, mais un trie... et non, je ne l'ai pas fait en 2mn

Sinon j'ai fait une petite amélioration, en utilisant un SortedDictionary pour les noeuds enfants (plutôt qu'une liste). On arrive à 4500 fois plus rapide que la recherche linéaire en moyenne... Par contre c'est au détriment de la mémoire, c'est forcément beaucoup plus gourmand à ce niveau là

EDIT: le code avec l'amélioration :
http://pastebin.com/mx9WdiYH

**tomlev** · 02/08/2011, 22h51

Envoyé par Maf77

EDIT: je vois toujours pas l’intérêt d'un dictonnary

Aucun pour ce que tu cherches à faire...

Le Trie que j'ai implémenté implémente IDictionary parce que ça semblait logique, mais j'ai aussi créé des méthodes pour rechercher ou supprimer par préfixe (FindPrefix et RemovePrefix).