EPWING の圧縮形式について
笠原 基之
(m-kasahr@sra.co.jp)
2001年 1月 5日

本書は、EPWING V4 から採用された圧縮形式について、現時点で分かっている ことを記したものである。 一応、本書の解釈に従って実装したプログラムを用いて、広辞苑第 5 版 (ISBN4-00-130072-9) の伸長ができていることは確認している。 (追記: 後に EPWING V6 で圧縮形式が若干変更された。本書に書かれた方法で は EPWING V6 の圧縮データは伸長できない。)

この圧縮辞書への対応は、川幡太一さん、今井あさとさんから情報提供がなけ れば不可能だった。 お二人には深く感謝する。

なお、特に断らない限り、データ中のバイト列を整数とみなす際は、ビッグエ ンディアン (Most Significant Byte が先頭バイトに来る形式) で表すものと する。


HONMON2 ファイルの概要

圧縮が使用されていない EPWING の書籍では、本文データが HONMON というファ イルに収められていたが、圧縮が使用されている書籍では代わりに HONMON2 というファイルに収められている。

HONMON2 ファイルは次のように、圧縮ヘッダ、圧縮インデックス、頻度テーブ ル、圧縮された本文の 4 つの部分から構成されている。


圧縮ヘッダ (32バイト)

圧縮ヘッダには 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 バイト文字のテーブル (長さ不定)

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 バイト文字のテーブル (長さ 200H)

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 で採用されている圧縮形式は、静的ハフマン符号である。 本文の伸長を行うには、頻度テーブルのデータから、圧縮時に使用したハフマ ン木を復元する必要がある。 以下にハフマン木の復元方法を記す。

  1. 2 バイト文字の頻度テーブルを読み込む。 文字番号と頻度の組を 1 つのノードの中に情報として格納する。 そして、生成した各ノードを一次元配列のように、先頭から順に一列に並べて いく。
  2. 同様に、1 バイト文字 256 個についても、文字番号と頻度の組を 1 つの ノードの中に情報として格納する。 生成したノードは、2 バイト文字のノードを並べた配列の末尾に追加していく ように、やはり順に一列に並べていく。
  3. 頻度 1 のブロック終端文字 1 個に対して、ノードを一つ割り当てる。 これも同様に、2 バイト文字と 1 バイト文字のノードを並べた配列の末尾に 追加する。
  4. 現時点で、ノードを並べた配列は 2 バイト文字のノード、1 バイト文字 のノード、ブロック終端文字のノードの順で並んでいるが、配列全体をいった ん頻度の高い順にソートする。 ソートについての詳細は、次の節で説明する。 配列中の各ノードはハフマン木の葉になるが、この時点ではまだ親ノードは決 まっておらず、以降の操作で親ノードが決定していく。
  5. ノードの配列を順に走査し、頻度がもっとも低く、かつ親ノードがまだ決 まっていないノードを探す。 複数あったら、ノード番号がもっとも大きいものを選ぶ。 選んだノードを覚えておく。
  6. ノードの配列の先頭から順にノードを走査し、5. で選んだノードを除い た中で、頻度のもっとも低く、かつ親ノードがまだ決まっていないノードを探す。 複数あったら、ノード番号がもっとも大きいものを選ぶ。 選んだノードを覚えておく。
  7. 中間ノードもしくは根ノードを一つ作り、ノードの配列の末尾に追加する。 6. で選んだノードがこの中間 (あるいは根) ノードの左側の子に、7. で 選んだノードが右側の子になるように、枝を張る。 この操作により、6. と 7. で選んだノードには、親が決まったことになるが、 作成した中間ノード自身には親が決まっていない。
  8. 以下、根となるノードが決まるまで 5. 〜 7. を繰り返す。 7. で生成された中間ノードは、次の回から、それ自身が 4., 5. での走査の 対象となることに注意する。

以上でハフマン木が完成する。

ソート方法

前節の、静的ハフマン木の作り方の説明の途中で、ノードを並べた配列をソー トする必要があることを述べたが、この節ではソートの仕方の詳細について説 明する。

ノードを並べた配列は 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 バイトだけ復号するこ とになる。


Copyright 1999, 2000 Motoyuki Kasahara