話題のwat-arrayを使ってBurrows-Wheeler変換(BWT)してみた - EchizenBlog-Zwei
先日PFIの岡野原氏によってwat-arrayというライブラリが公開された。 wat-array : wavelet木を利用した高速配列処理ライブラリ : Preferred Research Blog このライブラリは内部でウェーブレット木(wavelet tree)という簡潔データ構造(succinct data structure)を使っている。このため文字列に対するrank()やselect()などの操作が効率的にできるようになっている。 ・・・といっても馴染みのない人にとっては何が嬉しいのかピンと来ないかもしれない。そこでBurrows-Wheeler変換(BWT, Burrows-Wheeler Transform)を例にとってwat-arrayの使いみちを説明してみる。 Burrows-Wheeler変換というのはテキストを同じ文字が並びやすいように変換したもので、通常ランレ
「第3回自然言語処理勉強会＠東京」でCSAについて発表します - EchizenBlog-Zwei
@nokunoさんの好意で「第3回自然言語処理勉強会＠東京」でCompressed Suffix Arrayについて発表させていただくことになりました。 つきましては参考のため発表資料を以下に置いておきます。参加される方はもちろん、興味のある方はご覧になっていただけるとうれしいです。 第3回自然言語処理勉強会＠東京 : ATND 第3回自然言語処理勉強会＠東京を開催します - nokunoの日記 なお本資料は以下の皆様のアドバイスを頂きました。ありがとうございました(とくに@overlastさんには4-5時間もお付き合い頂きました。おかげさまでスライドの質が大幅アップしました。感謝)。 @overlastさん @tamago_donburiさん @tsubosakaさん @machyさん
Spaghetti Source - Suffix Array
Suffix Array (Larsson-Sadakane) 説明 Suffix Arrayとは，与えられた文字列の接尾辞の集合を辞書順ソートしたものである．近年，これを用いることによって多くの文字列の問題が解かれることがわかってきた． Larsson-Sadakane は Suffix Array を O(n (log n)^2) 時間で構成するアルゴリズムである．Mamber-Myers と同様のアイデアによって文字列長を倍加させ，O(log n) 回の multikey quicksort を行うことにより，全体で O(n (log n)^2) の計算量を達成する．詳しくは適当な文献を参照． Suffix Array を用いて解けるもっとも典型的な問題は，文字列の検索である．Suffix Array 上で二分探索を行えば，O(m log n) でパターンの検索ができる．また，Suf
Suffix Array向きのソートアルゴリズム - EchizenBlog-Zwei
Suffix Arrayのソートアルゴリズムは以前当ブログで紹介したSAIS(参考)など、Suffix Arrayの性質を生かしたものが多い。そして一般にSuffix Arrayはバイト単位でインデックスを与えるので、これを前提としている場合が多い。大抵の場合はそれでOKなのだが、問題がある場合がある。 それは、インデックスをUTF8の文字単位で与えたい場合や、単語単位で与えたい場合。この場合、大抵のSuffix Array向けソートアルゴリズムが使えない。そこで重要になってくるのが文字列に対する高速ソートアルゴリズム。これならばインデックスが飛び飛びでも使えるので汎用性がある(Suffix Arrayに特化した手法が使えないので速度面では劣るかもしれないが。) 例えば、SUFARY(参考)で使われているmultikey-qsortという方法は古くからある方法だがシンプルかつ高速で、とても
無題ドキュメント
次に、各Suffixにおける大小関係を定義します。この大小関係は辞書式順序です。辞書式順序とは、辞書に並んでいる通りの順番であり、簡単に言えば、 (1)両Suffixを頭（左）から順番に一文字ずつ比較していき、初めて違うところで、文字の大小関係で比較を行う (2)もし、二つを比較していき、片方のSuffixが終わりに達してしまったら、そちらの方が小さいと定義する。 例えば、(1)は上の例でいえば、 S5 と S7を比較するとすると S5 adabra S7 abra 一文字目は両方ともaで、同じなので二文字目（赤い部分）を比較すると、dとbであり、文字の大小関係で d > b なので S7 < S5 という大小関係がつきます。 (2)については、S0 と S7を比較すると S0 abracadabra S7 abra で、頭から4文字は同じであり、S7はデータの最後に達しました。この
Compressed Suffix Arrayの解説(1) -Suffix Array- - EchizenBlog-Zwei
< ---- < | > Compressed Suffix Arrayの解説(2) -SAの計算量- > ================================================ 最近(でもないか)話題のCompressed Suffix Array(CSA)について解説してみる。 CSAとはSuffix Array(SA)のインデックスを圧縮して小さくしたもの。大規模テキストデータに対する検索インデックスを作る場合など少しでもインデックスを小さくしたい場合に使われる。 CSAを知るにはSAから！ということで今回はSAの解説を。 Suffix Array(SA)とはデータ構造の一種で事前に(サイズがNの)テキストに対してインデックスを作っておくことでキーとなる文字列を入力として与えるとテキストに含まれるキーの位置をO(logN)で探索できる、というもの。 たとえば
Suffix Arrays の構築がいつまでたっても終わらない問題
Suffix Arrays の構築がいつまでたっても終わらない問題 2009-10-20-4 [Algorithm] よくあるトラブルなのでまとめておく。 suffix を文字列比較でソートするという単純な方法で Suffix Arrays を作るSUFARYでのトラブルについて。 - SUFARY 臨時復旧ページ http://ta2o.net/tools/sufary/ ちなみに Suffix Array の作成ロジック（もっとも簡単なやつ）はこんな感じ(C言語です)： #include <fcntl.h> #include <malloc.h> #include <stdio.h> #include <sys/mman.h> #include <sys/stat.h> #include <sys/types.h> /* usage: sufsort1 text > text.suf
昨年の論文をふりかえる - DO++
新年すっかりあけてました。 今年もよろしくお願いします。 年末年始はドタバタして昨年を振り返られなかったのですが、せっかくなので2008年に読んだ論文で私個人のベスト５を以下に列挙してみます。 D. Sontag, et. al. "Tightening LP Relaxations for MAP using Message Passing", UAI 2008 [pdf] Graphical ModelのMAP推定問題で従来解けなかった規模の複雑さの問題を高速にしかも最大であるという保障付きで解けるようにした。書いたメンバーはこの問題に関するオールスターのような感じ。解く問題は、n個の頂点からなるグラフで、各頂点には変数x1...xnがついていて、各頂点と各枝に対し関数gi(xi)、gij(xi,xj)が与えられた時、∑i gi(xi) + ∑ij gij(xi,xj)が最大となるよう
TXTCache Index uniquely : ホーム
圧縮インデックスライブラリ「TXTCache」,圧縮Suffix ArrayなどのJava実装パッケージ,オンメモリで全文検索を行うことができる,高速な検索エンジンやユニークなデータモデルの開発が可能となる圧縮インデックス(Compressed Index)のJavaのライブラリ。 接尾辞配列(Suffix Array)、圧縮接尾辞配列(Compressed Suffix Array)、LZ-Indexなどを含んだパッケージ。 オープンソース。 ライセンスは、GPLまたはLGPLのユーザー選択式。 無償。 GPL版ダウンロード LGPL版ダウンロード Operaの場合、お手数ですが、ダウンロード後、ファイル名に.zipを付ける必要があります。
DO++ : suffix arraysやいろいろ
suffix arraysの話は半年置きぐらいに書いているのかなぁ。 (ココログ全文検索機能無くて、不便ですね・・以前どこに書いたのか分からない。） 私が以前書いたSuffix Arraysの構築方法の記事が古くなってきたので（分かりにくいし）、近いうちにライブラリと一緒に内容も更新しようかなと。今回は、忘れないうちにメモも兼ねてSuffix Arraysの高速な構築方法について。 構築で今一番速いのは、msufsortとimproved two-stage (プログラム名はdivsufsort）(its)法だと思います。これらはデータサイズに対して線形時間で構築できる方法では無いのですが、大抵のデータでは線形時間の方法より高速に構築することが可能です。 msufsortはsuffix arrays:SAを直接構築するのではなく、その逆の値であるinverted suffix arrays
Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
white page / 全文検索や圧縮に関するlinks集
Copyright © 2004-2008, Yuta Mori, All Rights Reserved. yiv01157 at nifty dot com http://homepage3.nifty.com/wpage/
ブロックソート - Wikipedia
ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burrows-Wheeler Transform; BWT) は、1994年にマイケル・バローズ (Michael Burrows) とデビッド・ホイーラー (David Wheeler) が開発した可逆変換の方式で、データ圧縮の前処理に応用される。 ブロックソート自体はデータの大きさを変えない。しかし、データを整列することでデータ中に出現するパターンを、いくつかのよく知られている手法で圧縮し易いものにできる。後処理としてMove To Front (MTF)・連長圧縮 (RLE)・エントロピー符号と組み合わせて、データを圧縮する。 実装はbzip2等。 Python言語による実装例が文献[1]に出ている。 長さ n のデータを巡回シフトし、得られるすべての文字列を辞書順にソートする。このようにしてできた n×n
Compressed Full-Text Indexes - (nm06acmcompsurv.pdf)
Compressed Full-Text Indexes Gonzalo Navarro Center for Web Research, Department of Computer Science, University of Chile Veli Mäkinen Department of Computer Science, University of Helsinki, Finland Full-text indexes provide fast substring search over large text collections. A serious problem of these indexes has traditionally been their space consumption. A recent trend is to develop indexes tha
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Larsson Sadakane
two-stage (二段階ソート法）
サービス終了のお知らせ
Compressed Suffix Arrays - おなかすいたWiki！
Amazon.co.jp: The Burrows-Wheeler Transform:: Data Compression, Suffix Arrays, and Pattern Matching: Adjeroh, Donald, Bell, Timothy, Mukherjee, Amar: 本
Google Code Archive - Long-term storage for Google Code Project Hosting.