Naturel, chaîne et stockage

Version imprimable

Bonsoir,
j'ai une question toute bête mais bon... Je planche, pour le moment d'un point de vue théorique, sur un module pour faire de l'auto-complétion. Une solution m'a été donnée dans ce post.

Ceci m'a donné l'idée d'une autre méthode qui consiste, dans sa première version, à construire le dictionnaire suivant :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 { 'a': ['art', 'artiste', 'article'], 'ar': ['art', 'artiste', 'article'], 'art': ['artiste', 'article'], 'artis': ['artiste', 'article'], 'artist': ['artiste'], 'artic': ['article'], 'articl': ['article'], 'w': ['when', 'who', 'whendy'], 'wh': ['when', 'who', 'whendy'], 'whe': ['when', 'whendy'], 'when': ['whendy'], 'whend': ['whendy'] }
pour la liste de mots suivante :

Code:

['art', 'artiste', 'article', 'when', 'who', 'whendy']

Le problème avec cette méthode est la répétition du stockage de chaînes de caractères. Du coup, je voudrais faire quelque chose comme ci-dessous où on utilise les index dans la liste des mots:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 { 'a': [0, 1, 2], 'ar': [0, 1, 2], 'art': [1, 2], 'artis': [1, 2], 'artist': [1], 'artic': [2], 'articl': [2], 'w': [3, 4, 5], 'wh': [3, 4, 5], 'whe': [3, 5], 'when': [5], 'whend': [5] }
L'utilisation de naturels vaut-elle le coup ?

11/05/2010, 02h17
dividee

Je ne pense pas. A moins d'une grosse bêtise dans l'implémentation, les différentes copies d'une même chaîne de caractères seront des références à une seule et même chaîne stockée en mémoire. En fait, pour cette raison il est même fort possible que ton implémentation sous forme de {'préfixe' : 'mot'} utilise moins de mémoire que la forme {'préfixe' : 'suffixe'} vu qu'il y aura plus de répétitions d'une même chaîne et donc plus d'opportunités d'aliasing (càd de références multiples pointant sur un même objet).

Je peux me tromper, il faudrait tester pour en être sûr. Mais n'est-ce pas beau quand la solution la plus simple est aussi la plus efficace ? :D
11/05/2010, 14h18
wiztricks

Salut,

Question qui me turlupine.
Pourquoi ne pas travailler directement sur la liste: ['art', 'artiste', article', when', 'who', 'whendy'] - i.e. l'utiliser en tant que 'structure de données' parcourue par... - ?

- W
11/05/2010, 18h29
rambc

Citation:

Envoyé par dividee

Je ne pense pas. A moins d'une grosse bêtise dans l'implémentation, les différentes copies d'une même chaîne de caractères seront des références à une seule et même chaîne stockée en mémoire.

La chose que j'ai omise de dire est que le dictionnaire sera créé puis stocké via Pickle.

Citation:

Envoyé par dividee

Je peux me tromper, il faudrait tester pour en être sûr.

C'est vrai. Mais là je n'ai pas trop le temps d'où ma question mais je ferais des tests quand je mettrais réellement les mains dans le cambouis...

Citation:

Envoyé par wiztricks

Pourquoi ne pas travailler directement sur la liste: ['art', 'artiste', article', when', 'who', 'whendy'] - i.e. l'utiliser en tant que 'structure de données' parcourue par... ?

Que se passera-t-il avec 100 ou 1000 mots ? L'intérêt du dictionnaire tout fait est que l'on fait appel aux procédures "rapides" de Python du type if a in dico:...

Merci pour ces remarques. Je travaillais sur ce code et celui de l'auto-complétion la semaine prochaine.

Citation:

Envoyé par wiztricks

Pourquoi ne pas travailler directement sur la liste: ['art', 'artiste', article', when', 'who', 'whendy'] - i.e. l'utiliser en tant que 'structure de données' parcourue par... - ?

