JPH0936747A - データ圧縮方法及びデータ圧縮装置 - Google Patents

Abstract

(57)【要約】 【課題】 ＬＺスライド辞書法によるデータ圧縮におい
てハッシュ法を用いてデータ検索を行うことにより、デ
ータ検索に時間を要すること無く、高速でデータの圧縮
を行うことができるデータ圧縮方法及びデータ圧縮装置
を提供する。 【解決手段】 データ入出力装置１によって圧縮処理対
象データをメモリ３上に読込むと、制御回路２は、圧縮
処理対象データ列と同じデータ列をハッシュ法によって
ハッシュ表より検索し、その検索されたデータ列と圧縮
処理対象データ列との各データを１データずつ比較して
両データ列の一致データ長を出力する。検索候補がなく
なるまで検索及び比較を繰返して、出力された一致デー
タ長が最長であるデータ列を検索された先頭位置から始
まるデータ列の中から選択する。そして、選択されたデ
ータ列の先頭位置と一致データ長とを一致情報として出
力し、圧縮処理対象データ列の先頭位置を検索候補とし
てハッシュ表に登録するよう構成した。

Description

【発明の詳細な説明】

【０００１】

【発明が属する技術分野】本発明は、文章データ等のデ
ータを圧縮するデータ圧縮方法及びデータ圧縮装置に関
する。

【０００２】

【従来の技術】文章データ等のデータを圧縮するデータ
圧縮方法の一例として、ＬＺ（Lempel-Ziv）スライド辞
書法がある。このＬＺスライド辞書法は、図１２に示す
ように、圧縮処理対象であるデータをその先頭から検索
していき、１度出現したデータ列が再度出現した場合
は、以前に出現したデータ列の先頭アドレスと両データ
列で一致するデータの長さとを一致情報として、再度出
現したデータ列に置換えて出力することによりデータ圧
縮を行う方法である。

【０００３】このＬＺスライド辞書法においては、圧縮
対象データ列が以前に出現したデータであるか否かを検
索するために、様々なデータの検索法が用いられてい
る。例えば、２分木による検索法においては、入力デー
タ中に現れる各文字コードを先頭（根節点）として、順
次２つの節点に分岐して行く木構造をなす検索パスを構
成する。そして、ある文字コードとその後に続く文字コ
ードとについて、これらの文字コードを例えば１６進数
コードで表現した場合の大小の比較結果によって、後の
文字コードをどちらの節点に分岐させて配置するかを決
定して行く。

【０００４】

【発明が解決しようとする課題】しかしながら、上記２
分木による検索では、一つのデータ列を検索するのに節
点に配置された一文字毎に比較していくため、木の成長
状態がアンバランスになっている（検索パスの一部だけ
が長くなっている）場合には、その検索パスの最終の節
点（葉節点）に配置されたデータを検索するには、非常
に長い時間を要するという欠点がある。

【０００５】また、トライ木による検索法が採用される
こともあり、このトライ木の場合には、２分木に比べて
より高速に検索を行うことができる。しかし、上記トラ
イ木の場合、膨大なメモリ空間を必要とするという不具
合があった。

【０００６】本発明は上記課題を解決するもので、その
目的は、ＬＺスライド辞書法によるデータを圧縮する場
合に、データの検索を高速で実行できると共に、検索時
に必要なメモリ空間を極力少なくすることができるデー
タ圧縮方法及びデータ圧縮装置を提供するにある。

【０００７】

【課題を解決するための手段】本発明のデータ圧縮方法
は、ＬＺスライド辞書法を用いて文書データ等のデータ
を圧縮するデータ圧縮方法において、圧縮処理対象のデ
ータ中における圧縮処理済みデータの次の位置から始ま
る圧縮対象データ列と同じデータ列の候補を前記圧縮処
理済みデータの中からハッシュ法によって検索する検索
ステップと、この検索ステップにおいて検索されたデー
タ列と前記圧縮対象データ列とを比較して一致している
データ長を求める比較ステップと、前記圧縮対象データ
列と同じデータ列の候補を前記圧縮処理済みデータの中
から検索候補がなくなるまで前記検索ステップと前記比
較ステップを繰返し実行する繰返しステップと、前記比
較ステップにおいて求められた一致データ長の中から最
長のデータ長のデータ列を選択して出力する選択ステッ
プと、前記圧縮対象データ列をハッシュ法による検索候
補としてハッシュ表に登録する登録ステップとを備えた
ところに特徴を有する。

【０００８】この場合、繰返しステップにおいては、検
索及び比較を所定回数繰返した後打切るように構成する
ことが好ましい。また、検索及び比較の打切り回数は、
３乃至２０回に設定することが好ましい。更に、登録ス
テップにおいては、圧縮対象データ列をハッシュ法によ
る検索候補のうちの最初に検索される位置に登録するよ
うに構成することが良い。加えて、比較ステップにおい
て最長の一致データ長を検出したときの検索回数を統計
的に記憶することにより、繰返しステップにおける打切
り回数を自動的に最適化して決定するように構成しても
良い。

