Complétion#

Comparaion de plusieurs algorithmes pour implémenter un système de complétion.

Tester des idées#

Meilleur ordre pour a, ab, abc, abcd#

[2]:
from mlstatpy.nlp.completion import CompletionTrieNode
import itertools

queries = ["a", "ab", "abc", "abcd"]
for per in itertools.permutations(queries):
    trie = CompletionTrieNode.build([(None, w) for w in per])
    gain = sum(len(w) - trie.min_keystroke(w)[0] for w in per)
    print(gain, "ordre", per)
0 ordre ('a', 'ab', 'abc', 'abcd')
1 ordre ('a', 'ab', 'abcd', 'abc')
1 ordre ('a', 'abc', 'ab', 'abcd')
2 ordre ('a', 'abc', 'abcd', 'ab')
2 ordre ('a', 'abcd', 'ab', 'abc')
2 ordre ('a', 'abcd', 'abc', 'ab')
1 ordre ('ab', 'a', 'abc', 'abcd')
2 ordre ('ab', 'a', 'abcd', 'abc')
2 ordre ('ab', 'abc', 'a', 'abcd')
3 ordre ('ab', 'abc', 'abcd', 'a')
3 ordre ('ab', 'abcd', 'a', 'abc')
3 ordre ('ab', 'abcd', 'abc', 'a')
2 ordre ('abc', 'a', 'ab', 'abcd')
3 ordre ('abc', 'a', 'abcd', 'ab')
2 ordre ('abc', 'ab', 'a', 'abcd')
3 ordre ('abc', 'ab', 'abcd', 'a')
4 ordre ('abc', 'abcd', 'a', 'ab')
4 ordre ('abc', 'abcd', 'ab', 'a')
3 ordre ('abcd', 'a', 'ab', 'abc')
3 ordre ('abcd', 'a', 'abc', 'ab')
3 ordre ('abcd', 'ab', 'a', 'abc')
3 ordre ('abcd', 'ab', 'abc', 'a')
4 ordre ('abcd', 'abc', 'a', 'ab')
4 ordre ('abcd', 'abc', 'ab', 'a')

Meilleur ordre pour a, ab, abc, abcd, edf, edfh#

[3]:
queries = ["a", "ab", "abc", "abcd", "edf", "edfh"]
res = []
for per in itertools.permutations(queries):
    trie = CompletionTrieNode.build([(None, w) for w in per])
    gain = sum(len(w) - trie.min_keystroke(w)[0] for w in per)
    res.append((gain, "ordre", per))
res.sort(reverse=True)
for r in res[:30]:
    print(r)
(6, 'ordre', ('edfh', 'edf', 'abcd', 'abc', 'ab', 'a'))
(6, 'ordre', ('edfh', 'edf', 'abcd', 'abc', 'a', 'ab'))
(6, 'ordre', ('edfh', 'edf', 'abcd', 'ab', 'abc', 'a'))
(6, 'ordre', ('edfh', 'edf', 'abcd', 'ab', 'a', 'abc'))
(6, 'ordre', ('edfh', 'edf', 'abcd', 'a', 'abc', 'ab'))
(6, 'ordre', ('edfh', 'edf', 'abcd', 'a', 'ab', 'abc'))
(6, 'ordre', ('edfh', 'edf', 'abc', 'abcd', 'ab', 'a'))
(6, 'ordre', ('edfh', 'edf', 'abc', 'abcd', 'a', 'ab'))
(6, 'ordre', ('edf', 'edfh', 'abcd', 'abc', 'ab', 'a'))
(6, 'ordre', ('edf', 'edfh', 'abcd', 'abc', 'a', 'ab'))
(6, 'ordre', ('edf', 'edfh', 'abcd', 'ab', 'abc', 'a'))
(6, 'ordre', ('edf', 'edfh', 'abcd', 'ab', 'a', 'abc'))
(6, 'ordre', ('edf', 'edfh', 'abcd', 'a', 'abc', 'ab'))
(6, 'ordre', ('edf', 'edfh', 'abcd', 'a', 'ab', 'abc'))
(6, 'ordre', ('edf', 'edfh', 'abc', 'abcd', 'ab', 'a'))
(6, 'ordre', ('edf', 'edfh', 'abc', 'abcd', 'a', 'ab'))
(6, 'ordre', ('abcd', 'abc', 'edfh', 'edf', 'ab', 'a'))
(6, 'ordre', ('abcd', 'abc', 'edfh', 'edf', 'a', 'ab'))
(6, 'ordre', ('abcd', 'abc', 'edfh', 'ab', 'edf', 'a'))
(6, 'ordre', ('abcd', 'abc', 'edfh', 'ab', 'a', 'edf'))
(6, 'ordre', ('abcd', 'abc', 'edfh', 'a', 'edf', 'ab'))
(6, 'ordre', ('abcd', 'abc', 'edfh', 'a', 'ab', 'edf'))
(6, 'ordre', ('abcd', 'abc', 'edf', 'edfh', 'ab', 'a'))
(6, 'ordre', ('abcd', 'abc', 'edf', 'edfh', 'a', 'ab'))
(6, 'ordre', ('abcd', 'abc', 'edf', 'ab', 'edfh', 'a'))
(6, 'ordre', ('abcd', 'abc', 'edf', 'ab', 'a', 'edfh'))
(6, 'ordre', ('abcd', 'abc', 'edf', 'a', 'edfh', 'ab'))
(6, 'ordre', ('abcd', 'abc', 'edf', 'a', 'ab', 'edfh'))
(6, 'ordre', ('abcd', 'abc', 'ab', 'edfh', 'edf', 'a'))
(6, 'ordre', ('abcd', 'abc', 'ab', 'edfh', 'a', 'edf'))

