Les tries pour les recherches par préfixe : autocomplétion et correspondance du plus long préfixe

Ce que c'est

Le dictionnaire du NIST définit un trie comme un arbre pour stocker des chaînes de caractères, avec un nœud pour chaque préfixe commun. Chaque arête porte un symbole (un octet, un caractère ou un bit), et un marqueur terminal ou une feuille identifie les clés stockées. Rechercher une clé parcourt une arête par symbole, si bien que le coût dépend de la longueur de la clé, pas du nombre de clés stockées. Toutes les clés partageant un préfixe résident dans le sous-arbre situé sous le nœud de ce préfixe. Un arbre radix (Patricia ou trie compact) fusionne les chaînes de nœuds à enfant unique en une seule arête étiquetée, afin d'économiser de la mémoire. La table de routage IPv4 du noyau Linux est un LC-trie dont la recherche, comme le décrit sa documentation, retourne en arrière dans le trie pour trouver le plus long préfixe correspondant à une adresse de destination.

Pourquoi c'est important

Deux opérations sont malaisées avec des tables de hachage : « toutes les clés commençant par X » et « la plus longue clé stockée qui soit un préfixe de X ». Les tries transforment la première en un parcours de sous-arbre, et la seconde en une simple descente qui retient le dernier nœud terminal rencontré. L'autocomplétion, les routeurs de chemins HTTP, la correspondance du plus long préfixe IP, les tokeniseurs et les listes de blocage se ramènent tous à l'une de ces deux opérations.

Comment l'appliquer

• Fixer d'abord l'alphabet : les octets sont les plus simples ; pour du texte, normaliser (NFC Unicode, repliement de casse) de façon identique à l'insertion et à la recherche, et décider si les nœuds représentent des points de code ou des octets UTF-8.
• Choisir la disposition des nœuds selon la densité de l'alphabet : un tableau d'enfants pour les petits alphabets denses, un petit tableau trié ou une table de hachage pour les alphabets épars, une compression radix lorsque les clés partagent de longues séquences communes.
• Autocomplétion : descendre jusqu'au nœud du préfixe, puis parcourir avec une limite de résultats ; stocker des comptages par nœud ou un top-k mis en cache pour répondre à « les complétions les plus fréquentes » sans parcourir tout le sous-arbre.
• Correspondance du plus long préfixe : parcourir la requête, enregistrer le nœud terminal le plus profond rencontré, le retourner à la fin ou à l'échec du parcours.
• Avant d'en construire un, essayer un tableau trié : bisect_left sur le préfixe suivi d'un balayage tant que les entrées commencent encore par celui-ci traite l'autocomplétion sur des données statiques avec bien moins de mémoire. Un trie se justifie en cas de mises à jour fréquentes, de requêtes de plus long préfixe, ou de préfixes communs très longs.

Pièges

Des nœuds naïfs à 256 pointeurs coûtent chacun plusieurs kilooctets ; c'est la mémoire, pas la vitesse, qui pose habituellement problème. La suppression doit élaguer les nœuds non terminaux qui se retrouvent sans enfants. Des incohérences de normalisation rendent des clés invisibles. Un parcours récursif sur de longues clés se heurte aux limites de pile. Les tries ne répondent pas aux requêtes d'infixe, de suffixe ou floues ; celles-ci exigent d'autres index.