【０００９】本発明のデータ圧縮装置は、ＬＺスライド
辞書法を用いて文書データ等のデータを圧縮するデータ
圧縮装置において、圧縮処理対象のデータ中における圧
縮処理済みデータの次の位置から始まる圧縮対象データ
列と同じデータ列の候補を前記圧縮処理済みデータの中
からハッシュ法によって検索する検索手段と、この検索
手段により検索されたデータ列と前記圧縮対象データ列
とを比較して一致しているデータ長を求める比較手段
と、前記圧縮対象データ列と同じデータ列の候補を前記
圧縮処理済みデータの中から検索候補がなくなるまで検
索及び比較を繰返し実行する繰返し手段と、前記比較手
段により求められた一致データ長の中から最長のデータ
長のデータ列を選択して出力する選択手段と、前記圧縮
対象データ列をハッシュ法による検索候補としてハッシ
ュ表に登録する登録手段とを備えたところに特徴を有す
る。

【００１０】この構成の場合、繰返し手段は、検索及び
比較を所定回数繰返したら、その後の検索及び比較を打
切るように構成することが良い。また、繰返し手段にお
ける打切り回数は、３乃至２０回の何れかに設定するこ
とが好ましい。更に、登録手段を、圧縮対象データ列を
ハッシュ法による検索候補のうちの最初に検索される位
置に登録するように構成することも良い。そして、比較
手段により最長の一致データ長を検出したときの検索回
数を統計的に記憶することにより、繰返し手段における
打切り回数を自動的に最適化して決定するように構成す
ることも好ましい構成である。

【００１１】上記手段によれば、圧縮対象データ列と同
じデータ列を圧縮処理済みデータの中からハッシュ法に
よって検索するから、データ列を高速で検索することが
できる。そして、このハッシュ法による検索時には、メ
モリ空間にハッシュ表を作成するが、このハッシュ表に
は、検索候補のデータ列の位置（圧縮処理済みデータ中
における位置）を登録するだけであり、実際のデータを
登録しないから、ハッシュ表はそれほど大きなメモリ空
間を使用しない。また、ハッシュチェーンも、検索候補
のデータ列の位置をチェーン状に登録するだけであり、
実際のデータを登録しないから、それほど大きなメモリ
空間を使用しない。

【００１２】また、検索及び比較を所定回数繰返した
後、打切るように構成すると、データの検索をより一層
高速に実行できる。更に、検索及び比較を打切る回数
を、３乃至２０回に設定すると、データの圧縮効率を十
分良好なものとしながら、圧縮処理に要する時間も十分
短くすることができる。加えて、圧縮対象データ列をハ
ッシュ法による検索候補のうちの最初に検索される位置
に登録するように構成すると、最長の一致データ長を早
く得る確率を高くすることができる。また、比較ステッ
プにおいて、最長の一致データ長を検出したときの検索
回数を統計的に記憶することにより、繰返しステップに
おける打切り回数を自動的に最適化して決定するように
構成すると、データ圧縮効率及び圧縮処理速度を最適化
することができる。

【００１３】

【発明の実施の形態】以下本発明の第１実施例につい
て、図１乃至図１０を参照して説明する。データ圧縮装
置の電気的構成を示す図１において、データの入出力手
段であるデータ入出力装置１は例えばＳＣＳＩインター
フェイスなどからなり、圧縮対象となるデータファイル
が記憶されている例えばハードディスクやフロッピーデ
ィスクなどの図示しない外部記憶装置に対してデータの
入出力を行う機能を有している。上記データ入出力装置
１は、マイコンなどからなる制御回路２とアドレス及び
データバスライン並びに制御信号線を介して接続されて
いる。上記制御回路２には、メモリ３がアドレス及びデ
ータバスライン並びに制御信号線を介して接続されてい
る。

【００１４】また、制御回路２には、データ圧縮処理を
実行制御するための制御プログタムが記憶されている。
そして、上記制御回路２は、検索手段である検索ロジッ
ク４、比較手段である一致比較ロジック５、選択手段で
ある選択ロジック６、データ圧縮ロジック７、並びに、
登録手段である登録ロジック８としての各機能を有する
ように構成されている。そして、制御回路２は、繰返し
手段としての機能をも有している。以下、上記各ロジッ
クの機能について説明する。まず、検索ロジック４は、
メモリ３上に読込まれた圧縮対象データファイル中の圧
縮対象データ列に対してハッシング（ハッシュ関数によ
る演算）を行い、その圧縮対象データ列と同じデータ列
を、後述する検索表に先頭位置を示す位置情報が書込ま
れて登録されているデータ列の中から検索する機能を有
している。

【００１５】一致比較ロジック５は、圧縮対象データ列
と、検索ロジック４によって検索された先頭位置から始
まるデータ列とを１データ（例えば１文字）ずつ比較し
て、両者で一致しているデータ長を出力する機能を有し
ている。選択ロジック６は、一致比較ロジック５によっ
て出力される一致データ長が最長であるデータ列を、検
索ロジック４により検索された先頭位置から始まるデー
タ列の中から選択する機能を有している。データ圧縮ロ
ジック７は、選択ロジック６によって選択されたデータ
列の先頭位置と、一致比較ロジック５がそのデータ列に
ついて出力した一致データ長とを一致情報として出力す
るものである。そして、登録ロジック８は、圧縮処理対
象データ列の先頭位置を検索候補である位置情報として
ハッシュ表に登録するものである。

【００１６】次に、上記実施例の作用について図２乃至
図１０を参照して説明する。尚、図２及び図３に示すフ
ローチャートは、制御回路２の制御プログラムの制御内
容、即ち、データ圧縮処理の概略制御内容を示すもので
ある。また、圧縮対象データ（ファイル）として、図４
（ａ）に示すような文字を並べて成るデータを用いる。
この文字列のデータをデータ圧縮装置によって圧縮する
場合、操作者はデータ圧縮装置の図示しないキーボード
などの入力手段を操作することにより、圧縮対象データ
ファイルのファイル名を指定すると共に、圧縮処理の実
行コマンドを入力する。すると、制御回路２は、上記指
定されたデータファイルをデータ入出力装置１を介して
外部記憶装置から読込んでメモリ３上に転送した後、デ
ータ圧縮処理を開始する。