Cela m'a fait penser à ceci: si la liste est triée, e.g. ['art', 'article', 'artiste', 'when', 'whendy', 'who'], il suffit de pointer sur le premier élément qui a un préfixe donné, et de parcourir ensuite la liste tant que le préfixe est identique.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 { 'a': 0, 'ar': 0, 'art': 0, 'arti': 1, 'artic': 1, 'articl': 1, 'article': 1, 'artis': 2, 'artist': 2, 'artiste': 2, 'w': 3, 'wh': 3, 'whe': 3, 'when': 3, 'whend': 4 'whendy': 4 'who': 5 }
(j'ai considéré qu'un mot est préfixe de lui-même, mais ce n'est qu'un choix)

Voici une implémentation de ce que je décris dans mon post précédent:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Completer(object):
    def __init__(self, words):
        self._indexes = {}
        self._words = list(words)
        self._words.sort()
        for idx, word in enumerate(self._words):
            for i in xrange(len(word)+1):
                self._indexes.setdefault(word[:i], idx)
 
    def __getitem__(self, prefix):
        if prefix in self._indexes:
            idx = self._indexes[prefix]
            words = self._words
            while idx < len(words) and words[idx].startswith(prefix):
                yield words[idx]
                idx += 1

Code:

1
2
3
4
5
>>> c = Completer(['art', 'artiste', 'article', 'when', 'who', 'whendy'])
>>> list(c['wh'])
['when', 'whendy', 'who']
>>> list(c['art'])
['art', 'article', 'artiste']

12/05/2010, 12h15
rambc

Citation:

Envoyé par dividee

il suffit de pointer sur le premier élément qui a un préfixe donné, et de parcourir ensuite la liste tant que le préfixe est identique

Je vais ordonner la liste de mots et pour un préfixe donné garder le 1er indice et le dernier indice possible. C'est plus simple. Je posterais un truc ce soir ou demain.

Pour ta classe, ce n'est pas trop dans l'esprit de ce que je vais faire car j'aurais des données statiques. Ceci étant dit, je me dis en tapant ces lignes qu'en fait ta classe pourrait permettre de proposer une auto-complétion dynamique : par exemple, pour compléter des noms de variables ou autres friandises. Je garde cela sous le coude.

Finalement, j'ai fait ceci :

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
def dicoForAutoComplete(listOfWords, depth = 3):
# We clean double words and then sort the list.
    listOfWords = list(set(listOfWords))
    listOfWords = sorted(listOfWords)
 
# We build the dico.
    theDico = { 'words': listOfWords,
                'completions' : {}
              }
 
    for i_word, oneWord in enumerate(listOfWords):
        for i in range( min(depth,len(oneWord)) ):
            onePrefix = oneWord[:i+1]
 
            if onePrefix in theDico['completions']:
                theDico['completions'][onePrefix][1] = i_word + 1
            else:
                theDico['completions'][onePrefix] = [i_word, i_word + 1]
 
    return theDico
 
 
def listOfMatchingWords(dicoForAutoComplete, prefixToFind):
    if prefixToFind in dicoForAutoComplete['completions']:
        firstIndex = dicoForAutoComplete['completions'][prefixToFind][0]
        lastIndex = dicoForAutoComplete['completions'][prefixToFind][1]
 
        return dicoForAutoComplete['words'][ firstIndex: lastIndex ]
 
 
if __name__ == "__main__":
    keywords = [ 'article',
                 'artiste',
                 'art',
                 'when',
                 'who',
                 'whendy',
                 'bar',
                 'barbie',
                 'barbier',
                 'bar',
                 'barré'
               ]
 
    print("keywords")
    print(keywords)
 
    dicoForCompletions = dicoForAutoComplete( listOfWords = keywords,
                                              depth = 4 )
 
    print()
    print("dicoForCompletions")
    import pprint
    pp = pprint.PrettyPrinter(indent = 0)
    pp.pprint(dicoForCompletions)
 
    print()
    print("Searching for 'bar'")
    print(listOfMatchingWords(dicoForCompletions, 'bar'))

Ceci renvoie :

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
keywords
['article', 'artiste', 'art', 'when', 'who', 'whendy', 'bar', 'barbie', 'barbier', 'bar', 'barré']
 
