_
注意!
ここからの解説内容はできるだけわかりやすく説明するため、かなり私見を入れています。
厳密に言うと間違っている説明が含まれているかもしれませんが、ご容赦ください。

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から始めます)
  1. 先頭にx個のbit'1'を並べる
  2. その後ろにbit'0'を一つだけ置く
  3. ①と②で置いたbit数と同じ数の'0'を後ろに置く
  4. これを接頭符号として使う
  5. ④に1を足す
  6. これを接頭符号として使う
  7. 最大値になるまで⑤と⑥を繰り返す(①と②で置いたbitはそのまま)
  8. 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 復号

復号はデータの最後になるまで、以下の手順で行います。

  1. 0が出るまでbitを読む。(0までを前半bitとする)
  2. 0までのbit数と同じbit数読む(これを後半bitとする)
  3. 前半bitと後半bitを足す
  4. 足した数値が255以下だった場合、これは1Byteを表すので、ヘッダの辞書を使って1Byteを出力して①に戻る
  5. 足した数値が256以上だった場合、これはLZ77の距離、長さペアの距離を表す。
  6. 足した数値から256引いた数が距離である。
  7. 長さを得るため、①から③を実行する
  8. 足した数値+3が長さである。
  9. 復号した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

出力Byte 7C

また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

出力Byte 7C 09

また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

出力Byte 7C 09 F2

しばらくは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