【００１７】まず、図２のフローチャートにおいて、
「初期処理」の処理ステップＲ１を実行する。ここで
は、制御回路２は、メモリ３における圧縮処理に使用す
る領域のの初期化などを行う。続いて、「検索処理」の
処理ステップＲ２に移行する。この「検索処理」は、図
３のフローチャートによって示されるサブルーチンとし
て定義されており、以下この図３のフローチャートに従
って説明する。

【００１８】図３に示すように、制御回路２は、メモリ
３上に設けられた検索処理に関する領域の初期化を行い
（ステップＳ１）、続いて、次の「データ検索」を実行
する（ステップＳ２）。ここでは、検索ロジック４によ
って、ハッシングを行うためにメモリ３より図４（ａ）
に示すデータ列の０番目（第０アドレス）の文字データ
「Ａ」と、１番目（第１アドレス）の文字データ「Ｂ」
の２文字を読出す。この場合、ハッシュ関数として排他
的論理和を選び、第０アドレスの文字データ「Ａ」のＪ
ＩＳコード0x41と、第１アドレスの文字データ「Ｂ」の
ＪＩＳコード0x42との排他的論理和を論理演算して、ハ
ッシュ値0x03を得る。そして、このハッシュ値0x03によ
ってハッシュ表の検索を行うように構成されている。

【００１９】上記ハッシュ表はハッシュ値をインデック
スとして、そのハッシュ値を持つ文字列の先頭位置（ア
ドレス）が位置情報として登録されている表（データテ
ーブル）であり、メモリ３上に展開されている。尚、前
記ステップＲ１の初期化において、ハッシュ表及び後述
するハッシュチェーンには例えば全ビット「１」のデー
タ（0xFFFF…）が書込まれるように構成されており、こ
れにより、データの登録が無い状態となっている。従っ
て、この時点でハッシュ値0x03によってハッシュ表のデ
ータ検索を行って登録されているデータを読出すと、”
登録データなし”を検出する（図５参照）。尚、ハッシ
ュ表とハッシュチェーンとを合わせたものを、検索表
（検索対象）として定義する。

【００２０】続いて、「登録データなしか？」の判断を
行う（ステップＳ３）。この時点では”登録データな
し”を検出しているので、ステップＳ３にて「ＹＥＳ」
へ進み、図２に示すステップＲ３へ移行し、「検索結果
出力」の処理を実行する。ここでは、データ圧縮ロジッ
ク７によって、ステップＲ２で行われた検索処理の結果
を、出力データ列として図４（ｂ）に示すような形式で
出力するものである。尚、図４（ｂ）に示すように、圧
縮処理された出力データ列の第０アドレスには管理部が
配置されるが、この管理部の設定については後述する。

【００２１】また、上記ステップＲ３においては、ステ
ップＲ２の検索処理の結果、最長一致データ長が所定値
（例えば「３」）以上か否かを判断してデータを出力す
る。具体的には、この時点では、ステップＳ３で登録デ
ータを検出できなかったので一致情報の出力は行われ
ず、最長一致データ長は初期化されたまま「０」であ
り、所定値「３」未満であるから、第１アドレスに文字
データ「Ａ」をそのまま出力する。そして、「ハッシュ
表への登録」の処理を実行する（ステップＲ４）。ここ
では、ハッシュ表への位置情報の登録を行う。この登録
処理は、図６乃至１０に示す概念図のようにして実行さ
れる。

【００２２】具体的には、この時点での検索結果は、ハ
ッシュ表のインデックス0x03に対して登録されているデ
ータは一つも無かったので、ハッシュ表に先頭のデータ
「Ａ」の位置（アドレス）を示す位置情報「０」を、”
登録データなし”を示すコードに上書きして登録する
（図６参照）。そして、圧縮対象データ列のポインタを
インクリメントして、検索ロジック４が次に第１アドレ
スの文字データ「Ｂ」に注目するようにする。また、ル
ープカウンタをインクリメントする。

【００２３】続いて、「処理したデータ数分ループした
か？」の判断を行う（ステップＲ５）。ここでは、処理
データ数とループカウンタのカウント値とを比較するこ
とにより、ステップＲ４におけるハッシュ表への登録処
理を処理データ数分ループして実行したか否かを判断す
る。ここで、処理データ数は、選択ロジック６によって
得られる最長一致データ長が「３」以上の場合、後述す
るように圧縮処理が行われるため、その一致データ長に
等しく設定される数値である。そして、最長一致データ
長が「０」または「２」の場合は圧縮処理は行われず、
１文字データがそのまま出力されるので、処理データ数
は「１」と設定される数値である（最長一致データ長
「１」は出力されない）。

【００２４】そして、この時点では、最長一致データ長
は「０」であって処理データ数は「１」に設定されてい
るから、ループカウンタのカウント値「１」に等しく、
判断ステップＲ５において「ＹＥＳ」へ進み、「データ
終わり？」の判断を行う（ステップＲ６）。ここでは、
圧縮対象データ列を最後まで処理したか否かが判断され
るが、この時点ではまだ終りでないから、ステップＲ６
にて「ＮＯ」へ進み、ステップＲ２へ戻る。尚、ステッ
プＲ４及びＲ５は、登録ステップに対応している。

