Remplacer une base de données SQLite de 3 Go par un binaire FST (transducteur à états finis) de 10 Mo

• Taskusanakirja est un dictionnaire finnois-anglais qui propose une recherche par préfixe pendant la saisie
• Avec l’extension aux formes fléchies du finnois, le nombre d’entrées est monté à 40 à 60 millions, au point d’atteindre les limites d’un trie
• Une solution provisoire avec SQLite FTS était rapide, mais exigeait un téléchargement initial de 3 Go
• Un FST en Rust a réduit les données SQLite à un binaire d’environ 10 Mo, soit une réduction par 300
• Le FST partage à la fois les préfixes et les suffixes, ce qui correspond bien aux motifs flexionnels répétitifs

---

Structure de recherche de Taskusanakirja et premières limites

• Taskusanakirja, abrégé en tsk, est un dictionnaire finnois-anglais qui propose une recherche progressive pendant la saisie
• Cette fonctionnalité relève essentiellement d’un problème de recherche par préfixe, et la solution classique pour l’autocomplétion était une implémentation de trie
• La première implémentation a été écrite en Go, avec pour objectif initial de distribuer tout le programme sous la forme d’un seul .exe, d’un seul .app ou d’un unique binaire lié statiquement
• Pour éviter que, sur un corpus de taille intermédiaire à six chiffres, certaines entrées correspondant à quelques pourcents à un seul chiffre de l’ensemble ne soient toutes renvoyées, l’application limitait les résultats aux 50 ou 100 premiers et mémorisait les combinaisons de 1, 2 et 3 lettres
• Avec cette approche, il a été possible de faire tenir un trie avec les optimisations de base dans environ 60 Mo, sans latence perceptible après un an d’usage personnel intensif

Le problème d’échelle créé par les données flexionnelles du finnois

• Le finnois est une langue agglutinante, si bien qu’un mot de base peut prendre plus de 100 terminaisons quand on considère toutes les combinaisons possibles
• Ces combinaisons ne sont pas régulières, et l’orthographe finnoise très normalisée reflète directement les formes réellement prononcées, ce qui fait que les mots de base s’allongent, se déplacent et se transforment lorsqu’ils se combinent avec des terminaisons
• Un débutant peut facilement bloquer sur une phrase comme “Opiskelijassammekin on leijonan sydän”, et tsk voulait aussi inclure des informations pour aider à découper correctement les mots à la bonne frontière
• Du point de vue linguistique, ces transformations relèvent de l’alternance consonantique et de l’harmonie vocalique, deux mécanismes employés simultanément par le finnois
• Par exemple, katu signifie “street”, mais le génitif n’est pas katun mais kadun, car le t s’affaiblit en d à cause de la syllabe fermée
• Si l’on multiplie cette structure par 15 cas, 2 pluriels, 6 suffixes possessifs et un nombre indéfini d’enclitiques, un trie naïf ne peut pas mutualiser le coût des finales partagées par des milliers de mots, comme -ssa-mme-kin
• Environ 400 000 entrées tenaient dans un trie occupant environ 50 Mo de RAM, mais cette approche ne passait pas à l’échelle de 40 à 60 millions d’entrées
• Comme solution temporaire, les formes fléchies ont été placées dans une base SQLite FTS distincte, consultée à la demande ; cela fonctionnait sans latence perceptible, mais nécessitait un téléchargement initial de 3 Go

Le passage à Rust et au FST

• Neuf mois plus tard, une nouvelle tentative en Rust a conduit à l’écriture d’un petit programme Rust chargé d’extraire les données de la base SQLite de 3 Go pour les compresser en FST
• Le déclencheur a été l’article de BurntSushi aka Andrew Gallant, Index 1,600,000,000 Keys with Automata and Rust, dont l’idée centrale est que les automates finis peuvent représenter de façon compacte et rapide des ensembles ou des maps triés de chaînes de caractères
• Le binaire obtenu faisait environ 10 Mo, soit une réduction d’espace d’environ 300 fois par rapport à la base SQLite de 3 Go
• Ce cas d’usage correspondait particulièrement bien au crate fst, puisqu’il s’agissait de faire correspondre les formes fléchies et conjuguées d’une langue fortement agglutinante à leur définition d’origine
• Un trie compresse les préfixes, alors qu’un FST compresse à la fois les préfixes et les suffixes
• Le corpus du dictionnaire finnois contient un petit nombre de suffixes très fréquents et fortement répétés, ce qui rend le partage des suffixes particulièrement efficace
• Les données étant statiques et ne changeant pas à l’exécution, il a été possible d’éviter la plus grande faiblesse de fst

Pourquoi le FST est devenu plus petit qu’un trie

• L’élément clé qui rend un FST bien plus compact qu’un trie sur des données de langue naturelle est le partage des suffixes
• Un trie partage les préfixes, par exemple les trois premiers nœuds de kadun et kaduille, mais stocke séparément chaque chemin de suffixe distinct
• Un automate fini acyclique déterministe minimal fusionne deux sous-arbres structurellement identiques
• Dans un corpus où 100 000 mots se terminent selon une douzaine de schémas flexionnels communs, cette fusion produit un gain mémoire important
• L’heuristique essentielle de ce cas consiste à remplacer une base de données générique bricolée sur le moment par une petite structure de données statique spécialisée qui ne fait exactement que ce dont on a besoin, ce qui a permis une réduction mémoire par 300