Influence du poids#

[4]:
queries = ["actuellement", "actualité", "acte", "actes"]
weights = [1, 1, 1, 2]
total = sum(weights) * 1.0 / len(queries)
res = []
for per in itertools.permutations(zip(queries, weights)):
    trie = CompletionTrieNode.build([(None, w) for w, p in per])
    wks = [(w, p, len(w) - trie.min_keystroke(w)[0]) for w, p in per]
    gain = sum(g * p / total for w, p, g in wks)
    res.append((gain, wks))
res.sort(reverse=True)
for r in res:
    print(
        "{0:3.4} - {1}".format(r[0], " | ".join("%s p=%1.1f g=%1.1f" % _ for _ in r[1]))
    )
19.2 - actes p=2.0 g=4.0 | actuellement p=1.0 g=10.0 | acte p=1.0 g=1.0 | actualité p=1.0 g=5.0
19.2 - actes p=2.0 g=4.0 | actualité p=1.0 g=7.0 | acte p=1.0 g=1.0 | actuellement p=1.0 g=8.0
19.2 - actes p=2.0 g=4.0 | acte p=1.0 g=2.0 | actualité p=1.0 g=6.0 | actuellement p=1.0 g=8.0
19.2 - actes p=2.0 g=4.0 | actuellement p=1.0 g=10.0 | actualité p=1.0 g=6.0 | acte p=1.0 g=0.0
19.2 - actes p=2.0 g=4.0 | actualité p=1.0 g=7.0 | actuellement p=1.0 g=9.0 | acte p=1.0 g=0.0
19.2 - actes p=2.0 g=4.0 | acte p=1.0 g=2.0 | actuellement p=1.0 g=9.0 | actualité p=1.0 g=5.0
18.4 - actuellement p=1.0 g=11.0 | actes p=2.0 g=3.0 | actualité p=1.0 g=6.0 | acte p=1.0 g=0.0
18.4 - actuellement p=1.0 g=11.0 | actes p=2.0 g=3.0 | acte p=1.0 g=1.0 | actualité p=1.0 g=5.0
18.4 - actualité p=1.0 g=8.0 | actes p=2.0 g=3.0 | actuellement p=1.0 g=9.0 | acte p=1.0 g=0.0
18.4 - actualité p=1.0 g=8.0 | actes p=2.0 g=3.0 | acte p=1.0 g=1.0 | actuellement p=1.0 g=8.0
18.4 - acte p=1.0 g=3.0 | actes p=2.0 g=3.0 | actuellement p=1.0 g=9.0 | actualité p=1.0 g=5.0
18.4 - acte p=1.0 g=3.0 | actes p=2.0 g=3.0 | actualité p=1.0 g=6.0 | actuellement p=1.0 g=8.0
17.6 - actuellement p=1.0 g=11.0 | actualité p=1.0 g=7.0 | actes p=2.0 g=2.0 | acte p=1.0 g=0.0
17.6 - actuellement p=1.0 g=11.0 | acte p=1.0 g=2.0 | actes p=2.0 g=2.0 | actualité p=1.0 g=5.0
17.6 - actualité p=1.0 g=8.0 | actuellement p=1.0 g=10.0 | actes p=2.0 g=2.0 | acte p=1.0 g=0.0
17.6 - actualité p=1.0 g=8.0 | acte p=1.0 g=2.0 | actes p=2.0 g=2.0 | actuellement p=1.0 g=8.0
17.6 - acte p=1.0 g=3.0 | actuellement p=1.0 g=10.0 | actes p=2.0 g=2.0 | actualité p=1.0 g=5.0
17.6 - acte p=1.0 g=3.0 | actualité p=1.0 g=7.0 | actes p=2.0 g=2.0 | actuellement p=1.0 g=8.0
16.8 - actuellement p=1.0 g=11.0 | actualité p=1.0 g=7.0 | acte p=1.0 g=1.0 | actes p=2.0 g=1.0
16.8 - actuellement p=1.0 g=11.0 | acte p=1.0 g=2.0 | actualité p=1.0 g=6.0 | actes p=2.0 g=1.0
16.8 - actualité p=1.0 g=8.0 | actuellement p=1.0 g=10.0 | acte p=1.0 g=1.0 | actes p=2.0 g=1.0
16.8 - actualité p=1.0 g=8.0 | acte p=1.0 g=2.0 | actuellement p=1.0 g=9.0 | actes p=2.0 g=1.0
16.8 - acte p=1.0 g=3.0 | actuellement p=1.0 g=10.0 | actualité p=1.0 g=6.0 | actes p=2.0 g=1.0
16.8 - acte p=1.0 g=3.0 | actualité p=1.0 g=7.0 | actuellement p=1.0 g=9.0 | actes p=2.0 g=1.0