【００２５】続いて、ステップＲ２においては、前回と
同様にしてステップＳ１で最長一致データ長の初期化が
行われた後、ステップＳ２に移行して、今度は第１アド
レスの文字データ「Ｂ」と第２アドレスの文字データ
「Ｃ」とでハッシングを行い、ハッシュ値0x01を得る。
そして、インデックス0x01によってハッシュ表の検索を
行うが、やはり”登録データなし”を検出し、次のステ
ップＳ３で「ＮＯ」へ進み、ステップＲ３へ移行する。

【００２６】このステップＲ３においては、前回と同様
にして、出力データ列の第２アドレスに文字データ
「Ｂ」をそのまま出力する。そして、ステップＲ４に移
行し、ハッシュ表のインデックス0x01の領域に文字デー
タ「Ｂ」の位置（アドレス）を示す位置情報「１」を書
込んで登録する。また、圧縮対象データ列のポインタを
インクリメントして次は第２アドレスの文字データ
「Ｃ」に注目するようにしてから、次のステップＲ５に
移行する。このステップＲ５では、１文字だけ処理した
ので「ＹＥＳ」へ進み、ステップＲ６に移行する。この
ステップＲ６では、データはまだ終りではないので「Ｎ
Ｏ」へ進み、ステップＲ２に戻る。

【００２７】次の第３及び第４アドレスの文字列「Ｃ
Ｄ」、また第４及び第５アドレスの文字列「ＤＡ」につ
いても上記と同様に一致情報は出力されず、出力データ
列には文字データ「Ｃ」及び「Ｄ」をそのまま出力し、
ハッシュ表の各ハッシュ値のインデックスが示す領域に
は、位置情報「２」及び「３」がそれぞれ書込まれる。

【００２８】そして、圧縮処理対象データ列のポインタ
が「４」になると、ステップＳ２において第４及び第５
アドレスの文字列「ＡＢ」に対してハッシングが行われ
る。すると、ハッシュ値0x03を得るので、ハッシュ表の
検索を行うと登録データの位置情報「０」を得る（図６
参照）。よって、次の判断ステップＳ３では「ＮＯ」へ
進み、次の「同じデータ列か？」の判断ステップＳ４に
移行する。

【００２９】ここで、ハッシュ法は大集合から小集合へ
の写像を行うものであるから、異なるデータ列でも同一
のハッシュ値になる場合（衝突）がある。本実施例で
は、同じハッシュ値を示す文字列の位置情報は、全て同
一のインデックスに連なる連鎖的なデータ，所謂ハッシ
ュチェーン（以下、単にチェーンと称す）に登録される
ので、判断ステップＳ４においては、位置情報「０」の
データ列が現在の圧縮処理対象データ列と同じものであ
るかが確認される。そのため、判断ステップＳ４では、
一致比較ロジック５によって、圧縮処理対象データ列の
第０アドレスのデータ「Ａ」を読出して、第４アドレス
のデータ「Ａ」と比較し、一致の結果を得る。ここで、
同じハッシュ値において第１データが一致していれば第
２データも必ず一致するので確認は終了する。そして、
次の「１データずつ比較」の処理ステップＳ５に移行す
る。

【００３０】この処理ステップＳ５においては、文字列
の第３データ以降を１データずつ比較するため、一致比
較ロジック５により第２アドレスのデータ「Ｃ」及び第
６アドレスのデータ「Ｃ」を読出して比較し、一致の結
果を得る。次に第３アドレスのデータ「Ｄ」及び第７ア
ドレスのデータ「Ｅ」を読出して比較すると不一致の結
果を得るので、ここまでの一致データ長「３」を、メモ
リ３の現在の一致データ長の記憶領域に書込んで記憶さ
せる。尚、ステップＳ４及びＳ５は、比較ステップに対
応している。

【００３１】続いて、「最長一致長か？」の判断を行う
（ステップＳ６）。ここでは、選択ロジック７によっ
て、ステップＳ５において得られた現在の一致データ長
「３」が、最長一致データ長の領域に記憶されている内
容より大きいか否かが判断される。この場合、最長一致
データ長はステップＳ１で初期化されており「０」であ
るから、ステップＳ６にて「ＹＥＳ」へ進み、「一致位
置と最長一致長を更新」の処理を実行する（ステップＳ
７）。

【００３２】このステップＳ７においては、メモリ３上
の一致位置の記憶領域に「０」を、最長一致データ長の
記憶領域に「３」を書込んで記憶させる。そして、次の
「チェーンの次をとる」の処理ステップＳ８に移行す
る。尚、ステップＳ６及びＳ７は、選択ステップに対応
する。

【００３３】上記処理ステップＳ８においては、インデ
ックス0x03のチェーンの次の（この場合、第１）データ
を読出す。すると、”登録データなし”のコードが読出
されるので（図６参照）、次のステップＳ３では「Ｎ
Ｏ」へ進み、ステップＲ３へ移行する。尚、ステップＳ
２は検索ステップに対応し、ステップＳ３及びＳ８は繰
返しステップに対応する。

【００３４】そして、ステップＲ３では、ステップＲ２
の検索処理で得られた最長一致データ長が所定値「３」
以上であるので、データ圧縮ロジック７によって、出力
データ列の第５アドレスに一致情報として一致位置
「０」及び一致データ長「３」を、例えば各１バイトサ
イズとした２バイトサイズのデータとして書込む。そし
て、第５アドレスが一致情報であることを示すため、第
０アドレスの管理部に設定を行う。

