Eine 3-GB-SQLite-Datenbank durch eine 10-MB-FST-Binärdatei ersetzen

• Taskusanakirja ist ein Finnisch-Englisch-Wörterbuch, das während der Eingabe Präfixsuche bietet
• Durch die Erweiterung um finnische Flexionsformen wuchs die Zahl der Einträge auf 40 bis 60 Millionen, wodurch ein Trie an seine Grenzen kam
• Eine vorläufige Lösung mit SQLite FTS war schnell, erforderte aber zunächst einen Download von 3 GB
• Ein auf Rust basierendes FST reduzierte die SQLite-Daten auf eine Binärdatei von etwa 10 MB und sparte damit den Faktor 300
• Das FST teilt nicht nur Präfixe, sondern auch Suffixe und passt daher gut zu wiederkehrenden Flexionsmustern

---

Die Suchstruktur von Taskusanakirja und ihre anfänglichen Grenzen

• Taskusanakirja, kurz tsk, ist ein Finnisch-Englisch-Wörterbuch und bietet eine Funktion, bei der während des Tippens schrittweise gesucht wird
• Diese Funktion ist im Kern ein Problem der Präfixsuche, und die klassische Lösung für Präfixsuche in der Autovervollständigung war eine Implementierung mit Tries
• Die erste Implementierung wurde in Go geschrieben, und ein frühes Designziel war es, das gesamte Programm als eine .exe, eine .app oder eine einzelne statisch gelinkte Binärdatei auszuliefern
• Bei Wortmengen im mittleren sechsstelligen Bereich wurden nur die ersten etwa 50 oder 100 Ergebnisse zurückgegeben, statt alle Treffer für Einträge zu liefern, die einem einstelligen Prozentanteil davon entsprachen, und Kombinationen aus 1, 2 und 3 Buchstaben wurden memoisiert
• So ließ sich ein Trie mit grundlegenden Optimierungen auf etwa 60 MB unterbringen, und selbst nach einem Jahr intensiver privater Nutzung war keine spürbare Verzögerung festzustellen

Das Größenproblem durch finnische Flexionsdaten

• Finnisch ist eine agglutinierende Sprache, daher kann ein einzelnes Grundwort, wenn man alle Kombinationen berücksichtigt, mehr als 100 Endungen haben
• Diese Kombinationen sind nicht regelmäßig, und die stark regularisierte finnische Orthografie spiegelt die Formen tatsächlicher Sprecher direkt im Schriftbild wider, sodass Grundwörter beim Verbinden mit Endungen wachsen, sich verschieben und verändern
• Anfänger bleiben leicht an bestimmten Wörtern in Sätzen wie „Opiskelijassammekin on leijonan sydän“ hängen, und tsk sollte auch Informationen enthalten, die helfen, Wörter an den richtigen Grenzen zu zerlegen
• Sprachwissenschaftlich gehören solche Veränderungen zu Konsonantenwechsel und Vokalharmonie, und Finnisch verwendet beides zugleich
• Zum Beispiel bedeutet katu „street“, aber der Genitiv ist nicht katun, sondern kadun, weil das t in einer geschlossenen Silbe zu d abgeschwächt wird
• Multipliziert man diese Struktur mit 15 Fällen, 2 Pluralen, 6 Possessivsuffixen und einer unbestimmten Zahl an Klitika, kann ein naiver Trie die Kosten gemeinsam genutzter Endstücke wie -ssa-mme-kin, die Tausende Wörter teilen, nicht aufteilen
• Rund 400.000 Einträge ließen sich mit einem Trie in etwa 50 MB RAM halten, doch derselbe Ansatz skalierte nicht auf 40 bis 60 Millionen Einträge
• Als Zwischenlösung wurden Flexionsformen in eine separate SQLite-FTS-Datenbank ausgelagert und bei Bedarf durchsucht; das funktionierte ohne spürbare Latenz, erforderte aber einen einmaligen initialen 3-GB-Download

Das Ergebnis nach dem Wechsel zu Rust und FST

