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使う。 これに対し、もし８つの文字にばらつきがある、つまり出現確率が違う場合には 多く出てくる文字に対
BlockSorting
BlockSortingは、今までのデータ圧縮で有名な方法であるLZ法とは全く違う、ユニークな操作を用 いてデータを圧縮する方法であり、M.BurrowsさんとD.J.Wheelerさんが作者なので「BWTransform」 ともいいます。 このアルゴリズムは簡単に言ってしまえば、「データをぐるぐる回してソートして出力」というも のです。簡単すぎるかもしまいませんが、本当にそうなんです。 ちなみに、このBlockSorting、単体では全く圧縮しません。ただ可逆な形にデータを変換すると いうものです。しかし、BlockSorting後のデータは非常に圧縮されやすい状態になります。例える と、色々な形をしたスポンジ（データ）が箱にごちゃごちゃに入って山積みになっているとします 。 これをそのまま上からギューっと押しつぶすのがLZ法やHuffman法なのに対し、一度、形が似た も
Canonical Huffman Code
Daisuke Okanohara (VZV05226@nifty.com) 2003/12/9 公開 2003/12/11 誤植、chc.zipのmain.cppを修正 2003/12/13 multidecodeを実装 main.cppもそれに伴い変更 Canonical Huffman Code (以下CHC）は、Huffman法と同様に、最小冗長符号をHuffman木を作成、保持することなく、表引きで、符号化、復号化できる符号法です。 CHCは突然現れたアルゴリズムではなく、1950年代にHuffman法が登場して以来（Huffman法は、Fano符号で有名なFanoが出した最終試験免除の課題を学生だったHuffmanが試験直前に解決して発明された）、表向きにしろ、そうでないにしろさまざまな改良が、実装面、理論面でも行われてきました。その変種はいろいろありますが、その中で最も
圧縮/伸張技術の解説-ＢＷＴ(1)
近年の情報化社会において、インターネット、マルチメディア、分散ソフトウェア、をはじめとするコンピュータ技術の劇的な発展と普及により、システム間の通信情報量は増大の一途をたどっています。 データ圧縮技術は「サイズを減らす（同じサイズでより多くの情報を詰め込める）」という利点から、通信効率の改善、記憶装置の有効利用、に不可欠な基礎技術です。さらに「通信データ量を減らすことでCPUへの負荷を軽減しマルチタスク処理のレスポンスを改善する」という有用性もあり、その重要性は日に日に高まっています。 データ圧縮は本来、情報理論分野での「通信システムにおける情報量 の最小化の研究」の産物である「情報源符号化法」に端を発する技術であり、この分野では、工夫を凝らした様々な問題解決手法が提案されており、アルゴリズムを学ぶ上でたいへん興味深い分野の一つです。 代表的な例として、１８世紀頃から用いられていているモー
DO++ : 透過的データ圧縮
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
white page / 全文検索や圧縮に関するlinks集
Copyright © 2004-2008, Yuta Mori, All Rights Reserved. yiv01157 at nifty dot com http://homepage3.nifty.com/wpage/
List::FrontCode - naoyaのはてなダイアリー
先日 Array::Gap という Variable Byte Codes による整列済み整数の圧縮の実装を作りました。(id:naoya:20080906:1220685978) 今日は Front Coding を使った同じような圧縮リストクラス、List::FrontCode を作ってみました。Front Coding は辞書式順に整列済みの文字列リストなどを圧縮する手法です。WEB+DB PRESS Vol.42 のアルゴリズム&データ構造の記事で PFI の岡野原さんによる解説があったので、それを参考に実装しました。 Front Coding Front Coding は http://www.hoge.jp http://www.hoge.jp/a.htm http://www.hoge.jp/index.htm http://www.fuga.com/ http://www.
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
