JP3088740B2

JP3088740B2 - データ圧縮及び復元方式

Info

Publication number: JP3088740B2
Application number: JP02269930A
Authority: JP
Inventors: 広隆千葉; 佳之岡田; 茂吉田; 泰彦中野
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1990-10-08
Filing date: 1990-10-08
Publication date: 2000-09-18
Anticipated expiration: 2015-09-18
Also published as: JPH04145726A

Description

【発明の詳細な説明】［概要］符号化済データを相異なる部分列に分けて辞書に登録
し、入力データを辞書中の部分列の内、最大長一致する
もの登録番号で指定して符号化し、また符号語を辞書を
使用して復号するユニバーサル符号化の一種であるLZW
符号によるデータ圧縮及び復元方式に関し、辞書の初期登録により圧縮率を高めることを目的と
し、１文字のみならず、出現頻度の高い１文字以上からな
る文字列の組に予め登録番号を割り当てて辞書に初期登
録するように構成する。

［産業上の利用分野］本発明は、ユニバーサル符号の一種である増分分解型
の改良として知られたLZW符号によるデータ圧縮及び復
元方式に関する。

近年、文字コード，ベクトル情報，画像など様々な種
類のデータがコンピュータで扱われるようになってお
り、扱われるデータ量も急速に増加してきている。大量
のデータを扱うときは、データの中の冗長な部分を省い
てデータ量を圧縮することで、記憶容量を減らしたり、
速く伝送したりできるようになる。

様々なデータを１つの方式でデータ圧縮できる方法と
してユニバーサル符号化が提案されている。

ここで、本発明の分野は、文字コードの圧縮に限ら
ず、様々なデータに適用できるが、以下では、情報理論
で用いられている呼称を踏襲し、データの１ワード単位
を文字と呼び、データが任意ワードつながったものを文
字列と呼ぶことにする。

ユニバーサル符号の代表的な方法として、Ziv−Lempe
l（ジブ−レンペル）符号がある（詳しくは、例えば、
宗像『Ziv−Lempelのデータ圧縮法』，情報処理,Vol.2
6,No.1,1985年を参照のこと）。

Ziv−Lempel符号ではユニバーサル型と、増分分解型（Incremental parsing）の２つのアルゴリズムが提案されている。

さらに、ユニバーサル型アルゴリズムの改良として、
LZSS符号がある（T.C.Bell,“Better OPM/L Text Comp
ressin",IEEE Trans.on Commun.,Vol.COM−34,No.12,De
c.1986参照）。

また、増分分解型アルゴリズムの改良としては、LZW
（Lempel−Ziv−Welch）符号がある（T.A.Welch,“A Te
chnique for High−Performance Data Compressign",Co
mputer,June 1984参照）。

これらの符号の内、高速処理ができることと、アルゴ
リズムの簡単さからLZW符号が記憶装置のファイル圧縮
などで使われるようになっている。

［従来の技術］従来のLZW符号の符号化アルゴリズムを第８図に示
し、また復号化アルゴリズムを第９図に示す。

LZW符号化は、書き替え可能な辞書をもち、入力文字
コード・データ中を相異なる文字列に分け、この文字列
を出現した順に番号を付けて辞書に登録するとともに、
現在入力している文字列を辞書に登録してある最長一致
文字列の番号で表して符号化するものである。

第８図のLZW符号化処理では、まずステップS1（以下
「ステップ」を省略）で予め全文字につき一文字から成
る文字列を初期値として辞書に登録してから符号化を始
める。またS1では入力した最初の文字Ｋにより辞書を検
索して参照番号ωを求め、これを語頭文字列（prefix s
tring）とする。

次にS2で入力データの次の文字Ｋを読み込み、S3で文
字入力が終了したか否かをチェックした後、S4に進んで
S1で求めた語頭文字列ωにS2で読み込んだ文字Ｋを加え
た文字列ωＫが辞書にあるか否か探す。

S4で文字列ωＫが辞書になければ、S6に進んでS1で求
めた文字Ｋの参照番号ωを符号語code（ω）として出力
し、また文字列（ωＫ）に新たな参照番号を付加して辞
書に登録し、さらにS2の入力文字Ｋを参照番号ωに置き
換えるとともに、辞書アドレスｎをインクリメントとし
てS2に戻って次の文字Ｋを読み込む。

