Trie et automate fini déterministe

Buy a copy of a baby naming book and you'll never be at a loss for variable names.

— Un programmeur inspiré

Duplika utilise un dictionnaire d'environ 400'000 entrées. Jusqu'à tout récemment, celui-ci était stocké dans ce qui équivalait à une table de hachage. Au prix d'une consommation de mémoire importante, cette solution avait l'avantage d'être simple et d'offrir des recherches rapides.

Récemment, le développement de certaines fonctionnalités nécessita de réviser la manière dont le dictionnaire est représenté en mémoire. En particulier, le dictionnaire doit maintenant permettre d'énumérer rapidement tous les mots ayant un préfixe commun — chose difficile à réaliser avec une table de hachage!

Arbre de préfixe (trie)

Un arbre de préfixe, trie pour les intimes, permet de stocker des chaînes de caractères dans une arborescence où il existe un nœud pour chaque préfixe commun. Cette caractéristique permet d'énumérer rapidement tous les mots ayant un préfixe commun.

Par exemple, un trie stockant les mots ai, aient, aime, aimer, ais et ait aura la forme suivante.

Voici l'essentiel de l'implantation — triviale — initialement utilisée sur Duplika et à partir de laquelle le graphique ci-dessus a été généré.

function Node() {
    this.id = Node.IdCounter++;
    this.end = false;
    this.letters = [];
    this.children = [];
}

Node.IdCounter = 0;

Node.prototype.addChild = function(letter) {
    return this.child(letter) || this.addChild_(letter);
};

Node.prototype.addChild_ = function(letter) {
    var node = new Node(),
        index = this.childIndex(letter);
    this.children[index] = node;
    this.letters.push(letter);
    return node;
};

Node.prototype.child = function(letter) {
    var index = this.childIndex(letter);
    return this.children[index];
};

Node.prototype.childIndex = function(letter) {
    return letter.charCodeAt(0) - 'a'.charCodeAt(0);
}

Node.prototype.pathExists = function(suffix) {
    var node = this;
    for (var i = 0; i < suffix.length; i++) {
        node = node.child(suffix[i]);
        if (!node) {
            return false;
        }
    }
    return node.isTerminal();
};

Node.prototype.markTerminal = function() {
    this.end = true;
};

Node.prototype.isTerminal = function() {
    return this.end;
};
function Trie() {
    Node.call(this);
}
util.inherits(Trie, Node);

Trie.prototype.addAll = function(words) {
    words.forEach(this.add, this);
};

Trie.prototype.add = function(word) {
    if (word.length > 0) {
        var node = this;
        word.split('').forEach(function(letter) {
            node = node.addChild(letter);
        });
        node.markTerminal();
    }
};

Trie.prototype.contains = function(word) {
    return this.pathExists(word);
};

Il importe de remarquer que cette implantation accepte uniquement des mots formés de caractères compris entre a et z. En outre, quelques optimisations ont été effectuées afin de faciliter la vie à V8. En particulier, un tableau est utilisé pour stocker les références vers les enfants et l'ensemble des transitions est maintenu séparément.

Si un trie offre toutes les opérations recherchées, un problème devient vite apparent: la consommation de mémoire est abyssale. Le problème vient du fait que plusieurs suffixes communs sont stockés en double. Cela cause une explosion du nombre de nœuds composant l'arbre de préfixe.

Heureusement, le problème est connu et il existe plusieurs algorithmes permettant de convertir un arbre de préfixe en un automate fini déterministe minimal reconnaissant le même langage et préservant les mêmes propriétés.

Automate fini déterministe minimal

Généralement, les techniques de construction d'automates finis déterministes minimaux commencent par construire un arbre de préfixe puis le minimise par la suite. L'algorithme présenté dans Incremental Construction of Minimal Acyclic Finite-State Automata construit plutôt l'automate de manière progressive en minimisant ce dernier après chaque insertion. Cette technique réduit de manière significative la quantité de mémoire requise pour la construction de l'automate.

Pour bien visualiser le fonctionnement de l'algorithme, le plus simple est certainement d'en étudier une trace. Par exemple, considérons la construction de l'automate fini déterministe stockant les mots ai, aient, aime, aimer, ais et ait.

Après l'insertion de «ai».

Après l'insertion de «aient».

Après l'insertion de «aime».

Après l'insertion de «aimer».

Après l'insertion de «ais».

Après l'insertion de «ait».

L'automate fini déterministe équivalent à l'arbre de préfixe présenté précédemment aurait donc la forme suivante.

On remarque aisément que les suffixes communs ont été combinés. C'est ce qui permet de minimiser le nombre de nœuds nécessaires afin de représenter la même information.

L'implantation de cet algorithme est relativement simple, en particulier la version opérant sur une liste de mots triés. La version utilisée sur Duplika, affectueusement baptisée dtrie, est disponible sur github et peut être installée via npm.

Trie vs. automate

Considérant un dictionnaire de 388'000 entrées, voici quelques comparaisons entre les deux structures de données.

Trie Automate
Temps de chargement 3170 ms 2753 ms
Nombre de nœuds 722'079 42'149
Taille en mémoire --- 11 634 540 octets

La taille en mémoire correspond à ce que V8 appelle le «retained size». Le chiffre désigne la taille cumulative des objets composant la structure de données. Le profileur de V8 n'a pas été en mesure de calculer la taille du heap pour le trie; ce dernier est, semble-t-il, trop volumineux.

Les temps de recherche sont sensiblement les mêmes, avec généralement un léger avantage pour l'automate — quelques millisecondes pour 400'000 recherches. Autrement dit, pas d'amélioration véritable de ce côté.

Références