JP3012679B2

JP3012679B2 - データ圧縮方法

Info

Publication number: JP3012679B2
Application number: JP2281433A
Authority: JP
Inventors: 泰彦中野; 茂吉田; 佳之岡田; 広隆千葉
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1990-10-19
Filing date: 1990-10-19
Publication date: 2000-02-28
Anticipated expiration: 2015-02-28
Also published as: JPH04156111A

Description

【発明の詳細な説明】〔目次〕概要産業上の利用分野従来の技術（第７図乃至第13図）発明が解決しようとする課題課題を解決するための手段（第１図）作用実施例（ａ）一実施例の説明（第２図乃至第６図）（ｂ）他の実施例の説明発明の効果〔概要〕 LZW符号を用いてデータ圧縮するデータ圧縮方法に関
し、辞書中の登録部分列を高速に検索し、符号化時間を短
縮することを目的とし、符号化済データを相異なる部分列に分けて、該部分列
を辞書に登録しておき、連結する部分列の検索順を示す
検索用リストに従って、入力データと該辞書中の部分列
を比較検索し、入力データを該辞書中の部分列の内、最
大長一致するものの参照番号で指定して符号化するデー
タ圧縮方法において、検索された部分列を該検索用リス
ト中の１つ前の部分列と置き換えるように該検索用リス
トを書き換える。

〔産業上の利用分野〕

本発明は、LZW符号を用いてデータ圧縮するデータ圧
縮方法に関する。

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

様々なデータを１つの方式でデータ圧縮できる方法と
してユニバーサル符号化が提案されている。ここで、本
発明の分野は、文字コードの圧縮に限らず、様々なデー
タに適用できるが、以下では、情報論理で用いられてい
る呼称を踏襲し、データの1word単位を文字と呼び、デ
ータが任意wordつながったものを文字列と呼ぶことにす
る。

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

Ziv−Lempel符号ではユニバーサル型と、増分分
解型（Incremental parsing）の２つのアルゴリズムが
提案されている。さらに、ユニバーサル型アルゴリズム
の改良として、LZSS符号がある（T.C.Bell、“Better O
PM/L Text Compression"、IEEE Trans.on Commun.、Vo
l.COM−34,No.12,Dec.1986参照）。また、増分分解型ア
ルゴリズムの改良としては、LZW（Lempel−Ziv−Welc
h）符号がある（T.A.Welch、“A Technique for High−
Performance Deta Compression",Computer,June1984参
照）。

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

〔従来の技術〕

先ず、LZW符号について第７図乃至第９図を用いて説
明する。

第７図はLZW符号化処理フロー図、第８図はLZW復号化
処理フロー図、第９図はLZW符号化、復号化説明図であ
る。

尚、第９図では説明を簡単にするためabcの３文字の
組合わからなるデータを圧縮、復元する場合を取上げて
いる。

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

第７図のフロー図により符号化処理を説明する。

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

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

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

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

第９図（Ａ）、（Ｂ）を参照して符号化を具体的に説
明すると次のようになる。

先ず第９図（Ａ）の入力データを左から右へ読み込
む。最初の文字ａを入力したとき、辞書10にはａの他に
一致する文字列がないので、output code（参照番号
ω）を符号語として出力する。そして、拡張した文字列
abに参照番号４をつけて辞書10に登録する。実際の登録
は文字列（1b）の形となる。続いて２番目のｂが文字列
の先頭になる。辞書10にはｂの他に一致する文字列がな
いので、参照番号２を符号語として出力し、拡張した文
字列baを実際には2aの形で参照番号５をつけて辞書10に
登録する。３番目のａが次の文字列の先頭になる。以
下、同様にこの処理を続ける。

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

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

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

次にS2に進んで次の符号を読み込んでCODEにINcodeと
してセットする。

S3で新たな符号があるか否か、すなわち符号入力の終
了の有無をチェックしてS4に進み、S3で入力された符号
CODEが辞書に定義（登録）されているか否かチェックす
る。

