注意!
ここからの解説内容はできるだけわかりやすく説明するため、かなり私見を入れています。
厳密に言うと間違っている説明が含まれているかもしれませんが、ご容赦ください。
1. LS11フォーマット概要
三国志シリーズで使用されている圧縮方式です。
(厳密に言うと暗号化ではありませんのであしからず)
ファイルのヘッダにLS11と書かれているものがそうです。
三国志9、11での使用を確認しています。
そしてLS11は、ハフマン符号とLZ77を組み合わせた圧縮方式です。
ハフマン符号+LZ77は、GZIP、ZIP、LZHなどで使用されている
割とオーソドックスな組み合わせです。
もちろんそれぞれのフォーマットは細かな点で違うため、圧縮率に差があります。
LS11はかなり簡易な手法を用いているため、圧縮率は高くありません。
2. 圧縮理論
ここからは圧縮理論の説明に入ります。
概念から学びたい人は2.1 概念的な話から。
理論を学びたい人は2.2 理論の話から。
復号方法だけわかればいいや、という人は3. 復号方法まで飛ばしてください。
2.1 概念的な話
ここからは概念的な話です。
実際のものとは異なりますが、大まかなイメージを掴むためのものです。
理論の話がわからない場合、手助けになるかもしれません。
2.1.1 符号化
符号化とはある語をより短い語で置き換えることを言い、置き換えた短い語を符号といいます。
両者(符号化側と復号化側)が置換方法を認識していれば、符号化しても元に戻せるというわけです。
高校生やねらーがよく単語を略す感じに似てます。
(例
おはようございます → おは わくわくてかてか → wktk
おはようございますモラーさん。今日もわくわくてかてかしてございますね。 ↓(符号化) おはモラーさん。今日もwktkしてございますね。 |
上の2行を符号表といい、これがあれば符号化された文章も原文に復号できるというわけです。
そしてこのような符号化を行うことでデータを圧縮できます。
2.1.2 ハフマン符号化
ではハフマンと名がつく符号化はどのようなものでしょう?
ハフマン符号化にも色々種類があるのですが、基本は以下のものです。
よく使う語には短い符号を、あまり使わない語には長い符号を割り当てる
つまり、普通の人はおはようございますをよく使うのでおはと符号化した方がいいですが
花好きの人はおはなをよく使うのでこれをおはと符号化し、
おはようございますはおはようと符号化した方がいいでしょう
ねらーはわくわくてかてかをwktkと符号化た方がいいですが
料理好きの人は和風海鮮豆腐コロッケをwktkと符号化し、
わくわくてかてかはわくてかと符号化した方がいいでしょう。
なので例えば料理好きな人用の符号表は以下のように設定します。
語 |
符号 |
おはようございます |
おは |
和風海鮮豆腐コロッケ |
wktk |
わくわくてかてか |
わくてか |
こんな感じでよく使う語を考えて符号表を作成し、
符号化、圧縮しようというのがハフマン符号です。
2.1.2 LZ77
LZ77とは、「同じ文章がでてきたら距離と長さのペアに置換する」という圧縮手法のことです。
(例
おはようございますモラーさん。今日もわくわくてかてかしてございますね。 ↓LZ77 おはようございますモラーさん。今日もわく[2文字前から2文字]てか[2文字前から2文字]して[24文字前から5文字]ね。 |
文章中にわくが2回出てきてますね。
なので後ろのわくを2文字前から2文字分と同じものだよという意味のものに置き換えます。
文章中にてかが2回でてきてますね。
なので後ろのてかを2文字前から2文字分と同じものだよという意味のものに置き換えます。
文章中にございますが2回出てきてますね。
なので後ろのございますを24文字前から5文字分と同じものだよという意味のものに置き換えます。
繰り返しの文字が長ければ長いほど、データを圧縮できるというわけです。
2.1.3 ハフマン符号+LZ77
LS11ではこの2つを組み合わせます。
どうやるかというと、LZ77で圧縮してから、ハフマン符号化します。
(例
おはようございますモラーさん。今日もわくわくてかてかしてございますね。 ↓LZ77 おはようございますモラーさん。今日もわく[2文字前から2文字]てか[2文字前から2文字]して[24文字前から5文字]ね。 ↓ハフマン符号化 おはモラーさん。今日もわく[2,2]てか[2,2]して[24,5]ね。 |
まず2.1.2の例と同じようにLZ77で圧縮します。
次にハフマン符号化します。
おはようございますをおはに。
LZ77の距離と長さのペアも[距離,長さ]という符号で置き換えてしまいます。
こんな感じで圧縮を行うわけです。
2.2 理論の話
ここからは具体的な理論に入っていきます。
ちょっと難しくなるかもしれません。
2.2.1 接頭符号
まず、できるだけ短くするために、符号はbit単位で決められます。
(6bitや14bitなど、Byte単位である8の倍数でない中途半端なbit数の符号があるということ)
更に復号するために必ず一意に決められる必要があるとともに、
符号を読んでいる途中に他の符号と勘違いしないことも必要となります。
ハフマン符号化ではこれらの条件を満たすため、接頭符号が使われます。
接頭符号とは、簡単に言うと電話番号の割り当て方式です。
普通、電話番号は10桁ですが、一昔前は9桁のものもありました。
ここでちょっと考えて見ましょう。
AさんがBさんに電話をかけようと0123456789をプッシュします。 ところがCさんの電話番号は012345678です。 Aさんが012345678とプッシュした時点で、Cさんに繋がってしまう可能性があります。 これではまずいですね。 ですから012345678という電話番号が存在した場合、0123456789という電話番号は絶対に存在しません。 |
これが「接頭符号」です。
つまり、2進数で001という符号があった場合、
0010や0011、はたまた00111などといった001の後にbitが続く符号は存在しないということです。
このような接頭符号を使用することで、実際の圧縮データを読み出す時に、
001というbit列がきたとき、「これは001じゃなくて0011という符号かも??」
という疑念を抱かなくて済みます。
接頭符号はよく二分木で表現されます。
根から葉までの経路で0と1のbitを選び、葉の時点でのbit列を接頭符号として使います。
枝は符号として使用しません。
2.2.2 接頭符号の作り方
LS11の接頭符号は以下の手順で作っていきます。
(xは0から始めます)
- 先頭にx個のbit'1'を並べる
- その後ろにbit'0'を一つだけ置く
- ①と②で置いたbit数と同じ数の'0'を後ろに置く
- これを接頭符号として使う
- ④に1を足す
- これを接頭符号として使う
- 最大値になるまで⑤と⑥を繰り返す(①と②で置いたbitはそのまま)
- xに1を足して①に戻る
ちょっとやってみましょう。
手順 |
途中の接頭符号 |
使用する接頭符号 |
x=0 |
bit'1'を0個並べる |
|
|
その後ろにbit'0'を一つだけ置く |
0 |
|
置いたbit数と同じ数の'0'を後ろに置く |
00 |
00 |
1を足す |
01 |
01 |
最大になったのでxに1を足す |
|
|
x=1 |
bit'1'を1個並べる |
1 |
|
その後ろにbit'0'を一つだけ置く |
10 |
|
置いたbit数と同じ数の'0'を後ろに置く |
1000 |
1000 |
1を足す |
1001 |
1001 |
1を足す |
1010 |
1010 |
1を足す |
1011 |
1011 |
最大になったのでxに1を足す |
|
|
x=2 |
bit'1'を2個並べる |
11 |
|
その後ろにbit'0'を一つだけ置く |
110 |
|
置いたbit数と同じ数の'0'を後ろに置く |
110000 |
110000 |
1を足す |
110001 |
110001 |
1を足す |
110010 |
110010 |
1を足す |
110011 |
110011 |
1を足す |
110100 |
110100 |
1を足す |
110101 |
110101 |
1を足す |
110110 |
110110 |
1を足す |
110111 |
110111 |
最大になったのでxに1を足す |
|
|
・・・ |
こうやって作成していきます。
2.2.3 LZ77
LZ77は、Byte単位で以前出てきた繰り返しの文字を探し、距離と長さのペアに置換します。
距離は何Byte前かを表し、長さは何Byte読み取るかを表します。
これは符号と違い、bit単位ではなくByte単位であることに注意してください。
(例
01 02 03 04 05 02 03 04 06 ↓LZ77 01 02 03 04 05 [距離4、長さ3] 06 |
(この数字は全て16進数表記です)
ここで重要なのが、この距離と長さもLZ77で圧縮後にハフマン符号化されるということです。
詳しくは後述します。
また、場合によっては長さ>距離の場合もあるので注意しましょう。
(例
01 02 03 04 02 03 04 02 03 05 06 ↓LZ77 01 02 03 04 [距離3、長さ5] 05 06
01 02 02 02 02 02 02 02 02 02 03 ↓LZ77 01 02 [距離1、長さ8] 03 |
(この数字は全て16進数表記です)
2.2.4 ハフマン符号化
符号化するとき、データは全て単語、距離、長さの3種類に符号化されます。
単語とは1Byteのデータを符号化したものです。
単語は1Byteのデータなので、2^8=256語あります。
LS11では、ヘッダに書かれている辞書を使って符号表を作り、それに従い符号化します。
距離とはLZ77の距離を符号化したもの、
長さとはLZ77の長さを符号化したものです。
この距離と長さは必ずペアになります。
LS11では、この2つは計算で求めることができます。(表を作ってもできます)
ハフマン符号化では、まずデータを全て調べあげ、よく使うByte順に並べます。
これが単語の符号表なわけですが、辞書とも呼ばれます。
この辞書はLS11のヘッダ部分に収納されています。
では実際に符号表を作ってみましょう。
辞書は簡略化のため、00~FF(16進数)まで順番に並んでいるものとします。
本来はその使用頻度により、並び替えられているはずなので注意してください。
まず、単語の符号表を作成します。
辞書の最初のByteから、2.2.2で作成した接頭符号を順に割り当てていきます。
単語(16進数) |
符号(2進数) |
00 |
00 |
01 |
01 |
02 |
1000 |
03 |
1001 |
04 |
1010 |
05 |
1011 |
06 |
110000 |
07 |
110001 |
08 |
110010 |
09 |
110011 |
0A |
110100 |
0B |
110101 |
0C |
110110 |
0D |
110111 |
0E |
11100000 |
0F |
11100001 |
10 |
11100010 |
・・・ |
・・・ |
FD |
11111101111111 |
FE |
1111111000000000 |
FF |
1111111000000001 |
これで単語の符号表は完成です。
辞書の最初のByteほど、符号のbit数が短いのがわかりますね。
辞書の最初によく使うByteを最初の方に登録しておくことで、効率的な圧縮ができるというわけです。
次に距離の符号ですが、距離の符号は単語の最後の符号である1111111000000001の続きから使用します。
つまり1111111000000001の次の1111111000000010が距離0を表すというわけです。
表にするとこんな感じになります。
距離(10進数) |
符号(2進数) |
0 |
1111111000000010 |
1 |
1111111000000011 |
2 |
1111111000000100 |
3 |
1111111000000101 |
4 |
1111111000000110 |
5 |
1111111000000111 |
・・・ |
・・・ |
距離に最大値があるのかはちょっと確認できていません。
普通に考えるなら4096くらいが最大だと思うのですが。
最後に長さの符号です。
注意点は、単語、距離のハフマン符号は重複しませんが、
長さの符号は、単語または距離の符号と重複することです。
なぜかというと、長さの符号は必ず距離の符号の後ろに来るため、
重複していても区別できるからです。
長さの符号は、2.2.2で説明した接頭符号を順に割り当てていきますが、
最小値は3です。つまり長さが1や2の繰り返しはLZ77で圧縮しないことになります。
表にするとこんな感じになります。
長さ(10進数) |
符号(2進数) |
3 |
00 |
4 |
01 |
5 |
1000 |
6 |
1001 |
7 |
1010 |
8 |
1011 |
9 |
110000 |
10 |
110001 |
11 |
110010 |
12 |
110011 |
13 |
110100 |
・・・ |
・・・ |
長さも最大値があるのかは確認できていません。
普通に考えるなら256くらいが最大だと思います。
以上で符号表は完成です。
LS11はこの符号表を使ってデータをLZ77+ハフマン符号化により圧縮しているというわけです。
2.2.5 実際に使う符号表
本来なら、LS11のヘッダにある辞書を使って符合表を作成し、
表の符号に当てはまるか探しながら復号するのが常套手段です。
しかしLS11ではもっと簡単に復号ができるようになっています。
もう一度上の単語用の符号表を見てみましょう。
この符号の長さは2bit、4bit、6bit、8bitと必ず偶数になっています。
これを前半と後半の二つに分け、足してみると・・・
単語(16進数) |
符号(2進数) |
前半bit+後半bit(答えは10進数) |
00 |
00 |
0+0=0 |
01 |
01 |
0+1=1 |
02 |
1000 |
10+00=2 |
03 |
1001 |
10+01=3 |
04 |
1010 |
10+10=4 |
05 |
1011 |
10+11=5 |
06 |
110000 |
110+000=6 |
07 |
110001 |
110+001=7 |
08 |
110010 |
110+010=8 |
09 |
110011 |
110+011=9 |
0A |
110100 |
110+100=10 |
0B |
110101 |
110+101=11 |
0C |
110110 |
110+110=12 |
0D |
110111 |
110+111=13 |
0E |
11100000 |
1110+0000=14 |
0F |
11100001 |
1110+0001=15 |
10 |
11100010 |
1110+0010=16 |
・・・ |
FD |
11111101111111 |
1111110+1111111=253 |
FE |
1111111000000000 |
11111110+00000000=254 |
FF |
1111111000000001 |
11111110+00000001=255 |
なんと符号表の順番を表す数字が出てきました。
というわけでこの符号表から符号を探さなくても、計算で単語がわかってしまうというわけです。
同じように距離や長さもこれで計算できます。
3. 復号方法
長かった。いやマジで長くなりました。
2を全部読んだ方、お疲れ様です。
これから実際の復号方法について述べていきます。
3.1 LS11のヘッダ
まずLS11のヘッダは、以下の構成になっています。
(三国志11のデータを参照してます。三国志9では違う・・・かも?)
アドレス範囲 |
バイト数 |
内容 |
00-03 |
4B |
LS11 |
04-0F |
12B |
0 |
10-10F |
256B |
辞書 |
110-113 |
4B |
圧縮後のデータサイズ(Big endian) |
114-117 |
4B |
圧縮前のデータサイズ(Big endian) |
118-11B |
4B |
圧縮データの開始アドレス(Big endian) |
11C-11F |
4B |
0 |
以降は圧縮データです
3.2 復号
復号はデータの最後になるまで、以下の手順で行います。
- 0が出るまでbitを読む。(0までを前半bitとする)
- 0までのbit数と同じbit数読む(これを後半bitとする)
- 前半bitと後半bitを足す
- 足した数値が255以下だった場合、これは1Byteを表すので、ヘッダの辞書を使って1Byteを出力して①に戻る
- 足した数値が256以上だった場合、これはLZ77の距離、長さペアの距離を表す。
- 足した数値から256引いた数が距離である。
- 長さを得るため、①から③を実行する
- 足した数値+3が長さである。
- 復号したByte列の距離byte前から、長さbyte分のByte列を出力して①に戻る
文字で書いてもわかりにくいので、実際に復号してみましょう。
例として、以下のようなデータがあったとします。
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A |
B |
C |
D |
E |
F |
内容 |
00 |
4C |
53 |
31 |
31 |
00 |
00 |
00 |
00 |
00 |
00 |
00 |
00 |
00 |
00 |
00 |
00 |
LS11 |
10 |
81 |
DE |
C9 |
91 |
96 |
8E |
8C |
41 |
90 |
42 |
97 |
8F |
30 |
C6 |
A6 |
95 |
辞書 |
20 |
C0 |
94 |
C4 |
05 |
B6 |
93 |
02 |
C3 |
BC |
8D |
8B |
D9 |
78 |
92 |
1B |
0A |
30 |
8A |
89 |
48 |
CA |
BD |
DA |
32 |
B2 |
88 |
AF |
BA |
82 |
C5 |
B7 |
31 |
D7 |
40 |
AB |
F0 |
76 |
00 |
1C |
BB |
E3 |
B3 |
4B |
5D |
CD |
5B |
CF |
E0 |
D8 |
E5 |
50 |
75 |
52 |
BE |
73 |
DD |
ED |
D2 |
80 |
7A |
98 |
49 |
B9 |
B8 |
69 |
AE |
D3 |
60 |
A4 |
BF |
D6 |
E9 |
45 |
6E |
6A |
B4 |
EA |
20 |
86 |
C2 |
B0 |
A9 |
D4 |
C1 |
70 |
33 |
E6 |
D0 |
B1 |
4E |
55 |
EC |
F5 |
A3 |
39 |
AD |
6C |
43 |
E8 |
A2 |
CE |
80 |
70 |
6F |
71 |
DB |
6B |
9E |
DF |
40 |
68 |
5A |
AC |
CB |
FC |
63 |
9A |
9D |
90 |
9C |
87 |
A8 |
9F |
EF |
79 |
F2 |
4F |
F6 |
FB |
53 |
E7 |
AA |
5C |
CC |
77 |
A0 |
DC |
7B |
06 |
7E |
51 |
64 |
9B |
5F |
6D |
A0 |
F3 |
46 |
61 |
A7 |
A1 |
F1 |
B0 |
E2 |
74 |
60 |
4C |
44 |
56 |
50 |
C7 |
F4 |
57 |
62 |
35 |
B5 |
E4 |
07 |
C8 |
C0 |
FA |
34 |
83 |
67 |
D1 |
99 |
47 |
4A |
65 |
84 |
38 |
EE |
36 |
59 |
7D |
5E |
D0 |
85 |
E1 |
37 |
72 |
F7 |
58 |
4D |
D5 |
7C |
F8 |
54 |
66 |
03 |
01 |
1D |
04 |
E0 |
A5 |
EB |
F9 |
2E |
2B |
0B |
2D |
08 |
FE |
2F |
0D |
3B |
0C |
FF |
29 |
3C |
F0 |
09 |
10 |
2C |
3F |
3E |
26 |
27 |
3D |
3A |
1F |
0E |
23 |
19 |
16 |
11 |
21 |
100 |
1E |
15 |
0F |
18 |
28 |
25 |
2A |
24 |
13 |
FD |
14 |
17 |
1A |
7F |
22 |
12 |
110 |
00 |
05 |
28 |
25 |
00 |
08 |
0B |
2D |
00 |
00 |
01 |
20 |
00 |
00 |
00 |
00 |
サイズ |
120 |
FD |
2B |
F6 |
2F |
C2 |
3F |
77 |
F5 |
7D |
5F |
CE |
7F |
68 |
F5 |
7D |
5F |
圧縮データ |
130 |
CB |
BF |
76 |
F5 |
7D |
5F |
A6 |
FD |
E3 |
D5 |
F5 |
7E |
EB |
F5 |
6F |
57 |
140 |
D5 |
F6 |
FF |
64 |
F5 |
7D |
5F |
83 |
FD |
63 |
D5 |
F5 |
7E |
C7 |
F5 |
5F |
150 |
57 |
D5 |
F9 |
0F |
D6 |
FD |
5F |
57 |
EF |
FD |
0F |
57 |
D5 |
F8 |
2F |
23 |
160 |
D5 |
F5 |
7F |
3C |
FA |
2F |
57 |
D5 |
FA |
2F |
CC |
FD |
5F |
57 |
F5 |
2F |
170 |
CB |
7D |
5F |
57 |
E4 |
FF |
3E |
F5 |
7D |
5F |
D3 |
BF |
3C |
F5 |
7D |
5F |
180 |
A8 |
FE |
06 |
3F |
13 |
FD |
AB |
D5 |
F5 |
7D |
3F |
D7 |
7D |
5F |
57 |
E7 |
・・・ |
10~10Fまでの範囲が辞書です。
120~が圧縮データです。これを復号します。
まずハフマン符号化されているデータを復号するため、Bit列に直します。
FD |
2B |
F6 |
2F |
C2 |
3F |
1111 1101 |
0010 1011 |
1111 0110 |
0010 1111 |
1100 0010 |
0011 1111 |
0が出るまで(1が続く限り)bitを読み進めていきます。
1111110と7bit(前半bit)まで読み進めました。
次に、読んだbit数と同じ数の7bit(後半bit)を更に読み取ります。
1001010と7bit読み取りました。
FD |
2B |
F6 |
2F |
C2 |
3F |
1111 1101 |
0010 1011 |
1111 0110 |
0010 1111 |
1100 0010 |
0011 1111 |
そしてこの前半bitと後半bitを足します。
1111110+1001010=11001000=C8(16進数)
これはFF以下なので、辞書を使って1Byte復号します。
ヘッダにある辞書のC8番目(アドレスはD8)のByteが7Cなので、7Cを出力します。
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A |
B |
C |
D |
E |
F |
D0 |
85 |
E1 |
37 |
72 |
F7 |
58 |
4D |
D5 |
7C |
F8 |
54 |
66 |
03 |
01 |
1D |
04 |
また0が出るまでbitを読み進めていきます。
1111110と7bit(前半bit)まで読み進めました。
次に、読んだbit数と同じ数の7bit(後半bit)を更に読み取ります。
1100010と7bit読み取りました。
FD |
2B |
F6 |
2F |
C2 |
3F |
1111 1101 |
0010 1011 |
1111 0110 |
0010 1111 |
1100 0010 |
0011 1111 |
そしてこの前半bitと後半bitを足します。
1111110+1100010=11100000=E0(16進数)
これはFF以下なので、辞書を使って1Byte復号します。
ヘッダにある辞書のE0番目(アドレスはF0)のByteが09なので、09を出力します。
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A |
B |
C |
D |
E |
F |
F0 |
09 |
10 |
2C |
3F |
3E |
26 |
27 |
3D |
3A |
1F |
0E |
23 |
19 |
16 |
11 |
21 |
また0が出るまでbitを読み進めていきます。
1111110と7bit(前半bit)まで読み進めました。
次に、読んだbit数と同じ数の7bit(後半bit)を更に読み取ります。
0001000と7bit読み取りました。
FD |
2B |
F6 |
2F |
C2 |
3F |
1111 1101 |
0010 1011 |
1111 0110 |
0010 1111 |
1100 0010 |
0011 1111 |
そしてこの前半bitと後半bitを足します。
1111110+0001000=10000110=86(16進数)
これは255以下なので、辞書を使って1Byte復号します。
ヘッダにある辞書の86番目(アドレスは96)のByteがF2なので、F2を出力します。
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A |
B |
C |
D |
E |
F |
90 |
9C |
87 |
A8 |
9F |
EF |
79 |
F2 |
4F |
F6 |
FB |
53 |
E7 |
AA |
5C |
CC |
77 |
しばらくは1Byte復号が続きます。(割愛)
出力Byte |
7C 09 F2 25 00 00 4A 27 ・・・ BF 36 00 00 03 38 00 00 EC |
FE |
06 |
3F |
13 |
FC |
1111 1110 |
0000 0110 |
0011 1111 |
0001 0011 |
1111 1100 |
0が出るまでbitを読み進めていきます。
11111110と8bit(前半bit)まで読み進めました。
次に、読んだbit数と同じ数の8bit(後半bit)を更に読み取ります。
00000110と8bit読み取りました。
FE |
06 |
3F |
13 |
FC |
1111 1110 |
0000 0110 |
0011 1111 |
0001 0011 |
1111 1100 |
そしてこの前半bitと後半bitを足します。
1111110+0010011=100010001=104(16進数)
ようやく100(16進数)以上の値がでてきました。
この値から100を引いた値、104-100=4が距離となります。
次に長さを得るためにもう一度0が出るまでbitを読み進めます。
すぐ0がでてきましたね。
0と1bit(前半bit)読み進めました。
読んだbit数と同じ数の1bit(後半bit)を更に読み取ります。
0の1bit読み取りました。
FE |
06 |
3F |
13 |
FC |
1111 1110 |
0000 0110 |
0011 1111 |
0001 0011 |
1111 1100 |
そしてこの前半bitと後半bitを足し、更に3を足します。
0+0+3=3 これが長さです。
距離4、長さ3ということなので、今まで出力したByteの4Byte前から3Byte出力します。
出力Byte |
7C 09 F2 25 00 00 4A 27 ・・・ BF 36 00 00 03 38 00 00 EC 38 00 00 |
また、こんな場合もあるので注意しましょう。
出力Byte |
7C 09 F2 25 00 00 4A 27 ・・・ BF 36 00 00 03 38 00 00 EC 38 00 00 ・・・ C3 DE C0 CB |
FE |
05 |
7F |
2F |
F2 |
BF |
1111 1110 |
0000 0101 |
0111 1111 |
0010 1111 |
1111 0010 |
1011 1111 |
0が出るまでbitを読み進めていきます。
11111110と8bit(前半bit)まで読み進めました。
次に、読んだbit数と同じ数の8bit(後半bit)を更に読み取ります。
00000101と8bit読み取りました。
FE |
05 |
7F |
2F |
F2 |
BF |
1111 1110 |
0000 0101 |
0111 1111 |
0010 1111 |
1111 0010 |
1011 1111 |
そしてこの前半bitと後半bitを足します。
11111110+=100000011=103(16進数)
100より大きいので、この値から100を引いた値、103-100=3が距離となります。
次に長さを得るためにもう一度0が出るまでbitを読み進めます。
0と1bit(前半bit)読み進めました。
読んだbit数と同じ数の1bit(後半bit)を更に読み取ります。
1の1bit読み取りました。
FE |
05 |
7F |
2F |
F2 |
BF |
1111 1110 |
0000 0101 |
0111 1111 |
0010 1111 |
1111 0010 |
1011 1111 |
そしてこの前半bitと後半bitを足し、更に3を足します。
0+1+3=4 これが長さです。
{距離3、長さ4ということなので、今まで出力したByteの3Byte前から4Byte出力します。
長さが距離より大きい場合でも、基本は同じです。
3Byte前から3Byte出力したあと、3Byte前から1Byte出力、と分けて考えてもいいかもしれません。
出力Byte |
7C 09 F2 25 00 00 4A 27 ・・・ BF 36 00 00 03 38 00 00 EC 38 00 00 ・・・ C3 DE C0 CB DE C0 CB DE |
これをデータの最後まで繰り返すことで、復号できます。
出力Byteが復号されたデータです。
最終更新:2009年07月05日 19:22