【００３５】この管理部は、他の文字データと同じ１バ
イトサイズのデータであり、出力データ列の第０アドレ
スからデータ８個おきに挿入され、その内容は、その後
に続く８個のデータの内何データ目がデータ圧縮処理の
結果により出力された一致情報であるかを示すものであ
る。例えば、この場合設定を行うには、第０アドレスの
管理部の内容を読出すと、既に「１」が立てられている
ビットをクリアせずに新たな情報を付加するため、その
内容と第４ビット（第５アドレスに対応する）のみ
「１」を立てた１バイトデータとを排他的論理和により
論理演算する。この時点では、管理部の内容はステップ
Ｒ１における初期設定時に０クリアされているので、排
他的論理和により論理演算した結果は、図４（ｃ）に示
すように第４ビットのみ「１」となる。そして、ステッ
プＲ４に移行する。

【００３６】ステップＲ４においては、位置情報「４」
をハッシュ表に登録する。この時点では、図６に示すよ
うに、ハッシュ表のインデックス0x03が示す領域には位
置情報「０」が既に登録されているので、その位置情報
「０」をチェーンの第１領域に送出する。そして、ハッ
シュ表のインデックス0x03が示す領域に位置情報「４」
を書込んで更新登録する。この更新登録後の状態を図７
に示す。その後、圧縮処理対象データ列のポインタをイ
ンクリメントして「５」にすると、ループカウンタをイ
ンクリメントした後ステップＲ５に移行する。

【００３７】ステップＲ５においては、この時点での処
理データ数は、ステップＳ５において選択ロジック６に
より得られた最長一致データ長が「３」であるから
「３」と設定されており、ループカウンタは１であるか
ら「ＮＯ」と判断して、この後を２回ループしてステッ
プＲ４を２回実行する。即ち、文字列「ＢＣ」でハッシ
ングしてその位置情報「５」と、文字列「ＣＥ」でハッ
シングしてその位置情報「６」とを、ハッシュ表のそれ
ぞれのインデックスが示す領域に登録する。この処理の
終了時点で、圧縮処理対象データ列のポインタは「７」
である。そして、ステップＲ６では、データはまだ終了
ではないので「ＮＯ」と判断して、ステップＲ２に移行
する。

【００３８】ステップＲ２では、第７及び第８アドレス
の文字列「ＥＡ」について、上記と同様な処理により、
出力データ列への出力及びハッシュ表への登録を行う。
以下はデータ列「ＡＢ」に注目して説明する。第８及び
第９アドレスの文字列「ＡＢ」について処理を行う場
合、ステップＳ２でハッシングしてハッシュ表の検索を
行うと、位置情報「４」を得る（図７参照）。ステップ
Ｓ４及びＳ５において、第４アドレスから始まる文字列
について１データずつ比較をおこなうが、得られる一致
データ長は「２」である。従って、ステップＳ６では初
期化された最長一致データ長「０」と比較して「ＹＥ
Ｓ」と判断して、ステップＳ７に移行する。そして、ス
テップＳ７において一致位置「４」及び最長一致データ
長「２」を更新登録すると、ステップＳ８に移行する。

【００３９】ステップＳ８においては、インデックス0x
03のチェーンの第１領域に格納されたデータを読出す。
すると、位置情報「０」を得るので、ステップＳ３では
「ＮＯ」と判断してステップＳ４に移行し、更に、ステ
ップＳ４では「ＹＥＳ」と判断してステップＳ５に移行
する。この場合も、ステップＳ５において得られる一致
データ長は「２」であるので、以下同様にステップＳ
６，Ｓ８，Ｓ９，Ｓ１０，Ｓ３と移行して、ステップＳ
１０ではチェーンの第２領域に格納された”データな
し”コードを得るので、ステップＳ３では「ＹＥＳ」と
判断してステップＲ３に移行する。

【００４０】ステップＲ３においては、一致データ長が
「２」の場合はデータ圧縮効果がないので、先頭の文字
データ「Ａ」をそのまま出力データ列に出力する。そし
て、ステップＲ５でハッシュ表に登録されている位置情
報「４」をチェーンに送出し、位置情報「８」をハッシ
ュ表に登録する（図８参照）。以下、文字列「ＢＢ」及
び「ＢＡ」についても同様の処理を行う。

【００４１】次に、第１１及び第１２アドレスの文字列
「ＡＢ」について、検索処理を行う。まず、ハッシュ表
に登録された位置情報「８」について文字列の比較を行
うと、３文字目で異なるので一致データ長「２」を得
る。そして、次の検索処理でチェーンの第１領域に格納
された位置情報「４」を得て文字列の比較を行い、やは
り一致データ長「２」を得る。更に、次の検索処理でチ
ェーンの第２領域に格納された位置情報「０」を得て文
字列の比較を行う。すると、やはり一致データ長「２」
を得る。更に次の検索処理では”データなし”を検出し
て検索処理を終了するが、最長一致データ長は「２」で
あるから、結果として圧縮処理は実行されない。

