ハクソク

世界を動かす技術を、日本語で。

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

296日前原文(alexharri.com)

概要

  • Icelandicの人名UI表示 は、格変化（declension）が原因で難易度が高い。
  • 人名は 4つの格（主格・対格・与格・属格） ごとに形が異なる。
  • データベースでは 主格のみ保存 されており、他の格が必要な場合に問題発生。
  • JavaScriptライブラリで 自動的に格変化 を適用する方法を解説。
  • 圧縮技術とTrie構造による 効率的なデータ管理 の実装方法を紹介。

Icelandic人名の格変化とUI表示の課題

  • Icelandic語 では人名を文中で使う際、文構造に応じて 正しい格の形 を使う必要。
  • 誤った格 を使うと、母語話者には不自然に感じられる。
  • データベースには 主格（Nominative） のみが保存されている現状。
  • 他の格が必要な場合、 文を書き換える か 代名詞 を使うしかなく、どちらも理想的ではない。

JavaScriptライブラリによる自動格変化

  • applyCase("Guðmundur", "accusative") のように、主格から任意の格に変換可能な関数を実装。

  • Icelandic Morphology Database (DIM) のK-formatデータセットを利用し、格ごとの人名形を取得。

  • 4,500件以上の人名 のうち、約3,600件の格変化データを取得可能。

    • 例:
      • [ "Guðmundur", "Guðmund", "Guðmundi", "Guðmundar" ]

  • Personal Names Register で承認された人名のみをフィルタリングし、不要データを削減。

ナイーブ実装とその課題

  • 全人名と格変化形を 配列で保持 し、主格名から検索して該当格を返す実装。
  • 問題点:
    • バンドルサイズ が約30kB（gzip）と大きい。
    • DIM未収録の約800名 には非対応。

格変化パターンのコンパクトなエンコード

  • 4格の形を 共通接頭辞＋接尾辞列 として圧縮保存。
    • 例: "Guðmundur" → 共通接頭辞 "Guðmund"、接尾辞 "ur,,i,ar"
  • この方式により 格変化パターン を抽出しやすくなり、同じ変化パターンの人名グループ化が可能。

Trie構造による効率的な検索と圧縮

  • 人名の 末尾（suffix） ごとにTrie（接尾辞木）へ逆順で格変化パターンを格納。

  • 同じsuffix を持つ人名は同じ格変化パターンを共有しやすい特性を活用。

  • Trieの各ノードは 共通パターンを持つ場合に圧縮 し、データ量を大幅削減。

  • Trie探索時は 逆順で文字を辿り、該当パターンを取得。

    • 例:
      • "ur"で終わる複数人名が同じパターンを共有

Trie圧縮アルゴリズムの実装

  • 各ノードの子孫が 全て同じ値 なら、ノードに値を持たせて子ノードを削除。
  • 再帰的にTrieを巡回し、 圧縮可能な部分をまとめる ことで、バンドルサイズを4.5kB以下に抑制。

まとめ

  • Icelandic人名の格変化 はUI実装で避けて通れない課題。
  • データ駆動型のTrie圧縮 を用いることで、最小限のサイズかつ高いカバレッジを実現。
  • これにより、 自然なIcelandic表現 を保ったまま、効率的な人名表示が可能となる。

今後の展望と応用

  • Trie圧縮技術 は他言語の格変化や活用にも応用可能。
  • 新しい人名 や例外パターンの追加も、データ更新のみで柔軟に対応可能。
  • Webアプリや多言語対応システム での自然言語処理技術の進化に貢献。

Hackerたちの意見

まるで地獄の面接問題みたいだね。トライを逆にするなんて、一生に一度使うかどうかって感じだけど、その一度で絶対に魔法使いみたいに見えるだろうな。

└

トライを逆にしたわけじゃなくて、名前を入れる前に逆にしただけだと思うよ？

高校でスペイン語を初めて学んでた時、動詞の不定形と時制のペアを次々に出してくる（Windows）ソフトを見つけたんだ。それに合わせて不定形を活用しなきゃいけなくて。スペイン語の活用って、単語の末尾が変わることが多いし、不規則動詞は語幹が変わることもあるから、すごくいい練習になったし、ルールがしっかり身についた。おかげで得意になったよ。ロシア語を学び始めた時は、記事に出てたような格変化に本当に戸惑った。似たようなアプリを探したけど、パターンを説明してくれるものは見つからなかった。ちょっと話が逸れるけど、そんなアプリ（ウェブベースかmacOS/iOS用）知ってる人いる？

└

https://memrussian.com/?

└

wiktextractを使ってウィクショナリーから抽出した格変化データを使って、似たようなものを自分で作れるかもしれないよ: https://github.com/tatuylonen/wiktextract#pre-extracted-data

└

