Hatena::ブログ(Diary)

Topics Related to Computers and NLP

2013-07-28

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

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

接尾辞配列配列の生成に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によるインデックスLuceneとの性能検証


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

雑記

ちなみに初心者向けと言われるこの本

検索エンジンはなぜ見つけるのか

検索エンジンはなぜ見つけるのか

を読んでいたら、BWTとかFM-indexとか出てきて自分が理解していないことが沢山でてきて面白かった。

「簡単すぎる、ぬるいな」という方々はここらへんを見て下さい。
最近のSuffix Arrayによる全文検索について調べてみた

echizen_tmechizen_tm 2013/07/29 23:18 リンク張っていただきありがとうございます。

LCPの構築については以前、記事を書いたことがあるので紹介しておきます。
(わかりやすいかどうかは自信ないですが・・・)
http://d.hatena.ne.jp/echizen_tm/20110728/1311871765

akkikikiakkikiki 2013/07/30 13:35 ご丁寧にありがとうございます。このリンクについては見落としていました。。。劣化版の焼き直しに近い記事になってしまいましたが、精進いたします。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/akkikiki/20130728/1375029320