株式会社Yostar最新情報 プレスリリース2019.08.01 『アズールレーン』が第３回全国エンタメまつり「ぜんため」に初出展いたします プレスリリース2019.07.12 『コミックマーケット96』企業ブースに出展決定！ プレスリリース2019.04.25 対戦型麻雀ゲーム『雀魂』WEB版のサービスを開始いたしました MORE
テキスト圧縮はこれ一冊で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変換というのはテキストを同じ文字が並びやすいように変換したもので、通常ランレ
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
定兼 邦彦 (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) と呼ばれるもので，索引自体に 元のファイルの情報を全
A Lightweight External Memory BWT Construction Algorithm
Welcome to the home page of bwte: the first tool for the direct construction of the BWT of large files in external memory. Direct construction means that the BWT is built directly, without first computing the suffix array. bwte accesses the disk data only by sequential scans so it takes full advantage of the modern caching architectures. In addition, it stores all files (input, output, and interme
BlockSorting
BlockSortingは、今までのデータ圧縮で有名な方法であるLZ法とは全く違う、ユニークな操作を用 いてデータを圧縮する方法であり、M.BurrowsさんとD.J.Wheelerさんが作者なので「BWTransform」 ともいいます。 このアルゴリズムは簡単に言ってしまえば、「データをぐるぐる回してソートして出力」というも のです。簡単すぎるかもしまいませんが、本当にそうなんです。 ちなみに、このBlockSorting、単体では全く圧縮しません。ただ可逆な形にデータを変換すると いうものです。しかし、BlockSorting後のデータは非常に圧縮されやすい状態になります。例える と、色々な形をしたスポンジ（データ）が箱にごちゃごちゃに入って山積みになっているとします 。 これをそのまま上からギューっと押しつぶすのがLZ法やHuffman法なのに対し、一度、形が似た も
mots quotidiens. - PPM, 言語モデル, Burrows-Wheeler Transform
電通大の情報理論の 韓太舜先生 の最終講義が3月にあって, スライドが ここから 見られるのを知った。 院生のときに 『情報と符号化の数理』 (岩波書店 応用数学)を読んで, その明晰な内容と込められた哲学に感動した ので, 感慨深いです。 16ページ目の内容が本当なら, Weber-Fechnerの法則が理論から導けるという ことなのだろうか.. フルテキストは1975年なので, 閲覧制限がかかっていて見れないのが残念。 他も, 全体的に非常に興味深いのですが, とりあえず最後がワラタ。(笑) 論文の準備のためにPPM,PPM*,CTWなど圧縮関係の論文を(完璧ではないと 思いますが), 色々読んでみた。 PPMについては, 北先生のところで1998年に, PPM*を使った言語モデルの話 が出ています。 さて, PPMは岡野原君が 言語モデルと 似ている という話を書いているのですが,
BWT と PPM - naoyaのはてなダイアリー
Burrows Wheeler Transform (BWT, Block-sorting) と Prediction by partial matching (PPM) は本質的に同じ事をやっている、というお話です。 先日 Managing Gigabytes を読んでいたところ、P.69 で "block sorting is very closely related to the PPM* method, which is a variant of PPM that allows arbitrary-length contexts." という記述があり、どうにも気になったので調べてみました。 サマリとしては、BWT と PPM の一種である PPM* はいずれも文脈から次の1文字を一意に決定するという概念で見ると本質的に同じことをやっていると言える、というところです。 BWT のあら
Google Sites: Sign-in
Not your computer? Use a private browsing window to sign in. Learn more about using Guest mode
Algorithm::MTF / BWT → MTF → Range Coder によるデータ圧縮 - naoyaのはてなダイアリー
先日言及した Burrows Wheeler Transform (id:naoya:20081016:1224173077) による変換後のテキストは圧縮に使えたり、全文索引に利用できたりと応用範囲は広いです。 BWT により変換したテキストを圧縮するには、そのまま圧縮するのではなく先頭移動法 (Move-To-Front http://ja.wikipedia.org/wiki/Move_To_Front) を適用することでより情報に偏りを持たせてから圧縮するのがセオリーです。 今日は先頭移動法の Perl 実装を作ってみました。Algoritm::MTF です。 http://github.com/naoya/perl-algorithm-mtf/tree/master に置いています。 use Algorithm::MTF; my $encoder = Algorithm::MTF
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等。 長さ n のデータを巡回シフトし、得られるすべての文字列を辞書順にソートする。このようにしてできた n×n 行列の第 n 列を取り出したものが、BWT系列である
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
生物情報科学科 情報基礎実験 ３年生冬学期 10/26 – 11/5 （森下研究室担当）
大規模文字列解 析の理論と実践＠IBISML - DO++
bwte - white page
サービス終了のお知らせ
Amazon.co.jp: The Burrows-Wheeler Transform:: Data Compression, Suffix Arrays, and Pattern Matching: Adjeroh, Donald, Bell, Timothy, Mukherjee, Amar: 本