dicoForCompletions
{'completions': {'a': [0, 3],
               'ar': [0, 3],
               'art': [0, 3],
               'arti': [1, 3],
               'b': [3, 7],
               'ba': [3, 7],
               'bar': [3, 7],
               'barb': [4, 6],
               'barr': [6, 7],
               'w': [7, 10],
               'wh': [7, 10],
               'whe': [7, 9],
               'when': [7, 9],
               'who': [9, 10]},
'words': ['art',
         'article',
         'artiste',
         'bar',
         'barbie',
         'barbier',
         'barré',
         'when',
         'whendy',
         'who']}
 
Searching for 'bar'
['bar', 'barbie', 'barbier', 'barré']

Toute critique est la bienvenue.

13/05/2010, 00h22
Zavonen

Pour éviter les duplications, j'aurais utilisé un arbre.
Premier niveau la lettre a et éventuellement d'autres qui correspondent aux débuts possibles de mots.
Second niveau du sous-arbre de nœud 'a' la lettre 'r'. Et ainsi de suite. La complétion doit proposer à chaque déplacement dans l'arbre toutes les branches complètes du sous-arbre correspondant au nœud où on se trouve.
En python, comme en lisp et tous les langages manipulant les listes, les arbres sont représentables par des listes.
13/05/2010, 09h57
rambc

Citation:

Envoyé par Zavonen

Pour éviter les duplications, j'aurais utilisé un arbre.

J'y ai pensé dès le départ. J'ai un peu peur du temps de recherche lors de la recherche dans l'arbre. La méthode ci-dessus, peu élégante je le concède, est directe à utiliser et fait appel aux routine Python de recherche de clés.
13/05/2010, 10h35
dividee

Citation:

Envoyé par Zavonen

En python, comme en lisp et tous les langages manipulant les listes, les arbres sont représentables par des listes.

Un arbre certes, mais ton allusion à lisp fait penser à un arbre binaire et ici un arbre n-aire conviendrait mieux. On peut certes toujours encoder un arbre n-aire sous forme d'un arbre binaire, mais le temps d'exécution s'en ressentirait.

Le trie que j'avais implémenté ici est effectivement un arbre, mais la liste des sous-arbre d'un noeud donné est représenté par un dictionnaire, pour des raisons de performances. La solution dans ce post-ci sera plus efficace en terme de temps d'exécution en tout cas; pour ce qui est de l'utilisation mémoire il faudrait faire quelques tests...
13/05/2010, 10h47
rambc

Citation:

Envoyé par dividee

La solution dans ce post-ci sera plus efficace en terme de temps d'exécution en tout cas

C'est l'intuition que j'ai.

Citation:

Envoyé par dividee

pour ce qui est de l'utilisation mémoire il faudrait faire quelques tests...

Dans le cadre d'auto-complétion d'un langage de programmation, je ne pense pas qu'il y ait énormément de mots à compléter.
13/05/2010, 14h24
Zavonen

Citation:

Un arbre certes, mais ton allusion à lisp fait penser à un arbre binaire et ici un arbre n-aire conviendrait mieux.

Pas du tout!
http://www.google.fr/url?sa=t&source...96a_O-O1L2GuXQ
Cela dit, les arguments concernant l'efficacité sont peut-être fondés, il faudrait faire des tests.

D'accord j'ai été un peu vite en parlant d'arbre binaire, mais l'inefficacité est bien réelle.