一方、S4で文字列（ωＫ）が辞書にあれば、S5で文字
列（ωＫ）を参照番号ωに置き換え、再びS2に戻って文
字列（ωＫ）が辞書から探せなくなるまで最大一致長の
探索を続ける。

第10,11図を参照してLZW符号化を具体的に説明すると
次のようになる。

まず第10図の入力データINPUTは左から右へ読み込
む。最初の文字ａを入力したとき、辞書には文字ａの他
に一致する文字列がないので、OUTPUT CODE1（参照番号
ω）を符号語として出力する。そして文字ａを新たな語
頭文字列ωとする。

次に２番目の文字ｂを入力し、この入力文字ｂを語頭
文字列ωに加えた文字列ωＫ＝abは辞書にないことか
ら、文字ｂのOUTPUT CODE2を符号語として出力する。そ
して、拡張した文字列abに参照番号４をつけて辞書に登
録する。実際の登録は第11図の右側に示すように文字列
1bの形で登録される。そして２番目に入力した文字ｂが
新たな語頭文字列ωとなる。

続いて３番目の文字ａを入力したとすると、入力文字
ａに語頭文字列ωを加えた拡張文字列ωＫ＝ba＝2aは辞
書にないことから、文字ｂのOUTPUT CODE2を符号語とし
て出力した後、拡張文字列ωＫ＝baを2aで表わし、参照
番号５を付けて辞書に登録する。そして３番目に入力し
た文字ａが新たな語頭文字列ωとなる。

４番目の入力文字ｂについては拡張文字列ωＫ＝abは
符号語４として既に辞書に登録されているので、文字列
ωＫを新たな語頭文字列ωとし、５番目の文字ｃを入力
して拡張文字列ωＫ＝4c＝abcを作る。この拡張文字列
ωＫ＝abcは辞書に登録されていないことから、文字列a
b＝1bのOUTPUT CODE4を符号語として出力し、拡張文字
列ωＫ＝abcを辞書に4cの形で参照番号６を付けて登録
する。以下、同様にこの処理を続ける。

第９図の復号化処理は第８図の符号化の逆の操作を行
う。

第９図の復号化では、符号化と同様に予め辞書に全文
字につき一文字からなる文字列を初期値として登録して
から復号を始める。

まずS1で最初の符号（参照番号）を読み込み、現在の
CODEをOLDcodeとし、最初の符号は既に辞書に登録され
た一文字の参照番号のいずれかに該当することから、入
力符号CODEに一致する文字code（Ｋ）を探し出し、文字
Ｋを出力する。なお、出力した文字（Ｋ）は後の例外処
理のためFINcharにセットしておく。

次にS2に進んで次の符号を読み込んでCODEにINcodeと
してセットする。S3で新たな符号があるか否か、すなわ
ち符号入力の終了の有無をチェックしてS4に進み、S3で
入力された符号CODEが辞書に定義（登録）されているか
否かチェックする。通常、入力した符号語は前回までの
処理で辞書に登録されているため、S5に進んで符号CODE
に対応する文字列code（ωＫ）を辞書から読み出し、S6
で文字列Ｋを一時的にスタックし、参照番号code（ω）
を新たなCODEとして再度S5に戻り、このS5,S6の手順を
再帰的に参照番号ωが一文字に至るまで繰り返し、最後
にS7に進んでS6でスタックした文字をLILO（Last In Fa
st Out）形式でポップアップして出力する。同時にS7に
おいて、前回使った符号ωと今回復元した文字列の最初
に一文字Ｋを組（ω,K）と表した文字列に、新たな参照
番号を付加して辞書に登録する。

第12図を参照して復号化処理を具体的に説明すると次
のようになる。

まず第12図で最初の入力符号は１であり、一文字a,b,
cについては既に参照番号1,2,3として第２表に示すよう
に辞書に登録されているため、辞書の参照により符号１
に一致する参照番号の文字列ａに置き換えて出力する。
次の符号２についても同様にして文字ｂに置き換えて出
力する。このとき前回処理した符号と今回復号した最初
の一文字ｂとを組み合わせた1b（＝ab）に新たな参照番
号４を付加して辞書に登録する。

３番目の符号４は辞書の探索により1bからabと置き換
えて文字列abを出力する。同時に前回処理した符号２と
今回復号した文字列の１番目の文字ａとを組み合せた文
字列2a（＝ba）を新たな参照番号５を付加して辞書に登
録する。

以下同様に、この処理を繰り返す。

第12図の復号化では次の例外処理がある。

この例外処理は、第６番目の入力符号８の復号で生ず
る。符号８は復号時に辞書に定義されておらず、復号で
きない。この場合には、前回処理した符号５に前回復号
した文字列baの最初の一文字ｂを加えた文字列5bを求
め、さらに2ab,babと置き換えられて出力される。そし
て、文字列の出力語に前回の符号語５に今回復号した文
字列の文字ｂを加えた文字列5bに参照番号８を付加して
辞書に登録する。

この例外処理は第９図の復号化処理フローのS4,S8の
処理を通じて行われ、最終的にS7で文字列の出力と新た
な文字列に参照番号を付加して辞書への登録がS7で行わ
れる。

なお、第8,9図の符号化／復号化処理は、同じ辞書を
作り出しながら行う。

［発明が解決しようとする課題］従来のLZW符号は、過去に出現したデータを辞書に登
録し、登録済みの情報を使用して圧縮を行っている。し
かし、過去に出現したデータを全て辞書に登録すること
が効果的な辞書の登録法であると断言できない。例え
ば、画像データの場合、オール白やオール黒パターンの
出現頻度が高い事は分かっており、、これらのデータを
逐次登録していたのでは、辞書登録がある程度進まない
と高い圧縮率を得ることができない問題がある。

本発明は、このような従来の問題点に鑑みてなされた
もので、辞書の初期登録により圧縮率を高めることので
きるLZW符号によるデータ圧縮及び復元方式を提供する
ことを目的とする。

［課題を解決するための手段］第１図は本発明の原理説明図である。

まず本発明は、符号化済データを相異なる部分列に分
けて、この部分列を辞書10に登録しておき、入力データ
を辞書10中の部分列の内、最大長一致するもの登録番号
で指定して符号化する符号化手段100を備えたLZW符号に
よるデータ圧縮方式を対象とする。

このようなデータ圧縮方式につき本発明にあっては、
入力文字１文字毎に予め登録番号を割り当てて辞書10に
初期登録すると共に、２文字以上で出現頻度の高い文字
列に予め登録番号を割り当てて辞書10に初期登録してお
き、この辞書10を使用して前記符号化手段100により入
力データを圧縮符号化することを特徴とする。また圧縮
すべきデータ中において１文字が複数連続する文字列、
例えばaa,aaa,aaaa,aaaaa等にに予め登録番号を割り当
てて辞書10に初期登録する。

さらに本発明は、符号化済データを相異なる部分列に
分けて、この部分列を辞書10に登録しておき、入力デー
タを辞書10中の部分列の内、最大長一致するもの登録番
号で指定して符号化された符号語を、辞書10を使用して
元のデータに復元する復号化手段200を備えたデータ復
元方式を対象とする。

このようなデータ復元方式についても本発明にあって
は、入力文字１文字毎に予め登録番号を割り当てて辞書
10に初期登録すると共に、２文字以上で出現頻度の高い
文字列に予め登録番号を割り当てて辞書10に初期登録し
ておき、この辞書10を使用して復号化手段200により入
力データを復元することを特徴とする。また圧縮すべき
データ中において１文字が複数連続する文字列、例えば
aa,aaa,aaaa,aaaaa等にに予め登録番号を割り当てて辞
書10に初期登録する。

［作用］このような構成を備えた本発明のデータ圧縮及び復元
方式によれば、予め出現頻度の高い文字列、例えば同じ
文字が連続する文字列を、辞書の初期化時に個数に応じ
て登録番号に割り当てておき、登録済みの文字列λが出
現した場合には、登録番号を使用して圧縮処理を行うこ
とにより高圧縮を実現できる。

［実施例］第２図は本発明の一実施例を示した実施例構成図であ
る。

第２図において、12は制御手段としてのCPUであり、C
PU12に対してはプログラムメモリ14とデータメモリ26が
接続される。

プログラムメモリ14にはコントロールソフト16、LZW
符号を用いた最大一致長検索を行なう最大一致長検索ソ
フト18、入力文字列をLZW符号に変換する符号化ソフト2
0、符号化ソフト20でLZW符号に変換された符号を元の文
字列に復元する復号化ソフト22、及び処理対象となる１
文字のそれぞれに加えて使用頻度の高い文字列λ、例え
ばこの実施例にあっては文字列λとして同一文字ａが２
〜15個連続した各文字列に登録番号を付けて初期登録す
る初期登録ソフト24を備える。