Nouvelle métrique#

Intuition#

[5]:
def gain_moyen_par_mot(queries, weights):
    total = sum(weights) * 1.0
    res = []
    for per in itertools.permutations(zip(queries, weights)):
        trie = CompletionTrieNode.build([(None, w) for w, p in per])
        wks = [(w, p, len(w) - trie.min_keystroke(w)[0]) for w, p in per]
        gain = sum(g * p / total for w, p, g in wks)
        res.append((gain, wks))
    res.sort(reverse=True)
    for i, r in enumerate(res):
        print(
            "{0:3.4} - {1}".format(
                r[0], " | ".join("%s p=%1.1f g=%1.1f" % _ for _ in r[1])
            )
        )
        if i > 10:
            print("...")
            break
[6]:
queries = ["actuellement", "actualité", "actuel"]
weights = [1, 1, 1]
gain_moyen_par_mot(queries, weights)
7.0 - actuellement p=1.0 g=11.0 | actuel p=1.0 g=4.0 | actualité p=1.0 g=6.0
7.0 - actuellement p=1.0 g=11.0 | actualité p=1.0 g=7.0 | actuel p=1.0 g=3.0
7.0 - actuel p=1.0 g=5.0 | actuellement p=1.0 g=10.0 | actualité p=1.0 g=6.0
7.0 - actuel p=1.0 g=5.0 | actualité p=1.0 g=7.0 | actuellement p=1.0 g=9.0
7.0 - actualité p=1.0 g=8.0 | actuellement p=1.0 g=10.0 | actuel p=1.0 g=3.0
7.0 - actualité p=1.0 g=8.0 | actuel p=1.0 g=4.0 | actuellement p=1.0 g=9.0
[7]:
queries = ["actuellement", "actualité", "actuel"]
weights = [1, 1, 0]
gain_moyen_par_mot(queries, weights)
9.0 - actuellement p=1.0 g=11.0 | actualité p=1.0 g=7.0 | actuel p=0.0 g=3.0
9.0 - actualité p=1.0 g=8.0 | actuellement p=1.0 g=10.0 | actuel p=0.0 g=3.0
8.5 - actuellement p=1.0 g=11.0 | actuel p=0.0 g=4.0 | actualité p=1.0 g=6.0
8.5 - actualité p=1.0 g=8.0 | actuel p=0.0 g=4.0 | actuellement p=1.0 g=9.0
8.0 - actuel p=0.0 g=5.0 | actuellement p=1.0 g=10.0 | actualité p=1.0 g=6.0
8.0 - actuel p=0.0 g=5.0 | actualité p=1.0 g=7.0 | actuellement p=1.0 g=9.0
[8]:
queries = ["actuellement", "actualité"]
weights = [1, 1]
gain_moyen_par_mot(queries, weights)
9.0 - actuellement p=1.0 g=11.0 | actualité p=1.0 g=7.0
9.0 - actualité p=1.0 g=8.0 | actuellement p=1.0 g=10.0

Vérification#

[9]:
def gain_dynamique_moyen_par_mot(queries, weights, permutation=True):
    total = sum(weights) * 1.0
    res = []
    for per in itertools.permutations(zip(queries, weights)):
        trie = CompletionTrieNode.build([(None, w) for w, p in per])
        trie.precompute_stat()
        trie.update_stat_dynamic()
        wks = [(w, p, len(w) - trie.min_dynamic_keystroke(w)[0]) for w, p in per]
        gain = sum(g * p / total for w, p, g in wks)
        res.append((gain, wks))
        if not permutation:
            break
    res.sort(reverse=True)
    for i, r in enumerate(res):
        print(
            "{0:3.4} - {1}".format(
                r[0], " | ".join("%s p=%1.1f g=%1.1f" % _ for _ in r[1])
            )
        )
        if i > 10:
            print("...")
            break

