資料 & コード

技術書

• 形態素解析の理論と実装

MeCab

• MeCab
• 日本語形態素解析の裏側を覗く！MeCab はどのように形態素解析しているか
• MeCab
  汎用日本語形態素解析エンジン

形態素解析

• https://github.com/taku910/mecab
• https://github.com/WorksApplications/Sudachi
• https://github.com/mocobeta/janome
• https://github.com/ikawaha/kagome
• https://github.com/Leko/goya

ダブル配列

• https://s-yata.hatenadiary.org/entry/20100301/1267788256
• https://speakerdeck.com/kampersanda/toraitodaburupei-lie-falseji-chu

辞書

ダブル配列 (形態素解析の理論と実装)

ダブル配列はトライの一種で文字列の追加と検索を高速にできるコンパクトなデータ構造である。
ダブル配列は2つの同じ長さの配列BaseとCheckでトライを表現している。配列の添字がノードを表している。(これは本の図を見たほうが良い)
高速な実装だと一つの配列で表現している。e.g. https://github.com/takuyaa/yada/blob/master/src/unit.rs
文字列はすべてbyteコード単位のノードで表現される。仮に1文字でもバイト単位では複数のノードとして表現される。
現在のノード位置をsとしてcという文字に対する子ノードの位置tは以下である。

t = Base[s] + code(c)

• Check[t] == sなら遷移が存在
  • Base[t] < 0なら tは葉ノードで値がv = -Base[t]である
• Check[t] != sなら遷移が存在しない(検索文字列が存在しない)

Kagomeダブル配列