【００４２】以降、文字列「ＡＢ」，即ちインデックス
0x03のチェーンは、図９及び図１０に示すように、入力
データの位置情報「１１」と「１６」がハッシュ表に順
次登録されることにより、位置情報データが順次チェー
ンに送出されて次第に長くなって行く。その中で最長の
一致データ長が得られたものを一致情報として文字列の
代わりに出力データ列に出力する。以下同様にして、デ
ータ圧縮処理を圧縮処理対象データの全てについて行う
と、ステップＲ６で「ＹＥＳ」へ進み、「後処理」の処
理ステップＲ７に移行する。このステップＲ７では、図
４（ｂ）に示す圧縮処理後のデータであるメモリ３上の
出力データを、データ入出力装置１によって外部記憶装
置へ出力して、データ圧縮処理を終了する。

【００４３】以上のように本実施例によれば、制御回路
２によって、圧縮処理対象のデータ中における圧縮処理
済みデータの次の位置から始まる圧縮対象データ列と同
じデータ列の候補を圧縮処理済みデータの中からハッシ
ュ法によって検索すると共に、この検索されたデータ列
と圧縮対象データ列とを比較して一致しているデータ長
を求める構成とした。そして、制御回路２によって、圧
縮対象データ列と同じデータ列の候補を圧縮処理済みデ
ータの中から検索候補がなくなるまで上記検索及び比較
を繰返し実行するように構成した。更に、制御回路２に
よって、上記比較により求められた一致データ長の中か
ら最長のデータ長のデータ列を選択して出力すると共
に、圧縮対象データ列をハッシュ法による検索候補とし
てハッシュ表に登録するように構成した。この構成によ
れば、圧縮処理対象データ列と同じデータ列の検索を行
うのにハッシュ法を用いているので、データ列の検索が
高速に実行できると共に、使用するメモリ空間を十分小
さくすることができる。

【００４４】図１１は本発明の第２実施例を示すもので
あり、第１実施例と同一部分には同一符号を付して説明
を省略し、以下異なる部分のみ説明する。図１１におい
ては、第１実施例における図２のフローチャートのステ
ップＳ７とステップＳ８との間に、「検索回数カウンタ
＋１」の処理ステップＳ９及び「検索回数＝制限回数
？」の判断ステップＳ１０を挿入するように構成されて
いる。そして、第２の実施例の他の構成は、第１実施例
と同じ構成である。

【００４５】次に、上記第２実施例の作用を説明する。
第２実施例では、ステップＳ７の処理を終えると、次の
「検索回数カウンタ＋１」の処理ステップＳ９に移行す
る。このステップＳ９においては、検索ロジック４によ
って一つのデータ列について検索表を１回検索すると、
ステップＳ１で初期化された検索回数カウンタを１カウ
ントアップして、次の「検索回数＝制限回数？」の判断
ステップＳ１０に移行する。

【００４６】このステップＳ１０においては、検索回数
カウンタのカウント値が、検索表の検索の制限回数とし
て予め決められている値に等しくなったか否かが判断さ
れる。この場合、制限回数は「３」に設定されている。
上記ステップＳ１０において、検索回数カウンタのカウ
ント値が制限回数に等しくなると、「ＹＥＳ」へ進み、
検索処理を完了する。また、ステップＳ１０において、
検索回数カウンタのカウント値が制限回数に等しくない
と（制限回数より小さいと）、「ＮＯ」へ進み、ステッ
プＳ８に移行する。尚、第１実施例における繰返しステ
ップにステップＳ９及びＳ１０を加えたものが、第２実
施例の繰返しステップに対応する。

【００４７】ここで、第２実施例においても、第１実施
例と同じ圧縮処理対象データについて圧縮処理を行うも
のとして、同様に文字列「ＡＢ」に注目して説明する。
図７に示すように、ハッシュ値0x03のインデックスが示
すハッシュ表に文字列「ＡＢ」の位置情報「４」が登録
されている段階までは、ステップＳ９における検索回数
カウンタのカウント値は「３」未満であり、ステップＳ
１０においては「ＮＯ」と判断してステップＳ８に移行
するので、第１実施例と同様に処理される。

【００４８】そして、図８に示す、次の位置情報「８」
が登録された段階で、第１１及び第１２アドレスの文字
列「ＡＢ」について検索を行うと、ステップＳ８におい
てチェーンの第２領域にある位置情報「０」を読出した
後、ステップＳ３乃至Ｓ７まで同様に処理を行い、次の
ステップＳ９において検索回数カウンタのカウント値は
制限回数である「３」に達する。すると、ステップＳ１
０にて「ＹＥＳ」へ進むから、それ以上の検索及び比較
を行うこと無く検索処理を打切るように構成されてい
る。

【００４９】また、図９及び１０に示すように、その後
にデータ圧縮処理が進んで位置情報「１１」と「１６」
がハッシュ表に順次登録されることによりチェーンが更
に長くなった場合でも、この後に圧縮処理対象データ列
中に文字列「ＡＢ」が出現した場合は、ステップＲ２で
の検索処理は３回だけ，即ち、位置情報「１６」，「１
１」及び「８」についてのみ行ってそれ以上の検索表の
検索は行なわず、その中で最長の一致データ長が得られ
たものを一致情報として出力データ列に出力するように
構成されている。

【００５０】尚、第２実施例では、検索表内に出現して
いる一致データ列全てについて検索を行わないため、最
長の一致データ長が得られない可能性がある。しかし、
一般的な文章データの特徴として、「最長の一致長を有
するデータ列は、注目している位置の直ぐ近くに現れや
すい」という性質がある。従って、第２実施例のよう
に、最新の一致データ列から３回だけ検索する方式を用
いても、圧縮効率の劣化は殆ど無いのである。