• Neun Monate später wurde ein neuer Versuch in Rust gestartet, und dafür entstand ein minimales Rust-Programm, das Daten aus der 3-GB-SQLite-Datenbank extrahiert und in ein FST komprimiert
• Auslöser war der Artikel von BurntSushi aka Andrew Gallant Index 1,600,000,000 Keys with Automata and Rust, dessen Kerngedanke war, dass endliche Zustandsautomaten sortierte Mengen oder Maps von Strings klein und schnell darstellen können
• Die resultierende Binärdatei war etwa 10 MB groß und sparte gegenüber der 3-GB-SQLite-Datenbank ungefähr den Faktor 300 beim Speicherplatz
• Dieser Anwendungsfall passte auch besonders gut zum fst crate, weil es darum ging, Flexions- und Konjugationsformen einer stark agglutinierenden Sprache auf ihre ursprünglichen Definitionen zurückzuführen
• Ein Trie komprimiert Präfixe, ein FST komprimiert dagegen sowohl Präfixe als auch Suffixe
• Im finnischen Wörterbuchkorpus gibt es eine kleine Zahl sehr häufig wiederkehrender populärer Suffixe, weshalb das Teilen von Suffixen einen großen Effekt hat
• Die Daten sind statische Daten, die sich zur Laufzeit nicht ändern, wodurch die größte Schwäche von fst vermieden werden konnte

Warum das FST kleiner als ein Trie wurde

• Der entscheidende Punkt, der ein FST bei natürlichsprachlichen Daten deutlich kleiner als ein Trie macht, ist das Teilen von Suffixen
• Ein Trie teilt Präfixe, etwa indem kadun und kaduille die ersten drei Knoten gemeinsam nutzen, speichert unterschiedliche Suffixpfade jedoch jeweils separat
• Ein minimaler azyklischer deterministischer endlicher Automat führt zwei strukturell identische Unterbäume zusammen
• In einem Korpus, in dem 100.000 Wörter mit denselben ungefähr 12 Flexionsmustern enden, führt dieses Zusammenführen zu großen Speichereinsparungen
• Die zentrale Heuristik dieses Falls besteht darin, eine improvisierte Allzweckdatenbank durch eine kleine, statische Spezialdatenstruktur zu ersetzen, die exakt nur die benötigte Aufgabe erfüllt, und so eine 300-fache Speicherersparnis zu erzielen

Die verbleibende Rolle der vorläufigen SQLite-Lösung und die Distributionsgröße

• Die Entscheidung für SQLite vor neun Monaten war das Ergebnis, lieber „schlecht, aber einfach“ zu wählen als „das Gute nicht umsetzen zu können“, und sie hat tatsächlich funktioniert
• Weil bereits ein Verständnis für den B-Baum von SQLite und die Full Text Search extension vorhanden war, war das damals eine Lösung, mit der sich schnell experimentieren ließ
• Dieselbe FTS-Erweiterung wird auch für einige seltener genutzte Funktionen verwendet, die im Alpha von tsk v2.0.0 noch fehlen, könnte aber komplett entfernt werden, falls sie den aktuellen Memory Footprint verschlechtert
• Die Pro-Version von v2 liegt inklusive allem bei etwa 20 MB, also dreimal kleiner als die kostenlose Version von v1
• tsk begann ursprünglich als TUI-Go-Programm, entwickelte sich aus dem früheren fzf-basierten Prototyp finstem weiter und steht in Verbindung mit the highest-ROI program I’ve written so far
• taskusanakirja bedeutet auf Finnisch „pocket dictionary“, und es gilt weiterhin der Maßstab, dass es, wenn es nicht einmal auf einen alten Laptop passt, eher einem kompilierbaren alten Oxford-Wörterbuch ähnelt als einem Taschenwörterbuch
• Es gibt ein wiederkehrendes Muster von „Es ist in Ordnung, ein Problem zweimal zu lösen“, und statt aus Schuldgefühl darüber zu verharren, dass man nach einer bereits besseren bestehenden Implementierung suchen sollte, kommt man oft schneller an die echten Grenzen, wenn man ein paar Räder selbst neu erfindet
• Diese Sichtweise steht in Verbindung mit der Caplanian view von „Übung“, und Do Ten Times as Much wird als unangenehmer, aber funktionierender Rat präsentiert

[GN⁺]

