Propriétés mathématiques

On s’intéresse principalement à la métrique \(M'\) 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.

Lemme L1 : Dynamic Minimum Keystroke

On note \(d(q, S)\) la longueur du plus long préfixe de \(q\) inclus dans \(S\).

\[d(q, S) = \max\acc{ l(p) | p \prec q, \; p \in S, \; p \neq q}\]

\begin{eqnarray*} M'(q, S) &=& \min_{d(q, S) \infegal k < l(q)} \acc{ M'(q[1..k], S) + \min( K(q, k, S), l(q) - k) } \end{eqnarray*}

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 \(q\). 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 \(M'\) 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, \(q_1 \preceq q_2 \Longrightarrow M'(q_1, S) \infegal M'(q_2, S)\). Le lemme suivant précise pourquoi

Lemme L2 : calcul de *M”(q, S)*

On suppose que \(p(q, S)\) est la complétion la plus longue de l’ensemble \(S\) qui commence \(q\) :

\begin{eqnarray*} k^* &=& \max\acc{ k | q[[1..k]] \prec q \text{ et } q \in S} \\ p(q, S) &=& q[[1..k^*]] \end{eqnarray*}

La métrique \(M'(q, S)\) vérifie la propriété suivante :

\[M'(q, S) = M'(p(q, S), S) + l(q) - l(p(q, S))\]

La métrique \(M'(q, S)\) 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 \(k < k^*\) tel que :

\begin{eqnarray*} && M'(q[[1..k]], S) + l(q) - l(q[[1..k]]) < M'(q[[1..k^*]], S) + l(q) - l(q[[1..k^*]]) \\ & \Longrightarrow & M'(q[[1..k]], S) - k < M'(q[[1..k^*]], S) - k^* \\ & \Longrightarrow & M'(q[[1..k]], S) + (k^* - k) < M'(q[[1..k^*]], S) \end{eqnarray*}

Cela signifie qu’on a réussi une façon plus efficace d’écrire le préfixe \(q[[1..k^*]]\). Or par définition \(M'(q[[1..k^*]], S)\) est censée être le nombre de caractères minimal pour obtenir \(q[[1..k^*]]\). Ce n’est donc pas possible. Cette propriété est importante puisque pour calculer \(M'(q[[1..k^*]], S)\), 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 \(M\), par définition \(\forall q \notin S, \; M(q, S) = 0\). La métrique \(M"\) m’évoque la côte anglaise. L’itération \(n\) 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 \(M'\) et \(M"\) sont très souvent égales. Je vais laisser ce \(\delta\) 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 \(q_1 \preceq q_2\) alors l’ensemble des complétions vérifie \(C(q_1) \supset C(q_2)\). On peut même dire que : \(C(q) = \cup \acc{ C(s) | s \succ q \in S}\). 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 \(K(q, k, S)\) définie en (2).

\begin{eqnarray*} M(q, S) &=& \min_{0 \infegal k \infegal l(q)} k + K(q, k, S) \end{eqnarray*}

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 \(K(q, k, S) > l(q) - k\), on sait déjà que que le préfixe \(q[1..k]\) ne sera pas le minimum. Cette remarque est applicable aux métriques \(M'\) et \(M"\).