Implémentation#
J’allais vous raconter en détail ce qu’est un trie et le paragraphe suivant vous en dira sans doute un peu plus à ce sujet. Le trie est le moyen le plus efficace de trouver un mot aléatoire ou un préfixe aléatoire dans une liste. Mais il y a mieux et plus simple dans notre cas où il faut trouver une longue liste de mots connue à l’avance - donc pas aléatoire -. Et puis, c’était sous mes yeux. Il y a plus simple et aussi efficace quand les listes des mots et des complétions sont connues à l’avance.
Notion de trie#
Une implémentation des tries est décrite dans ce notebook :
Arbre et Trie.
Les résultats de ce chapitre ont été produits avec le module completion
et le notebook Complétion. Le notebook
Completion profiling montre les résultats du profiling.
L’implémentation Python est très gourmande en mémoire et elle serait
plus efficace en C++.
utilisation ou recherche
C’est différent de construire toutes les complétions pour un préfixe plutôt que toutes les complétions pour tous les préfixes. Le premier cas correspond à un utilisateur qui cherche quelque chose. Il faut être rapide quitte à retourner un résultat tronqué.
Le second cas correspond à objectif de recherche des d’optimisation. Les enjeux sont plus de réussir à calculer toutes les complétions en un temps raisonnable et avec une utilisation mémoire raisonnable également.
mémoire
D’après la remarque précédente, il n’est pas utile de conserver pour un préfixe donné l’intégralité des complétions qui commencent par ce préfixe. Dans le pire des cas, cette liste a besoin de contenir autant de complétions que le nombre de caractères de la plus longue complétioms.
Algorithme élégant#
Il faut relire le premier problème d”optimisation pour commencer à se poser la question : comment calculer la quantité \(E(C, C, \sigma)\) lorsque \(\sigma\) correspond à l’ordre alphabétique ? La réponse est simple : il suffit de parcourir les complétions une et une seule fois. Supposons qu’au cours de ce parcours, on est à la complétion d’indice \(i\). On conserve un compteur \(p(k, i)=K(c(i), k, C)\) qui représente la position de la complétion \(c(i)\) dans la liste des complétions affichées par le système de complétion pour le préfixe \(c(i)[[1..k]]\). Le coût de l’algorithme est en \(O(N\ln N + LN)\) où \(N\) est le nombre de complétions et \(L\) la longueur maximale d’une complétion.
Dans le cas où \(\sigma\) est quelconque et \(C \neq Q\), on procède en deux étapes. Dans un premier temps, on utilise une variante de l’algorithme précédent pour calculer \(M'(q, C)\) pour les requêtes \(q\) dans l’ensemble des complétions.
Dans un second temps, on effectue une sorte de fusion entre les deux listes triées alphabétiquement. Le coût de l’algorithme est en \(O(ILN + 2 N\ln N + M \ln M + max(N,M))\) où \(M\) est le nombre de requêtes dans l’ensemble \(Q\). Cette partie repose sur le lemme lié au calcul des métriques pour les réquêtes hors de l’ensemble des complétions. \(I\) est un nombre d’itération nécessaires pour que les métriques \(M'\) convergent pour l’ensemble des complétions. En pratique, c’est très petit.
L’algorithme est implémenté dans le module
completion_simple et plus particulièrement la fonction
CompletionSystem.compute_metrics.