【００５１】以上のように第２実施例によれば、検索処
理を行う回数をカウントして、予め３回として設定され
た制限回数に等しくなると検索を打切り、その時点で最
長の一致データ長を示したデータ列の先頭位置とその一
致データ長とを一致情報として出力するように構成した
ので、一致データ列がなくなるまで検索表の検索を反復
する第１実施例とは異なり、検索に要する時間はチェー
ンが長くなった場合でも毎回同じとなり、データ圧縮処
理をより一層高速に実行することができる。しかも、こ
の場合、データ圧縮効率を低下させることはほとんどな
い。

【００５２】尚、本発明は上記し且つ図面に記載した実
施例にのみ限定されること無く、次のような変形が可能
である。まず、文字データの１６進数コードをＪＩＳコ
ードとしたが、ＥＢＣＤＩＣコード若しくはＡＳＣＩＩ
コードでも良い。また、ハッシュ関数を排他的論理和と
したが、これに限らず、衝突の発生がなるべく少なくな
るような適当な演算（論理演算に限らない）を適宜選択
するように構成しても良い。更に、ステップＲ３におい
て、一致情報を出力する最長一致データ長の所定値を
「３」としたが、「４」以上の適当な値に設定しても良
い。加えて、ハッシングの対象とする文字数を３文字以
上としても良い。

【００５３】また、一致情報のデータ（２バイトのデー
タ）は、一致位置（アドレス）を表わす１バイトのデー
タと、一致データ長を表わす１バイトのデータとから構
成したが、これに限らず、圧縮対象データの大きさと予
想される最大一致データ長との兼合いによって適宜変更
しても良く、例えば一致位置のサイズを１２ビット、一
致データ長のサイズを４ビットとしても良い。更に、一
致情報のデータサイズは２バイトに限らず、圧縮処理対
象データの大きさに応じてビット数が更に必要な場合
は、例えば３バイトとしても良い。この場合、その一致
情報のデータサイズに応じて圧縮効率を考慮し、一致情
報を出力する最低の一致データ長を「３」から「４」に
するなど、適宜変更して良い。

【００５４】更にまた、圧縮処理対象データは、アルフ
ァベットなどからなる言語の文章に限らず、日本語など
のその他の言語でも良い。また、言語の１文字を表現す
る１６進数コードが２バイトである場合は、管理部を、
そのデータサイズを２バイトとして、１６文字毎に１個
付加するように構成しても良い。

【００５５】また、反復ロジックにおける検索の制限回
数（打切り回数）を３回としたが、この回数は、データ
圧縮効率と処理速度とを考慮して、どちらをより重視す
るかによって適宜決定すれば良い。例えば、圧縮効率を
重視する場合は検索制限回数を大きな値に設定し、処理
速度を重視する場合は検索制限回数を小さな値に設定す
る。データ圧縮効率と処理速度との適当なバランスを重
視して決定する場合は、検索制限回数は３乃至２０回の
何れかに設定することが望ましい。この場合、最も好ま
しい制限回数は、１０回前後である。また、圧縮処理対
象とするデータの性質に応じて、ユーザーが検索の制限
回数を指定可能にするように構成しても良い。

【００５６】一方、上記各実施例においては、最新の圧
縮対象データ列をハッシュ表の最初に検索される位置に
登録するように構成したが、これに限られるものではな
く、最新の圧縮対象データ列を一番最後に検索される位
置に登録するように構成しても良い。

【００５７】また、上記各実施例のステップＳ５におい
て、限界として規定される最長一致データ長（最長一致
データ長の記憶領域の物理的な制限，若しくは、文章デ
ータの性質からこれ以上の一致データ長は有り得ないと
想定されるもの）を検出した場合は、それ以降の検索を
打切るように構成しても良い。この構成によれば、更に
圧縮処理を高速にすることができる。

【００５８】更に、図１１のフローチャートの「リター
ン」の直前に、「検索回数を記憶」の処理ステップＳ１
１を設け、データ列の検索毎に、最長の一致長が検出さ
れたデータ列が何回目の検索で見付かったか、その検索
回数をメモリ３に記憶させるように構成する。そして、
データ圧縮処理がある程度進んだ段階で、「検索回数最
適化処理」の処理ルーチンを実行するように構成しても
良い。この処理ルーチンにおいては、ステップＳ１１で
記憶させた検索回数に対して適当な統計処理を行うこと
によって、圧縮効率が十分良い範囲で且つ検索処理時間
を十分短縮できる検索回数を自動的に求めて設定する
（最適化する）ことができるように構成されている。

【００５９】尚、上記各実施例や変形例等によって圧縮
処理して出力した出力データに対して、例えば算術符号
化などの他の圧縮方法を適用して更にデータ圧縮するよ
うに構成しても良く、このように構成すると、更にデー
タ圧縮効率を高めることができる。

【００６０】

【発明の効果】本発明は、以上の説明から明らかなよう
に、ＬＺスライド辞書法を用いて文書データ等のデータ
を圧縮するデータ圧縮処理において、圧縮対象データ列
と同じデータ列を圧縮処理済みデータの中からハッシュ
法によって検索する構成としたので、データ列を高速で
検索することができると共に、検索時に必要なメモリ空
間を極力少なくすることができる。

