2011年10月12日水曜日

木構造とか


このエントリーをはてなブックマークに追加


2分木



  • O(¥log m)

    • m:木の深さ

    • 2分木なので、深さの対数log2 (均等に振り分けないと無駄に深くなるけど)




Trie木



  • O(n)

    • n:文字列長

    • すでに辞書式ソート済みなので、文字列長で検索できる。



  • メモリ

    • 多数の短い文字列群は、共通するキーをもつ確率が高いのでメモリを節約できる。

    • 逆に長い文字列はパトリシア木が良い。




パトリシア木



  • トライ木であるノードからあるノードまでの間、1本道で分岐がない場合、ひとつのノードにまとめてしまう。

  • 常に成功する場合に適している

    • ひとつのノードにキー値がまとまってるからかな




suffix木



  • wikipedia

  • suffixで生成された部分文字列をキーとして木に登録

  • 接尾辞リンク

    • ひとつ前の接尾辞を指す BANANA <- ANANA <- NANA <- ANA <- NA <- A





AC法



  • マッチングに失敗した際に、次に調べるべきノードを予め登録しておくもの

    • ある入力文字列(ex.東京都)に特定のキーワード(Trieに登録済み)が存在するかを調べる際に、ある経路でマッチングに失敗したときに、入力文字列を一文字削って、それ(ex.京都)をTrie木の頭から調べるのではなく、次にどこから始めるべきか、予め登録して高速化している。



  • 入力文字列を一文字ずつ削る場合の話なので、事前に形態素解析してある場合は失敗したらそこまでなので、AC法は必要ない。





0 件のコメント:

コメントを投稿