Vers un nouvel Oracle : l'Oracle à transitions gardées

Parmi les structures de données permettant d'indexer au moins tous les sous-chaînes d'un texte donné $T$, l'Oracle est le plus économique, tant du point de vue de la consommation mémoire que du temps nécessaire à la construction. Cette structure est un automate qui accepte les facteurs ou les suffixes (selon la version) de $T$. Il existe un algorithme de construction "on-line", qui est étonnamment simple à comprendre et à implémenter. Le seul (mais pas le moindre) inconvénient de cette structure est qu'elle reconnaît également des mots qui ne sont ni facteurs ni suffixes du texte indexé. Dans une précédente étude, nous avons établi une caractérisation combinatoire de l'ensemble de mots reconnus par l'Oracle, et nous avons montré que le nombre de mots de cet ensemble qui ne sont pas facteurs/suffixes de $T$ peut être exponentiel par rapport à la taille de $T$ dans le pire des cas. Nous étendons ici ce résultat en montrant expérimentalement que ce nombre est également exponentiel en moyenne par rapport à la taille de $T$, et nous introduisons une variante de cette structure, qui améliore de façon drastique la qualité de l'automate. Nous avons modifié l'algorithme existant afin de construire cette nouvelle structure. Toutefois, malgré l'enrichissement apporté à cette structure, sa complexité demeure meilleure que celle des autres structures d'indexation (excepté l'Oracle original lui même) qui reconnaisse au moins les facteurs/suffixes de $T$.