Goya: 形態素解析の実装の詳細

[Leko]

• きっかけは仕事でダブル配列を実装したこと
  • ダブル配列とは？トライ木とは？
  • 参加してたISUCONで出題されたことがある
  • 当時解けなくて悔しくて覚えた
• 突き詰めればDFS、基数木、ダブル配列、DPができれば作れる
• ipadicのパース
• ダブル配列の構築
  • ナイーブなトライ木を作ってダブル配列に圧縮
  • トリプルアレイとは違うアプローチだと思う
  • 終端ノードに-1ではなく単語IDを直接入れて辞書サイズを縮小
  • FSTってのを使うと辞書サイズがかなり小さくできるそう。検索速度はどうか？
• ダブル配列の探索
  • イメージ的にはトリプルアレイからダブルアレイに変換するアプローチだと思われる。実際は基数木使ってるけども
  • おそらくかなり素朴。構築（特に隙間探し）がかなり遅い。隙間だけをLinkedListにしたり最適化が必要そう
  • 衝突回避のため辞書を奇数木に一度変換してからダブル配列に落としている
  • TAILも使ってない
  • janomeではSFTというのを使ってるそう。Rustにもstring-to-intの実装があるが試してない
• 未知語の処理
  • 要はこれ https://taku910.github.io/mecab/learn.html
  • 文字クラスと範囲
  • タイミング制御とグルーピング
  • 未知語のコスト算出
• 同音異義語の処理
• ラティス構築
• コスト計算
• Viterbiアルゴリズムによる最小コスト法（前向きDP）

— テキスト処理入門：Pythonで高速な辞書を作ろう（その1） | 中国語・韓国語翻訳・音声合成なら高電社
— ゼロから作った形態素解析器Taiyakiで学ぶ形態素解析 - The jonki
— Double-Array Construction
— ダブル配列の実装方法
—
— [ダブル配列の豆知識](https://www.slideshare.net/s5yata/dsirnlp-04s5yata