Quelques tests rapides semblent confirmer que la technique de rambc est à la fois plus rapide et moins gourmande en mémoire que mon implémentation de Trie (qui n'est pas vraiment optimisée) pour une liste de 330 000 mots français. Le rapport est d'environ 3 pour 1 pour l'utilisation mémoire et plus que cela encore pour la vitesse d'exécution. La solution de rambc a, de plus, l'avantage de la simplicité.

rambc, en ce qui concerne l'implémentation, elle me semble bien. Même si, personnellement, je préfère une interface objet pour un conteneur plutôt qu'une interface de type ADT, c'est plus dans le style de Python. En particulier le dico 'theDico' semble n'être là que pour créer un namespace séparé, ce qui est exactement ce que fait une classe...

La façon de construire les intervalles est particulièrement bien pensée et efficace.

Une petite simplification:
Code:

1 2 3 4 def listOfMatchingWords(dicoForAutoComplete, prefixToFind): if prefixToFind in dicoForAutoComplete['completions']: firstIndex, lastIndex = dicoForAutoComplete['completions'][prefixToFind] return dicoForAutoComplete['words'][ firstIndex: lastIndex ]
Ce que j'aurais écris comme version "OO", avec des fonctionnalités identiques:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Completer(object): def __init__(self, words, depth=3): self._indexes = {} self._words = list(words) self._words.sort() for idx, word in enumerate(self._words): for i in xrange(min(depth, len(word))): prefix = word[:i+1] if prefix in self._indexes: self._indexes[prefix][1] = idx+1 else: self._indexes[prefix] = [idx, idx+1] def __getitem__(self, prefix): if prefix in self._indexes: start,stop = self._indexes[prefix] return self._words[start:stop]
Maintenant,
1) pourquoi ne pas considérer la chaîne vide comme un préfixe de toutes les chaînes ? Juste pour avoir un maximum de généralité, même si l'auto-complétion n'est pas déclenchée automatiquement cela permet toujours à l'utilisateur de faire Ctrl+Espace (ou le raccourci que tu comptes utiliser) et d'avoir la liste complète des mots-clés, sans devoir gérer ce cas différemment.

2) pourquoi se limiter à une profondeur donnée ? Cela me semble bizarre dans le cadre d'une auto-complétion; si l'utilisateur tape une lettre de plus l'autocomplétion ne fonctionne plus ? Je comprends que cela évite de perdre beaucoup de mémoire à stocker des préfixes qui n'appartiennent qu'à un ou deux mots-clés, mais on pourrait quand-même offrir la possibilité en simulant les entrées qui manquent.

Si un préfixe ne se trouve pas dans le dictionnaire, la fonction de recherche trouve le plus grand "sous-préfixe" qui s'y trouve et effectue une simple filtrage sur les mots résultants (on pourrait faire une recherche dichotomique avec le module bisect mais je n'ai pas été jusque là).

Du coup, la profondeur donnée (depth) n'influe pas sur l'aspect fonctionnel, il permet simplement un compromis entre utilisation mémoire et performances.

Dans le code ci-dessous, j'ai été plus loin en supprimant du dictionnaire les préfixes qui appartiennent à moins de min_width mots, ce qui me semble un critère plus intéressant
pour choisir entre utilisation mémoire et performances, mais cela allonge le temps de construction du dictionnaire, ce qui n'est pas un problème pour toi si tu comptes "pickler" le résultat.
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 class Completer(object): def __init__(self, words, min_width=5, max_depth=12): self._indexes = {} self._words = list(words) self._words.sort() for idx, word in enumerate(self._words): for i in xrange(1 + min(max_depth, len(word))): prefix = word[:i] if prefix in self._indexes: self._indexes[prefix][1] = idx+1 else: self._indexes[prefix] = [idx, idx+1] # suppress prefixes contained in less than min_width words for k,(v1,v2) in self._indexes.items(): if v2-v1 < min_width: del self._indexes[k] def __getitem__(self, prefix): if prefix in self._indexes: start,stop = self._indexes[prefix] return self._words[start:stop] else: p = prefix while p not in self._indexes: p = p[:-1] start,stop = self._indexes[p] return [w for w in self._words[start:stop] if w.startswith(prefix)]

Citation:

Envoyé par dividee

rambc, en ce qui concerne l'implémentation, elle me semble bien. Même si, personnellement, je préfère une interface objet pour un conteneur plutôt qu'une interface de type ADT, c'est plus dans le style de Python. En particulier le dico 'theDico' semble n'être là que pour créer un namespace séparé, ce qui est exactement ce que fait une classe...

En fait, je vais partir d'une liste de mots clés fixés, par exemple les mots clés de langages comme Python, LaTeX, le langage que j'ai inventé dans le cadre de mon projet... La 1ère fonction créera le dictionnaire qui sera stocké via Pickle. Ce dictionnaire sera ensuite utiliser par l'éditeur qui aura dans son code la 2nde fonction qui va à la recherche de préfixes. C'est pour cela que ce fonctionnement me convient. De plus dans la mesure où je ne vais utiliser que des attributs sans méthode, je n'ai pas trop envie d'utiliser une classe.

Citation:

Envoyé par dividee

Une petite simplification: ...

Effectivement. Merci.

Citation:

