Isländische Namensdeklinationsmuster mit einem 3.27kB-Trie komprimieren

(alexharri.com)

2 Punkte von GN⁺ 2025-08-04 | Noch keine Kommentare. | Auf WhatsApp teilen

Die Deklination isländischer Personennamen verändert sich je nach Kontext in vier Formen
Durch eine datenbasierte JavaScript-Bibliothek wurde eine Funktion entwickelt, die den passenden grammatischen Fall für den eingegebenen Namen zurückgibt
Würden alle Namen direkt gespeichert, entstünden Speicherzuwachs und Datenlücken; dieses Problem wird durch Trie-Strukturen und Komprimierungstechniken gelöst
Dank der Trie-Komprimierung ist eine automatische Ableitung anhand gemeinsamer Muster möglich, wodurch eine sehr kleine Datenbank entsteht, die über 80 % der Daten abdeckt
In regulären Szenarien werden über 74 % Genauigkeit erreicht; für den öffentlichen Bereich und Kontexte mit streng erforderlicher Genauigkeit wird eine separate strict-Version angeboten

Hintergrund des Problems

Bei der Anzeige von isländischen Personennamen in isländischen Oberflächen treten Schwierigkeiten durch die isländische Deklination auf
Isländische Namen haben je nach Grammatikfall Nominativ, Akkusativ, Dativ und Genitiv bis zu vier unterschiedliche Formen
In Datenbanken werden Namen meist in der Nominativform gespeichert, wodurch es zu Schwierigkeiten kommt, wenn im Kontext ein anderer Fall benötigt wird
Eine falsche Form wirkt auf Muttersprachler unnatürlich oder hölzern

Die isländische Institution Árnastofnun stellt die Daten der DIM(Database of Icelandic Morphology) bereit
Für Namensdeklinationen können die Daten im CSV-Format über Kristín’s Format (K-format) aufbereitet werden
Der gesamte DIM-Datensatz umfasst 7 Millionen Zeilen und ist damit zu groß; nach dem Filtern auf offiziell freigegebene Personennamen (4.500) können für etwa 3.600 Namen Deklinationsinformationen gewonnen werden
Für jeden Namen kann ein Array der Formen von Nominativ bis Genitiv aufgebaut werden

Die erste Implementierung begann mit einer applyCase-Funktion, die aus einem Namen~Fall-Transformations-Array die passende Form zurückgibt
Die reine Array-Ladeweise war jedoch mit 30kB gzip noch groß
Ein weiterer Nachteil bestand darin, dass auf Namen ohne Eintrag in den Daten nicht geantwortet werden konnte

Es werden gemeinsame Präfixe zwischen den vier Formen eines Namens extrahiert und nur die jeweilige Suffix-Menge (Suffix-Kodierung) gespeichert, um Duplikate zu minimieren
Dabei zeigte sich, dass viele Namen demselben Deklinationsmuster folgen

Durch den Einsatz einer Trie-Struktur (Einfügen der Suffixe in umgekehrter Reihenfolge) wurde die Wertabbildung für Namensgruppen mit ähnlichen Mustern optimiert
Unter gemeinsamen Mustern (Namenendungen) wird die Deklinationsinformation nur einmal gespeichert, was eine hohe Vorhersagekraft für neue Namen ermöglicht

Ist der Wert in den Blättern eines Unterbaums gleich, wird er im Elternknoten abgelegt und die Kinder werden entfernt, wodurch der Baum komprimiert wird
Dadurch wurde die Knotenzahl um bis zu 15.4 % reduziert und die Größe auf 4.01kB verkleinert
Eine zweite Kompression fasst Schwester-Blattknoten mit gleichem Wert zu einem Knoten zusammen und erreicht 3.27kB

Bei der Eingabe neuer Namen ist eine automatische Deklination anhand ähnlicher Muster möglich
Bei bisher unbekannten Namen wurden 74 % korrekte Deklinationen und 26 % Fehler gemessen; in realen Nutzerszenarien liegt die Fehlerquote jedoch nur bei 0.34 %
Je höher die Regularität und Vollständigkeit der Daten ist, desto stärker steigen die Kompression und die Genauigkeit der automatischen Ableitung

Abschließend wurde die komprimierte Trie im beygla-Repository ausgeliefert
Sie wird als Minimalgröße (4.46kB) sowie als strengere und vollständigere, anpassbare strict-Modulvariante (15kB) angeboten
In öffentlichen Dokumenten und Umgebungen, die 100 % Genauigkeit verlangen, sollte die strict-Version genutzt werden; für normale Web-Apps ist die leichtgewichtige Version ausreichend

Die Komprimierung von sprachlichen Deklinationsmustern mit Trie-Strukturen lässt sich auf andere flektierende Sprachen für Eigennamen, Adressen und andere Substantive übertragen
Die Kombination aus hochgradiger Regularität der Daten und Trie-Komprimierung stellt eine Strategie zur maximalen Daten-/Leistungseffizienz in der automatisierten flektiven Verarbeitung dar

Während der Entwicklung von beygla gab es umfangreiches Expertenfeedback und weitere Optimierungen
Mit zusätzlicher Trie-Komprimierung wurde die Größe von 3.43kB auf 3.27kB reduziert

Der Artikel zeigt ein Beispiel für die Automatisierung der isländischen Namensdeklination mit einer klein gehaltenen, auf einem Trie basierenden Struktur
Er liefert ein praxisnahes Datenverarbeitungsmodell für den Ausgleich zwischen Speicherbedarf und Genauigkeit