様々な操作を高速にサポートするデータ圧縮法に関する論文を公開しました。 - Yasuo Tabeiの日記
様々な操作を高速にサポートするデータ圧縮法に関する論文を公開しました。本論文はデータ圧縮に関する国際会議 Data Compression Conference (DCC2015)に採択された論文でarXivから入手出来ます。 Djamal Belazzougui, Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen, Alberto Ordóñez, Simon J. Puglisi, Yasuo Tabei: Queries on LZ-Bounded Encodings, Data Compression Conference (DCC), 2015. 論文へのリンク(arXiv) 提案法はLempel-Ziv(LZ)法に類似性がありその簡易版になっています。LZ法では各テキスト上の位置より前に出現する部分文字列の最長一致文字をテキスト
文法圧縮入門：超高速テキスト処理のためのデータ圧縮（NLP2014チュートリアル）
言語処理学会第２０回年次大会（2014/3）のチュートリアル講義資料です。 - 要旨 - 文法圧縮とは，入力テキストをよりコンパクトな文脈自由文法（CFG）に変換する圧縮法の総称である． 文法圧縮の強みは圧縮テキストを展開すること無く，検索等のテキスト処理を効率よく行える点にある． 驚くべきことにその処理速度は，元テキスト上での同じ処理を理論的に，時には実際にも凌駕する． また近年，ウェブアーカイブやログ，ゲノム配列等の大規模実データを高効率に圧縮できることで注目を集めている． しかしながら，文法圧縮についての初学者向けの解説資料はまだまだ少ない． そこで本チュートリアルでは，文法圧縮の歴史的背景から最新動向までを幅広く紹介する． 具体的には文法変換アルゴリズム，圧縮テキスト上での文字列パターン検索，文法圧縮に基づく省メモリデータ構造等の解説を行う．
30分でわかる高性能な圧縮符号vertical code - EchizenBlog-Zwei
検索エンジンの転置インデックスなどデータ列を小さいデータサイズで持たせたい、という状況がある。こういう場合圧縮符号を使うのが一般的でunary符号やgamma符号、delta符号など様々な種類がある。 圧縮符号の中でイチオシなのがvertical code(vcode)。これは岡野原(@hillbig)氏によって提案された圧縮符号で単純な仕組みでdelta符号並の性能を誇っている。 本記事ではvcodeのポイントを絞って30分でわかるように解説してみる。 vcodeは本棚に本を並べる作業を連想すると理解しやすい。本棚は予め高さが決まっているので全ての本が入るような本棚を用意する。つまり というようなものを想像する。 この本棚は8冊の本が並んでいるが左から5冊目の本が他よりも背が高い。このため5冊目の本に合わせて背の高い本棚が必要になる。だが他の本は5冊目の本ほどに背が高くないので、5冊目が
「第3回自然言語処理勉強会＠東京」でCSAについて発表します - EchizenBlog-Zwei
@nokunoさんの好意で「第3回自然言語処理勉強会＠東京」でCompressed Suffix Arrayについて発表させていただくことになりました。 つきましては参考のため発表資料を以下に置いておきます。参加される方はもちろん、興味のある方はご覧になっていただけるとうれしいです。 第3回自然言語処理勉強会＠東京 : ATND 第3回自然言語処理勉強会＠東京を開催します - nokunoの日記 なお本資料は以下の皆様のアドバイスを頂きました。ありがとうございました(とくに@overlastさんには4-5時間もお付き合い頂きました。おかげさまでスライドの質が大幅アップしました。感謝)。 @overlastさん @tamago_donburiさん @tsubosakaさん @machyさん
整数列圧縮 その2 - NewPFD -｜JAVAでデータマイング！
JAVAでデータマイング！ 『情報工学の難しいそうなアルゴリズムをJAVAで実装して、ひたすらその結果を公開する』ブログになる予定。 PR Calendar <<April>> S M T W T F S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Theme NaiveBayes ( 2 ) スムージング ( 0 ) はじめに ( 1 ) 計算テクニック ( 0 ) 整数列圧縮 ( 2 ) 外れ値除去 ( 0 ) LSH ( 4 ) 協調フィルタリング ( 0 ) ブースティング ( 0 ) Kmeans ( 0 ) 階層的クラスタリング ( 2 ) EMアルゴリズム ( 0 ) BM ( 0 ) SVD ( 0 ) PLSI ( 0 ) LDA ( 0 ) パーセプトロ
LZMA SDK (Software Development Kit)
What's new: 24.09: The default dictionary size values for LZMA/LZMA2 compression methods were increased. 24.05: New filter for RISC-V executables. 23.01: New filter for ARM64 executables. BCJ2 filter was improved for better compression ratio. Some bugs were fixed. 21.07: Some minor changes and fixes. 21.06: The bug in LZMA encoding function was fixed. 21.03 beta: LZMA dicrionary up to 4 GB. Speed
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)で探索できる、というもの。 たとえば
Compressed Suffix Arrayの解説(4) -unary記法- - EchizenBlog-Zwei
< Compressed Suffix Arrayの解説(3) -圧縮の方針- < | > Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- > ================================================ まずは下準備。数値列をunary記法でbit列に変換する方法を説明。 unary(ユナリィ)記法というのは数値の数だけの0を並べて、最後に1を置くというもの。具体例を挙げると 数値 unary 0 1 1 01 2 001 3 0001 4 00001 5 000001となる。 unary記法では1が数値間の境界を表すために各数値毎のbitサイズを固定長にする必要がない。例えば数値列 1 1 2 2 1 2は各数値をそれぞれ1byteで表したとすると全体で48bit(6byte)必要になる。一方で
[IR] Google WSDM'09講演で述べられている符号化方式を実装してみた - tsubosakaの日記
MG勉強会の後にid:sleepy_yoshiさんに教えてもらったWSDM 2009における講演"Challenges in Building Large-Scale Information Retrieval Systems"で述べられている符号化方式のGroup Varint Encodingを実装してみた。 資料 講演スライド スライドの日本語による解説記事 整数の符号化方式 転置インデックスなどで文章番号のリストを前の値との差分で表すなどの方法を用いると出現する、ほとんどの値は小さな値となるためこれを4バイト使って表現するのは記憶容量の無駄である。 このためVarint Encoding、ガンマ符号、デルタ符号、Rice Coding、Simple 9、pForDeltaなど様々な符号化方式が提案されている。このうちVarint Encodingは実装が手軽なことからよく用いられて
![[IR] Google WSDM'09講演で述べられている符号化方式を実装してみた - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/d5a026a6225c4524c834d0237efa271b5b0d54f0/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124030436%2F1557332443)
データ圧縮法概説 目次
最終更新日：2001年7月2日 第1章へ webmaster@snap-tck.com Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)
連想配列の進化 - DO++
キーに対して値を結びつける連想配列は多くのアプリケーションの肝であり、コンパクトかつ高速な処理が可能な連想配列を追い求め日夜研究が進められています。 特に非常に巨大な連想配列を高速に処理するというのが重要な課題となっています。例えば、音声認識・文字認識・機械翻訳などで使われている言語モデルでは、非常に大量のN個の単語列の情報（特に頻度）を格納することが重要になります。 この場合、キーが単語列であり、値が単語列のコーパス中での頻度に対応します。 例えばGoogle N-gram Corpusからは数十億種類ものN-gramのキーとその頻度などが取得できます。これらを主記憶上に格納し、それに関する情報（頻度や特徴情報）を操作することが必要になります。 そのほかにも大規模なデータを扱う問題の多くが巨大な連想配列を必要とします。 ここではこのような連想配列の中でも、キーの情報を格納することすら難し
BlockSorting
BlockSortingは、今までのデータ圧縮で有名な方法であるLZ法とは全く違う、ユニークな操作を用 いてデータを圧縮する方法であり、M.BurrowsさんとD.J.Wheelerさんが作者なので「BWTransform」 ともいいます。 このアルゴリズムは簡単に言ってしまえば、「データをぐるぐる回してソートして出力」というも のです。簡単すぎるかもしまいませんが、本当にそうなんです。 ちなみに、このBlockSorting、単体では全く圧縮しません。ただ可逆な形にデータを変換すると いうものです。しかし、BlockSorting後のデータは非常に圧縮されやすい状態になります。例える と、色々な形をしたスポンジ（データ）が箱にごちゃごちゃに入って山積みになっているとします 。 これをそのまま上からギューっと押しつぶすのがLZ法やHuffman法なのに対し、一度、形が似た も
Prediction by Partial Matching - Wikipedia
Prediction by Partial Matching（PPM）は1984年にJ.G.ClearyとI.H.Wittenによって考案されたデータ圧縮アルゴリズムの1つ。 この改良版が7-zip等に用いられている。非常に高い圧縮率の反面、圧縮速度はかなり遅くメモリも多く消費するアルゴリズムである。 この亜種としてPPMC、PPMd、PPMZ等がある。 aabacaabbaとデータを符号化したとして、次にどの記号が出現するかを統計的に予測する。この場合、統計的にaの次にはaが出現する可能性が高い。逆にcが出現する可能性は低いであろう。このように出現確率に偏りがあるとハフマン符号や算術符号で圧縮することができる。しかし、上記の場合に次に出現する符号をaを50%、bを40%、cを10%と予測したとすると、他の記号は絶対に現れないということになり、新たな記号（dとする）が出現したときに対応でき
PPM
PPMとは？ PPMというのは、既出したデータから次の文字を予測して、確率を変化させる ことにより圧縮するものである。 例えば abcdabcdabcdabc○ と来て○に入る文字は何だろうと考えてみたとき、dが出やすいというのは直感的に わかる。そういう場合はdの確率を上げ、他の文字の出現確率を下げる。すると、圧縮 される。たぶんわからないと思うので、詳しく説明します。 確率を上げるとなぜ圧縮率が上がるか？ 例えば８種類の文字 a,b,c,d,e,f,g,h があって、それを0と1で表すのならば a:000 b:001 c:010 d:011 e:100 f:101 g:110 h:111 （方法Ａ） とそれぞれに3bit割り振ればよい。つまり一文字に付き3bit使う。 これに対し、もし８つの文字にばらつきがある、つまり出現確率が違う場合には 多く出てくる文字に対
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 のあら
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Compressed Suffix Arrays - おなかすいたWiki！
YAPC::Asia 2009 1日目 「Perlで圧縮」の資料 - naoyaのはてなダイアリー
サービス終了のお知らせ
サービス終了のお知らせ