Discussion :

[rambc]

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 :

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

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 :

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

['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 :

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

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 ?

[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 ?

[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

[dividee]

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 :

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

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)

[dividee]

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

Code :

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

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 :

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

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']

[rambc]

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.

[rambc]

Finalement, j'ai fait ceci :

Code :

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

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 :

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

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.

[rambc]

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.

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...

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.