木構造とか

2分木

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

Trie木

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


• メモリ
  
  
  
  • 多数の短い文字列群は、共通するキーをもつ確率が高いのでメモリを節約できる。
  
  
  • 逆に長い文字列はパトリシア木が良い。
  
  
  
  

パトリシア木

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


• 常に成功する場合に適している
  
  
  
  • ひとつのノードにキー値がまとまってるからかな
  
  
  
  

suffix木

• wikipedia


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


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

AC法

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


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