サイトトップへ
OSASK.NET
SourceForge.JP
サイトトップへ       新掲示板   Wiki(凍結済)   旧掲示板(廃止済)   ニュース(廃止済)   最新チェッカー      
2: 2004-09-20 (Mon) 03:09:31 source 3: 2004-09-20 (Mon) 19:17:23 source
Line 1: Line 1:
-* tek5で使われているレンジコーダの原理を紹介するページ+* tek5で使われているレンジコーダの効果を紹介するページ
-(by [[K]], 2004.09.19) -(by [[K]], 2004.09.19)
-l2d3とかtek0とかUC0とかは(まあ)分かるけど、レンジコーダってなによ、どうしてそんなもので小さくなるのよ、ってたまに聞かれるので、適当に説明。 -l2d3とかtek0とかUC0とかは(まあ)分かるけど、レンジコーダってなによ、どうしてそんなもので小さくなるのよ、ってたまに聞かれるので、適当に説明。
Line 14: Line 14:
|デコード|1|01|001|0001|00001|000001|0000001|0000000| |デコード|1|01|001|0001|00001|000001|0000001|0000000|
|エンコード|000|001|010|011|100|101|110|111| |エンコード|000|001|010|011|100|101|110|111|
--このテーブルはこう使います。たとえば010001100000000000000000を出力したいときは、+-このテーブルはこう使います。たとえば 010001100000000000000000 を出力したいときは、
--01_0001_1_0000000_0000000_000 --01_0001_1_0000000_0000000_000
-と分解して、 -と分解して、
Line 20: Line 20:
-と出力します(後ろには適当に0を補った)。これなら24ビットを18ビットで出力できたことになります。 -と出力します(後ろには適当に0を補った)。これなら24ビットを18ビットで出力できたことになります。
-この例ですと、"1"を出力するのに3bit要しますが、"0"は最小で0.429ビットで出力できています。これが1ビットをより少ないビットで出力できるという分かりやすい例だと思います。 -この例ですと、"1"を出力するのに3bit要しますが、"0"は最小で0.429ビットで出力できています。これが1ビットをより少ないビットで出力できるという分かりやすい例だと思います。
--ちなみにレンジコーダのほうがもっと柔軟で拡張性のある考え方ですが、とにかく1ビットを1ビット未満の長さで出すという発想は同じなのです。+-ちなみに''レンジコーダのほうがもっと柔軟で拡張性のある考え方''ですが、とにかくビットの出現頻度の偏(かたよ)りを利用して1ビットを1ビット未満の長さで出すという発想は同じなのです。つまり、これはレンジコーダのアルゴリズムとは''全く別である''ことを忘れないでください。 
 + 
 +*** こんな1ビット単位のレンジコーダで縮むのか 
 +-ここまでの話で推測できるように、ビットが"0"か"1"に偏(かたよ)ってないと、レンジコーダによる圧縮は効きません。偏りが無い場合のテーブルは、 
 +|デコード|0|1| 
 +|エンコード|0|1| 
 +-にするのが一番いいのですが、しかしこれだと当然ながら圧縮されないのです。しかも偏りはかなり必要です。わずかな偏りではほとんど圧縮できません。 
 +-実際のファイルをただのビット列だと見たら、偏りはほとんどありません。"0"の個数は"1"の個数と大体同じです。2倍も3倍も違ったりはしません。これじゃあダメなのです。これじゃあハフマンに勝てないのです。ということで、ここからはその辺を解決するためのテクニックを紹介します。これはLZMAやtek5で実際に使われているやり方です。 
 + 
 +-まず、データをビットの列ではなく、バイトの列(8bitの列)であると解釈します。そして、そのうちの下位7bitのことは考えないでおいて、上位1bitだけを考えてみます。そうすると、100バイトのファイルならとにかく100bitの列が得られます。 
 +-この100bitですが、もしこれがASCIIテキストなら、そのほとんどが"0"です。他の形式のファイルだとしても、それなりに偏りがでます。まあこの段階で偏りがほとんど無いとしても実は問題ないのですが、とりあえずそれなりに偏りがあるとします。そうだとすれば、これは結構縮みます。これで残りは700bitです。 
 +-今度は第2ビットを取り出して、それで偏りを・・・と思うかもしれませんが、そうはしません。そもそもこの方法でやっていくと、最下位ビット(第8ビット)なんてほとんど偏りがありません(まあ偶数ばかりとか奇数ばかりのバイナリとかだったら効果があるかもしれませんが)。そんなのはうまくいかないので、第2ビット以降のビット列の考え方は違います。 
 +-それぞれのバイト列について、第1ビットが"0"だった場合と、第1ビットが"1"だった場合とで分類して、それぞれをまとめて、別々に第2ビットを取り出します。これだと、まあまあ偏ります。つまりデコードの場合、まず最上位ビット(第1ビット)をデコードして、次にその最上位ビットに基づいて第2ビットのエンコード用の対応表を選択して、それでデコードするわけです。 
 +-第3ビットは、第1と第2の結果の両方が使えますので、4通りに分けてから統計を取ります。・・・この調子で行くと最下位ビットは128通りに分けられます。下位のビットほど細かく分類されているので偏ります。それで平均してみると1バイトがたとえば6bitくらいで出力できていて、これでうまくいくわけです。 
 +-理解を助けるために例を出します。たとえば、もし、0x00と0xffしかないファイルがあって、しかもこれがランダムで等確率に並んでいたとしましょう。これですと最上位ビットは"0"なのか"1"なのか全く予測できませんし、偏りが無いので平均1bitで出力されます。しかし第2ビットは第1ビットが"0"なら"0"がくるものばかりで極端に偏っていますし、第1ビットが"1"なら"1"が来るものばかりで偏っています。そんなわけで、これは平均0ビットでエンコードされます。第3ビットは、それまでの上位2ビットが"00"と"11"の場合で場合分けされて別々に偏りを出しているので、やはり平均0bitでいけます。これが第8ビットまで続いて、結局、このデータ列は1/8に圧縮できることになります。これはハフマンでやった場合と全く同じです。 
 +-もう一つ例を出します。0x01と0x23です。この場合、第1ビットはどちらも"0"ですので極端に偏って平均0ビット。第2ビットも"0"しかないので、平均0ビット。しかし第3ビットは"0"と"1"が半々に出てくるので平均1ビット。第4ビットはそれまでが"000"の場合は"0"だけですし、"001"の場合も"0"だけですので、どちらも極端に偏ってそれぞれ平均0ビット。・・・というふうになって、やっぱりこのデータ列も1/8に圧縮できることになります。これもやはりハフマンと同じです。 
 +-これでとりあえずレンジコーダではハフマンと同程度にはできそうだと分かってもらえたと思いますが、今度はレンジコーダのほうがよくできる例を出します。普通にハフマンを使うと、0x00と0xffのどちらも最低で1ビットを割り振るので、つまり1/8より小さくすることはできません(LHAがそれより小さくできるのはもっぱらスライド辞書を併用しているからです。もちろんLZMAやtek5もスライド辞書を併用していますが)。しかし、レンジコーダによるエンコードなら、0x00がほとんどで0xffはめったに出ない、なんていう場合、圧縮率を1/8よりもっとずっとよくできます。というのは、第1ビットの統計の部分で偏りが出るからです。 
 + 
 +*** もっと偏りを出すための方法 
 +-LZMAやtek5ではさらに圧縮率を上げるために、つまりもっと偏りを出すために、さらに工夫をしています。 
 +-たとえば、C言語ソースなどのテキストファイルを考えたとき、アルファベットの直後にはアルファベットが来やすいだろうとか、数字の後ろには数字が来ることが多いだろうとか、タブの後ろにはタブが来そうだとか、0x0dのあとには0x0aが来そうだとか、そういう性質を、ビットの偏りに反映させたいと考えます。 
 +-具体的にはどうするのかというと、ビット列を作る場合に、直前の1バイトがいくつであったかを調べ、それによってまた場合分けしてやろうということです。256通り全てで統計を取ると大変すぎるので、たいていは直前バイトの上位3ビットを取り出して、8通りの状態から第1ビットのデコード方法を決めます(上位3ビットくらいをみれば、直前が数字であったか、アルファベットであったか、タブであったかくらいは分かる)。そして第2ビットは、直前バイトの8通りにさらに先ほどの第1ビットのデコード結果を加えて、16通りでやります。この調子で行くと最後の第8ビットは1024通りにもなりますが、それぞれの状況に応じてビット列がどうなっているかを調べて、エンコード・デコードしていくのです。 
 +-直前バイトの上位3bitを使うというのはデフォルトでしかなく、-lcオプションで、0~8に調整できます。8だと直前バイトの8bitをすべて使ってやるので、最後の第8ビットは3万通り以上にも分けられていることになります。一方で、-lc0ですと直前バイトの情報は全く使わないことになります。-lc8で直前バイトをフルに使うと、それぞれの状況に応じてのビットの出現頻度統計情報をメモリで管理しなければいけなくなり、それは第8ビットのところで3万通り以上ですし、そのほかの第1~第7ビットの分も入れると6万通りを超えます。そのためエンコード時にもデコード時にもこれらを管理するためのワークエリアが必要になります。 
 +-他にも-lpというオプションがあり、これはバイト列の何番目かによって統計情報が変えるほうが偏りが出るのではないかというものです。1バイト目は0x00が多いとか、2バイト目は0xaaが多いとか、そういうものです。このような性質が周期的に繰り返されていると仮定して、そのバイト位置のオフセットの下位1ビット(2バイト周期)、下位2ビット(4バイト周期)、下位3ビット(8バイト周期)、下位4ビット(16バイト周期)をビット列の場合分けに利用するというものです。-lc8で-lp4にした場合、ワークエリアはかなり大量に必要になります。 
 + 
 +*** LZMAからtek5での改良点 
 +-書き途中
* こめんと欄 * こめんと欄
#comment #comment

Front page   Diff Backup Copy Rename ReloadPrint View   New Page Page list Search Recent changes   Help
ログイン
ユーザー名:
パスワード:
 
新着

目次
メンバー一覧


recent(20)
2016-10-01 2016-09-08
  • @MenuBar.
2016-09-07 2016-09-04 2016-08-15 2015-09-23 2014-07-30 2014-07-04 2014-02-04 2013-10-26 2013-06-21 2013-06-17 2013-06-15 2013-04-02 2013-02-09 2013-02-04 2012-12-25 2012-12-01 2012-05-28 2012-03-31

トピック一覧
一般用コメント最新
新掲示板lina
2016/9/5 20:58
SandBoxゲスト
2016/9/4 12:01
RecentDeletedlina
2015/6/2 19:29
Old-OSASK-MLlina
2014/6/29 9:14
hideyosi/メールhideyosi
2014/1/6 20:17
hideyosi/募集中lina
2013/11/8 19:56

このサイトは川合秀実から委託を受けて、OSASKコミュニティによって管理・運営されています。
このサイトに関するお問い合わせは掲示板にお願いいたします。