【００６１】また、この構成の場合、検索及び比較を所
定回数繰返した後、打切るように構成すると、データの
検索及びそれに伴うデータ圧縮処理をより一層高速に実
行できる。更に、検索を打切る回数を、３乃至２０回の
何れかに設定すると、データの圧縮効率と圧縮処理速度
との適度なバランスをとることができる。そして、最新
の圧縮対象データ列をハッシュ法による検索候補のうち
の最初に検索される位置に登録するように構成すると、
最長の一致データ長を得る確率を高めることができる。
また、最長の一致データ長を検出したときの検索回数を
統計的に記憶することにより、検索を打切る回数を自動
的に最適化して決定するように構成すると、データ圧縮
効率及び圧縮処理速度を最適化することができる。

【図面の簡単な説明】

【図１】本発明の第１実施例の構成を示すブロック図

【図２】制御内容のフローチャート

【図３】図２のステップＲ２の制御内容のフローチャー
ト

【図４】入力データ及び出力データ並びに管理部の内容
を示す図

【図５】初期化された状態の検索表の内容を示す概念図

【図６】ハッシュ表の更新登録処理を示す概念図

【図７】図６相当図

【図８】図６相当図

【図９】図６相当図

【図１０】図６相当図

【図１１】本発明の第２実施例を示す図２相当図

【図１２】ＬＺスライド辞書法によるデータ圧縮処理の
概念図

【符号の説明】

１はデータ入出力装置、４は検索ロジック（検索手
段）、５は一致比較ロジック（比較手段）、６は選択ロ
ジック（選択手段）、７はデータ圧縮ロジック、８は登
録ロジック（登録手段）を示す。

Claims (10)

【特許請求の範囲】
1. 【請求項１】 ＬＺスライド辞書法を用いて文書データ
   等のデータを圧縮するデータ圧縮方法において、 圧縮処理対象のデータ中における圧縮処理済みデータの
   次の位置から始まる圧縮対象データ列と同じデータ列の
   候補を前記圧縮処理済みデータの中からハッシュ法によ
   って検索する検索ステップと、 この検索ステップにおいて検索されたデータ列と、前記
   圧縮対象データ列とを比較して一致しているデータ長を
   求める比較ステップと、 前記圧縮対象データ列と同じデータ列の候補を前記圧縮
   処理済みデータの中から検索候補がなくなるまで前記検
   索ステップと前記比較ステップを繰返し実行する繰返し
   ステップと、 前記比較ステップにおいて求められた一致データ長の中
   から最長のデータ長のデータ列を選択して出力する選択
   ステップと、 前記圧縮対象データ列をハッシュ法による検索候補とし
   てハッシュ表に登録する登録ステップとを備えたことを
   特徴とするデータ圧縮方法。
2. 【請求項２】 前記繰返しステップにおいては、検索ス
   テップ及び比較ステップを所定回数繰返したら、その後
   の検索ステップ及び比較ステップを打切るように構成さ
   れていることを特徴とする請求項１記載のデータ圧縮方
   法。
3. 【請求項３】 前記繰返しステップにおける打切り回数
   は、３乃至２０回に設定されていることを特徴とする請
   求項２記載のデータ圧縮方法。
4. 【請求項４】 前記登録ステップにおいては、前記圧縮
   対象データ列をハッシュ法による検索候補のうちの最初
   に検索される位置に登録することを特徴とする請求項１
   乃至３の何れかに記載のデータ圧縮方法。
5. 【請求項５】 前記比較ステップにおいて最長の一致デ
   ータ長を検出したときの検索回数を統計的に記憶するこ
   とにより、前記繰返しステップにおける打切り回数を自
   動的に最適化して決定することを特徴とする請求項２ま
   たは４記載のデータ圧縮方法。
6. 【請求項６】 ＬＺスライド辞書法を用いて文書データ
   等のデータを圧縮するデータ圧縮装置において、 圧縮処理対象のデータ中における圧縮処理済みデータの
   次の位置から始まる圧縮対象データ列と同じデータ列の
   候補を前記圧縮処理済みデータの中からハッシュ法によ
   って検索する検索手段と、 この検索手段により検索されたデータ列と、前記圧縮対
   象データ列とを比較して一致しているデータ長を求める
   比較手段と、 前記圧縮対象データ列と同じデータ列の候補を前記圧縮
   処理済みデータの中から検索候補がなくなるまで検索及
   び比較を繰返し実行する繰返し手段と、 前記比較手段により求められた一致データ長の中から最
   長のデータ長のデータ列を選択して出力する選択手段
   と、 前記圧縮対象データ列をハッシュ法による検索候補とし
   てハッシュ表に登録する登録手段とを備えたことを特徴
   とするデータ圧縮装置。
7. 【請求項７】 前記繰返し手段は、検索及び比較を所定
   回数繰返したら、その後の検索及び比較を打切るように
   構成されていることを特徴とする請求項６記載のデータ
   圧縮装置。
8. 【請求項８】 前記繰返し手段における打切り回数は、
   ３乃至２０回に設定されていることを特徴とする請求項
   ７記載のデータ圧縮装置。
9. 【請求項９】 前記登録手段は、前記圧縮対象データ列
   をハッシュ法による検索候補のうちの最初に検索される
   位置に登録することを特徴とする請求項６乃至８の何れ
   かに記載のデータ圧縮装置。
10. 【請求項１０】 前記繰返し手段は、前記比較手段によ
    り最長の一致データ長を検出したときの検索回数を統計
    的に記憶することにより、検索及び比較の打切り回数を
    自動的に最適化して決定することを特徴とする請求項６
    または９記載のデータ圧縮装置。