木構造とか
2分木
)
- m:木の深さ
- 2分木なので、深さの対数log2 (均等に振り分けないと無駄に深くなるけど)
Trie木
)
- n:文字列長
- すでに辞書式ソート済みなので、文字列長で検索できる。
- メモリ
- 多数の短い文字列群は、共通するキーをもつ確率が高いのでメモリを節約できる。
- 逆に長い文字列はパトリシア木が良い。
パトリシア木
- トライ木であるノードからあるノードまでの間、1本道で分岐がない場合、ひとつのノードにまとめてしまう。
- 常に成功する場合に適している
suffix木
- wikipedia
- suffixで生成された部分文字列をキーとして木に登録
- 接尾辞リンク
- ひとつ前の接尾辞を指す BANANA <- ANANA <- NANA <- ANA <- NA <- A
AC法
- マッチングに失敗した際に、次に調べるべきノードを予め登録しておくもの
- ある入力文字列(ex.東京都)に特定のキーワード(Trieに登録済み)が存在するかを調べる際に、ある経路でマッチングに失敗したときに、入力文字列を一文字削って、それ(ex.京都)をTrie木の頭から調べるのではなく、次にどこから始めるべきか、予め登録して高速化している。
- 入力文字列を一文字ずつ削る場合の話なので、事前に形態素解析してある場合は失敗したらそこまでなので、AC法は必要ない。
0 件のコメント:
コメントを投稿