アイスランド語の名前の屈折パターンを3.27kBのトライで圧縮する
(alexharri.com)- アイスランド語の個人名の屈折処理は、文脈に応じて4つの形に変化する
- データ駆動型のJavaScriptライブラリを通じて、入力された名前に対して適切な文法的格を返す機能を開発
- すべての名前を直接保存すると容量増加とデータ欠落の問題が発生するため、トライ（trie）構造と圧縮技術を活用して解決した
- トライ圧縮により共通パターンに基づく自動推論が可能になり、データの80%以上をカバーする非常に小さいデータベースを実現した
- 通常は74%以上の精度を示し、公的部門や高精度が求められる場面では別途strict版を提供
問題の背景
- アイスランド語インターフェースで個人名を表示する際、**屈折（declension）**によって困難が発生する
- アイスランド語の名前は主格、対格、与格、生格など4つの文法的格で異なる形を持つ
- データベースには一般に名前が主格形式で保存されており、文脈上別の格が必要なときに問題が起きる
- 正しい形を使わないと、母語話者でないような印象や不自然さを与える
データ収集と整形
- アイスランドはÁrnastofnunが管理するDIM（Database of Icelandic Morphology）データを公開している
- 名前に関する屈折データは**Kristín’s Format（K-format）**CSVとして加工可能
- DIM全体のデータは700万行と非常に大きいため、**公式に承認された個人名（4,500件）**のうち、約3,600件について屈折情報を取得可能
- 各名前について主格〜生格形式の配列を構成できる
ライブラリの基本構造
- 初期実装は名前と格変形配列から適切な形を返すapplyCase関数で始まった
- しかし単純な配列読み込み方式では、**容量（30kB gzipped）**が大きい
- データに含まれていない名前には対応できないという制約がある
重複排除とパターン抽出
- 名前の4つの形の間の共通接頭辞を抽出し、各**接尾辞セット（suffix encoding）**のみを保存して重複を最小化
- 同じ屈折パターンをたどる名前が多いことを発見
パターンマッチングのためのトライ（trie）導入
- **トライ構造（接尾辞ベースの逆順挿入）**を用いて、似たパターンを共有する名前群の値マッピングを最適化
- 共通パターン（name endings）配下で1回だけ屈折情報を保存することで、新しい名前にも高い予測力を確保
トライ圧縮と最適化
- 部分木のリーフ（leaf）で値が同じ場合、上位ノードに値を割り当てて子ノードを削除し、木を圧縮
- これによりノード数を最大15.4%削減し、容量を4.01kBまで縮小
- 兄弟のリーフノードで値が同じものを1つのノードにマージする第2圧縮で3.27kBまで到達
トライ性能と一般化
- 新しい名前入力時に類似パターンベースの自動屈折が可能
- 未知の名前に対しては74%が正しい屈折、26%が誤りという結果だったが、実利用者ベースの誤り率はわずか0.34%
- データの**規則性（regularity）と網羅性（comprehensiveness）**が高いほど、圧縮と自動推論精度の向上効果が大きい
実ライブラリと適用
- 最終的に圧縮トライを使用したbeyglaライブラリとして配布
- 最小サイズ（4.46kB）と、より厳密で完全なカスタム**strictモジュール（15kB）**で提供
- 公的文書などで100%の正確性が必要な場面ではstrict版、一般的なWebアプリには軽量版を選択可能
結論と拡張可能性
- トライを活用した言語の屈折パターンデータ圧縮は、アイスランド語以外にも、様々な屈折言語の人名、住所、その他名詞処理の自動化に適用可能
- 規則性の高いデータとトライ圧縮の組み合わせは、同型屈折処理自動化のデータ/性能効率を最大化する有効な方針
参考/謝辞
- beyglaの開発過程では、多くの専門家のフィードバックと最適化が行われた
- トライの追加圧縮により3.43kB→3.27kBまで容量を削減
要約
- アイスランド語の人名屈折自動化をパターンベースのトライデータ構造で軽量化・自動化した事例
- 適切な容量と精度トレードオフを考慮した実務向けデータ処理戦略の示唆に富む事例
1件のコメント
Hacker Newsのコメント
高校時代にスペイン語を初めて学んだとき、Windows用ソフトウェアを使って不定詞と時制が次々に表示され、それに合う動詞活用を入力させられた経験がある。こうした訓練のおかげで文法規則が身について上達した。しかしロシア語を学ぶときには格変化が急に難しくなり、似たパターンを説明したり練習できたりするアプリをいくら探しても見つからなかった。こういう用途の（Web または macOS/iOS）アプリを知っている人がいるか気になる
Ankiには「KOFI(Konjugation First)」という方法を使うフラッシュカードデッキがある。KOFIは、言語学習の前にまずすべての活用パターンを覚える方式を意味する。フランス語を学んだあとで活用力が足りず、後からこの方式を試してみたが、文法的に間違って話しても日常的な意思疎通には問題ないとはいえ、自分の求めるレベルではなかった。この方法は、言語を学ぶ前にすべての活用パターンを短期間で習得することを目標にしている。いつか新しい言語に本気で適用してみたい。フランス語への興味は薄れてしまい、途中でやめてしまった。関連Ankiデッキへのリンク
ロシア語を学んでいたとき、spaCy Pythonモジュールとロシア語用の大型モジュールを組み合わせて、文脈ベースのレンマ化と文法タグ抽出を行うスクリプトを作ったことがある。だが実際にロシア語力が伸びたのは、変化を論理的に分解しようとする試みをやめて、使用経験と反復を通じて頭の中にパターン（例外を含む）のライブラリを積み上げたときのほうがずっと効果的だった。ちなみにここでいう文脈とは、文中での意味のこと
25年前にスペイン語を独学したときは、スペイン語/英語辞書を使っていた。動詞の不定詞に数字インデックスが付いていて、同じ活用パターンを持つグループに分類されていた。辞書の前半には各グループの代表動詞について全時制の活用表が載っていた。不規則動詞は別のインデックスで、同様に似た不規則動詞どうしが同じグループにまとめられていた（例: tener, detener）。すべての動詞が数十個の固有パターンにきれいに整理されていた。この仕組みを活用したクイズソフトを作ろうとも考えたが、結局作れなかった。記事で触れられていた reverse-string trie パターンが、こうした分類方法にも使えるのか気になる
ロシア語の格変化を覚えるために、前置詞+形容詞+名詞の組み合わせでフラッシュカードを作り、暗記速度を上げようというアイデアがあった。以前に先にラテン語を学んでいたが、ラテン語の格変化はすぐ覚えられる気がしなかった（修道士なら別かもしれないが？）一方で、ロシア語は早く身につけたかった。しかし結局プロジェクトにはならなかった
スペイン語活用の練習には iOS用の ConjuGato を使っている。ゲームモードでは動詞の不定詞/時制/人称が与えられ、活用形を思い出す方式だ。不規則動詞だけを別に練習できるので、例外を覚えるのに効果的
データベースに格変化情報が欠けている800個の名前については、手作業で格変化を付けるのがいちばん直感的な解決策のように思える。ネイティブ話者なら数時間で終えられるだろうし、まったく見慣れない名前の場合でも、少なくとも明らかに不自然ではない形に推定できるはずだ。あるいはLLMにやらせれば非常に安く済むだろう。結果をこうした trie 構造でエンコードして配布するのは依然として良いアイデアだ。ただし、trie を格変化推定器にまでする必要はない
もっと多くの名前を扱うのが望ましい—DIMでは継続的に補完すべき部分だ。アイスランドでは許可名リストに新しい名前が頻繁に追加されるので、常にギャップが生じざるを得ない。自分としては手元でデータを追加する自信がなく、100件の未確認名の結果をレビューするたびに「これで合ってるのか？」と思うことがよくあった。似た名前をDIMで調べてみて、「自分ならそうは変化させないのに」と何度も感じた。だからDIMデータを言語専門家が保守する“信頼できる情報源”として扱っている
手作業もよいが、公式リストにない名前（外国名など）には依然として限界がある。私も中央集権的な名前リストがある国に住んでいるが、例外申請は可能だし、リストができる前に生まれた人や移民などはリストに名前がないこともある。こうした複合的な状況では、「だいたい適切な変化形を予測する」機能が依然として有用だ
LLMが trie より格変化予測をうまくやれると考える根拠は見つからなかった（実例がLLMの学習データに入っていないなら、Web検索のほうが良いだろう）
既存のLLMがすでにこうしたパターンを学習しているのか気になる
Railsがこの問題を自動で処理してくれるのか確信はないが、昔はこういう魔法をよくやっていた。以前 pluralise のソースコードを見たことがあるが、ウェールズ語の不規則複数規則まで全部エンコードされていた
ひとつの最適化アイデアとして、trie が接尾辞文字列そのものに直接マッピングするのではなく、一意な接尾辞配列を作って、trie からその配列のインデックスを参照する方式がある。たとえば:
そして次のようにインデックスを参照する:
Claude Codeで実際に試してみたところ、gzip後はむしろ100バイト増え（3456 -> 3556）、圧縮前サイズだけが20%減った。gzip自体が繰り返しパターンに対してすでにかなり最適化されているからだと思う
さらに一歩進めて、接尾辞そのものを trie に入れ、同一サブツリーを識別して重複排除する方法もあるだろう。gzipが使えるなら、接尾辞配列を活用する賢い最適化方法が確かにありそうだ。バイナリ最適化フォーマットを使えばさらに良くなるかもしれない
個人的には、非圧縮で <1kb に収められる魔法のような解決策がありそうだという気がしてならない。100%正確に名前を分類する最小化正規表現リストを作るとか？ とても大きな bloom filter とか？ あるいは一般的なハッシュの代わりに特化した特徴量を使う方法とか？
悪夢のような面接問題みたいだ。trie をひっくり返して（逆順で）使うなんて一生に一度あるかないかだが、その一度をやったら魔法使い扱いされそう
こういう処理はJSでやるより、データベースからすべての name-case の組み合わせを返して、表示時点で必要なものだけ選んで出してもよさそうだ。つまりローカライズ層で処理する方式だ。多言語が交差する状況ではどうなるのか気になる。アイスランド語UIがフランス名を扱うときは常に主格を使うだろうし、英語UIがアイスランド名を扱うときも同様だろう。結局、ユーザーを直接指定したり呼びかけたりする文脈や、管理パネル（「user x が user y に返信した」）のような場面でだけ必要性が高まりそうだ
「idur」「tur」「ður」で終わる特定の格変化パターンの名前が88個もあるが、同じ接尾辞が常に同じ格変化パターンに従うわけではない。問題は単純な規則のようでいて、実際にはとても興味深い。接尾辞パターンは直前の音節の発音と関係しているのだろうか？ 未知の名前にもっとよく対応するには、単に文字ベースではなく、名前の発音表現をNLPで抽出して trie などで引くべきなのか気になる
こういうことを考え始めると Dependent Types の議論に流れ込みかねないので注意すべきだ
鋭いアイデアだ。実際、同じ発音の名前でも格変化パターンが異なる場合がある。たとえば:
beygla/strict の状況では、代替案として perfect hashing を考えられるかもしれない
アイスランド語の人名の格変換は、こういう方法がうまく通用するほど単純で決定的なパターンを持っているのかと驚かされる。言語というのは一般にはかなり複雑なものだからだ