一方、データメモリ26には、これから符号化しようと
する文字列或いはこれから復号化しようとする符号列を
格納するデータバッファ28と、LZW符号を対象とした符
号化及び復号化の際に逐次作成されながら使用される辞
書10を備える。

この第２図の実施例における本発明による辞書の初期
登録の次のようにして行われる。

まず、CPU12はコントロールソフト16による制御のも
とに初期登録ソフト24を起動し、辞書10の初期登録を行
なう。即ち、CPU12は初期登録ソフト24に基づき、処理
対象となる文字種における１文字のそれぞれに登録番号
（参照番号）を付けて辞書10に初期登録する。

説明を簡単にするため処理対象としてa,b,cの３文字
を考えると、第５図の辞書構成説明図に示すように参照
番号1,2,3を付けて文字a,b,cが初期登録される。

これに加えて本発明にあっては、出現頻度の高い文字
列λとして文字ａが２〜10個連続した文字列を第５図の
辞書構成に示すように、aa,aaa,・・・,aaaaaaaaaaに登
録番号４〜12を付けて辞書に初期登録するる。尚、第５
図では、ａ×2,a×3,・・・,a×10として示している。

このような辞書10に対する初期登録が済んだならば、
データメモリ26のデータバッファ28に対しては所望の入
力データ又は符号データを格納し、符号化ソフト20によ
る符号化処理或いは復号化ソフト22に基づく復号処理が
行われる。

本発明によるLZW符号の符号化アルゴリズムを第３図
に示し、復号化アルゴリズムを第４図に示す。

ここで第５図の入力文字を対象として第３図のLZW符
号の符号化を説明すると、まずS1で文字コードｉを辞書
アドレスｉに１文字ずつ登録する初期登録に加え、予め
出現頻度が高い文字をλとし、文字λを１つだけでな
く、λの個数に応じて複数通りの文字列を辞書に登録し
ておく。例えば文字a,b,を対象とした第６図の辞書構成
の例では、文字ａを１個から10個までの連続する文字列
の各々を登録している。

S1の初期登録が済んだならば、S2〜S7の処理により初
期登録した文字λが複数連続した場合の処理を行う。即
に、S3でＫ＝λを判別してS4で文字λの連続個数を示す
λカウンタを１つインクリメントし、入力文字Ｋが文字
λでなくなるまで繰り返す。即ち、第５図の１番目の入
力文字ａは文字λであることから、S3からS4に進んでλ
カウンタを１つインクリメントする。次の入力文字ｂは
文字λでないことからS5に進み、このときλカウンタ＝
１であることからS6へ進んでλカウンタの値を符号コー
ドCODE（λ）＝CODE1として出力し、S7で２番目に入力
した文字ｂを新たな語頭文字列ωとする。

次のS8、S9、S11,S12,S13及びS22は第８図に示した従
来のLZW符号化処理と同じであり、カッコ内に第８図の
符号を示している。

このような従来Ｓ同じLZW符号化の処理中に、本発明
にあっては、新たにS10から分岐してS14〜S21の処理に
至る出現頻度の高い文字λの処理が入る。

具体的には、S7で２番目に入力した文字ｂを語数多文
字列ωとした後に、S8で３番目の文字ａを読み、S9を介
してS10でＫ＝λが判別されてS14の処理に進む。

S14にあっては、そのときの語頭文字列ω＝ｂを符号
コードCODE（ω）＝CODE2として出力した後、S15でλカ
ウンタ１を１つインクリメントし、S16で次の文字ｂを
読み、S18を介してS19でＫ＝λを判別し、この場合には
文字ｂはλでないことからS20で符号コードとしてcode
（λ）＝code1を出力し、λ＝０にリセットしした後に
再びS7に戻る。

これに対し第５図の13番目の入力文字からはλとして
の文字ａが７つ連続することから、この場合にはS15〜1
9の処理の繰り返しによりλカウンタの計数値λ＝７が
得られ、S20において符号コードとしてcode9を出力する
ようになる。

ここで10個以上の文字ａが連続する文字列の場合、例
えば15個のａが連続する場合は、参照番号12,7の２つ符
号コードを使って表現する。また、本発明のデータ符号
方式では、符号処理の途中でλに相当する文字が出現し
た場合、S14においてそれまでの文字列ωを符号コード
として出力し、文字列ωＫ＝ωλの辞書登録は行わな
い。