通常、入力した符号語は前回までの処理で辞書に登録
されているため、S5に進んで符号CODEに対応する文字列
code（ωＫ）を辞書から読み出し、S6で文字列Ｋを一時
的にスタックし、参照番号code（ω）を新たなCODEとし
て再度S5に戻り、このS5、S6の手順を再帰的に参照番号
ωが一文字に至るまで繰り返し、最後にS7に進んでS6で
スタックした文字をLIFO（Last In Fast Out）形式でポ
ップアップして出力する。同時にS7において、前回使っ
た符号ωと今回復元した文字列の最初の一文字Ｋを組
（ω、Ｋ）と表した文字列に、新たな参照番号を付加し
て辞書に登録する。

第９図（Ｃ）、（Ｄ）を参照して復号化処理を具体的
に説明すると次のようになる。

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

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

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

第９図（ｄ）の復号化では次の例外処理がある。

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

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

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

第７図の流れ図に示す手順で符号化すると、１つの文
字列を辞書探索するたびに最悪、辞書全体をサーチしな
ければならないために時間がかかった。そこで、従来は
辞書探索に外部ハッシュ法（open hashing、または、ch
aining）を用いて処理速度を上げていた（例えば、オー
ム社刊、情報処理学会編、情報処理バンドブック、を参
照のこと）。

第10図は外部ハッシュ法の説明図である。

文字列からなる集合Ｓを考えた時、Ｓの文字列ｘのあ
る位置を、文字列ｘからｘの格納位置のアドレスが直接
計算できる仕組みになっていると高速の探索ができる。
これを実現するのがハッシュ法である。

記憶場合（ハッシュ表）に０からｍ−１までのアドレ
スが付されているとすると、ハッシュ法では、関数 h:S→〔0,1,・・・,m−１〕を一つ定めて、Ｓの文字列ｘのアドレスをｈ（ｘ）で求
める。関数ｈをハッシュ関数、値ｈ（ｘ）をｘのハッシ
ュ・アドレスといっている。

ハッシュ法は、通常、Ｓの大きさがｍに比べてはるか
に大きい場合に用いられる。そこで、ｈをどのように選
んだとしても、Ｓの相異なる文字列x₁、x₂に対してｈ
（x₁）＝ｈ（x₂）となる場合が起こり得る。これを衝突
と呼び、衝突に対する対策の一つとして外部ハッシュ法
（open hashingまたは、chainig）が用いられる。

外部ハッシュ法は、第10図に示すように、ハッシュア
ドレスｉごとにリストを用意し、ｈ（ｘ）＝ｉとなるｘ
はそのリストの先頭から順にしまう。同じハッシュアド
レスをもつそれぞれのリストはバケット（bucket）と呼
ばれる。

第11図乃至第13図は従来技術の説明図であり、第11図
は探索木の一例、第12図はその文字列格納テーブルと外
部ハッシュテーブルの状態、第13図は辞書探索に外部ハ
ッシュ法を用いたLZW符号のフローチャートである。
（詳細については翔泳社刊、AP−Labo編著、ハードディ
スク・クックブック参照のこと）。

第12図において、文字列格納テーブル10bは、インデ
ックスｉに対するコードと文字ext〔ｉ〕が格納されて
おり、配列first100はインデックス（アドレス）ｉに対
する最初の連結インデックスfirst〔ｉ〕が、配列next1
01はそのインデックス（アドレス）ｉに対する次の連結
インデックスnext〔ｉ〕を格納する。

配列first100が第10図の外部ハッシュ法の索引dictin
aryに対応し、配列next101が第10図の連結リストに対応
する。

外部ハッシュ法では、新たな文字Ｋを入力したとき、
それまでの文字列の参照番号（ハッシュ・アドレス）ｉ
に文字Ｋを付加した文字列の参照番号を外部ハッシュ法
で求めるものである。

外部ハッシュ法により、参照番号ｉの文字列に一文字
を付加した文字列をｉをハッシュ・アドレス（索引）と
して引く。連結リストには、文字列ｉに付加された文字
がnameに格納してあり、nameの文字と文字Ｋの一致を検
査し、不一致なら逐次連結リストを手繰ることによっ
て、これまで出現した全ての一文字付加文字列を探索す
ることができる。もし、バケット中に文字Ｋを付加した
文字列がない場合は、最終的にリストの連結アドレス０
が得られ、該当する文字列が登録されていないことを知
ることができる。

次に、第11図に示すように、文字列“ab"、“ah"、
“az"、“abf"、“abx"、“ahd"、“ahf"、“azc"、“a
zg"、“azw"が辞書に登録されている場合に、文字列“a
zw"を検索する場合を例にとり、従来の検索法を説明す
る。

