>サイトトップへ >このカテゴリの一覧へ

X 6133 : 1997(ISO/IEC11558 : 1992)

(1) 

まえがき

この規格は,工業標準化法に基づいて,日本工業標準調査会の審議を経て,通商産業大臣が制定した日

本工業規格である。

この規格の一部が,技術的性質をもつ特許権,出願公開後の特許出願,実用新案権,又は出願公開後の

実用新案登録出願に抵触する可能性があることに注意を喚起する。主務大臣及び日本工業標準調査会は,

このような技術的性質をもつ特許権,出願公開後の特許出願,実用新案権,又は出願公開後の実用新案登

録出願にかかわる確認について,責任はもたない。

JIS X 6133

には,次に示す

附属書がある。

附属書 A(参考)  一般的な DCLZ アルゴリズムの例

附属書 B(参考)  与えられた入力列に対する符号値出力の例

附属書 C(参考)  参考文献


1

  (ISO/IEC 11558 : 1992)

目次

ページ

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


日本工業規格

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

  (ISO/IEC 11558 : 1992)

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>2)  の固有列とは,辞書に登録のない列であり,かつ,最初の

n

−1 バイトは,辞書に登録済みであることを意味する。辞書に登録できる最大の列の長さは,128 バイト

とする。

固有ペアを検出すると,アルゴリズムはペアの第 1 バイトの符号語を出力する。バイトの固有列を見

つけると,アルゴリズムは最初の n−1 バイトの列の符号値の符号語を出力する。

辞書が凍結状態になく(7.2.2 参照)

,かつ,が 128 を超えていない場合,固有ペア又は固有列を辞書に

登録し,使用していない次の符号値を割り当てる。

アルゴリズムは,現在の固有ペアの 2 番目のバイト又は現在の固有列の最後のバイトの次の固有ペア,

又は固有列を検索する。

7.2.2

辞書の凍結  辞書は,次のとき凍結状態とする。

−  利用できる符号値をすべて割り当てたとき。

−  アルゴリズムが固有ペア又は固有列の辞書登録をしないと判断したとき。例えば,辞書の未使用箇所

の検索に時間がかかり過ぎ。


3

  (ISO/IEC 11558 : 1992)

辞書を空状態にリセットすることによって辞書を凍結状態から解除することができる(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

  (ISO/IEC 11558 : 1992)

7.4

符号語  辞書が空状態のとき,符号語の長さは 9 ビットとする。符号語の長さは,符号値が大きく

なり,

現在の符号語長では表現できなくなったとき,

必要に応じて増加しなければならない

7.3.1.3 参照)

符号語の長さは,アルゴリズムによって増加させてもよい。現在の符号語長が,符号値の表現に必要な

長さより長い場合,冗長ビットは,要求ビットより上位とし “0” を設定する。

符号語の長さを減少させる方法は,次による。

−  アルゴリズムが辞書を空状態にリセットする。

−  辞書のリセットの制御符号を示す符号語を出力する。符号語の拡張制御符号の符号語が多く存在する

場合,符号語の長さは最後の拡張制御符号による。

−  次のバイトまで,必要な長さのパッドビット “0” を付加する。

−  次の符号語は,9 ビット長とする。

出力時に符号語は,符号語のビットを最下位のビットから順に 8 ビット長のバイトの連続ビットとして,

一番右側から入力し,8 ビット長のバイト単位に構成する。バイトのすべてのビットを入力すると,その

バイトを出力し,次の符号語のビットは,出力列の次のバイトに入力する。


5

  (ISO/IEC 11558 : 1992)

附属書 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

  (ISO/IEC 11558 : 1992)

A.1.4

バイト列の処理  A.1.5 の命令を繰り返し実行し,レコードの終わりが EOR に達するか,列が辞書

に存在しなくなるまで列の長さを拡張する。EOR に達した場合,その列に対応する辞書符号を出力し,符

号語生成器は,EOR 符号語と適切な数のパッドビットを生成する。列が辞書に存在しない場合,その列を

辞書に登録し,登録ができない場合,辞書を凍結する。最後のバイトを除いて,列のすべてのバイトに対

応する辞書符号を出力し,バイトはすべて捨てる。残ったバイトがレコードの最後のバイトの場合,この

バイトの符号化バイトを出力する。符号語生成器は,EOR 符号語と適切な数のパッドビットを生成する。

A.1.5

一組のバイト又は列の拡張  一組又は列の最後のバイトが,そのレコードの最後のバイトでない場

合,

入力列から次のバイトを取り出し,

現在の一組又は列に追加して新たに形成した列を辞書で検索する。


7

  (ISO/IEC 11558 : 1992)

表 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 nul

              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 nul

                  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

  (ISO/IEC 11558 : 1992)

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

  (ISO/IEC 11558 : 1992)

附属書 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

  (ISO/IEC 11558 : 1992)

附属書 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

磁気テープ原案作成委員会  構成表

(敬称略,順不同)

氏名

所属

(委員長)

大  石  完  一

パルステック工業株式会社

(幹事)

富  田  正  典

日本システムインテグレーション株式会社

(幹事)

徳  永  賢  次

住友スリーエム株式会社

金  子      悟

富士通株式会社

竹  内      正

株式会社トリム・アソシエイツ

平  川      卓

富士写真フイルム株式会社

新  井      清

日本システムハウス株式会社

今  井  伸  二

日本電気株式会社

安  藤  晴  夫

日立マクセル株式会社

樋  口  重  光

株式会社日立製作所

堀  川  憲  一

ソニー株式会社

荒  木      学

日本ユニシス株式会社

岸  野  忠  信

財団法人日本規格協会

永  松  荘  一

通商産業省機械情報産業局

藤  井  隆  宏

通商産業省工業技術院

兼  谷  明  男

通商産業省工業技術院

(関係者)

佐々木  修  二

財団法人日本電子部品信頼性センター

(事務局)

東  條  喜  義

社団法人日本電子工業振興協会

内  山  誠  作

社団法人日本電子工業振興協会