次に第４図の本発明による復号処理を説明する。

第４図の復号処理にあっては、S1〜S4,S8及びS9が出
現頻度の高い文字λの連続個数を示す符号コードを復号
するために設けられており、それ以外の処理は第９図に
示した従来の復号化処理と同じであり、括弧内の符号で
対応関係を示す。

いま第７図に示す入力符号コードを復元する場合を例
にとると、12番目の符号コードまでは従来の復号と同じ
である。但し、符号コードcode1については、S4又はS9
でλ＝ａを１個分出力している。

第７図の13番目の符号コードcode9については、S8で
λコードであることが判別されてS9に進み、符号コード
の値９による辞書の参照により７個分の文字ａを出力す
る。

尚、上記の実施例にあっては、初期登録する文字列と
して同じ文字が複数連続する文字列を例にとるものであ
ったが、本発明はこれに限定されず、出現頻度が高い文
字列であれば適宜の文字列を初期登録するようにしても
よい。

［発明の効果］以上説明したように本発明によれば、文字列の使用頻
度を考慮して辞書に予め複数の個数を表現した文字列を
登録使用しておき、この辞書を使用して圧縮復元を行う
事により、LZW符号のデータ圧縮の圧縮率を更に高い圧
縮率とすることができる。

【図面の簡単な説明】

第１図は本発明の原理説明図；第２図は本発明の実施例構成図；第３図は本発明によるLZW符号の符号化の処理フロー
図；第４図は本発明によるLZW符号の復号の処理フロー図；対５図は本発明によるLZW符号の符号化説明図；第６図は本発明による辞書構成説明図；第７図は本発明によるLZW符号の復元説明図；第８図は従来のLZW符号化処理フロー図；第９図は従来のLZW復号化処理フロー図；第10図は従来のLZW符号化説明図；第11図は従来の辞書構成例の説明図；第12図は従来のLZW復号説明図である。図中、 10:辞書 12:CPU 14:プログラムメモリ 16:コントロールソフト 18:最大一致長検索ソフト 20:符号化ソフト 22:復号化ソフト 24:初期登録ソフト 26:データメモリ 28:データバッファ 100:符号化手段 200:復号化手段

───────────────────────────────────────────────────── フロントページの続き (72)発明者中野泰彦神奈川県川崎市中原区上小田中1015番地富士通株式会社内 (56)参考文献特開昭60−116228（ＪＰ，Ａ) 特開昭61−232724（ＪＰ，Ａ) 特開昭63−209228（ＪＰ，Ａ) 特開昭63−209229（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) H03M 7/40

Claims

(57)【特許請求の範囲】

【請求項１】符号化済データを相異なる部分列に分け
て、該部分列を辞書（10）に登録しておき、入力データ
を該辞書（10）の中の部分列の内、最大長一致するもの
の登録番号で指定して符号化する符号化手段（100）を
備えたデータ圧縮方式に於いて、入力文字１文字毎に予め登録番号を割り当てて前記辞書
（10）に初期登録すると共に、２文字以上で出現頻度の
高い文字列に予め登録番号を割り当てて前記辞書（10）
に初期登録しておき、該辞書（10）を使用して前記符号化手段（100）により
入力データを圧縮符号化することを特徴とするデータ圧
縮方式。
【請求項２】請求項１記載のデータ圧縮方式に於いて、圧縮すべきデータ中において１文字が複数連続する文字
列に予め登録番号を割り当てて前記辞書（10）に初期登
録したことを特徴とするデータ圧縮方式。
【請求項３】符号化済データを相異なる部分列に分け
て、該部分列を辞書（10）に登録しておき、入力データ
を該辞書（10）の中の部分列の内、最大長一致するもの
の登録番号で指定して符号化された符号語を、前記辞書
（10）を使用して元のデータに復元する復号化手段（20
0）を備えたデータ復元方式に於いて、入力文字１文字毎に予め登録番号を割り当てて前記辞書
（10）に初期登録すると共に、２文字以上で出現頻度の
高い文字列に予め登録番号を割り当てて前記辞書（10）
に初期登録しておき、該辞書（10）を使用して前記復号化手段（200）により
入力データを復元することを特徴とするデータ圧縮方
式。
【請求項４】請求項３記載のデータ復元方式に於いて、圧縮すべきデータ中において１文字が複数連続する文字
列に予め登録番号を割り当てて前記辞書（10）に初期登
録したことを特徴とするデータ復元方式。