LCP(Longest Common Prefix)を用いたSuffix Arrayの検索 - EchizenBlog-Zwei
Suffix Arrayは「インデックスの構築」と「キーワードの検索」からなる。それぞれ構築には文字列のsortが、検索には文字列の二分探索が必要になる。 以前にCompressed Suffix Arrayのライブラリtsubomiを実装したときにはsortについてはマルチキー・クイックソート(multikey-quicksort)というアルゴリズムを用いた。一方で二分探索については特に工夫をしていなかった。 さすがにこのまま放っておくのは気が引けたのでSuffix Array論文を読みなおしてみたらLCP(Longest Common Prefix)を用いた二分探索の方法が書いてあった。シンプルだが賢い方法だったのでメモしておく。これはすごい(というか今まで読み飛ばしてたことのほうが問題ですね。はい)。 さて。まずLCP(Longest Common Prefix)とは何かと言うとその
TXTCache Index uniquely : ホーム
圧縮インデックスライブラリ「TXTCache」,圧縮Suffix ArrayなどのJava実装パッケージ,オンメモリで全文検索を行うことができる,高速な検索エンジンやユニークなデータモデルの開発が可能となる圧縮インデックス(Compressed Index)のJavaのライブラリ。 接尾辞配列(Suffix Array)、圧縮接尾辞配列(Compressed Suffix Array)、LZ-Indexなどを含んだパッケージ。 オープンソース。 ライセンスは、GPLまたはLGPLのユーザー選択式。 無償。 GPL版ダウンロード LGPL版ダウンロード Operaの場合、お手数ですが、ダウンロード後、ファイル名に.zipを付ける必要があります。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
