X 6133 : 1997(ISO/IEC11558 : 1992)
(1)
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
まえがき
この規格は，工業標準化法に基づいて，日本工業標準調査会の審議を経て，通商産業大臣が制定した日
本工業規格である。
この規格の一部が，技術的性質をもつ特許権，出願公開後の特許出願，実用新案権，又は出願公開後の
実用新案登録出願に抵触する可能性があることに注意を喚起する。主務大臣及び日本工業標準調査会は，
このような技術的性質をもつ特許権，出願公開後の特許出願，実用新案権，又は出願公開後の実用新案登
録出願にかかわる確認について，責任はもたない。
JIS X 6133には，次に示す附属書がある。
附属書A（参考） 一般的なDCLZアルゴリズムの例
附属書B（参考） 与えられた入力列に対する符号値出力の例
附属書C（参考） 参考文献
1
X 6133 : 1997 (ISO/IEC 11558 : 1992)
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
目次
ページ
1. 適用範囲 ························································································································ 1
2. 適合性 ··························································································································· 1
3. 引用規格 ························································································································ 1
4. 用語の定義 ····················································································································· 1
4.1 符号 ···························································································································· 1
4.2 符号 ···························································································································· 2
4.3 圧縮比 ························································································································· 2
4.4 辞書 ···························································································································· 2
4.5 空状態 ························································································································· 2
4.6 凍結状態 ······················································································································ 2
5. 表記法 ··························································································································· 2
6. アルゴリズムの識別子 ······································································································ 2
7. DCLZ圧縮アルゴリズム ··································································································· 2
7.1 概要 ···························································································································· 2
7.2 動作原理 ······················································································································ 2
7.3 符号値 ························································································································· 3
7.4 符号語 ························································································································· 4
附属書A（参考） 一般的なDCLZアルゴリズムの例 ································································· 5
附属書B（参考） 与えられた入力列に対する符号値出力の例 ······················································ 8
附属書C（参考） 参考文献··································································································· 9
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
日本工業規格 JIS
X 6133 : 1997
(ISO/IEC 11558 : 1992)
情報交換用データ圧縮
埋め込み辞書での
適応符号化−DCLZアルゴリズム
Information technology−Data compression for
information interchange−Adaptive coding
with embedded dictionary−DCLZ algorithm
序文 この規格は，1992年初版として発行されたISO/IEC 11558 (Information technology-Data compression
for information interchange−Adaptive coding with embedded dictionary−DCLZ algorithm) を翻訳し，技術的内
容及び規格票の様式を変更することなく作成した日本工業規格である。
1. 適用範囲 この規格は，8ビット法による符号化情報の表現に必要なビット数を削減するロスレス圧
縮アルゴリズムについて規定する。このアルゴリズムは，DCLZ（LempelとZivによるデータ圧縮）と呼
称する。
この規格は，圧縮時に用いる辞書をリセットし，凍結する方法については規定しない。
このアルゴリズムは，情報交換媒体に記録するときに特に有効であるが，用途はこれに限定しない。
2. 適合性 圧縮アルゴリズムは，出力データ列がこの規格の7.のすべての要求を満たすとき，この規格
に適合する。
3. 引用規格 次の規格は，この規格がよりどころとしている規格を含んでいる。出版時に明示された版
号が有効であるが，すべての規格は改正されるので，この規格の関係者は，次の最新のものを調査し適用
するよう推奨する。
ISO/IEC 11576 : 1994 Information technology−Procedure for the registration of algorithms for the loseless
compression of data
4. 用語の定義 この規格で用いる用語の定義は，次による。
4.1
符号値 (Code Value) 圧縮アルゴリズムによって生成した0〜4095の整数。
4.2
符号語 (Codeword) 2進数で符号値を表現する連続する9，10，11又は12ビットの出力列。
4.3
圧縮比 (compression ratio) 圧縮アルゴリズムの入力列のビット数を圧縮アルゴリズムの出力列の
ビット数で除した数値。
2
X 6133 : 1997 (ISO/IEC 11558 : 1992)
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
4.4
辞書 (dictionary) 入力列から選択したバイト列の保持に使用する3 832個の登録から成る表。各登
録は，264以上で重複がない符号値で識別される。
4.5
空状態 (empty state) 辞書にデータがない状態。
4.6
凍結状態 (frozen state) 辞書にデータが追加できない状態。
5. 表記法 特に表記がない限りこの規格での表記法は，次による。
− 数値は，10進数で表す。
− EOR：レコードの終わり (end of record)
6. アルゴリズムの識別子 ここで規定するアルゴリズムの識別子は， “32” とする。
7. DCLZ圧縮アルゴリズム
7.1
概要 DCLZ圧縮アルゴリズムは，8ビットデータバイト列の形で入力情報を受け，8ビットバイト
に編集し，ビット列の形で符号語を出力する。アルゴリズムは，入力列の中で繰り返し現れるバイト列の
連続性を検出し，その冗長性を出力列から削除する。
情報処理システム及び情報処理装置が生成，伝送又は記録する情報は，データの繰返し頻度が高く，圧
縮処理によって出力列が入力列より少ないビット数になる。しかし出力列より長いビットで構成すること
もあり，圧縮比は実際の入力データ列の特性に依存する。
このアルゴリズムによる圧縮は，データに損失がなく，復元アルゴリズムによって元のデータを正確に
復元することができる。
このアルゴリズムは，種々の長さのデータレコードを逐次法で処理するデータ記憶再生装置に適用でき
る。
7.2
動作原理 基本的な動作原理は，入力列のバイト列に対して辞書を生成し，バイト列の繰り返しの
検出に辞書を使用し，それぞれの繰返し列に対して符号語を生成する。符号語は，繰返し列を辞書に登録
するときに参照する符号値で表す。
7.2.1
辞書の生成 辞書は，アルゴリズムの動作開始前に空状態にリセットする（7.3.1.2参照）。
アルゴリズムは入力列を検査し，最初の固有ペア又は固有列の出現を検索する。固有ペアとは辞書に登
録がない2バイトの列である。nバイト (n＞2) の固有列とは，辞書に登録のない列であり，かつ，最初の
n−1バイトは，辞書に登録済みであることを意味する。辞書に登録できる最大の列の長さは，128バイト
とする。
固有ペアを検出すると，アルゴリズムはペアの第1バイトの符号語を出力する。nバイトの固有列を見
つけると，アルゴリズムは最初のn−1バイトの列の符号値の符号語を出力する。
辞書が凍結状態になく（7.2.2参照），かつ，nが128を超えていない場合，固有ペア又は固有列を辞書に
登録し，使用していない次の符号値を割り当てる。
アルゴリズムは，現在の固有ペアの2番目のバイト又は現在の固有列の最後のバイトの次の固有ペア，
又は固有列を検索する。
7.2.2
辞書の凍結 辞書は，次のとき凍結状態とする。
− 利用できる符号値をすべて割り当てたとき。
− アルゴリズムが固有ペア又は固有列の辞書登録をしないと判断したとき。例えば，辞書の未使用箇所
の検索に時間がかかり過ぎ。
3
X 6133 : 1997 (ISO/IEC 11558 : 1992)
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
辞書を空状態にリセットすることによって辞書を凍結状態から解除することができる（7.3.1.1参照）。
7.2.3
辞書の空状態へのリセット アルゴリズムは，入力したすべてのバイトを符号語で表現したとき，
辞書を空状態にリセットできる。
例えば，アルゴリズムは現在の辞書登録内容が入力列の反復特性を十分に反映できず圧縮度が適切でな
いと判断したとき，辞書をリセットできる。
7.2.4
境界 自然境界が，入力列のバイト集合間に存在することがある。例えば，列がレコードの連続で，
1バイト以上のバイトから構成する場合，自然境界がレコード間に存在する。アルゴリズムは，出力列で
この境界を表示するので，復元アルゴリズムは境界を認識し，再構成する。
境界は，固有ペア又は固有列の入力列の検索に一時的に保持された単一バイト，バイトペア又はバイト
列の符号値を表す符号語にEOR符号語（7.3.1.4参照）が出力されたことによって判別できる。入力列の検
索は，次のレコードの最初のバイトから続行する。入力列の境界間のデータは，すべて出力列の対応する
境界間の符号語によって表現し，出力列の境界は，EOR符号語に続く符号語のパッドビットの最後に位置
する。
7.2.5
辞書の再生 辞書は，独立しており出力列には含まない。復元アルゴリズムが適切であれば，圧縮
アルゴリズムの出力列から辞書を再生し，データを元の表現に復元できる。
7.3
符号値
0から7の符号値は，制御符号とする（7.3.1参照）。
8から263の符号値は，符号化バイトとする（7.3.2参照）。
264 から4 095の符号値は，辞書符号とする（7.3.3参照）。
7.3.1
制御符号 制御符号は，四つの符号値0，1，2及び3で定義し，4〜7の符号値は使用しない。
7.3.1.1
辞書の凍結 辞書の凍結を示す制御符号は，符号値0とする。アルゴリズムは，必ずしも符号値
0を出力しない。
アルゴリズムは，すべての入力バイトを符号語で表現し，辞書の凍結を決定した後，符号値0を出力で
きる。
7.3.1.2
辞書のリセット 辞書を空状態にリセット後に，アルゴリズムが出力する最初の制御符号は，符
号値1とし，この場合以外には符号値1を出力してはならない。
出力列は，符号値1を含む符号語に続き必要に応じて次の8ビットバイトまで必要な数の “0” ビットを
付加する。
7.3.1.3
符号語長の拡張 符号語長の拡張の制御符号は，符号値2とする。この制御符号に続くすべての
符号語のビット数は，次の符号語長拡張の制御符号があればその後ろまで，この符号値を含む符号語のビ
ット数より1ビット増加する。
7.3.1.4
レコードの終わり (EOR) レコードの終わり (EOR) の制御符号は，符号値3とする。この制御
符号に続く符号語の符号値のバイト，バイトペア又はバイト列の後に，入力列の境界が存在する。
このEORの符号値を含む符号語は，出力列では必要に応じて，次の8ビットバイトの構成に必要な数の
パッドビット “0” が続くこととする。次の符号語は，次の8ビットバイトの構成に必要な数のパッドビッ
ト “0” が続くこととする。これらの条件によって，入力列のレコードを表現する符号語のセットは，8ビ
ットバイトで始まり，8ビットバイトで終わることを保証する。
7.3.2
符号化バイト 1符号化バイトは，入力列の1バイトを表現し，1バイトで表現可能な数値（0か
ら255）になる。符号化バイトは，符号化するバイトの値に8を加えなければならない。
7.3.3
辞書符号 辞書符号は，バイトペア又はバイト列の辞書登録を示す。
4
X 6133 : 1997 (ISO/IEC 11558 : 1992)
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
7.4
符号語 辞書が空状態のとき，符号語の長さは9ビットとする。符号語の長さは，符号値が大きく
なり，現在の符号語長では表現できなくなったとき，必要に応じて増加しなければならない（7.3.1.3参照）。
符号語の長さは，アルゴリズムによって増加させてもよい。現在の符号語長が，符号値の表現に必要な
長さより長い場合，冗長ビットは，要求ビットより上位とし “0” を設定する。
符号語の長さを減少させる方法は，次による。
− アルゴリズムが辞書を空状態にリセットする。
− 辞書のリセットの制御符号を示す符号語を出力する。符号語の拡張制御符号の符号語が多く存在する
場合，符号語の長さは最後の拡張制御符号による。
− 次のバイトまで，必要な長さのパッドビット “0” を付加する。
− 次の符号語は，9ビット長とする。
出力時に符号語は，符号語のビットを最下位のビットから順に8ビット長のバイトの連続ビットとして，
一番右側から入力し，8ビット長のバイト単位に構成する。バイトのすべてのビットを入力すると，その
バイトを出力し，次の符号語のビットは，出力列の次のバイトに入力する。
5
X 6133 : 1997 (ISO/IEC 11558 : 1992)
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
附属書A（参考） 一般的なDCLZアルゴリズムの例
この附属書は，一般的なDCLZ圧縮アルゴリズムについて記述する。記述は，疑似符号として知られて
いる構造化英語とする。言語は通常な英語の語い（彙），構文，意味に加えて特別な単語 (ENDIF) と形式
を利用し，無条件の実行もしくは特定条件，又は条件の組合せの実行という命令を表現する。更に，その
条件を表現したり，注釈を与えることもある。これらはすべてアルゴリズムの理解に有効である。
条件付き実行か，繰返しの実行かのセット内での命令群は，字下げの階層で示す。1セットは，階層し
た字下げ命令すべてからなる。
反復か，条件付きの実行かの指示部分を除き，ページ上部から順番に命令を実行する。コメントは括弧
でくくり，命令と区別する。
アルゴリズムの特定の適用は，互いに異なってもよい。例えば，辞書の凍結，又は空状態のリセットを
決定する方法などである。
アルゴリズムは，二部構成をとる。一部では，入力列を処理して符号値を生成し，二部ではその符号値
から符号語を生成する。入力列では，一部で生成した特定の符号値で表現した最後のバイトにレコードの
境界が続く場合，指示フラグをその符号値に付加する。そのフラグは，二部に対しEOR符号値を含む符号
語の生成を指示する。
A.1 符号値発生器 アルゴリズムの動作を表A.1に示す。 “Pop” は“符号値の出力”を意味し， “Pop&flag”
は，“フラグ付きの符号値の出力”を意味する。出力する符号値は，括弧でくくる。
このアルゴリズムの重要な要素は，Current̲Stringと呼ぶ列で，入力列と辞書の入力との整合をとるため
に使用し，NULであってもよい。NULでない場合，130バイト未満とする。辞書の入力は2〜128バイト
長の列とし，129バイトの列は，辞書では検索できない。入力列の最後のバイトは，レコードの境界が続
くこととして処理する。
表A.1に示すアルゴリズムの基本的な概要を次に説明する。
A.1.1 初期設定 辞書を空の状態に初期化し，辞書のリセット制御符号を出力する。A.1.2の命令を繰り返
し実行し，一度の反復で1個のレコードを処理し，すべての入力列のバイトを処理する。
A.1.2 1個のレコードの処理 入力列からレコードの先頭のバイトを取り出し，レコードがこのバイトだけ
の場合，このバイトの符号化バイトを出力する。符号語生成器は，EOR符号語と必要な数のパッドビット
を生成する。その他の場合，A.1.3の命令をこのレコードのすべてのバイトの処理が完了するまで繰り返し
実行する。
A.1.3 一組のバイトの処理 入力列から次のバイトを取り出し，先頭のバイトと組み合わせて一組のバイ
トとする。この一組のバイトが辞書に存在する場合，A.1.4の命令を実行する。辞書に存在しない場合は，
この一組のバイトを辞書に登録し，登録できない場合，辞書を凍結する。この一組のバイトの最初のバイ
トの符号化バイトを出力し，最初のバイトは捨てる。残ったバイトがレコードの最後のバイトの場合は，
そのバイトの符号化バイトを出力する。符号語生成器は，EOR符号語と必要な数のパッドビットを生成す
る。
6
X 6133 : 1997 (ISO/IEC 11558 : 1992)
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
A.1.4 バイト列の処理 A.1.5の命令を繰り返し実行し，レコードの終わりがEORに達するか，列が辞書
に存在しなくなるまで列の長さを拡張する。EORに達した場合，その列に対応する辞書符号を出力し，符
号語生成器は，EOR符号語と適切な数のパッドビットを生成する。列が辞書に存在しない場合，その列を
辞書に登録し，登録ができない場合，辞書を凍結する。最後のバイトを除いて，列のすべてのバイトに対
応する辞書符号を出力し，バイトはすべて捨てる。残ったバイトがレコードの最後のバイトの場合，この
バイトの符号化バイトを出力する。符号語生成器は，EOR符号語と適切な数のパッドビットを生成する。
A.1.5 一組のバイト又は列の拡張 一組又は列の最後のバイトが，そのレコードの最後のバイトでない場
合，入力列から次のバイトを取り出し，現在の一組又は列に追加して新たに形成した列を辞書で検索する。
7
X 6133 : 1997 (ISO/IEC 11558 : 1992)
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
表A.1 符号値生成器
Reset dictionary to empty state
Pop (Dictionary Reset)
Regard dictionary as not frozen
REPEAT {processing one record}
Initialize Current̲string to next byte from input stream
IF a record boundary follows that byte {i. e. record is only 1 byte}
THEN Pop&flag (Encoded Byte for that byte)
ELSE REPEAT {processing pairs and strings}
Append next byte from input stream to Current̲string
Search dictionary for Current̲string
IF search failed {i. e. if a unique pair is found}
THEN IF dictionary is not frozen
THEN Attempt to add Current̲string to dictionary
IF not successful
THEN Regard dictionary as frozen
ENDIF
ENDIF
Pop (Encoded Byte for 1st byte of Current̲string)
Remove 1st byte from Current̲string
IF record boundary follows remaining byte in Current̲string
THEN Pop&flag (encoded Byte for that byte)
Set Current̲string to null
ENDIF
ELSE REPEAT {a unique pair has not been found, so continue examining the input stream, looking for a
unique string or a record boundary}
IF record boundary follows last byte of Current̲string
THEN Pop&flag (Dictionary Code for Current̲string)
Set Current̲string to null
ELSE Append next byte from input stream to Current̲string
Search dictionary for Current̲string
ENDIF
UNTIL Current̲string is null or dictionary search fails
IF search failed {i. e. if the string is a unique string}
THEN IF dictionary is not frozen and
Current̲string length＜129 bytes
THEN Attempt to add Current̲string to dictionary
IF not successful
THEN Regard dictionary as frozen
ENDIF
END IF
Pop (Dictionary Code for entry of all but last byte of Current̲string)
IF record boundary follow last byte of Current̲string
THEN Pop&flag (Encoded Byte for last byte)
Set Current̲string to null
ELSE Remove all bytes but last of Current̲string
ENDIF
ENDIF
ENDIF
UNTIL Current̲string is null {i. e. processing of this record is complete}
ENDIF
UNTIL input stream is exhausted {i. e. processing of all record is complete}
8
X 6133 : 1997 (ISO/IEC 11558 : 1992)
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
A.2 符号語生成器 アルゴリズムは，符号値から符号語を生成し，出力列のバイト境界に対するパッディ
ングは，必要に応じて実行する。
アルゴリズムの操作は，表A.2に示す。出力する符号語の内容は，括弧でくくる。
表A.2 符号語生成器
Set Codeword size to 9 bits
REPEAT (process all Code Values, one per cycle)
Fetch next Code Value
IF Code Value is Dictionary Reset
THEN Output Codeword (Dictionary Reset)
IF last bit of Codeword is not at byte boundary in output stream
THEN Output ZERO bits to next byte boundary
ENDIF
Set Codeword size to 9 bits
ELSE IF Codeword size is too small to express Code Value
THEN REPEAT
Output Codeword (Increment Codeword Size)
Increment Codeword size by one bit
UNTIL Codeword size is not sufficient to express Value
ENDIF
IF Code Value is flagged
THEN Output Codeword (EOR)
IF last bit of Codeword is not at byte boundary in output stream
THEN Output ZERO bits to next byte boundary
ENDIF
ENDIF
Output Codeword (Code Value)
IF Code Value is flagged
THEN Output ZERO bits to next byte boundary
ENDIF
ENDIF
UNTIL Code Value stream is exhausted
9
X 6133 : 1997 (ISO/IEC 11558 : 1992)
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
附属書B（参考） 与えられた入力列に対する符号値出力の例
次の例では行順に進行する。
入力列：abcdabcdabcdabcdabcdaabcdx
入力
バイト
辞書符号
辞書登録
符号値出力
符号値の意味
1
辞書のリセット
a
b
264
ab
105
aに対する符号化バイト
c
265
bc
106
bに対する符号化バイト
d
266
cd
107
cに対する符号化バイト
a
267
da
108
dに対する符号化バイト
b
c
268
abc
264
abに対する辞書符号
d
a
269
cda
266
cdに対する辞書符号
b
c
d
270
abcd
268
abcに対する辞書符号
a
b
271
dab
267
daに対する辞書符号
c
d
272
bcd
265
bcに対する辞書符号
a
b
c
273
dabc
271
dabに対する辞書符号
d
a
a
274
cdaa
269
cdaに対する辞書符号
b
c
d
x
275
abcdx
270
abcdに対する辞書符号
y
276
xy
128
xに対する符号化バイト
z
277
yz
129
yに対する符号化バイト
3
EOR
130
zに対する符号化バイト
この例では，データの表現するビット数は，224から168に減少し，圧縮率は，1.333になる。入力列が長
くなれば，入力列繰返し数，出現回数及び辞書への登録が多くなり，圧縮率も高くなる。圧縮率の代表的
な値は，2〜4の範囲である。
10
X 6133 : 1997 (ISO/IEC 11558 : 1992)
2019年7月1日の法改正により名称が変わりました。まえがきを除き，本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。
附属書C（参考） 参考文献
Mark J. Bianchi et al. “Data Compression in a Half-Inch Reel-to-Reel Tape Drive”
Hewlett-Packard Journal, Volume 40, No.3, June 1989, pp 26-31
JIS磁気テープ原案作成委員会 構成表
（敬称略，順不同）
氏名
所属
（委員長）
大 石 完 一
パルステック工業株式会社
（幹事）
富 田 正 典
日本システムインテグレーション株式会社
（幹事）
徳 永 賢 次
住友スリーエム株式会社
金 子 悟
富士通株式会社
竹 内 正
株式会社トリム・アソシエイツ
平 川 卓
富士写真フイルム株式会社
新 井 清
日本システムハウス株式会社
今 井 伸 二
日本電気株式会社
安 藤 晴 夫
日立マクセル株式会社
樋 口 重 光
株式会社日立製作所
堀 川 憲 一
ソニー株式会社
荒 木 学
日本ユニシス株式会社
岸 野 忠 信
財団法人日本規格協会
永 松 荘 一
通商産業省機械情報産業局
藤 井 隆 宏
通商産業省工業技術院
兼 谷 明 男
通商産業省工業技術院
（関係者）
佐々木 修 二
財団法人日本電子部品信頼性センター
（事務局）
東 條 喜 義
社団法人日本電子工業振興協会
内 山 誠 作
社団法人日本電子工業振興協会