- 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
Datensammlung und Bereinigung
- 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
Grundstruktur der Bibliothek
- 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
Duplikatentfernung und Musterauswertung
- 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
Einführung von Trie für das Pattern-Matching
- 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
Trie-Komprimierung und -Optimierung
- 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
Trie-Leistung und Verallgemeinerung
- 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
Praxisanwendung der Bibliothek
- 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
Fazit und Erweiterbarkeit
- 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
Danksagung
- 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
Zusammenfassung
- 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
1 Kommentare
Hacker-News-Kommentare
Als ich in der Oberstufe zum ersten Mal Spanisch lernte, nutzte ich eine Windows-Software, die einem Infinitive und Zeiten nur so um die Ohren haute und bei der man dann die passende Verbform eingeben musste. Durch dieses Training gingen mir die Grammatikregeln richtig in Fleisch und Blut über. Als ich später Russisch lernte, wurden die Kasusbeugungen plötzlich schwierig, und ich konnte trotz intensiver Suche keine App finden, mit der man ähnliche Muster erklären oder üben könnte. Ich frage mich, ob jemand eine App für genau so einen Zweck kennt (Web oder macOS/iOS)
In Anki gibt es ein Flashcard-Deck, das die Methode „KOFI (Konjugation First)“ verwendet. KOFI bedeutet, vor dem eigentlichen Sprachenlernen zuerst alle Beugungsmuster zu lernen. Nachdem ich Französisch gelernt hatte und mit meinen Konjugationsfähigkeiten unzufrieden war, habe ich diese Methode später ausprobiert. Für die alltägliche Kommunikation war es zwar kein Problem, grammatikalisch falsch zu sprechen, aber das entsprach nicht dem Niveau, das ich wollte. Das Ziel dieser Methode ist, alle Beugungsmuster in kurzer Zeit zu lernen, bevor man die Sprache selbst lernt. Ich würde das gern irgendwann ernsthaft auf eine neue Sprache anwenden. Mein Interesse an Französisch hat allerdings nachgelassen, daher habe ich es unterwegs aufgegeben. Link zum Anki-Deck
Beim Russischlernen habe ich einmal ein Skript gebaut, das das Python-Modul spaCy zusammen mit einem großen russischen Modell verwendet, um kontextbasierte Lemmatisierung und Grammatik-Tag-Extraktion durchzuführen. Aber als sich mein Russisch tatsächlich verbesserte, war es viel effektiver, den Versuch aufzugeben, Beugungen logisch zu zerlegen, und stattdessen durch Nutzungserfahrung und Wiederholung eine Bibliothek von Mustern im Kopf aufzubauen, inklusive Ausnahmen. Mit Kontext ist hier übrigens die Bedeutung innerhalb des Satzes gemeint
Als ich mir vor 25 Jahren selbst Spanisch beibrachte, benutzte ich ein Spanisch/Englisch-Wörterbuch. Bei den Infinitiven standen Zahlenindizes, die sie in Gruppen mit demselben Konjugationsmuster einordneten. Im vorderen Teil des Wörterbuchs gab es für jede Gruppe die vollständigen Konjugationstabellen eines repräsentativen Verbs in allen Zeiten. Unregelmäßige Verben hatten eigene Indizes und wurden ebenfalls nach ähnlichen unregelmäßigen Mustern gruppiert (z. B. tener, detener). Alle Verben waren sauber in einige Dutzend eindeutige Muster einsortiert. Ich hatte auch mal vor, Quiz-Software auf Basis dieses Systems zu bauen, habe es aber am Ende nicht getan. Ich frage mich, ob das im Artikel erwähnte Reverse-String-Trie-Muster auch für so eine Art Klassifikation genutzt werden könnte
Um russische Kasusbeugungen zu lernen, hatte ich die Idee, Flashcards mit Kombinationen aus Präposition + Adjektiv + Substantiv zu erstellen, um das Auswendiglernen zu beschleunigen. Ich hatte zuvor schon Latein gelernt; bei lateinischen Kasusbeugungen erwartet man nicht unbedingt, sie schnell zu memorieren (außer vielleicht als Mönch?), aber bei Russisch wollte ich schneller vorankommen. Letztlich wurde daraus aber kein Projekt
Für spanische Konjugationsübungen nutze ich ConjuGato für iOS. Im Spielmodus bekommt man Infinitiv/Zeit/Person vorgegeben und muss die konjugierte Form abrufen. Man kann auch nur unregelmäßige Verben üben, was effektiv ist, um Ausnahmen zu lernen
Bei den 800 Namen, für die in der Datenbank Kasusbeugungsinformationen fehlen, scheint die naheliegendste Lösung zu sein, die Beugungen von Hand zu vergeben. Für Muttersprachler wäre das in ein paar Stunden erledigt, und selbst bei völlig unbekannten Namen ließe sich zumindest eine Form schätzen, die nicht offensichtlich seltsam wirkt. Oder man lässt es ein LLM machen, was sehr billig wäre. Das Ergebnis dann in so einer Trie-Struktur zu kodieren und auszuliefern ist weiterhin eine gute Idee. Nur müsste man das Trie nicht auch noch als Schätzer für Kasusbeugungen benutzen
Es wäre wünschenswert, mehr Namen abzudecken — bei DIM ist das etwas, das laufend ergänzt werden muss. In Island kommen regelmäßig neue Namen auf die Liste zugelassener Namen, daher wird es zwangsläufig immer Lücken geben. Ich bin mir selbst nicht sicher genug, um Daten direkt hinzuzufügen, und beim Prüfen der Ergebnisse für 100 unbestätigte Namen gab es öfter Momente, in denen ich dachte: „Ist das wirklich richtig?“ Ich habe ähnliche Namen in DIM nachgeschlagen und mehrmals gedacht: „So würde ich das nicht beugen.“ Deshalb nehme ich die DIM-Daten als von Sprachexperten gepflegte Quelle der Wahrheit
Handarbeit ist gut, aber bei Namen, die nicht auf der offiziellen Liste stehen (etwa ausländischen Namen), bleibt das trotzdem begrenzt. Ich lebe auch in einem Land mit einer zentralen Namensliste, aber man kann Ausnahmen beantragen, und Menschen, die vor Einführung der Liste geboren wurden oder eingewandert sind, können Namen haben, die dort nicht stehen. In solchen komplexen Mischlagen bleibt eine Funktion zur „ungefähr passenden Beugungsvorhersage“ weiterhin nützlich
Ich habe keine Grundlage dafür gefunden zu sagen, dass ein LLM Kasusbeugungen besser vorhersagt als ein Trie (wenn das konkrete Beispiel nicht schon in den Trainingsdaten des LLM enthalten ist, wäre Websuche wohl besser)
Das weckt die Frage, ob bestehende LLMs solche Muster bereits gelernt haben
Ich bin nicht sicher, ob Rails dieses Problem automatisch löst, aber früher konnte es solche Magie ziemlich gut. Ich habe mir einmal den Source Code von pluralise angesehen, und dort waren sogar unregelmäßige Pluralregeln des Walisischen kodiert
Eine Optimierungsidee wäre, das Trie nicht direkt auf die Suffix-Strings selbst abbilden zu lassen, sondern ein Array eindeutiger Suffixe anzulegen und das Trie auf die Indizes dieses Arrays verweisen zu lassen. Zum Beispiel:
und dann so auf die Indizes zu verweisen:
Ich habe das selbst mit Claude Code ausprobiert, und im gzip-Zustand wurde es sogar um 100 Byte größer (3456 -> 3556), während nur die unkomprimierte Größe um 20 % sank. Vermutlich liegt das daran, dass gzip selbst bei wiederholten Mustern bereits sehr gut optimiert ist
Man könnte noch einen Schritt weitergehen, die Suffixe selbst in ein Trie legen und identische Teilbäume erkennen und deduplizieren. Wenn man gzip verwenden kann, gibt es bestimmt clevere Optimierungen mit so einem Suffix-Array. Mit einem binären, optimierten Format wäre es vielleicht noch besser
Ich habe persönlich ständig das Gefühl, es müsse eine magische Lösung geben, die das unkomprimiert auf <1kb bringt. Eine minimierte Liste regulärer Ausdrücke, die Namen mit 100% Genauigkeit klassifiziert? Ein sehr großer Bloom-Filter? Oder ein Ansatz, der statt gewöhnlicher Hashes spezialisierte Features nutzt?
Das klingt wie eine Interviewaufgabe direkt aus dem Albtraum. Ein Trie umgedreht zu verwenden, also in umgekehrter Reihenfolge, ist wahrscheinlich so etwas, das man im Leben genau einmal braucht — aber wenn man es dann einsetzt, wirkt man wie ein Zauberer
Statt das in JS zu machen, könnte man auch einfach aus der Datenbank alle Kombinationen aus name-case zurückgeben und beim Anzeigen nur das auswählen, was gerade gebraucht wird. Also eher in der Lokalisierungsschicht. Ich frage mich, wie das in sprachübergreifenden Situationen wäre. Wenn eine isländische UI mit französischen Namen zu tun hat, würde man wahrscheinlich immer den Nominativ verwenden, und bei einer englischen UI mit isländischen Namen wohl genauso. Wirklich wichtig wird es am Ende wohl nur in Kontexten, in denen man Nutzer direkt bezeichnet oder anspricht, oder in Admin-Panels („Benutzer x hat Benutzer y geantwortet“) und Ähnlichem
Es gibt ganze 88 Namen mit bestimmten Beugungsmustern, die auf „idur“, „tur“ oder „ður“ enden, aber dasselbe Suffix folgt nicht immer demselben Beugungsmuster. Das Problem wirkt wie eine einfache Regel, ist in Wirklichkeit aber ausgesprochen interessant. Hängt das Suffixmuster vielleicht mit der Aussprache der unmittelbar vorhergehenden Silbe zusammen? Wenn man unbekannte Namen besser behandeln wollte, müsste man dann statt nur buchstabenbasiert vielleicht per NLP eine Lautdarstellung des Namens ableiten und darüber ein Trie oder Ähnliches abfragen?
Bei solchen Überlegungen muss man aufpassen, nicht in Diskussionen über Dependent Types abzudriften
Scharfsinnige Idee. Tatsächlich gibt es sogar Namen mit gleicher Aussprache, aber unterschiedlichen Beugungsmustern. Zum Beispiel:
In beygla/strict-Situationen könnte man Perfect Hashing als Alternative in Betracht ziehen
Es überrascht mich, dass isländische Namensbeugung offenbar einfach genug und mit ausreichend deterministischen Mustern versehen ist, damit so ein Ansatz gut funktioniert. Sprache ist normalerweise doch ziemlich komplex