Lobste.rs-Kommentare

• Der Artikel selbst war schon interessant, und ich mochte, wie hier das richtige Werkzeug auf die richtige Aufgabe angewendet wurde und so eine Verbesserung im einstelligen Faktorbereich herauskam, aber noch eindrucksvoller als der Haupttext war für mich die letzte Fußnote
  Sie trifft genau dieses lähmende Schuldgefühl, dass das Tool, das man gerade baut, vielleicht schon vor 30 oder 40 Jahren von jemand anderem besser umgesetzt wurde. Aber das ist eine Falle, und die Aussage, dass man ein paar Räder selbst neu erfinden muss, um überhaupt bis an die Grenze des Radbauens zu kommen, hat mich angesprochen. In den meisten Bereichen reichen vier oder fünf davon, und selbst in strengen Disziplinen wie Mathematik oder Informatik können es vielleicht nur zweiundzwanzig oder dreiundzwanzig sein; die Fragen, die man sich beim eigenen Nachbauen stellt, bringen einen viel schneller an die echte Frontlinie als bloßes Lernen

  • Ein wichtiger verwandter Punkt im Text ist, dass auch die ineffiziente Brute-Force-Implementierung mit einer SQLite-DB als Referenzimplementierung wertvoll war
    Weil es zunächst überhaupt eine funktionierende Referenzimplementierung gab, wurde es viel einfacher, eine effiziente Implementierung als Ersatz zu bauen
  • Das passt exakt zu dem Problem, das ich gerade habe. Ich wollte etwas bauen, das für meinen Problemraum optimiert ist, habe aber gezögert, weil ich wusste, dass das verallgemeinerte Problem längst gelöst ist
    Wenn ich mir die bestehenden Lösungen anschaue, hängt daran aber viel Ballast, den ich nicht brauche. Aus Erfahrung weiß ich eigentlich, dass es sich lohnt, meine Idee weiterzuverfolgen, und trotzdem habe ich ständig gedacht, ich würde vielleicht etwas übersehen. Nachdem ich das gelesen habe, probiere ich es jetzt einfach. Selbst wenn es scheitert, werde ich dabei etwas lernen

• Sehr cool. Musste an Compressing Icelandic name declension patterns into a 3.27 kB trie denken

• Beim Implementieren eines Scrabble-Bots bin ich auf die verwandte Datenstruktur DAWG (Directed Acyclic Word Graph) gestoßen, und für diesen Einsatzzweck scheint sie ziemlich verbreitet zu sein
  Der Hauptunterschied zum fst-Crate scheint zu sein, dass nicht jedes Wort auf eine eindeutige Ganzzahl abgebildet wird. Die Größe wurde ähnlich stark reduziert und die Performance wurde ebenfalls massiv besser. Ein Scrabble-Bot muss im Grunde das gesamte Wörterbuch nach Wörtern filtern, die auf einfache Regexe wie ..cat.. passen, in der Praxis aber alle einfachen Regexe verarbeiten, die auf dem aktuellen Brett möglich sind. Ein Vorgang, der früher etwa eine Minute dauerte, wurde zu einer faktisch nicht wahrnehmbaren Verzögerung

  • Das DAWG-Paper von Appel und Jacobson aus dem Jahr 1988 wurde vor Kurzem hier schon einmal gepostet und auch früher bereits geteilt

• Der verlinkte Artikel ist ebenfalls lesenswert: https://burntsushi.net/transducers/

• fst war schließlich auch das Werkzeug, das ich für die deutsche Unterstützung von srgn verwendet habe, nachdem Andrew es selbst empfohlen hatte
  Es ist derselbe Problemraum des Komprimierens gemeinsamer Präfixe und Suffixe, und es funktioniert wirklich gut. Da es außerdem ein CLI-Tool ist, musste auch der Startup-Overhead minimiert werden, und das fst-Crate unterstützt Zero-Copy-Loading, sodass es keinen Runtime-Overhead gibt. Das FST wird zur Compile-Zeit erzeugt

• Wirklich großartig, und ich wünschte, es gäbe so etwas auch für Deutsch und Englisch. Deutsche Komposita bringen mich noch immer oft durcheinander