アイスランド語の名前の屈折パターンを3.27kBのトライで圧縮する

• アイスランド語の個人名の屈折処理は、文脈に応じて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まで容量を削減

要約

• アイスランド語の人名屈折自動化をパターンベースのトライデータ構造で軽量化・自動化した事例
• 適切な容量と精度トレードオフを考慮した実務向けデータ処理戦略の示唆に富む事例