25年前にスペイン語を独学していたとき、スペイン語/英語の辞書を持っていたんだ。それは動詞をスペイン語の不定詞にしか翻訳しなかったけど、各動詞には同じ活用パターンを持つ動詞のクラスにマッピングされる数値インデックスが付いていた。辞書の前の方には、各クラスのサンプル動詞のすべての時制の活用パターンが載っているセクションがあったんだ。例えば、すべての語幹変化動詞は一つのインデックスにまとめられ、完全に不規則な動詞はそれぞれ独自のクラスに分類され、似たような振る舞いをする不規則動詞（たしか「tener」と「detener」）は同じクラスを共有していた。だから、スペイン語の動詞は数十のユニークなパターンにきれいに分類されていて、インデックスもすでにできていた。君が言ってたように、どんな動詞でもどんな時制でも活用できるクイズソフトを作ろうと思ってたけど、「結局やらなかった」んだ。この記事の逆文字列トライパターンがクラスのマッピングを再構築するのにどうなるのか気になるな。

└

…ロシア語を学んでいる…パターンを説明して…そんなアプリがあればいいな。非ネイティブのロシア語話者だけど、過去にspaCyのPythonモジュールを使って、2つのロシア語モジュールのうちの大きい方で文脈に応じたレマタイゼーションと文法タグの抽出を行うスクリプトを作ったことがある。でも、ロシア語での一番の成果は、活用を分析的に分解する必要を手放して、使うことで頭の中にパターン（と例外）のメンタルライブラリを構築することだった。編集：文の中の文脈のことを言ってるんだ、広い意味じゃなくて。

└

「KOFI」メソッドを使ったAnki（フラッシュカード）のデッキがいくつかあるよ: > KOFI（Konjugation First）は、私が作った挑発的な言語学習アプローチの名前で、言語を正式に学び始める前に、その言語のすべての活用形を学ぶことを目指している。フランス語を学んだ数年後にフランス語のものを使ったんだけど、私の活用がひどかったからね。基本的な時制や間違った時制を使ってもなんとかなるし、相手も理解してくれるけど、それは本当に求めているものじゃない。KOFIメソッドは、言語を学ぶ前に数ヶ月で全ての活用パターンを教えることになってるから、いつか新しい言語で本気で試してみたいな。フランス語への興味は薄れてしまったから、続けなかったけど。 https://ankiweb.net/shared/info/1131659186

└

Clozemasterを使ってロシア語を効果的に学んだよ。説明されてる通りではないけど、たくさんの「クローズ」を通してパターンを脳に刻み込むことができるんだ。

└

iOSでConjuGatoを使ってスペイン語の活用を練習してるよ。動詞の不定詞や時制、人物が与えられて、その活用を考えるゲームモードがあって、例外を学ぶために不規則動詞だけに絞ることもできるんだ。

└

ロシア語が読めるなら、pymorphy3っていう形態素解析用のPythonアプリがあるよ。ドキュメントはこちら: https://pymorphy2.readthedocs.io/en/stable/。このアプリはOpenCorpora辞書に基づいてるんだ: https://opencorpora.org/dict.php。この辞書はZaliznyak辞書に基づいていて、Wiktionaryの記事でもいつも参照されてるよ。

└

このソフトウェアのリンク、まだ持ってる？

beygla/strictの代わりに、完璧なハッシングがいいかもね。

└

標準の完全ハッシュよりもさらに圧縮できるよ。なぜなら、すべての値がユニークじゃないから、衝突があっても同じバケットに複数の名前->接尾辞の組み合わせを保存できるかもしれないからね。もちろん、それだと「名前が処理されていない」と言う能力を失うことになるけど。

Railsがこれを自動で処理するかは分からないけど、歴史的に得意な魔法みたいな感じがする。pluraliseのソースコードを読んだ時、ウェールズ語の不規則な複数形のルールがちゃんとエンコードされてるのを見つけたのを覚えてる。

└

Rails大好き！何にでも方法があるよね。

データベースに格変化データが欠けてる800の名前については、手作業で格変化を割り当てるのが一番簡単な方法だと思う。ネイティブスピーカーなら、数時間もあればできるはずだし（もし見たことのない名前があっても、彼らの推測が他のネイティブスピーカーにとって明らかに間違って聞こえない限り大丈夫）。それか、LLMにやらせるのも安上がりだね。こうやってトライにエンコードするのは結果を配布するのにいい方法だけど、トライが格変化を推測するのに良い方法である必要はない。

└

うん、それはいいアイデアだね。ただ、承認されていない名前（または外国の名前）が使われている場合には、問題は解決しないけどね。私も中央管理の個人名リストがある国に住んでるけど、例外をリクエストできるし、リストができる前に生まれた人もいるから、その人たちの名前はリストに載ってないこともある。移民も帰化の際に名前を保持できると思うし、他にもいろいろな複雑さがあるから、適切な格変化をある程度予測できる能力はやっぱり役立つよ。

