- La déclinaison des noms propres islandais varie selon le contexte en 4 formes
- Développement, via une bibliothèque JavaScript basée sur les données, d'une fonction renvoyant le cas grammatical approprié pour un nom saisi
- En stockant tous les noms, on rencontre une augmentation de taille et des problèmes de données manquantes ; l'utilisation d'une structure en trie et de techniques de compression permet de les résoudre
- Grâce à la compression par trie, il devient possible d'inférer automatiquement à partir de motifs communs et d'obtenir une base de données extrêmement petite, couvrant plus de 80 % des données
- En situation normale, la précision dépasse 74 %, tandis qu'une version stricte distincte (
strict) est fournie pour le secteur public et les cas exigeant une grande exactitude
Contexte du problème
- L'affichage des noms personnels dans une interface islandaise est compliqué par la déclinaison
- Les noms islandais ont des formes différentes selon les 4 cas grammaticaux : nominatif, accusatif, datif et génitif
- Les bases de données stockent généralement les noms sous forme nominative, ce qui pose problème quand d'autres cas grammaticaux sont nécessaires selon le contexte
- Utiliser une forme incorrecte donne une impression peu naturelle, voire maladroite, à un locuteur natif
Collecte et nettoyage des données
- L'Islande a publié les données DIM (Database of Icelandic Morphology), gérées par Árnastofnun
- Les données de déclinaison des noms peuvent être transformées au format CSV Kristín's Format (K-format)
- Les données DIM comptent 7 millions de lignes au total, ce qui est extrêmement volumineux ; en retenant seulement les noms personnels officiellement approuvés (4 500), on obtient des informations de déclinaison pour un peu plus de 3 600 noms
- Pour chaque nom, on peut construire un tableau des formes allant du nominatif au génitif
Structure de base de la bibliothèque
- L'implémentation initiale commence avec une fonction applyCase qui renvoyait la forme appropriée à partir d'un tableau nom~cas
- Mais le chargement simple du tableau est massif (30 kB gzipped)
- Elle ne pouvait pas gérer les noms qui ne sont pas inclus dans les données
Déduplication et extraction de motifs
- J'ai extrait les préfixes communs entre les 4 formes d'un nom et j'ai stocké uniquement des ensembles de suffixes (encodage de suffixes) pour minimiser les doublons
- Il existe beaucoup de noms suivant le même schéma de déclinaison
Introduction d'un trie pour la correspondance de motifs
- L'adoption d'une structure trie (insertion inversée par suffixe) permet d'optimiser la correspondance de valeurs pour les groupes de noms partageant des motifs similaires
- L'information de déclinaison n'est stockée qu'une seule fois sous les terminaisons communes des noms, tout en conservant une forte capacité de prédiction pour les noms nouveaux
Compression et optimisation du trie
- Si la valeur est identique pour chaque feuille (leaf) d'un sous-arbre, j'affecte la valeur au nœud parent et je supprime les enfants pour compresser l'arbre
- Ainsi, le nombre de nœuds diminue de 15,4 % et la taille est réduite à 4,01 kB
- Une deuxième compression qui fusionne les nœuds feuilles frères ayant la même valeur atteint 3,27 kB
Performances et généralisation du trie
- Lorsqu'un nouveau nom est saisi, la déclinaison peut être faite automatiquement grâce aux motifs similaires
- Pour des noms inconnus en pratique, 74 % des résultats sont corrects et 26 % erronés ; pour les utilisateurs réels, le taux d'erreur n'est que de 0,34 %
- Plus la régularité (regularity) et la couverture (comprehensiveness) des données sont élevées, plus les gains sur la précision de la compression et de l'inférence automatique sont importants
Déploiement réel de la bibliothèque
- La librairie beygla, qui utilise un trie compressé, a été publiée
- Elle est proposée en taille minimale (4,46 kB) et en module strict plus rigoureux et plus complet (15 kB)
- Le version strict est destinée aux documents officiels, où 100 % de précision est exigée, tandis que la version légère convient aux applications web courantes
Conclusion et possibilités d'extension
- La compression des données de schéma de déclinaison via trie peut être appliquée à l'automatisation des noms propres, adresses et autres noms dans plusieurs langues flexionnelles en dehors de l'islandais
- La combinaison de données à forte régularité et de compression par trie constitue une voie optimale pour maximiser l'efficacité des données et des performances du traitement automatique de la déclinaison
Remerciements
- Le développement de beygla a bénéficié de retours d'experts et d'une série d'optimisations
- La compression supplémentaire du trie a réduit la taille de 3,43 kB à 3,27 kB
Résumé
- C'est un exemple de cas d'automatisation et de miniaturisation du problème de déclinaison des noms islandais avec une structure trie basée sur des motifs
- Cela illustre une stratégie pratique de traitement des données, en choisissant intelligemment le compromis entre taille et précision
1 commentaires
Avis Hacker News
Quand j’ai commencé à apprendre l’espagnol au lycée, j’utilisais un logiciel Windows qui affichait à la chaîne des infinitifs et des temps, et il fallait saisir la forme conjuguée correspondante. Ce genre d’entraînement m’a vraiment permis d’intérioriser les règles de grammaire et de gagner en aisance. En revanche, en apprenant le russe, les déclinaisons des cas sont soudain devenues difficiles, et j’ai eu beau chercher une app capable d’expliquer ou de faire pratiquer des schémas similaires, je n’en ai pas trouvé. Je me demande si quelqu’un connaît une app (web ou macOS/iOS) faite pour ça
Il existe un deck de flashcards Anki qui utilise une méthode appelée « KOFI (Konjugation First) ». KOFI consiste à apprendre d’abord tous les schémas de conjugaison avant d’apprendre la langue elle-même. Après avoir étudié le français, j’ai essayé cette méthode plus tard parce que ma maîtrise des conjugaisons était insuffisante ; même si parler avec des erreurs de grammaire ne gêne pas la communication quotidienne, ce n’était pas le niveau que je visais. L’objectif de cette méthode est de maîtriser en peu de temps tous les schémas de conjugaison avant d’apprendre la langue. J’aimerais l’appliquer sérieusement un jour à une nouvelle langue. J’ai fini par abandonner le français parce que mon intérêt avait diminué. Lien vers le deck Anki correspondant
En apprenant le russe, j’ai déjà écrit un script combinant le module Python spaCy et un gros modèle russe pour faire de la lemmatisation contextuelle et extraire des tags grammaticaux. Mais en pratique, quand mon niveau de russe a vraiment progressé, il a été bien plus efficace d’arrêter d’essayer de démonter les déclinaisons de manière logique et de construire dans ma tête une bibliothèque de schémas, exceptions comprises, à force d’usage et de répétition. Ici, par contexte, j’entends le sens dans la phrase
Quand j’apprenais l’espagnol en autodidacte il y a 25 ans, j’utilisais un dictionnaire espagnol/anglais. Les infinitifs verbaux portaient un index numérique qui les classait par groupes partageant le même schéma de conjugaison. Au début du dictionnaire, il y avait pour chaque groupe le tableau complet des temps du verbe représentatif. Les verbes irréguliers avaient un index séparé et étaient eux aussi regroupés avec des verbes irréguliers similaires (par ex. tener, detener). Tous les verbes étaient ainsi proprement organisés en quelques dizaines de schémas distincts. J’avais même pensé créer un logiciel de quiz basé sur ce système, mais je ne l’ai jamais fait. Je me demande si le motif de reverse-string trie mentionné dans l’article pourrait aussi servir à ce type de classification
Pour mémoriser les déclinaisons russes, j’avais eu l’idée de créer des flashcards avec des combinaisons préposition + adjectif + nom afin d’accélérer la mémorisation. J’avais auparavant appris le latin, mais pour ses déclinaisons je ne m’attendais pas à les retenir vite (sauf peut-être si j’étais moine ?), alors qu’en russe je voulais aller plus rapidement. Mais là encore, le projet n’a jamais abouti
J’utilise ConjuGato sur iOS pour pratiquer les conjugaisons espagnoles. En mode jeu, on te donne l’infinitif, le temps et la personne, et tu dois retrouver la forme conjuguée. On peut aussi s’entraîner uniquement sur les verbes irréguliers, ce qui est efficace pour assimiler les exceptions
Pour les 800 noms dont les informations de déclinaison manquent dans la base de données, la solution la plus simple me paraît être d’ajouter les déclinaisons à la main. Pour un locuteur natif, cela se ferait en quelques heures, et même pour des noms totalement inconnus, il devrait au moins être possible d’estimer une forme qui ne sonne pas manifestement faux. Ou alors on pourrait demander à un LLM de le faire pour un coût dérisoire. Encoder ensuite le résultat dans une structure de trie pour la distribution reste une bonne idée. En revanche, il n’est pas nécessaire d’utiliser le trie comme estimateur de déclinaison
Il serait préférable de gérer davantage de noms — c’est un point à améliorer en continu dans DIM. En Islande, de nouveaux noms sont souvent ajoutés à la liste des noms autorisés, donc il y aura toujours des lacunes. Personnellement, je manque de confiance pour ajouter moi-même des données, et à chaque revue de résultats sur 100 noms non vérifiés, il m’arrive souvent de me demander « est-ce vraiment correct ? ». Plusieurs fois, j’ai cherché des noms similaires dans DIM en me disant « je ne les déclinerais pas comme ça ». Donc je traite les données DIM comme une source de vérité maintenue par des experts linguistiques
Le travail manuel est bien, mais il a toujours ses limites pour les noms qui ne figurent pas sur la liste officielle, comme les noms étrangers. Je vis moi aussi dans un pays avec une liste centralisée de prénoms, mais on peut demander des exceptions, et des personnes nées avant l’existence de la liste ou des immigrés peuvent porter des noms qui n’y figurent pas. Dans ce type de situations composites, une fonction de « prédiction de déclinaison à peu près correcte » reste utile
Je n’ai trouvé aucun élément permettant de dire qu’un LLM prédirait mieux les déclinaisons qu’un trie (si l’exemple concret n’est pas dans ses données d’entraînement, une recherche web serait probablement plus utile)
Cela m’amène à me demander si les LLM existants ont déjà appris ce genre de motifs
Je ne suis pas sûr que Rails gère automatiquement ce problème, mais autrefois il faisait ce genre de magie. J’avais regardé le code source de
pluraliseil y a longtemps, et même les règles de pluriel irrégulier du gallois y étaient encodéesUne idée d’optimisation serait, au lieu de faire pointer directement le trie vers la chaîne de suffixes, de créer un tableau de suffixes uniques puis de faire référencer depuis le trie l’index dans ce tableau. Par exemple :
puis de référencer les index ainsi :
Je l’ai essayé moi-même avec Claude Code, et une fois gzippé c’était au contraire 100 octets plus gros (3456 -> 3556), même si la taille avant compression a baissé de 20 %. J’imagine que c’est parce que gzip est déjà très bien optimisé pour ce type de motifs répétitifs
On pourrait aller plus loin en mettant les suffixes eux-mêmes dans un trie, puis en identifiant les sous-arbres identiques pour les dédupliquer. Si on peut utiliser gzip, il doit sûrement exister une optimisation plus intelligente exploitant ce tableau de suffixes. Avec un format binaire optimisé, ce serait peut-être encore mieux
J’ai personnellement l’impression tenace qu’il doit exister une solution quasi magique pour descendre sous 1kb sans compression. Une liste minimale d’expressions régulières qui classerait les noms avec 100 % de précision ? Un très gros bloom filter ? Ou bien une méthode utilisant des features spécialisées plutôt qu’un hash générique ?
On dirait une question d’entretien cauchemardesque. Utiliser un trie à l’envers (en ordre inverse) est le genre de chose qu’on ne fait qu’une seule fois dans sa vie, mais une fois qu’on le fait, on passe pour un magicien
Plutôt que de faire ça en JS, on pourrait peut-être faire renvoyer par la base de données toutes les combinaisons nom-cas, puis ne sélectionner à l’affichage que celles dont on a besoin. En d’autres termes, le traitement se ferait dans la couche de localisation. Je me demande comment cela fonctionnerait dans des contextes multilingues. Si une interface islandaise gère des noms français, elle utiliserait probablement toujours le nominatif, et pareil si une interface anglaise gère des noms islandais. En fin de compte, le besoin semble surtout important dans les contextes où l’on s’adresse directement à l’utilisateur, ou dans des interfaces d’administration du type « l’utilisateur x a répondu à l’utilisateur y »
Il existe 88 noms suivant un certain schéma de déclinaison qui se terminent par « idur », « tur » ou « ður », mais un même suffixe ne suit pas toujours le même schéma de déclinaison. Le problème ressemble à une règle simple, alors qu’en réalité il est très intéressant. Est-ce que le schéma de suffixe dépendrait de la prononciation de la syllabe précédente ? Pour mieux gérer des noms inconnus, faudrait-il extraire via du NLP une représentation phonétique du nom, puis l’interroger avec un trie ou autre, plutôt que de s’appuyer uniquement sur les lettres ?
Il faut faire attention, ce genre de réflexion peut facilement dériver vers une discussion sur les Dependent Types
C’est une idée pertinente. En réalité, il existe même des noms de prononciation identique qui suivent des schémas de déclinaison différents. Par exemple :
Dans un contexte beygla/strict, on peut envisager le perfect hashing comme alternative
Je suis surpris que la déclinaison des noms islandais suive des motifs suffisamment déterministes et simples pour qu’une approche comme celle-ci fonctionne si bien. En général, les langues sont quand même assez complexes