Envoyé par dividee

1) pourquoi ne pas considérer la chaîne vide comme un préfixe de toutes les chaînes ? Juste pour avoir un maximum de généralité, même si l'auto-complétion n'est pas déclenchée automatiquement cela permet toujours à l'utilisateur de faire Ctrl+Espace (ou le raccourci que tu comptes utiliser) et d'avoir la liste complète des mots-clés, sans devoir gérer ce cas différemment.

Très bien vu !

Citation:

Envoyé par dividee

2) pourquoi se limiter à une profondeur donnée ? Cela me semble bizarre dans le cadre d'une auto-complétion; si l'utilisateur tape une lettre de plus l'autocomplétion ne fonctionne plus ? Je comprends que cela évite de perdre beaucoup de mémoire à stocker des préfixes qui n'appartiennent qu'à un ou deux mots-clés, mais on pourrait quand-même offrir la possibilité en simulant les entrées qui manquent.

Cela n'est pas gênant, il suffit de nourrir la fonction avec une profondeur de 99 par exemple. Cela me coûtait rien à programmer donc je l'ai mis.

Citation:

Envoyé par dividee

Si un préfixe ne se trouve pas dans le dictionnaire, la fonction de recherche trouve le plus grand "sous-préfixe" qui s'y trouve et effectue une simple filtrage sur les mots résultants (on pourrait faire une recherche dichotomique avec le module bisect mais je n'ai pas été jusque là).

Seconde très bonne idée. Pour bisect, j'attendrais la semaine prochaine pour zieuter ça.

Citation:

Envoyé par dividee

Dans le code ci-dessous, j'ai été plus loin en supprimant du dictionnaire les préfixes qui appartiennent à moins de min_width mots, ce qui me semble un critère plus intéressant
pour choisir entre utilisation mémoire et performances, mais cela allonge le temps de construction du dictionnaire, ce qui n'est pas un problème pour toi si tu comptes "pickler" le résultat.

Pourquoi pas mais cela a un TRES gros inconvénient côté utilisateur : un comportement non uniforme. A choisir, je préfère que l'auto-complétion soit jusqu'au boutiste.

Voilà le code mis en jour.
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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 def dicoForAutoComplete(listOfWords, depth = 0): """ depth = 0 means that we build all the possible prefixes... """ # We clean double words and then sort the list. listOfWords = list(set(listOfWords)) listOfWords = sorted(listOfWords) # We calculate the maximum depth. if depth == 0: for oneWord in listOfWords: depth = max(depth, len(oneWord)-1) # We build the dico. theDico = { 'words': listOfWords, 'completions' : {} } for i_word, oneWord in enumerate(listOfWords): for i in range( min(depth,len(oneWord)) ): onePrefix = oneWord[:i+1] if onePrefix != listOfWords[i_word]: if onePrefix in theDico['completions']: theDico['completions'][onePrefix][1] = i_word + 1 else: theDico['completions'][onePrefix] = [i_word, i_word + 1] return theDico def listOfMatchingWords(dicoForAutoComplete, prefixToFind): if prefixToFind.strip() == '': return dicoForAutoComplete['words'] if prefixToFind in dicoForAutoComplete['completions']: firstIndex, lastIndex = dicoForAutoComplete['completions'][prefixToFind] return dicoForAutoComplete['words'][ firstIndex: lastIndex ] def theMissingLetters(prefix, word): return word[len(prefix):] if __name__ == "__main__": keywords = [ 'article', 'artiste', 'art', 'when', 'who', 'whendy', 'bar', 'barbie', 'barbier', 'bar', 'barré' ] print("keywords") print(keywords) dicoForCompletions = dicoForAutoComplete( listOfWords = keywords, depth = 0 ) print() print("The ORDERED list of keywords") print(dicoForCompletions['words']) """ print() print("dicoForCompletions") import pprint pp = pprint.PrettyPrinter(indent = 0) pp.pprint(dicoForCompletions) """ for pref in ['when', 'ar', '']: print() print("Searching for the prefix '" + pref + "'") print(listOfMatchingWords(dicoForCompletions, pref)) print() pref = 'art' word = 'article' print("The missing letters for the prefix '" + pref + "' and the word '" + word + "'") print(pref + '-' + theMissingLetters(pref, word))
Ce code apporte deux petites améliorations :