初期状態の文字列の格納テーブル10bの状態と外部ハ
ッシュテーブル10a（100、101）の様子を第12図に示す
通りである。

第１文字目の“a"は既に登録済みであり、２文字目の
“z"を検索するために、“a"をハッシュアドレスとして
配列fisrを引くと、P1が見つかる。従ってP1に格納され
ている“a"に続く文字列の“ab"が見つかる。しかし、
これとは一致しないので、今度はP1はハッシュアドレス
として配列nextを引くとP2となる。ここでP2に格納され
ている文字列の“ah"が見つかるが、これも一致しない
ので、更にP2をハッシュアドレスとして配列nextを引く
とP3が見つかる。ここで２文字目の文字“z"と一致す
る。

次に３文字目の文字“w"の検索に移る。３文字目の検
索は、先ずP3をハッシュアドレスとした配列firstを引
く。するとP8となり３文字目の“d"が検索される。しか
し一致しないので、今度はP8をハッシュアドレスとした
配列nextを引くとP9となる。しかし、これも一致しない
のでP9をハッシュアドレスとする配列nextをさらに引く
とP10となり、目的の３文字目の“w"が見つかる。検索
は第11図の〜の経路を通って行われる。

〔発明が解決しようとする課題〕

従来では、一度文字列が登録されると外部ハッシュテ
ーブルは固定となり、書き換えられることはなかった。

従って検索頻度の高い文字列でも、一度検索経路の長
い所に格納されると、毎回その長い経路を通って検索さ
れるので効率が悪く、登録が遅れたために、使用頻度の
高い文字列でも、同じハッシュアドレスを持つリストの
後の方に登録されていれば、検索に毎回時間がかかると
いう問題があった。

従って、本発明は、辞書中の登録部分列を高速に検索
し、符号化時間を短縮することができるデータ圧縮方法
を提供することを目的とする。

〔課題を解決するための手段〕

第１図は本発明の原理図である。

本発明は、第１図に示すように、符号化済データを相
異なる部分列に分けて、該部分列を辞書10に登録してお
き、連結する部分列の検索順を示す検索用リスト10aに
従って、入力データと該辞書10中の部分列を比較検索
し、入力データを該辞書10中の部分列の内、最大長一致
するものの参照番号で指定して符号化するデータ圧縮方
法において、検索された部分列を該検索用リスト10a中
の１つ前の部分列と置き換えるように該検索用リスト10
aを書き換えるものである。

又、本発明は、前記検索用リスト10aは、前記部分列
の文字数の少ないものから多いものに検索順を示してお
り、前記検索された部分列を前記検索用リスト10aの同
一文字数の部分列において１つ前にくるように前記検索
用リスト10aを書き換えるものである。

〔作用〕

本発明は、文字列の使用頻度を考慮して、一度検索さ
れた文字列は、同じハッシュアドレスを持つ文字列中の
１つ前に置き換える処理を行う。すると２回目の検索か
らは、同じ文字列を検索するのに検索回数が一文字につ
き一回少なつて済む。検索される度に、前へ前へと置き
換えられるので、検索回数が多いほど連結リスト中で、
同じハッシュアドレスを持つ文字列中の先頭の方に登録
されるようになる。

このため、辞書を用いた符号化を高速化でき、符号化
時間を短縮できる。

〔実施例〕

（ａ）一実施例の説明第２図は、本発明の一実施例処理フロー図、第３図乃
至第６図はその動作説明図である。

尚、S1〜S7は第７図のS1〜S7と同一である。

S1）プロセッサ（第１図参照）は、第１番目の文字を含
むように辞書10を初期化する。即ち、文字コードｌを辞
書10のアドレス、ｍ（＝ｌ）に登録する。

又、文字数に辞書10への現登録文字列数ｎをセットす
る。

更に文字列格納テーブル10bを用いて入力した最初の
文字Ｋを語頭文字列として参照番号（インデックス）ｉ
に変換する。

次に、辞書検索用配列first100のfirst〔NMAX〕、nex
t101のnext〔NMAX〕、文字列テーブル10bのext〔NMAX〕
を０に初期化する。

S2）プロセッサは、次の入力文字Ｋを読む。

S3）プロセッサは、次の文字Ｋがあるかを調べる。