Pas de changement :

[10]:
queries = ["actuellement", "actualité", "actuel"]
weights = [1, 1, 0]
gain_dynamique_moyen_par_mot(queries, weights)
9.0 - actuellement p=1.0 g=11.0 | actualité p=1.0 g=7.0 | actuel p=0.0 g=3.0
9.0 - actualité p=1.0 g=8.0 | actuellement p=1.0 g=10.0 | actuel p=0.0 g=3.0
8.5 - actuellement p=1.0 g=11.0 | actuel p=0.0 g=4.0 | actualité p=1.0 g=6.0
8.5 - actuel p=0.0 g=5.0 | actualité p=1.0 g=7.0 | actuellement p=1.0 g=10.0
8.5 - actualité p=1.0 g=8.0 | actuel p=0.0 g=4.0 | actuellement p=1.0 g=9.0
8.0 - actuel p=0.0 g=5.0 | actuellement p=1.0 g=10.0 | actualité p=1.0 g=6.0

Changements :

[11]:
queries = ["actuellement", "actualité", "actuel"]
weights = [1, 1, 1]
gain_dynamique_moyen_par_mot(queries, weights)
7.333 - actuel p=1.0 g=5.0 | actualité p=1.0 g=7.0 | actuellement p=1.0 g=10.0
7.0 - actuellement p=1.0 g=11.0 | actuel p=1.0 g=4.0 | actualité p=1.0 g=6.0
7.0 - actuellement p=1.0 g=11.0 | actualité p=1.0 g=7.0 | actuel p=1.0 g=3.0
7.0 - actuel p=1.0 g=5.0 | actuellement p=1.0 g=10.0 | actualité p=1.0 g=6.0
7.0 - actualité p=1.0 g=8.0 | actuellement p=1.0 g=10.0 | actuel p=1.0 g=3.0
7.0 - actualité p=1.0 g=8.0 | actuel p=1.0 g=4.0 | actuellement p=1.0 g=9.0
[12]:
gain_moyen_par_mot(queries, weights)
7.0 - actuellement p=1.0 g=11.0 | actuel p=1.0 g=4.0 | actualité p=1.0 g=6.0
7.0 - actuellement p=1.0 g=11.0 | actualité p=1.0 g=7.0 | actuel p=1.0 g=3.0
7.0 - actuel p=1.0 g=5.0 | actuellement p=1.0 g=10.0 | actualité p=1.0 g=6.0
7.0 - actuel p=1.0 g=5.0 | actualité p=1.0 g=7.0 | actuellement p=1.0 g=9.0
7.0 - actualité p=1.0 g=8.0 | actuellement p=1.0 g=10.0 | actuel p=1.0 g=3.0
7.0 - actualité p=1.0 g=8.0 | actuel p=1.0 g=4.0 | actuellement p=1.0 g=9.0

Ajouter une complétion#

[13]:
queries = [
    "macérer",
    "maline",
    "machinerie",
    "machinerie infernale",
    "machinerie infernalissime",
    "machine artistique",
    "machine automatique",
    "machine chaplin",
    "machine intelligente",
    "machine learning",
]
weights = [1] * len(queries)
gain_dynamique_moyen_par_mot(queries, weights, permutation=False)
10.1 - macérer p=1.0 g=6.0 | maline p=1.0 g=4.0 | machinerie p=1.0 g=7.0 | machinerie infernale p=1.0 g=16.0 | machinerie infernalissime p=1.0 g=20.0 | machine artistique p=1.0 g=12.0 | machine automatique p=1.0 g=12.0 | machine chaplin p=1.0 g=7.0 | machine intelligente p=1.0 g=11.0 | machine learning p=1.0 g=6.0
[14]:
queries = ["machine"] + queries
weights = [1] * len(queries)
weights[queries.index("machine")] = 0.0
gain_dynamique_moyen_par_mot(queries, weights, permutation=False)
12.3 - machine p=0.0 g=6.0 | macérer p=1.0 g=5.0 | maline p=1.0 g=3.0 | machinerie p=1.0 g=8.0 | machinerie infernale p=1.0 g=17.0 | machinerie infernalissime p=1.0 g=21.0 | machine artistique p=1.0 g=15.0 | machine automatique p=1.0 g=15.0 | machine chaplin p=1.0 g=11.0 | machine intelligente p=1.0 g=16.0 | machine learning p=1.0 g=12.0

Wikipedia#

[15]: