検索インデックス周り（主に接尾辞配列周り）に関する基礎の話

資料リンク集みたいなものですね。不完全なので、徐々に詳しく書いていきたい記事です。
接尾辞配列がなぜ巷で「痺れる、憧れるぅ！」状態なのかを理解した。
検索速度、スケーラビリティ、網羅性の観点から優れているみたいだ。
Lucene（Solr）を扱う際は、接尾辞配列のインデックスをサポートしていないみたいです。

接尾辞配列配列の生成にO(n^2logn)というのを常識のごとくウィキペディア日本語版に書かれていたのだが、よくわからなかった。
O(nlogn)回の比較ソートが必要なのはわかるが、一回の比較にO(n)の時間がかかるとは？
・・・ここを見ている時に「文字列の比較」であることを思い出した。「あれ、nって要素の数じゃない」と一瞬思ったが、接尾辞配列においては「文字列の長さ＝接尾辞配列の要素数」であることをまた、思い出して勝手に納得した。

検索クエリの長さをmとすると、二分探索を用いればO(mlogn)での探索が可能です。それはいいんですが、その後のO(m + logn)に時間計算量の改善に関して「？」が大量に頭に浮かんできました。ここらへんが知りたいんですよ、僕は。最長一致接頭辞（Longest Common Prefix)を使う、という記述を観測するも、具体的な方法が書いていない。記述するのはいいんですが、リンク貼って頂けるとありがたいです。

O(m + logn)の謎はStackoverflowが解決してくれました。QuoraとStackoverflowは大抵の事を解決してくれます。
参考：How does LCP help in finding the number of occurences of a pattern?

少し面倒になってきたので、今は全部翻訳はしませんが、一番重要な箇所は「前処理で構築されたLCP arrayを使用する」と「クエリの各文字は必ず一回しか比較に使用されないこと」。O(mlogn)の探索の問題点は「比較の際に毎回接頭辞を比較するため、O(m)になってしまうこと」でした。それが必ず一回になるためO(m + logn)となります。
（ちなみにここらへんの話はウィキペディア英語版の接尾辞配列に載っていました）

あと残りの疑問点としては「LCP arrayはどうやって構築するか」ですね。これは英語のウィキペディアを参照すると良さそうです。英語のウィキペディアやばすぎますね。僕は日本語が大好きなのですが、僕が観測している範囲内では接尾辞配列に関しては情報量に差がありすぎますね。

Luceneを始めるにあたっての資料：
http://d.hatena.ne.jp/arahk/20101028/1288263461
http://d.hatena.ne.jp/sleepy_yoshi/20110405/p1

参考資料：
Suffix ArrayとSedue周りのお話（すごいわかりやすい、転置インデックスと接尾辞配列を用いたインデックスが違うことにはじめて気が付いた）

Suffix Array@Solr勉強会 from nobu_k

Suffix ArrayによるインデックスとLuceneとの性能検証

Suffix Array 検証その後 from moai kids

Suffix Arrayの構築アルゴリズムに関して
http://stackoverflow.com/questions/7857674/whats-the-current-state-of-the-art-suffix-array-construction-algorithm