Ce qu’a laissé la solution SQLite provisoire et la taille du déploiement

• Le choix de SQLite neuf mois plus tôt relevait d’un compromis du type « faire quelque chose de mauvais mais simple » plutôt que « ne rien faire de bien », et cela a effectivement fonctionné
• Comme les B-trees de SQLite et l’extension Full Text Search étaient déjà bien compris, c’était à l’époque une solution rapide à expérimenter
• La même extension FTS est aussi utilisée pour certaines fonctionnalités moins employées, absentes de l’alpha tsk v2.0.0, mais elle pourrait être supprimée entièrement si elle nuisait à l’empreinte mémoire actuelle
• La version Pro de v2 est estimée à environ 20 Mo tout compris, soit trois fois moins que la version gratuite v1
• tsk a commencé comme un programme TUI en Go, a évolué à partir du prototype précédent fzf appelé finstem, et se rattache à the highest-ROI program I’ve written so far
• taskusanakirja signifie “pocket dictionary” en finnois, et l’idée reste que si l’application ne tient même pas sur un vieux portable, ce n’est plus un dictionnaire de poche mais plutôt un vieux dictionnaire Oxford compilé
• On retrouve ici l’idée qu’« il n’y a pas de mal à résoudre deux fois le même problème » : au lieu de se laisser bloquer par la culpabilité de ne pas avoir trouvé une meilleure implémentation existante, refaire soi-même quelques roues permet d’atteindre plus vite les véritables limites
• Ce point de vue rejoint la “pratique” dans la Caplanian view, ainsi que Do Ten Times as Much, présenté comme un conseil inconfortable mais efficace

[GN⁺]

Avis sur Lobste.rs

• L’article lui-même était intéressant, et j’ai aimé voir le bon outil appliqué au bon problème pour obtenir une amélioration d’un ordre de grandeur, mais la dernière note de bas de page m’a encore plus marqué que le corps du texte.
  Elle met exactement le doigt sur cette hésitation qui nous paralyse, cette culpabilité à l’idée que l’outil qu’on est en train de construire a peut-être déjà été mieux implémenté par quelqu’un il y a 30 ou 40 ans. Mais c’est un piège, et l’idée qu’il faut refaire quelques roues soi-même pour atteindre les limites de la fabrication de roues m’a parlé. Dans la plupart des domaines, quatre ou cinq suffisent ; même dans des disciplines rigoureuses comme les mathématiques ou l’informatique théorique, une vingtaine peut suffire ; et l’argument est que les questions qu’on se pose en les reconstruisant soi-même nous amènent beaucoup plus vite à la vraie frontière du domaine qu’une simple étude théorique

  • Un point connexe important dans l’article est que même une implémentation inefficace et brutale construite avec une base SQLite avait de la valeur en tant qu’implémentation de référence.
    Le simple fait d’avoir une implémentation de référence fonctionnelle a rendu bien plus facile la création d’une implémentation efficace pour la remplacer
  • Ça correspond exactement au problème que je rencontre en ce moment. Je veux construire quelque chose d’optimisé pour mon espace de problème, mais je restais bloqué parce que je savais que le problème généralisé avait déjà été résolu.
    Pourtant, quand je regarde les solutions existantes, elles traînent beaucoup de bagages dont je n’ai pas besoin. D’après mon expérience, je sais que ça vaut la peine de pousser mon idée, mais je me demandais toujours si je n’étais pas en train de rater quelque chose ; après avoir lu ça, j’ai décidé de simplement essayer. Même en cas d’échec, il y aura quelque chose à apprendre dans le processus

• Excellent. Ça m’a rappelé Compressing Icelandic name declension patterns into a 3.27 kB trie

• En implémentant un bot de Scrabble, j’ai découvert une structure de données apparentée appelée DAWG (Directed Acyclic Word Graph), qui semble assez courante pour cet usage.
  La principale différence avec le crate fst semble être qu’elle n’associe pas chaque mot à un entier unique. De la même façon, on obtient une grosse réduction de taille et des performances spectaculairement meilleures. Un bot de Scrabble doit essentiellement filtrer tout le dictionnaire avec des mots correspondant à une expression régulière simple comme ..cat.., mais en pratique il faut traiter toutes les expressions régulières simples possibles à partir du plateau courant. Une opération qui demandait environ une minute est devenue imperceptible

  • L’article de 1988 d’Appel et Jacobson sur les DAWG a été publié récemment aussi, et déjà partagé auparavant

• L’article lié vaut aussi la lecture : https://burntsushi.net/transducers/

• fst est aussi l’outil qui a fini par être utilisé pour la prise en charge de l’allemand dans srgn, après qu’Andrew l’a recommandé directement.
  C’est le même espace de problème, avec compression des préfixes et suffixes communs, et ça marche vraiment très bien. Comme c’était aussi un outil CLI, il fallait en plus minimiser le coût de démarrage ; le crate fst prend en charge le chargement zero-copy, donc il n’y a pas de surcoût à l’exécution. Le FST est construit au moment de la compilation

• Vraiment génial, et j’aimerais qu’il existe quelque chose comme ça aussi pour l’allemand et l’anglais. Les mots composés allemands continuent encore souvent à me perturber