テキスト圧縮はこれ一冊でOK！？な優良書籍「The Burrows-Wheeler Transform」を読んだ - EchizenBlog-Zwei
以前より気になっていた書籍「The Burrows-Wheeler Transform Data Compression, Suffix Arrays, and Pattern matching」を読む機会を得ることができた。それなりに高額な本だったので購入が躊躇っていたのだけど、これは自分用に購入してもいいかも。というくらいの良書だったので紹介しておく。 本書はタイトルのとおりBWT(Burrows-Wheeler変換)に関する書籍。サブタイトルにあるようにデータ圧縮やSuffixArrayによる全文検索についても充実した内容になっている。最後のPattern matchingはテキストから検索キーとexactにマッチした、もしくは類似した箇所を取り出すよ、という話。2008年の本なので比較的新しい話題も扱っていて満足度が高い。 また本書の特色は圧縮ありきで始まり、そこから全文検索可能な
話題の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
私がCompressed Suffix Arrayを学ぶのに参考にした資料へのリンクをまとめてみた。 CSAだけじゃなく、これからSuffix Arrayを学ぶ人にも便利かもしれない。 解説記事 # ［を］ Perl による Suffix Array の実装] SUFARYの開発者、たつを氏による解説 perlで20行くらいでSuffix Arrayが作れる 入門用におすすめ # DO/Suffix Array 岡野原氏によるSuffix Arrayの解説記事 高速化などの高度な話題が豊富 中級者向け # white page Suffix Arrayのリンク集が充実 多くのライブラリが公開されている ツール・ライブラリ # SUFARY 臨時復旧ページ たつを氏によるSuffix Arrayライブラリ 非常に使い勝手が良い # sary: Suffix Arrayのライブラリとツール 高
Fm-index version 2
FM-Index Version 2 Paolo Ferragina and Rossano Venturini Dipartimento di Informatica, University of Pisa, Italy The present software offers a new implementation of the compressed full-text index data structure, called FM-index. The FM-index was proposed by Paolo Ferragina and Giovanni Manzini in [FOCS '00]. An implementation of the FM-index (vers. 1.0) was presented in [SODA '01]. This data struct
CSAを使った全文検索ライブラリtsubomiを公開してみる - EchizenBlog-Zwei
しばらく前から作っていた全文検索ライブラリtsubomiを公開しておく。 本ライブラリは接尾辞配列(Suffix Array)というアルゴリズムを使っていて、入力として与えたキーワードを含む行をテキストデータから探して、その行と出現位置を取得できる。さらに圧縮接尾辞配列(Compressed Suffix Array)による圧縮もサポートしているのでインデックスサイズを小さく抑えることができる。 本ライブラリは検索のためのAPIのほかに、インデックス作成、圧縮、検索を行うツールが付属している。ツールを使うだけでも、ある程度のことができる。 以下、簡単に紹介。 tsubomiはGoogleCodeでコードを管理している。詳細は下記URLを参照。 http://code.google.com/p/tsubomi/ コード管理にはsubversionを使っているので $$ svn checkou
定兼 邦彦 (Kunihiko Sadakane) - 圧縮接尾辞配列ライブラリ - researchmap
文字列を圧縮したまま検索するライブラリです． 文字列の一部を高速に復元することもできます． 圧縮接尾辞配列ライブラリ (2010-08-10版) Direct BWT construction External Memory BWT construction http://code.google.com/p/csalib/ にもあります． 注意: dbwt100717.zipにはバグがありました．Ubuntuでは動かない可能性が高いです． dbwt100730.zipを使ってください． 索引とは，本の索引と同じ意味で，検索を高速に行うためのデータのことです． ただし，本の索引では代表的な言葉のみが登録されていますが，このライブラリの索引は 任意の語が検索できるようになっています． このライブラリの索引は自己索引 (self-index) と呼ばれるもので，索引自体に 元のファイルの情報を全
圧縮接尾辞配列ライブラリ csalibの圧縮率の高さは異常 - EchizenBlog-Zwei
圧縮接尾辞配列の第一人者、定兼先生が開発、公開してくださっているcsalibを試してみたのでメモ。 http://researchmap.jp/sada/csalib/ まずはgooglecodeからcsalibとdbwtを入手。解凍しmakeする。 $$ mkdir csalib/ $$ cd csalib/ $$ wget http://csalib.googlecode.com/file/csalib100810.zip $$ unzip csalib100810.zip $$ make $$ cd .. $$ mkdir dbwt/ $$ cd dbwt/ $$ wget http://csalib.googlecode.com/file/dbwt100730.zip $$ make $$ cd ..このライブラリはdbwtでテキストをBurrows-Wheeler変換し、その後m
Compressed Suffix Arrayの記事まとめ - EchizenBlog-Zwei
一応CSAの記事を書き終えたので、各記事へのリンクリストを。 補足:記事を7つも読むの面倒くさい人は、↓にもう少し簡単な圧縮法の解説を書いておいたので参照されたい。 15分でわかる(とうれしい)Suffix Arrayの簡単な圧縮法 Compressed Suffix Arrayの解説(1) -Suffix Array- Compressed Suffix Arrayの解説(2) -SAの計算量- Compressed Suffix Arrayの解説(3) -圧縮の方針- Compressed Suffix Arrayの解説(4) -unary記法- Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- Compressed Suffix Arrayの解説(6) -B Vectorと Ψ Vector- Compressed Suffix
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)で探索できる、というもの。 たとえば
Run-Length Compressed Suffix Array
This web page will no longer be updated. See the author's web pages for further releases. RLCSA [4, 3, 7] is a compressed suffix array implementation that has been optimized for highly repetitive text collections. Examples of such collections include version control data and individual genomes. This implementation also serves as a testbed for many techniques used with compressed suffix arrays. The
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
生物情報科学科 情報基礎実験 ３年生冬学期 10/26 – 11/5 （森下研究室担当）
Larsson Sadakane
two-stage (二段階ソート法）
サービス終了のお知らせ
大規模文字列解 析の理論と実践＠IBISML - DO++
Compressed Suffix Arrays - おなかすいたWiki！