S7）次の文字Ｋがなければ、文字Ｋの符号code（ω）を
出力して終了する。

S4、S5）一方、次の文字Ｋがあれば、辞書検索ステップ
に入る。

先ず、プロセッサは検索用インデックスｉを文字列ω
とし、登録用インデックスｊを０に、位置検知用インデ
ックスlkを０にする。

次に、配列first100を参照しインデックスｉの連結イ
ンデックスfirst〔ｉ〕を求め、インデックスｉにセッ
トする。

このインデック、ｉが「０」かを調べ、「０」でなけ
れば、文字列テーブル10bのインデックスｉの文字列ext
〔ｉ〕が入力文字Ｋかを調べる。

入力文字Ｋでなければ、登録用インデックスｊを位置
検知用インデックスlkにセーブし、検索用インデックス
ｉを登録用インデックスｊにセーブする。

更に、配列next101をインデックスｉで参照し、連結
インデックスnext〔ｉ〕を求め、インデックスｉにセッ
トし、インデックスｉ＝０かの判定に戻る。

S8）一方、文字列ext〔ｉ〕が入力文字「Ｋ」なら、位
置検知用インデックスlkが「０」かを判定する。

lkが「０」でないことは、３番目以降の連結インデッ
クスで入力文字Ｋが見付かったことになり、前の部分列
と入れ替えを行う。

即ち、インデックスｉをインデックスlkのnext〔lk〕
に移し、配列next101のインデックスｉのnext〔ｉ〕を
インデックスｊのnext〔ｊ〕に移し、インデックスｊを
next〔ｉ〕に移して、ステップへ戻る。

一方、lk＝０であると、２番目以前の連結インデック
スで入力文字Ｋが見付かったことになる。

そこで、登録用インデックスｊが「０」かを判定す
る。

ｊ＝０ということは、first〔ｉ〕、即ち連結の１番
目の連結インデックスで入力文字Ｋが見付かったことに
なり、入れ替えの必要がないため、ステップS2へ戻る。

一方、ｊ≠０であると、２番目以降の連結インデック
スで入力文字Ｋが見付かったことになり、先頭への入れ
替えを行う。

即ち、配列next101のインデックスｉのnext〔ｉ〕を
１つ前のインデックスｊのnext〔ｊ〕に移し、配列firs
t100のインデックスωのfirst〔ω〕をnext〔ｉ〕に移
し、インデックスｉをfirst〔ω〕に移す。

これによって、入力文字Ｋのインデックスｉが先頭に
書き換えられる。

そして、ステップS2へ戻る。

S6）ステップS4で、ｉ＝０なら辞書10にないため、登録
ステップに入る。

先ず、code（ω）を符号語として出力する。

次に、文字列数ｎをインデックスｉにセットし、文字
列数ｎをｎ＋１にインクリメントし、文字Ｋを文字列テ
ーブル10bのインデックスｉにnext〔ｉ〕として格納す
る。

次に、登録用インデックスｊが「０」かを調べる。

ｊ＝０なら、その段の文字列は１個のため、インデッ
クスｉ配列firstのfirst〔ω〕にセットする。

一方、ｊ≠０なら、その段の文字列は２個以上のた
め、インデックスｉを配列next〔ω〕にセットする。

そして、文字Ｋをインデックスｉにセットし、ステッ
プに戻る。

第３図乃至第６図を用いて具体例について説明する。

第３図（Ａ）のように、第11図と同一の例をとり、文
字列「azw」を検索することで説明する。

第３図（Ａ）の場合、文字列テーブル10b、配列first
100、配列next101は第３図（Ｂ）となる。

入力文字Ｋ＝Ｚを入力し、配列first、配列nextをた
どると、インデックスｉとして、next〔ｉ＝P2〕＝P3が
得られる。

この時、ext〔P3〕＝Ｚであるから、ｊ＝P2、lk＝P1
である。

従って、ステップS8で、lk≠０となり、第３図（Ａ）
のように「Ｚ」を１つ前の「ｈ」といれ代える。

即ち、第４図に示すように、ｉ＝P3をnext〔lk＝P1〕
に、next〔ｉ＝P3〕＝０をnext〔ｊ＝P2〕に、ｊ＝P2を
next〔ｉ＝P3〕にセットする。

これによって、連結状態は、第４図（Ａ）のように、
第３図（Ａ）の「Ｚ」と「ｈ」が入れ代わり、テーブル
状態は第４図（Ｂ）の如くなる。

次に、ステップS2に戻り、次文字「ｗ」が入力される
と、配列first100、配列next101を第５図（Ｂ）のよう
にたどり、インデックスｉとしてnext〔P9〕＝P10が得
られる。

この時、ext〔P10〕＝ｗであり、ｊ＝P9、lk＝P8であ
る。

従って、ステップS8で、lk≠０となり、第５図（Ａ）
のように「ｗ」を１つ前の「ｇ」と入れ代える。

即ち、ｉ＝P10をnext〔lk＝P8〕に、next〔ｉ＝P10〕
＝０をnext〔ｊ＝P9〕に、ｊ＝P9をnext〔ｉ＝P10〕に
セットする。

これによって連結状態は、第６図（Ａ）のように、第
５図（Ａ）の「ｇ」と「ｗ」が入れ代わり、テーブル状
態は第６図（Ｂ）の如くなる。

このように、検索文字が１文字づつ見つかる度に、ハ
ッシュテーブルの中身を同じハッシュアドレスを持つ文
字列中の１つ前に置き換えるうに書き換えていくことに
より、次回、同じ文字列の検索が行われた場合、前回よ
り短い経路で検索が行われ検索処理が高速化できる。こ
の方法は、一度検索されても連結リスト中の位置が１つ
ずつしか上がらないので、使用頻度の少ない文字列がき
た場合は、なかなか上がらず、使用頻度の高い文字列が
来た場合は、１回検索される度に確実に１個ずつ位置が
上がっていくので、検索頻度に対応した連結リスト構造
が構築できる。

またコード及び文字の登録処理と、ハッシュテーブル
配列first、配列nextの登録処理、連結リストの書き換
えと次文字への検索続行処理をそれぞれパイプラインで
行うようにすればより高速な符号化処理が行える。

（ｂ）他の実施例の説明上述の実施例の他に、本発明は次のような変形が可能
である。

ハッシュテーブルの形式は配列first、配列nextの
形式に限らず、他のものであってもよい。

code（ω）として、更にランレングス符号化等を用
いて圧縮してもよい。

文字列に限らず、符号化データ列であってもよい。

以上本発明を実施例により説明したが、本発明は本発
明の主旨に従い種々の変形が可能であり、本発明からこ
れらを排除するものではない。

〔発明の効果〕

以上説明した様に、本発明によれば，次の効果を奏す
る。

LZW符号化に際し、辞書検索をするとき、検索され
た文字列が常に最短経路で検索されるように外部ハッシ
ュテーブルを逐一書き直しながら検索を行うので、使用
頻度の高い文字列など検索経路が短くなり高速な検索処
理ができ、符号化が高速化される。

１つの前のものと置き代えるだけなので、それ程急
激に検索木を変えないので、比較的ランダム符号列の検
索の効率が向上する。

【図面の簡単な説明】

第１図は本発明の原理図、第２図は本発明の一実施例処理フロー図、第３図乃至第６図は本発明の一実施例動作説明図、第７図はLZW符号化処理フロー図、第８図はLZW復号化処理フロー図、第９図はLZW符号化、復号化説明図、第10図は外部ハッシュ法の説明図、第11図乃至第13図は従来技術の説明図である。図中、10……辞書、 10a……検索用リスト。

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

Claims

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

【請求項１】符号化済データを相異なる部分列に分け
て、該部分列を辞書（10）に登録しておき、連結する部分列の検索順を示す検索用リスト（10a）に
従って、入力データと該辞書（10）中の部分列を比較検
索し、入力データを該辞書（10）中の部分列の内、最大長一致
するものの参照番号で指定して符号化するデータ圧縮方
法において、検索された部分列を該検索用リスト（10a）中の１つ前
の部分列と置き換えるように該検索用リスト（10a）を
書き換えることを特徴とするデータ圧縮方法。
【請求項２】前記検索用リスト（10a）は、前記部分列
の文字数の少ないものから多いものに検索順を示してお
り、前記検索された部分列を前記検索用リスト（10a）の同
一文字数の部分列において１つ前にくるように前記検索
用リスト（10a）を書き換えることを特徴とする請求項（１）記載のデータ圧縮方法。