Suffix Array の検索

• ref:404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)

面白い応用としては、Suffix Arrayというものがあります。これは無秩序に並んだデータ、例えば一般的なテキストファイルに対応する秩序だったデータ構造を用意し、それに対して二分探索をかけることで、本来線形探索しかできなかったデータをO(log n)で検索するアルゴリズムです。これを使うとDVD一枚分の文書でも一瞬にして探索することが出来ます。

ダウト。文字列の比較が定数時間でできるなんてのは幻想ですよ。
ただしくは、検索対象のシーケンスの長さを m として、ナイーブな実装では最悪時間計算量は O(m log n)。Longest Common Prefix(LCP) を計算しておいて、さらに LCP を対象として Range Minimum Query(RMQ) の前準備をしておけば、O(m + log n)。
あと、Dan さんの説明だと HyperEstraier/Senna あたりと比較して何がいいのか分からないと思うので適当に補足すると、Suffix Array というのは転置インデックスと違って、任意長のシーケンスを効率よく検索できるという利点があるとかなんとか。ついでに、その構造を使って任意文字列の統計量の計算ができるとか。