Tree?Trie?
そういや自分の実装してるデータ構造が単なるTrieというよりもいわゆる一種のSuffixTreeなんじゃないかと思って調べてみるテスト
そうすると、SuffixTreeなのかSuffixTrieなのか色々と説明が揺れていて困る
一説では
SuffixTree=SuffixTrie
と書いてあったり
また一説では
SuffixTrie < SuffixTree < SuffixArray
と書いてあったり。ちなみに大小記号は"優れている"と言う意味合いで使っております。包含関係なら真逆かしら
んー、変なところにはまると嫌なので、単なるHashを利用したTrie構造って感じでごまかすことにしようかなー
なんでSuffixTrie?
やろうとしてることはSuffixのスコアの照会です。
その際に先頭からの部分一致でも正解としたいがためにHashが使えずに悩んだ末にSuffixTrie(?)なら幸せになれるんじゃないかなーなんていう単純な思考です
SuffixTrieの実装もかなりいい加減で、世の中には線形時間で構築するアルゴリズムも提案されているみたいですが、多分私の実装だとくらいはかかってるんじゃないかなー(計算してないからもしかしたら二乗オーダーかも;
しかしながら構築さえしちゃえば正解集合の照会が実質定数時間で行えるので非常に幸せになれると思います
