Hatena::Groupstudyroom

文::字

2010-11-23

Common-Prefix Search, TRIE, Double-Array 21:06  Common-Prefix Search, TRIE, Double-Array - 文::字 を含むブックマーク

自分の理解のために少しずつまとめていく。

Common Prefix Search (共通接頭辞検索) とは

複数の単語が登録されている辞書 A と自然言語で書かれたテキスト B があったとき、テキスト B の任意の開始位置から始まる部分文字列に対して、辞書 A に含まれている単語を全て列挙する処理。

これをテキスト B の全ての開始位置に適用することで、テキスト B に含まれ、かつ辞書 A にも含まれる全ての単語を抽出することができる。

応用例としては形態素解析キーワードリンク(はてなダイアリーキーワードWikipedia) がある。

参考:

これだけだと何のこと言ってるかよく分からないんで具体的な例を考えてみるんだけど、例えば「東京ドームに行った」という文があるとき、以下の 9 回の検索が行われる (ということで大丈夫だろうか)。

  • 東京ドームに行った
  • 京ドームに行った
    • 何もマッチしない
  • ドームに行った
    • 辞書にある「ドーム」がマッチする
  • ームに行った
    • 何もマッチしない
  • ムに行った
    • 何もマッチしない
  • に行った
    • 辞書にある「に」がマッチする
  • 行った
    • 辞書にある「行った」がマッチする
  • った
    • 辞書にある「った」がマッチする
    • 辞書にある「た」がマッチする

TRIE

想定される処理、トライ木への挿入、トライ木からの検索。

実装方法としては以下がある。

  • リスト実装
    • 遅い、メモリ食う
  • 配列実装
    • 速い、メモリ食う
  • Double-Array
    • 速い、メモリ食わない
    • ChaSenMeCab でも使われている実績あり

参考文献

ClaudiaClaudia2013/12/28 21:54Well I guess I don't have to spend the weekend fignriug this one out!

MuskanMuskan2013/12/29 15:40<a href="http://ggcsnzoqc.com">Unlearplaled</a> accuracy, unequivocal clarity, and undeniable importance!

JorgeJorge2013/12/30 02:42Your cranium must be pretocting some very valuable brains. http://unpwtjksv.com [url=http://tpjswsbepxf.com]tpjswsbepxf[/url] [link=http://wtivpuljx.com]wtivpuljx[/link]