高速文字列解析の"別"世界 - 気ままなブログ
1月に「高速文字列解析の世界」を購入してから半年が経ちました。以下、文字列本と呼びます。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 クリック: 324回この商品を含むブログ (4件) を見る 全文検索として、「CSA」や「FM-Index」が紹介されていますが、「全文検索システム」を作るには、これらだけでは不十分です。なぜなら、以下のような特徴があるからです。 文書IDの識別が遅い。 各文書IDに出現する頻度を求めるのが遅い。 ちなみに、転置インデックス(or N-gramインデックス)を使った場合、これらの処理は高速ですね。 インデックスを圧縮しているのだからしょうがないとも考えられますが、作りたいですよねぇ、「全文検索システム」。こ
Wavelet Treeをもう一度 - 気ままなブログ
文字列本のメインであるウェーブレット木をもう一度素直に見直すことにした。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 クリック: 324回この商品を含むブログ (5件) を見る Wavelet Treeに関する著者のスライドは以下である。 http://www.slideshare.net/pfi/ss-15916040 ふらふらと論文を眺めていたら、Navarro神の「Wavelet Trees for All」というサーベイ論文が加筆されて更新されていた。内容自体はあまり変わっていないと思うが図が増えていた。以下がその論文である。 http://www.dcc.uchile.cl/~gnavarro/ps/jda13.pdf 大半の内
文法圧縮入門：超高速テキスト処理のためのデータ圧縮（NLP2014チュートリアル）
言語処理学会第２０回年次大会（2014/3）のチュートリアル講義資料です。 - 要旨 - 文法圧縮とは，入力テキストをよりコンパクトな文脈自由文法（CFG）に変換する圧縮法の総称である． 文法圧縮の強みは圧縮テキストを展開すること無く，検索等のテキスト処理を効率よく行える点にある． 驚くべきことにその処理速度は，元テキスト上での同じ処理を理論的に，時には実際にも凌駕する． また近年，ウェブアーカイブやログ，ゲノム配列等の大規模実データを高効率に圧縮できることで注目を集めている． しかしながら，文法圧縮についての初学者向けの解説資料はまだまだ少ない． そこで本チュートリアルでは，文法圧縮の歴史的背景から最新動向までを幅広く紹介する． 具体的には文法変換アルゴリズム，圧縮テキスト上での文字列パターン検索，文法圧縮に基づく省メモリデータ構造等の解説を行う．Read less
30分でわかる高性能な圧縮符号vertical code - EchizenBlog-Zwei
検索エンジンの転置インデックスなどデータ列を小さいデータサイズで持たせたい、という状況がある。こういう場合圧縮符号を使うのが一般的でunary符号やgamma符号、delta符号など様々な種類がある。 圧縮符号の中でイチオシなのがvertical code(vcode)。これは岡野原(@hillbig)氏によって提案された圧縮符号で単純な仕組みでdelta符号並の性能を誇っている。 本記事ではvcodeのポイントを絞って30分でわかるように解説してみる。 vcodeは本棚に本を並べる作業を連想すると理解しやすい。本棚は予め高さが決まっているので全ての本が入るような本棚を用意する。つまり というようなものを想像する。 この本棚は8冊の本が並んでいるが左から5冊目の本が他よりも背が高い。このため5冊目の本に合わせて背の高い本棚が必要になる。だが他の本は5冊目の本ほどに背が高くないので、5冊目が
γ符号、δ符号、ゴロム符号による圧縮効果 - naoyaのはてなダイアリー
通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。 Variable Byte Code (Byte Aligned 符号とも呼ばれます) は整数の符号化手法の一つで、この無駄を幾分解消します。詳しくは Introduction to Information Retrieval (以下 IIR) の第5章に掲載されています。(http://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html で公開されています) Variable Byte Code はその名の通りバイトレベルの可変長符号で、1バイトの先頭1ビットを continuation ビットとして扱い、続く 7 ビット
MPEGラボ | 第20回 [ mpeg.co.jp ] h.264について
2023.11 弊社ドメイン[mpeg.co.jp]の変更(2023/03)に伴い、この度(2023/11)、全社員のメールアドレスを変更(mpeg.co.jp)することをお知らせ致します。 2023.6 FOR-A CONNECT 2023 内覧会(6/22[Thu]～6/23[Fri])無事に終えることができました。ご来場頂きました皆様、ありがとうございました。 2023.6 FOR-A CONNECT 2023 内覧会(6/22[Thu]～6/23[Fri])に合わせ、弊社にて内覧会を開催し、映像機器とIT技術が融合した製品、ソリューションを展示致します。 2023.3 株式会社朋栄アイ・ビー・イーと株式会社シーパスの2社を、2023年3月1日株式会社アイ・ビー・イーに経営統合しました。 ホームページのドメインをmpeg.co.jpへ変更しました。
高速な算術圧縮を実現する「Range Coder」
はじめに 本記事では、全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。 算術圧縮は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号法です。各文字に固定の符号を割り当てるHuffman法とは違い、符号化を状態更新とみなし、すべての文字を符号し終わった後の状態を保存することで符号化を実現します。これにより1文字単位の符号長を1bitより細かく調整することが可能となります。 算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化、復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは、算術符号の処理をバイト単位で行うことで高速な処理を可能にします。 また、算術圧縮については概要から説明します。 対象読者 C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ま
Data Compression Pointers
This page is partly written in Japanese. 日本語と英語のちゃんぽんです。 News [2005-03] Some Recent News: Mark Nelson's DataCompression.info sold to Visicron According to this page, Jean-loup Gailly seemingly abandoned the project. info-zip.org, gzip.org, and zlib.org are not maintained. Mark Adler maintains the new official site, http://www.zlib.net/. Rainer Nausedat passed away. [2003-07] LZW Patent and Softwar
画像圧縮アルゴリズム (10) 算術符号化
Range Coder復号化処理による数直線の変化は、以下のようになります。 復号化の場合、数直線は常に0からRangeまでの範囲になります。符号が数直線上のどこに位置しているのかをチェックして、Rangeを復号化されたデータが持つ範囲に変換するところは、やはり算術符号化での処理と本質的に変わりありません。 処理方法は以上になりますが、ここでいくつかの問題を解決する必要があります。まず一つは、符号化と復号化での計算で使用している変数Range / Sizeが0になる可能性があるということで、このときはRangeを計算した結果が0になってしまうため、処理を続けることができなくなります。よってRangeの取り得る最小値は、データのサイズより大きくなければなりません。Range / Sizeが0になった場合、サンプル・プログラムでは単純にエラー終了しています。Rangeの最小値はサンプル・プログ
静かな注目を集める圧縮アルゴリズム「LZMA」
GNUプロジェクトの配布アーカイブなどを中心に、LZMAを用いた圧縮形式を目にする機会が増えてきた。組み込み用途などへの活用も期待されるこの圧縮形式を紹介しよう。 2001年に開発された可逆圧縮アルゴリズム「LZMA」（Lempel-Ziv-Markov chain-Algorithm）が静かな注目を集めている。LZMAといえば、高い圧縮率を備え、Windowsアーカイバ「7-Zip」に採用されていることでも知られる。 ZIPやLHAなど、ファイルのアーカイブと圧縮が統合されているWindows由来のプログラムとは異なり、UNIXやLinuxでは伝統的にアーカイブと圧縮が個々のコマンドとして用意されており、それらを組み合わせて利用することになる。現在では、アーカイブがtar、圧縮にはGNU zip（.gz）やbzip2（.bz2）が併用されることが多い。 .gzや.bz2をしのぐ圧縮率が特
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
