Propriétés mathématiques¶
On s’intéresse principalement à la métrique définie par
Dynamic Minimum Keystroke (1) mais les résultats
seront étendues aux autres quand cela est possible.
Calcul pour une complétion¶
On a besoin d’une propriété pour calculer élégamment les métriques pour l’ensemble des complétions.
Il n’est pas nécessaire de regarder tous les préfixes mais seulement ceux entre le plus long préfixe
qui est aussi une complétion et la requête . La démonstration est identique à la démonstration
du lemme qui suit. L’idée de cette propriété est de pouvoir réduire le coût de l’algorithme
de calcul des métriques. Ce n’est pas la seule écriture qu’on puisse en fait.
Le calcul de la métrique suggère qu’on doit faire ce calcul dans le sens
des préfixes croissants mais il serait plus simple de le faire dans le sens des complétions
de poids croissant (les complétions de moindre poids sont toujours affichées avant).

Si l’algorithme est plus simple (sens de la fléche dans le figure précédente), il faut parfois plusieurs itérations pour obtenir la valeur finale.
Calcul pour une requête en dehors¶
Mais il est faux de dire que pour deux requêtes en dehors de l’ensemble
des complétions, .
Le lemme suivant précise pourquoi
Lemme L2 : calcul de *M”(q, S)*
On suppose que est la complétion la plus longue
de l’ensemble
qui commence
:
La métrique vérifie la propriété suivante :
La métrique est égale à celle du plus long préfixe inclus
dans l’ensemble les complétions à laquelle on ajoute la différence des longueurs.
Cela correspond aux caractères que l’utilisateur doit saisir.
La démonstration est assez simple. On suppose que cela n’est pas vrai et qu’il existe
un existe
tel que :
Cela signifie qu’on a réussi une façon plus efficace d’écrire le préfixe
. Or par définition
est censée être le nombre de caractères minimal pour obtenir
.
Ce n’est donc pas possible.
Cette propriété est importante puisque pour calculer
,
il suffit de regarder le plus long préfixe appartenant à l’ensemble des complétions
et seulement celui-ci. Cet algorithme et implémenté par la méthode
enumerate_test_metric
.
En ce qui concerne la métrique , par définition
. La métrique
m’évoque la côte anglaise.
L’itération
fonctionne de la même manière à partir du moment où
la requête considérée ne fait pas partie de l’ensemble des complétions mais
il y a l’étage d’en dessous qui pose un doute.
Il y a un brin de poésie dans ce +1. L’application de l’implémentation du calcul
de la métrique montre que
et
sont très souvent égales.
Je vais laisser ce
sous forme de poésie pour le moment.
Il faudrait terminer la démonstration pour M…
Complétions emboîtées¶
On considère les complétions suivantes :
actu
actualité
actualités
actuel
actuellement
Pour le préfixe actue, on suggère actuel at actuellement.
Pour le préfixe actua, on suggère actualité at actualités.
Pour le préfixe actu, on suggère la concaténation de ces deux listes.
Par conséquent, pour construire les listes de complétions associées à chaque préfixe,
il paraît de partir des feuilles de l’arbre puis de fusionner les listes
de complétions jusqu’au noeud racine.
Plus concrètement, si deux complétions
vérifie alors l’ensemble des complétions
vérifie
. On peut même dire que :
. Cela signifie qu’une fois qu’on
a construit un trie représentant l’ensemble des complétions, il suffit de
partir des feuilles de l’arbre jusqu’à la racine pour construire la
liste des complétions à chaque étape et que pour un noeud précis,
la liste des complétions est l’union des listes de complétions des noeuds
fils.
Listes tronquées de complétions¶
On reprend la première métrique (1) qui
utilise la fonction définie en (2).
Etant donné que le nombre minimum de caractères pour obtenir une complétion dans le trie
ne peut pas être supérieur à la longueur, si , on sait déjà que
que le préfixe
ne sera pas le minimum. Cette remarque est applicable
aux métriques
et
.