簡単な形態素解析の実装をしてみた（Ruby）その2

前回の続き

nanjakkun.hatenablog.jp

前回の実装では辞書引きの効率に問題があったので改善しました。

辞書の構造としてトライ木を使うようにしました。トライ木の実装自体にはバリエーションがあるのですが、割とオーソドックスな方法で。

次回以降に別のトライ木実装にもチャレンジしようと思います。

コード

https://github.com/nanjakkun/morph_ruby/blob/main/lib/morph/longest_match/v2/analyzer.rb

計算量

※ちょっと自信ないです

辞書のデータ構造次第で計算量が変わります。

• 入力文字数をN
• 辞書の単語数をD
• 辞書中の最長接頭辞単語の最大文字数をK

とすると、

• 辞書の実装が配列の場合(前回の実装)、O(ND)
• 辞書の実装がハッシュマップの場合、O(N**3)
• 辞書の実装がTrieの場合、O(NK**2)

参考

トライ (データ構造) - Wikipedia