Le script ne propose plus "when" pour complétion de "when".
Une fonction renvoie les lettres manquantes pour compléter un préfixe dans un nom donné..

Voici ce qui est renvoyé :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 The original list of keywords ['article', 'artiste', 'art', 'when', 'who', 'whendy', 'bar', 'barbie', 'barbier', 'bar', 'barré'] The ORDERED list of keywords ['art', 'article', 'artiste', 'bar', 'barbie', 'barbier', 'barré', 'when', 'whendy', 'who'] Searching for the prefix 'when' ['whendy'] Searching for the prefix 'ar' ['art', 'article', 'artiste'] Searching for the prefix '' ['art', 'article', 'artiste', 'bar', 'barbie', 'barbier', 'barré', 'when', 'whendy', 'who'] The missing letters for the prefix 'art' and the word 'article' art-icle

14/05/2010, 17h32
dividee

Bonjour,

Citation:

Envoyé par rambc

La 1ère fonction créera le dictionnaire qui sera stocké via Pickle. Ce dictionnaire sera ensuite utiliser par l'éditeur qui aura dans son code la 2nde fonction qui va à la recherche de préfixes.

Je ne vois pas en quoi cela pose problème de pickler un objet plutôt qu'un dictionnaire. Il faudra bien sûr que la définition de la classe soit accessible quand on charge l'object "picklé", mais je ne vois pas non plus pourquoi cela serait un problème.

Citation:

Envoyé par rambc

C'est pour cela que ce fonctionnement me convient. De plus dans la mesure où je ne vais utiliser que des attributs sans méthode, je n'ai pas trop envie d'utiliser une classe.

Sans méthodes ? Ben il y en a deux, ce sont les deux fonctions dont tu parles. Le constructeur est la première fonction et la seconde la fonction de recherche (j'ai utilisé __getitem__ dans mon code car je trouve que cela donne une API sympathique).

Le constructeur ne sera pas utilisé quand l'objet est "dépicklé", mais on ne gagne rien à l'enlever non plus. Je ne sais pas si tu comptes distribuer le fichier "picklé" avec le programme, mais tu pourrais te contenter de distribuer le fichier de keywords et construire le dictionnaire (ou l'objet) à la première exécution en "picklant" le résultat pour les exécutions futures. Si le nombre de keywords ne dépasse pas quelques centaines, ce n'est sans doute même pas nécessaire, autant le reconstruire à chaque fois.

Je n'essaie pas de te convaincre à tout prix, après tout, le plus important est que tu te sentes à l'aise avec ton code. Je défends juste ma solution...

Concernant l'ajout du paramètre min_width:

Citation:

Envoyé par rambc

Pourquoi pas mais cela a un TRES gros inconvénient côté utilisateur : un comportement non uniforme. A choisir, je préfère que l'auto-complétion soit jusqu'au boutiste.

Je ne vois pas où est le comportement non uniforme. La longueur des préfixes dans le dictionnaire va certes varier mais c'est masqué à l'utilisateur par la fonction de recherche. C'est le bénéfice de l'abstraction.

Que ce soit dans ton code (un type de données abstrait constitué par un dictionnaire et deux fonctions) ou le mien (une classe), l'utilisateur n'accède pas au dictionnaire directement, mais par l'intermédiaire de la fonction de recherche. La version "objet" a pour avantage de rendre plus explicite cette encapsulation, en décourageant l'accès direct au dictionnaire (d'où l'utilisation d'un _ dans le nom de l'attribut).

La seule chose qui variera ce sont les performances, et elle seront plus homogènes avec un "min_width" qu'avec un "max_depth" (même si, en fait, dans mon code l'algorithme ne gère pas le min_width de façon optimale; au lieu de supprimer les entrées contenant moins de min_width mots, il faudrait supprimer tous ses "fils" (les préfixes plus longs)).

Enfin bon, si ton auto-complétion ne contient pas beaucoup de mots (quelques dizaines ou quelques centaines), ce n'est pas très important de toute façon; autant créer tous les préfixes. On ne va pas s'arracher les cheveux pour quelques Ko de mémoire...