EPWING の圧縮形式について
笠原 基之
(m-kasahr@sra.co.jp)
2001年 1月 5日
本書は、EPWING V4 から採用された圧縮形式について、現時点で分かっている ことを記したものである。 一応、本書の解釈に従って実装したプログラムを用いて、広辞苑第 5 版 (ISBN4-00-130072-9) の伸長ができていることは確認している。 (追記: 後に EPWING V6 で圧縮形式が若干変更された。本書に書かれた方法で は EPWING V6 の圧縮データは伸長できない。)
この圧縮辞書への対応は、川幡太一さん、今井あさとさんから情報提供がなけ れば不可能だった。 お二人には深く感謝する。
なお、特に断らない限り、データ中のバイト列を整数とみなす際は、ビッグエ ンディアン (Most Significant Byte が先頭バイトに来る形式) で表すものと する。
圧縮が使用されていない EPWING の書籍では、本文データが HONMON というファ イルに収められていたが、圧縮が使用されている書籍では代わりに HONMON2 というファイルに収められている。
HONMON2 ファイルは次のように、圧縮ヘッダ、圧縮インデックス、頻度テーブ ル、圧縮された本文の 4 つの部分から構成されている。
圧縮ヘッダには 32 バイトからなり、各パートの開始位置および長さなどが記 録してある。
| 圧縮インデックスの開始位置 | 4バイト |
| 圧縮インデックスの長さ | 4バイト |
| 頻度テーブルの開始位置 | 4バイト |
| 頻度テーブルの長さ | 4バイト |
| 本文の開始位置 | 4バイト |
| 予備領域? | 4バイト (00000000H) |
| 書籍管理情報の開始位置? | 4バイト (本文の開始位置に同じ) |
| 不明 | 4バイト (ffffedffH) |
圧縮インデックスには、各ブロックの開始位置を記録してある。 (ここで言う「ブロック」は JIS X 4081 のブロックのこと。1 ブロック は 2048バイト。)
第 1 ブロックから順に開始位置が記録してあるが、記録の仕方が若干複雑で、 ブロックを 16 個一組にして、インデックスを記録している。 ブロック一組分のインデックスは 36 バイトからなり、次のような構成になっ ている。
そのブロック一組の基底位置 (4 バイト)
1 番目のブロックの開始オフセット (2 バイト、必ず 0000H)
2 番目のブロックの開始オフセット (2 バイト)
: (略)
16 番目のブロックの開始オフセット (2 バイト)
各ブロックの開始位置は、(基底位置 + 開始オフセット) になる。 たとえば、ブロック一組のインデックス 36 バイトが次のようになっていたと する。
00 03 c2 a0 00 00 02 42 07 75 0c b9 12 11 17 5e
1c bb 22 1a 27 70 2c b7 32 2d 37 82 3c ad 41 d8
47 15 4c 49
各ブロックの実際の開始位置は次のようになる。
1 番目のブロックの開始位置: 0003c2a0H + 0000H = 0003c2a0H
2 番目のブロックの開始位置: 0003c2a0H + 0242H = 0003c4e2H
: (略)
16 番目のブロックの開始位置: 0003c2a0H + 4c49H = 00040ee9H
なお、最後のブロック一組のインデックスは、次のように途中から 0000H に なってしまっていることがある。 これは、ブロックの総数が 16 で割りきれず、対応するブロックがないため である。
08 e3 78 cb 00 00 05 5f 0b 0f 11 17 17 31 1c ee
21 ae 27 22 2d 5c 32 f6 35 cf 00 00 00 00 00 00
00 00 00 00
頻度テーブルは、次のような構成になっている。
| 2 バイト文字のテーブル | 頻度テーブルの長さ - 512 バイト |
| 1 バイト文字のテーブル | 512 バイト |
頻度テーブルの長さは圧縮ヘッダ部に書かれており、1 バイトテーブルは 512 バイト固定である。 したがって、2 バイト文字のテーブルは頻度テーブル全体の長さから 512 を 引いたバイト数になる。 このテーブルは、静的ハフマン符号用のハフマン木の生成に使用される。
2 バイト文字のうち、頻度の高い文字について、降順に文字と頻度を並べてあ る。 頻度の単位はよく分からないが、必ず奇数である。 このテーブルは次の 4 バイトからなる組を (頻度テーブルの長さ - 512) / 4回繰り返した構成になっている。
| 文字番号 (2 バイト) |
| 頻度 (2 バイト) |
たとえば、テーブルの最初の 32 バイトが次のようになっているとする。
00 00 fa cf 00 04 1d ff 24 26 16 dd 24 73 13 c1
24 24 13 91 00 02 13 6b 00 06 10 e1 00 08 10 cf
文字番号と頻度は次の通りになる。
| 文字番号 | 頻度 |
| 0000 | facfH |
| 0004 | 1dffH |
| 2426 (く) | 16ddH |
| 2473 (ん) | 13c1H |
| 2424 (い) | 1391H |
| 0002 | 146bH |
| 0006 | 10e1H |
| 0008 | 10cfH |
1 バイト文字 00H〜 ffH の頻度が文字番号順で記されている。2 バイト文字 のテーブルと同様に頻度の単位はよく分からないが、やはり必ず奇数であり、 頻度は 2 バイトで表される。
たとえば、テーブルの最初の 32 バイトが次のようになっているとする。
19 e1 11 cd 10 8f 11 0b 13 77 13 8d 10 c7 0f 6f
06 27 04 4f 04 ef 03 8f 04 a1 03 a9 05 45 05 55
文字番号と頻度は次の通りになる。
| 文字番号 | 頻度 |
| 00 | 19e1H |
| 01 | 11cdH |
| 02 | 108fH |
| 03 | 110bH |
| 04 | 1377H |
ブロック毎に独立して、静的ハフマン符号で圧縮されている。 必ずブロックの末尾には「ブロック終端文字」が付加されている。
EPWING で採用されている圧縮形式は、静的ハフマン符号である。 本文の伸長を行うには、頻度テーブルのデータから、圧縮時に使用したハフマ ン木を復元する必要がある。 以下にハフマン木の復元方法を記す。
以上でハフマン木が完成する。
前節の、静的ハフマン木の作り方の説明の途中で、ノードを並べた配列をソー トする必要があることを述べたが、この節ではソートの仕方の詳細について説 明する。
ノードを並べた配列は 2 バイト文字のノード、1 バイト文字のノード、ブロッ ク終端文字のノードの順で並んでいるが、配列全体を頻度の高い順にソートす る。
ソートは必ず、後ろに示したものと完全に等価な実装を用いなければならない。 この実装では、同じ頻度を持った複数のノードの順序がソートする前後で入れ 替わるのだが、この入れ替わり具合いを完全に再現できないと、正しく復号で きない。
具体的にソートプログラムの骨格部分を示す。 アルゴリズムは、一般に選択ソート (selection sort) と呼ばれるものであ る。
とそれぞれ表すと、ソートは次のように行う。 (ISO C 風の記述。C 言語を知っていれば、とくに表記に関する説明は必要 ないと思われる。)
for (i = 0; i < node_num - 1; i = i + 1) {
most = i;
for (j = i; j < node_num; j = j + 1) {
if (node[j].frequency > node[most].frequency) {
most = j;
}
}
tmp_node = node[i];
node[i] = node[most];
node[most] = tmp_node;
}
生成した静的ハフマン木を用いて伸長を行う際は、左側の子ノードへの枝をビッ ト `1' に、右側のノードへの枝をビット `0' に対応させる。 たとえば、根から左→右→右と降りたところにある葉ノードの符号は `100' になる。
圧縮データは、バイト列の先頭から各バイトを MSB (Most Significant Bit) → LSB (Least Significant Bit) の方向で読んでいく。 また、各ブロックの終わりには、必ずブロック終端文字が付加される。
なお、各ブロックは 2048 バイトからなるが、圧縮データ自体は 2049 バイト から構成されていることもあるようだ。 先頭のバイトを第 0 バイトとすると、2047 バイト目には (もう残り 1 バイ ト分しか余白がないので) 1 バイト文字しか置けない筈だが、2 バイト文字 の符号が出現することがある。 どうやら、その次のブロックの先頭のバイトと合わせて 2 バイト分を符号化 してしまっているためのようである。
したがってこの場合は、2 バイト分のうちの最初の 1 バイトだけ復号するこ とになる。