X 6136 : 1999 (ISO/IEC 15200 : 1996)
(1)
まえがき
この規格は，工業標準化法に基づいて，日本工業標準調査会の審議を経て，通商産業大臣が制定した日
本工業規格である。
この規格の一部が，技術的性質をもつ特許権，出願公開後の特許出願，実用新案権，又は出願公開後の
実用新案登録出願に抵触する可能性があることに注意を喚起する。通商産業大臣及び日本工業標準調査会
は，このような技術的性質をもつ特許権，出願公開後の特許出願，実用新案権，又は出願公開後の実用新
案登録出願にかかわる確認について，責任はもたない。
JIS X 6136
には，次に示す附属書がある。
附属書 A（参考） ALDC 符号化様式
附属書 B（参考） ALDC 概要
附属書 C（参考） ALDC 符号化法流れ図
附属書 D（参考） 参考文献
X 6136 : 1999 (ISO/IEC 15200 : 1996)
(1)
目次
ページ
序文
0
1.
適用範囲
0
2.
適合性
0
3.
引用規格
0
4.
定義
0
4.1
圧縮データ列 (Compressed Data Stream)
0
4.2
コピーポインタ (Copy Pointer) 2
4.3
カレントアドレス (Current Address)
2
4.4
データバイト (Data Byte)
2
4.5
変位領域 (Displacement Field)
2
4.6
終了マーカ (End Marker)
2
4.7
履歴バッファ (History Buffer)
2
4.8
生データ (Literal)
2
4.9
一致文字列 (Matching String)
2
4.10
一致数 (Match Count)
2
4.11
一致数領域 (Match Count Field)
2
4.12
パッドビット (Pad Bits)
2
5.
表記法
2
5.1
数字の表し方
2
5.2
名称
2
6.
ALDC 圧縮アルゴリズム
2
6.1
512−バイト履歴バッファに対する符号化記述
2
6.2
圧縮データ列の概要
3
附属書 A（参考） ALDC 符号化様式
5
附属書 B（参考） ALDC 概要
7
附属書 C（参考） ALDC 符号化法流れ図
8
附属書 D（参考） 参考文献
12
日本工業規格
JIS
X
6136
: 1999
(ISO/IEC 15200 :
1996
)
情報交換用データ圧縮−
適合化無損失アルゴリズム
(ALDC)
Information technology
−Adaptive Lossless Data Compression algorithm
(ALDC)
序文 この規格は，1996 年に第 1 版として発行された ISO/IEC 15200，Information technology−Adaptive
Lossless Data Compression algorithm (ALDC)
を翻訳し，技術的内容及び規格票の様式を変更することなく作
成した日本工業規格である。
1.
適用範囲 この規格は，データを表現するビット数を削減する無損失データ圧縮について規定する。
このアルゴリズムは，適合化無損失データ圧縮アルゴリズム (ALDC) として知られている。このアルゴリ
ズムの ISO/IEC 11576 による識別番号は，次のとおりとする。
ALDC 512
−バイト履歴バッファ
：3
ALDC 1
024
−バイト履歴バッファ
：4
ALDC 2
048
−バイト履歴バッファ
：5
備考 この規格の対応国際規格を次に示す。
ISO/IEC 15200 : 1996
Information technology−Adaptive Lossless Data Compression algorithm
(ALDC)
2.
適合性 圧縮アルゴリズムは，出力データ列がこの規格の要求を満たすとき，この規格に適合する。
3.
引用規格 次に掲げる規格は，この規格に引用されることによって，この規格の規定の一部を構成す
る。この引用規格は，その最新版を適用する。
ISO/IEC 11576 : 1996
Information technology−Procedure for the registration of algorithms for the lossless
compression of data
4.
定義 この規格で用いる主な用語の定義は，次による。
4.1
圧縮データ列 (Compressed Data Stream) 圧縮後の出力データ列。
2
X 6136 : 1999 (ISO/IEC 15200 : 1996)
4.2
コピーポインタ (Copy Pointer) 圧縮データ列の一部。履歴バッファに同一グループが存在するこ
とを示す二つ以上の連続するバイトのグループを表し，レングスコード領域と変位領域からなる。
4.3
カレントアドレス (Current Address) データバイトを書き込む履歴バッファの位置。
4.4
データバイト (Data Byte) 履歴バッファに以前に記録したすべてのデータと比較し，履歴バッフ
ァに記録する入力データの現在のバイト。
4.5
変位領域 (Displacement Field) 履歴バッファ内の一致データ列の最初のバイトの位置を示すコピ
ーポインタの一部。
4.6
終了マーカ (End Marker) 圧縮データ列の終了を示す 12 個の“1”の連続列。
4.7
履歴バッファ (History Buffer) データの圧縮及び復元に使用する入力データを貯える段階構造。
4.8
生データ (Literal) 履歴バッファ内に一致するバイトが存在しないデータバイト。
4.9
一致文字列 (Matching String) 履歴バッファ内の連続するバイトと一致する入力データの連続す
るバイト。
4.10
一致数 (Match Count) 一致文字列のバイト数
4.11
一致数領域 (Match Count Field) 履歴バッファ内で一致した連続するバイトの数を示すコピーポ
インタの一部。
4.12
パッドビット (Pad Bits) 8 ビットバイトを構成するために，必要に応じて圧縮データ列に挿入す
る“0”のビット。
5.
表記法
5.1
数字の表し方 数字の表し方は，特に指定のない限り，次による。
− ビットの設定は，
“0”又は“1”で表す。
− 2 進数表記の数字及びビットの組合せは，
“0”及び“1”の列で表し，最上位ビットを左とする。
− その他の数字は，10 進数とする。
5.2
名称 エンティティの名称は，規定しない。
6.
ALDC
圧縮アルゴリズム ALDC 符号化手順の概要は，附属書 B とし，流れ図は，附属書 C による。
6.1
512
−バイト履歴バッファに対する符号化記述 符号化を開始するとき，履歴バッファ内のすべての
バイトを“0”に設定する。符号化が開始されるとデータバイトを，カレントアドレス 0 から履歴バッファ
に順次格納する。
符号器は，入力データを 1 バイトごとに処理し，処理中の現在のバイトを，データバイトとして参照す
る。符号器はデータバイトを，入力データ列から受け取り，履歴バッファのカレントアドレスに書き込み，
カレントアドレスを 1 増加する。
カレントアドレスが 512 バイトの履歴バッファの最大アドレスである 511
を超えたとき，カレントアドレスを“0”に設定する。
ステップ 1 符号器は，一致するバイトを見つけるため，履歴バッファ内に既に書き込んだ各バイト
とデータバイトを比較する。
ステップ 2 データバイトが履歴バッファ内に既に書き込んだバイトと一致しないとき，処理はステ
ップ 6 に進む。
− データバイトが履歴バッファ内の 1 バイト以上のバイトと一致するとき，すべての
一致バイトについて，それ以前の一致バイト列からの連続であるか否かを注視する。
− 連続でないとき，一致バイトの変位領域の値と 1 バイトの一致数があったことを記
3
X 6136 : 1999 (ISO/IEC 15200 : 1996)
録する。
− 一致バイトが以前の文字列の連続であるとき，その列の一致数を 1 だけ増加する。
ステップ 3 一致数が 271 に達したとき，対応しているバイト列をコピーポインタで識別し，コピー
ポインタを圧縮データ列に追加する。一致数領域と変位領域の記述方法は，6.2 による。
次のデータバイトを読み取り，その処理は
ステップ 1 へ戻る。読み取るデータがないと
き，処理は
ステップ 7 に進む。
参考 271 の値は，実装上の理由によって選択している。
ステップ 4 一致数が 271 に達しないとき，保留の一致文字列に継続するデータバイトがあるか否か
を検査する。
− 以前のどの一致文字列にも連続せず，かつ，2 バイト以上で構成する一致文字列が
あるとき，最小値をもつ変位領域の一致文字列をコピーポインタによって識別し，
コピーポインタを圧縮データ列に追加する。次のデータバイトを読み取る。読み取
るデータがないとき，
ステップ 7 に進む。
− 以前の一致文字に連続せず，かつ，一致が 1 バイトだけのとき，それ以前の 1 バイ
トの一致を生データとして 6.2 によって圧縮データ列に追加する。次のデータバイ
トを読み取る。読み取るデータがないとき，処理は
ステップ 7 に進む。
ステップ 5 一致数が 271 に達する一致文字列がなく，かつ，以前の一致文字列との連続が少なくと
も一つあるとき，次のデータバイトを読み取る。処理は，
ステップ 1 に戻る。
読み取るデータがないとき，その時点で保留の文字列はコピーポインタで識別し，圧縮
データ列に追加する。処理は，
ステップ 7 に進む。
ステップ 6 データバイトが履歴バッファ内のいずれのバイトとも一致しないとき，それ以前の保留
文字列に対して検査を行う。
2
バイト以上，以前に一致文字列があるとき，それらをコピーポインタで識別し，圧縮
データ列に追加する。一致しないデータバイトは，生データとして圧縮データ列に追加
する。次のデータを読み取り，処理は
ステップ 1 に戻る。
読み取るデータがないとき，処理は
ステップ 7 に進む。
2
バイト以上の一致文字列で保留がなく，かつ，1 バイト一致の保留があるとき，データ
バイトに先立つバイトは，生データとして圧縮データ列に追加する。一致を検出できな
かったデータバイトは，生データとして圧縮データ列へ追加する。次のデータバイトを
読み取り，処理は
ステップ 1 に戻る。
読み取るデータがないとき，処理は
ステップ 7 に進む。
ステップ 7 終了マーカを圧縮データ列に追加し，必要によってパッドビットを追加する。
この処理によって符号化処理を終了する。
6.2
圧縮データ列の概要 6.1 の入力データの処理によって，圧縮データ列を出力する。圧縮データ列の
構成は，次による。
− “0”のビットを前置きした生データ
− “1”のビットを前置きしたコピーポインタ
− “1”のビットを前置きした終了マーカ
− パッドビット
すべてのデータを読み取ったとき，圧縮したデータ列は，
“1”のビットを設定し，終了しなければなら
4
X 6136 : 1999 (ISO/IEC 15200 : 1996)
ない。その列は終了マーカ及び必要によってパッドビットが続く。
符号化の間に，同じ一致数の一致データ列を一つ以上検出した場合，最下位の変位領域をもったコピー
ポインタを使用しなければならない。一致数領域は，2 ビット，4 ビット，6 ビット，8 ビット又は 12 ビッ
トとし，
表 1 で規定する。512 バイト，1 024 バイト又は 2 048 バイトの履歴バッファに対し，変位領域の
長さは，それぞれ 9 ビット，10 ビット又は 11 ビットとする。
表 1 一致数領域
一致数領域の設定
バイトの数
00 2
01 3
10 00
4
: :
: :
10 11
7
110 000
8
: :
: :
110 111
15
1110 0000
16
: :
: :
1110 1111
31
1111 0000 0000
32
: :
: :
1111 1110 1110
270
1111 1110 1111
271
5
X 6136 : 1999 (ISO/IEC 15200 : 1996)
附属書 A（参考） ALDC 符号化様式
この附属書（参考）は，本体に関連する事柄を補足するもので，規定の一部ではない。
A.1
命名法 圧縮データの符号化様式は，BNF 記法（バッカスナウア記法）で記述する。
記号の定義は，次による。
記 号
定 義
：＝
この記号の左側の非終端変数は，右側の表現で置き換えることができる。
<
>
非終端変数
[
]
括弧内の表現は，0 回又はそれ以上の回数出現する。
｜
論理的分離 OR
(
)
説明文
0, 1
終端 2 進数“0”又は“1”
A.2 ALDC
＿1 アルゴリズム−符号化様式（512−バイト履歴バッファ）
＜圧縮データ＞：＝0＜生データ＞［0＜生データ＞｜1＜コピーポインタ＞］｜＜終了マーカ＞＜パッ
ド＞
＜生データ＞：＝<b><b><b><b><b><b><b><b>（8 ビットバイトデータ）
＜b＞：＝0｜1
＜コピーポインタ＞：＝<一致数領域><変位領域>
＜一致数領域＞：＝（2，4，6，8 又は 12 ビット）
一致数領域の設定
バイト中の一致数
00 2
01 3
10 00
4
：
：
：
：
10 11
7
110 000
8
：
：
：
：
110 111
15
1110 0000
16
：
：
：
：
1110 1111
31
1111 0000 0000
32
：
：
：
：
1111 1110 1110
270
1111 1110 1111
271
＜変位領域＞：＝<b><b><b><b><b><b><b><b><b>（9 ビット）
＜パッド＞：＝8 ビットの境界を維持するために必要な“0”に設定するビット数
＜終了マーカ＞：＝1111 1111 1111
6
X 6136 : 1999 (ISO/IEC 15200 : 1996)
A.3 ALDC
＿2 アルゴリズム−符号化様式（1 024−バイト履歴バッファ）
（変位領域が 10 ビットであることを除いて ALDC＿1 の定義と同一）
〈変位領域〉
：＝<b><b><b><b><b><b><b><b><b><b>（10 ビット）
A.4 ALDC
＿4 アルゴリズム−符号化様式（2 048−バイト履歴バッファ）
（変位領域が 11 ビットであることを除いて ALDC＿1 の定義と同一）
〈変位領域〉
：＝<b><b><b><b><b><b><b><b><b><b><b>（11 ビット）
7
X 6136 : 1999 (ISO/IEC 15200 : 1996)
附属書 B（参考） ALDC 概要
この附属書（参考）は，本体に関連する事柄を補足するもので，規定の一部ではない。
ALDC
アルゴリズムは，8 ビットデータバイトの入力を受け，圧縮形式でデータを表現するビット列を
出力する。ALDC アルゴリズムは，データ圧縮アルゴリズム Lempel−Ziv1 (LZ1) の一つの手法である。
LZ1
アルゴリズムは，データを貯える段階構造をもつ履歴バッファを使用して圧縮を行う。履歴バッフ
ァは，入力データの格納及び入力データと同一履歴バッファ内の以前のすべてのデータとの比較を行う。
LZ1
の符号化過程と復元化過程では，このデータ構造を同一の既知状態に初期化し，同一方法で更新する。
その結果，二つの履歴が同一になり，圧縮データ列に履歴情報を含む必要がない。
入力データは，履歴バッファに入る。履歴バッファ内に以前に格納した他のすべてのバイトと各々の入
力バイトを比較する。以前の一致文字列の続きの一致を見つけることによって，圧縮を行う。符号化過程
の最初に履歴バッファは，空になる。履歴バッファ内でいずれの一致も見つけられない場合，圧縮データ
列は，生データだけとする。バイトは，2 バイト以上の一致がおきるまで，生データとして符号化する。
履歴バッファにデータが蓄積すると，入力データを履歴バッファに存在するデータ列のコピーポインタと
して符号化表現する可能性が増加する。これが，LZ1 アルゴリズムでデータを圧縮する原理となる。
8
X 6136 : 1999 (ISO/IEC 15200 : 1996)
附属書 C（参考） ALDC 符号化法流れ図
この附属書（参考）は，本体に関連する事柄を補足するもので，規定の一部ではない。
9
X 6136 : 1999 (ISO/IEC 15200 : 1996)
10
X 6136 : 1999 (ISO/IEC 15200 : 1996)
11
X 6136 : 1999 (ISO/IEC 15200 : 1996)
12
X 6136 : 1999 (ISO/IEC 15200 : 1996)
附属書 D（参考） 参考文献
この附属書（参考）は，本体に関連する参考文献を記載するもので，規定の一部ではない。
J. Ziv and A. Lempel,
“A universal algorithm for sequential data compression”, IEEE Trans. Inform. Theory,
vol. IT-23, no.3, pp.337-343, 1997.
磁気テープ JIS 原案作成委員会 構成表
氏名
所属
（委員長）
大 石 完 一
パルステック工業株式会社
（幹事）
富 田 正 典
日本システムインテグレーション株式会社
（幹事）
徳 永 賢 次
イメーション株式会社
平 川 卓
富士写真フイルム株式会社
村 上 恒 夫
日本システムハウス株式会社
荒 木 学
日本ユニシス株式会社
樋 口 重 光
株式会社日立製作所
安 藤 晴 夫
日立マクセル株式会社
竹 内 正
株式会社トリム
船 越 正 次 TDK 株式会社
金 子 悟
富士通株式会社
堀 川 憲 一
ソニー株式会社
藤 原 圭 介
ソニー株式会社
川 田 道 孝
日本電気株式会社
岸 野 忠 信
財団法人日本規格協会
永 松 荘 一
通商産業省機械情報産業局
兼 松 明 男
通商産業省工業技術院標準部
（オブザーバー）
橋 本 繁 晴
財団法人日本規格協会
（オブザーバー）
中 島 敏 明
財団法人日本電子部品信頼性センター
（事務局）
長谷川 久 子
社団法人日本電子工業振興協会