Algorithme d'auto complétion

Bonsoir,
je cherche des infos sur ce sujet. Je ne sais pas par où commencer pour faire quelque chose d'efficace.

J'ai des références ici, je vais voir cela.

Bonjour,

J'ai eu ce même problème à résoudre.

Tu trouvera une solution ici...
arbre.py

Le principe est de construire un dictionnaire { préfixé : suffixe, ... }
En donnant une liste de mot à arbre.py

La construction est lente mais l'auto complémentation est rapide.

Si je devais le refaire, j'utiliserai C pour faire un module se basant sur des arbres binaires ou autre type d'algorithme similaire.

Citation:

Envoyé par vincent.mbg

Tu trouvera une solution ici...
arbre.py

Merci. :ccool: Je vais regarder cela cette semaine.

Citation:

Envoyé par vincent.mbg

La construction est lente mais l'auto complémentation est rapide.

Si je devais le refaire, j'utiliserai C pour faire un module se basant sur des arbres binaires ou autre type d'algorithme similaire.

Dans ce cas, il faudrait ensuite voir comment communiquer le résultat à Python via Cython. Jamais fait.

Il faut voir ce que tu entends par lent. La construction est-elle statique, ie faite une fois pour toute ? Si c'est la cas, je ne vois pas le souci. Ce qui compte c'est d'avoir des réponses rapides.

Je reposterais ici une fois que j'aurais parcouru ton code.

De nouveau merci :ccool: car ta solution me convient. Je vais utiliser ton script pour créer le dictionnaire des concordances pour ensuite le stocker via pickle par exemple.

Question licence, cela te gêne si je cite juste un lien vers cette page pour indiquer ton aide ?

Question licence, le programme qui utilisera le scripte arbre.py devra également être redistribué sous licence GNU (GPL). Tu dois également laisser la ligne

Copyright 2009, 2010 Vincent Maillol Benoît Gaëtan

Si tu apportes des modifications, tu dois ajouter la ligne.
Copyright 2010 ton prénom, ton nom

Je crois que tu dois mettre la liste des modifications apportées mais je suis pas sûr.

En fait, je pense que je vais enrichir ton code pour qu'il fournisse la liste des mots possibles.

Je reposterais ici.

Citation:

Dans ce cas, il faudrait ensuite voir comment communiquer le résultat à Python via Cython. Jamais fait.

J'avais écrit ce module en C ici mais il fallait que les personnes
qui installe le soft est un compilateur pour compiler l'extension. Le code C était 10 fois plus rapide que le code python mais soufrait de bug. De plus ça ne réglait pas le fait que le temps de création d'un dictionnaire augment de manière exponentielle en fonction du nombre de mot à découper. :aie:

Citation:

Il faut voir ce que tu entends par lent. La construction est-elle statique, ie faite une fois pour toute ? Si c'est la cas, je ne vois pas le souci. Ce qui compte c'est d'avoir des réponses rapides.

Oui le problème viens d'une application dont l'apport de nouveau mots serait plus important que l'utilisation de la complémentation. L'algorithme ne serait pas adapté...

Citation:

En fait, je pense que je vais enrichir ton code pour qu'il fournisse la liste des mots possibles.

Je reposterais ici.

Ceci devrait être un bon début
Code:

1 2 mots_possibles = [ for mot in liste_de_mot if mot.starswich( prefix ) and mot != prefix ]
Bon code

Bonsoir,

Ce post m'a inspiré pour écrire un implémentation d'un Trie en Python. La voici, si cela intéresse quelqu'un:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 from collections import defaultdict from itertools import chain class Trie(object): def __init__(self, items=()): self.__data = defaultdict(Trie) self.__item = None self.__len = 0 self.update(items) def update(self, items): for item in items: self.add(item) def add(self, item): if item not in self: n = self for e in item: n.__len += 1 n = n.__data[e] n.__item = item n.__len += 1 def __len__(self): return self.__len def __getitem__(self, item): n = self for e in item: if e in n.__data: n = n.__data[e] else: return Trie() return n def __contains__(self, item): t = self[item] return t.__item == item def __iter__(self): return chain( () if self.__item is None else (self.__item,), *self.__data.itervalues()) def sorted(self): return chain( () if self.__item is None else (self.__item,), *(self.__data[k] for k in sorted(self.__data))) def __delitem__(self, item): t = self[item] if t.__len > 0: n = self for e in item: n.__len -= t.__len n = n.__data[e] n.__data = defaultdict(Trie) n.__item = None n.__len = 0
L'interface est un mix entre l'interface d'un dictionnaire et d'un ensemble:
t = Trie(seq) <-- crée un trie et y ajoute les mots de la séquence
t.update(seq) <-- ajoute les mots de la sequence au Trie
t.add(mot) <-- ajoute mot au Trie
len(t) <-- nombre de mots dans le trie
iter(t) (ou for x in t) <-- itère sur les mots de t (non trié)
t.sorted() <-- itération triée sur t (comme sorted(t) mais normalement plus rapide, en tout cas si le trie est de grande taille)
mot in t <-- test d'appartenance
t["prefix"] <-- sous-trie de t dont les mots commencent par "prefix"; cette méthode (__getitem__) est la raison d'être du trie.
On peut donc écrire par exemple: for mot in t["prefix"].sorted().
del t["prefix"] <-- suppression de tous les mots commençant par "prefix".

Attention toutefois, les sous-tries ne doivent pas être modifiés directement, les méthodes add, update et __del__ ne doivent être appelées que sur le trie racine.

Les "mots" ne doivent pas forcément être des strings; cela peut être n'importe quelle type de séquence, du moment que ses éléments sont utilisables comme clés dans un dictionnaire..

Va falloir que je teste cela. Je ferais ceci la semaine prochaine.

Bah te fatigue pas, c'est pas super efficace en réalité... Il y a quelques propriétés intéressantes, comme pouvoir supprimer efficacement tous les mots commençant par un préfixe donné, mais cela t'est sans doute inutile. Cela pourrait être efficace si les mots sont très longs (plusieurs centaines de caractères) mais cela n'est pas ton cas non plus je pense...

Voir ici la suite de ce post.