└

LLMがトライよりも推測が得意である理由は全くないと思う（もし実際の例がそのトレーニングデータに含まれていたら、ウェブ検索の方が適切だろうけど）。

└

既存のLLMはもうこれらのパターンを知っているのかな？

└

もっと名前をカバーできるといいよね。DIMではそれが進行中なんだ。アイスランドの名前の承認リストには頻繁に名前が追加されるから、どうしても遅れが出ちゃうんだよね。自分でデータを追加する自信はあまりないな。間違えることが多そうだから。トップ100の未知の名前をレビューしてるとき、間違ってるかもって思う結果がよく出てきたんだけど、確信は持てなかった。そういうときは、DIMで似た名前を調べて確認して、「ああ、こういう名前は拒否しないだろうな」って思ったりしたよ。だから、言語の専門家が管理してるDIMのデータを信頼してるんだ。

実際、正確な格変化パターンを持つアイスランドの名前は88個承認されていて、すべて「dur」、「tur」または「ður」で終わる。… > でも、それはすぐに崩れる。他の「ður」や「dur」で終わる名前もあって、異なる格変化パターンに従っている。私の「すべては完全に秩序あるべき」というコンピュータサイエンス脳は、こういうほとんど trivial な問題にいつも反応して、実はもっと面白いことがあるんだよね。接尾辞パターンは接尾辞の前の音節の発音に基づいているのかな？もし未知の名前に対して君の仕事を改善したいなら、使われている文字を考えるのではなく、名前の発音を表現するためにNLPを使って、それを調べる必要があるのかな（トライやその他の方法で）？

└

接尾辞パターンは接尾辞の前の音節の発音に基づいているのかな？気をつけて、これは「依存型は答えなのか？」の穴に落ちる原因だから。

└

うーん、いいアイデアだね。同じ発音なのに、格変化のパターンが違う名前もあるよね。例えば、- Ástvaldur -> ur,,i,ar - Baldur -> ur,ur,ri,urs。「aldur」の語尾は同じ発音だけど、「Ástvaldur」の格変化パターンを「Baldur」に適用すると、こうなるんだ：- Baldur - Bald - Baldi - Baldar。最後の3つの形はすごく変な感じがする（パートナーに確認してもらったら、彼女も引いてた）。アイスランド語の話し言葉は、書き言葉に驚くほど近いんだ。名前やその語尾の「音声的」なバージョンを使った場合、トライの結果があまり変わらないとは思わないよ。

もう一つの最適化アイデア: トライが接尾辞文字列に直接マッピングするのではなく、ユニークな接尾辞の配列を作って、トライがその配列のインデックスにマッピングするようにする。例えば、const suffixes = [",,,", "a,u,u,u", ",,i,s", ",,,s", "i,a,a,a", ...]; そして、このリストのインデックスを使って var serializedInput = "{e:{n:{ein:0_r: ...

└

俺（クロード・コード）はこれを試してみたけど、実際にはgzippedサイズが100バイト増えたよ（3456 -> 3556）、非圧縮サイズは20%しか減らなかった。gzipはすでに繰り返しパターンをうまく処理するからだろうね。

└

接尾辞自体をトライに入れて、同じ部分木を特定することで、さらに一歩進めることができるよ。gzipが使えるなら、接尾辞配列を使う賢い方法があるはずだし、それが最適化されたバイナリ形式を使えるなら、木のためにより良い結果になるかもしれないね。

JSでこれをやるメリットがあるとは驚きだね。データベースが名前を持つ全てのケースを返して、表示時に必要なものを選ぶ方がいいんじゃないかな。要するに、ローカライズされた言語テンプレートを生成してるのと同じレイヤーで。とはいえ、これが言語間の状況でどうなるのか気になるな。アイスランド語のUIがフランス語の名前を表示する時は、常に主格を使うのかな？英語のUIがアイスランド語の名前を表示する時も同じ？ユーザーが直接呼びかけられる時や、管理パネル（「ユーザーXがユーザーYに応答しました」）で主に重要になると思うけど。

アイスランド語の名前の格変化は、この方法が確実に機能するほど決定的なのかな？それならラッキーだね。言語って、通常はかなりごちゃごちゃしてるから。

└

アイスランドは人口が比較的少なく、言語が政府によって積極的に管理されているから、助けになるかもしれないね。

脳が叫んでるんだけど、<1kbの非圧縮サイズで解決策があるはずなんだ（厳密でないバージョンのために）。名前を100%正しく分類する最小限の正規表現リストを生成するのかな？それとも、十分大きなブルームフィルター？ハッシュの代わりにエンジニアリングされた特徴を使うようなブルームフィルター？