(57)【特許請求の範囲】
【請求項１】
被圧縮データ列に圧縮処理を行って圧縮データを作成するデータ圧縮方法において、
被圧縮データ列内の連続する複数の文字を検索する文字列に設定する文字列設定工程と、
前記文字列を表現するビット列中の各ビットを少なくとも２個のコードに振り分けて第１、第２の検索用コードを生成する検索用コード振り分け工程と、
前記第１、第２の検索用コードをそれぞれ配列のアドレスとして用いて予め過去の文字列の出現位置に関する情報が登録された第１、第２の配列テーブルから第１、第２の配列内容を取得する、配列内容取得工程と、
前記取得した第１、第２の配列内容を照合する照合工程と、
前記照合した第１、第２の配列内容が一致したとき、前記第１または第２の配列内容に基づいて前記文字列に対する過去の出現位置情報を取得する出現位置情報取得工程と、を備える、データ圧縮方法。
【請求項２】
被圧縮データ列に圧縮処理を行って圧縮データを作成するデータ圧縮方法において、
被圧縮データ列内の連続する複数の文字を検索する文字列に設定する文字列設定工程と、
前記文字列を表現するビット列中の各ビットを２個のコードに振り分けて検索用の第１のコードと該第１のコードの相補コードである第２のコードを生成する検索用コード振り分け工程と、
現時点で検索すべき文字列に関する前記第１のコードを配列のアドレスとして用いて、過去に出現した文字列に関する前記第２のコードが予め登録された第１の配列テーブルから、配列の内容を取得する、配列内容取得工程と、
前記取得した配列内容と前記第２のコードを照合する照合工程と、
前記照合結果が一致の場合、前記第１のコードを配列のアドレスとして用いて予め過去の文字列の出現位置に関する情報が登録された第２の配列テーブルから前記設定された文字列の過去の出現位置に関する情報を取得する出現位置情報取得工程と、を備える、データ圧縮方法。
【請求項３】
被圧縮データ列に圧縮処理を行って圧縮データを作成するデータ圧縮方法において、
被圧縮データ列内の連続する複数の文字を検索する文字列に設定する文字列設定工程と、
前記文字列を表現するビット列中の各ビットを２個のコードに振り分けて検索用の第１のコードと該第１のコードの相補コードである第２のコードを生成する検索用コード振り分け工程と、
前記第１のコードに演算を行って前記第１のコードを起点とする複数のコードを取得する、演算工程と、
現時点で検索すべき文字列に関する前記取得された複数のコードを配列のアドレスとして用いて、過去に出現した文字列に関する前記第２のコードが予め登録された第１の配列テーブルから、複数の配列内容を取得する、配列内容取得工程と、
前記取得した複数の配列内容と前記第２のコードとを照合する照合工程と、
前記照合結果が一致の場合、前記演算工程で得られたコードを配列のアドレスとして用いて、予め過去の文字列の出現位置に関する情報が登録された第２の配列テーブルから前記設定された文字列の過去の出現位置に関する情報を取得する出現位置情報取得工程と、を備える、データ圧縮方法。
【請求項４】
前記演算工程における演算は、掛け算またはシフト演算の何れか一方である、請求項３に記載のデータ圧縮方法。
【請求項５】
さらに、前記取得された出現位置情報を符号化して出力する符号化工程を備える、請求項１乃至４の何れか１項に記載のデータ圧縮方法。
【請求項６】
前記符号化工程は、
前記出現位置情報取得工程において前記文字列に対する過去の出現位置にかかる情報を取得できたときにコピー符号を出力するコピー符号生成工程と、
前記出現位置情報取得工程において前記文字列に対する過去の出現位置にかかる情報を取得できなかったときにリテラル符号を出力するリテラル符号生成工程とを有する、請求項５に記載のデータ圧縮方法。
【請求項７】
前記コピー符号生成工程は、
前記出現位置情報取得工程において得られた前記設定された文字列の出現位置を起点として当該起点以降のアドレスに対応する配列の内容と前記設定された文字列以降の文字列とが連続して一致する文字列長を一致長情報として求める一致長算出工程と、
前記過去の出現位置情報と前記一致長情報とを符号化して出力する符号化出力工程とを有する、請求項６に記載のデータ圧縮方法。
【請求項８】
前記リテラル符号生成工程は、前記設定された文字列の最初の文字の入力データをそのまままたは符号化して出力する工程を有する、請求項６または７に記載のデータ圧縮方法。
【請求項９】
前記第１および第２のコードは、前記設定された文字列の各文字を表すビット列の複数の下位ビットおよび複数の上位ビットが比較的均等に両者に分配される様に振り分けられる、請求項１に記載のデータ圧縮方法。
【請求項１０】
前記第１および第２のコードは、前記設定された文字列の各文字を表すビット列の最下位ビットが比較的均等に両者に分配される様に振り分けられる、請求項１または９に記載のデータ圧縮方法。
【請求項１１】
前記第１および第２のコードは、前記設定された文字列の各文字を表すビット列の最下位ビットを共通に含む様に振り分けられる、請求項１に記載のデータ圧縮方法。
【請求項１２】
前記第１のコードは、前記設定された文字列の各文字を表すビット列の下位複数のビットで構成され、前記第２のコードは、その上位複数のビットで構成されている、請求項２または３に記載のデータ圧縮方法。
【請求項１３】
被圧縮データ列に圧縮処理を行って圧縮データを作成するデータ圧縮装置において、
被圧縮データ列内の連続する複数の文字を検索する文字列に設定する文字列設定手段と、
前記文字列を表現するビット列中の各ビットを少なくとも２個のコードに振り分けて第１、第２の検索用コードを生成する検索用コード振り分け手段と、
前記第１、第２の検索用コードをそれぞれ配列のアドレスとして用いて予め過去の文字列の出現位置に関する情報が登録された第１、第２の配列テーブルから第１、第２の配列内容を取得する、配列内容取得手段と、
前記取得した第１、第２の配列内容を照合する照合手段と、
前記照合した第１、第２の配列内容が一致したとき、前記第１または第２の配列内容に基づいて前記文字列に対する過去の出現位置情報を取得する出現位置情報取得手段と、を備える、データ圧縮装置。
【請求項１４】
被圧縮データ列に圧縮処理を行って圧縮データを作成するデータ圧縮装置において、
被圧縮データ列内の連続する複数の文字を検索する文字列に設定する文字列設定手段と、
前記文字列を表現するビット列中の各ビットを２個のコードに振り分けて検索用の第１のコードと該第１のコードの相補コードである第２のコードを生成する検索用コード振り分け手段と、
現時点で検索すべき文字列に関する前記第１のコードを配列のアドレスとして用いて、過去に出現した文字列に関する前記第２のコードが予め登録された第１の配列テーブルから、配列の内容を取得する、配列内容取得手段と、
前記取得した配列内容と前記第２のコードを照合する照合手段と、
前記照合結果が一致の場合、前記第１のコードを配列のアドレスとして用いて予め過去の文字列の出現位置に関する情報が登録された第２の配列テーブルから前記設定された文字列の過去の出現位置に関する情報を取得する出現位置情報取得手段と、を備える、データ圧縮装置。
【請求項１５】
被圧縮データ列に圧縮処理を行って圧縮データを作成するデータ圧縮装置において、
被圧縮データ列内の連続する複数の文字を検索する文字列に設定する文字列設定手段と、
前記文字列を表現するビット列中の各ビットを２個のコードに振り分けて検索用の第１のコードと該第１のコードの相補コードである第２のコードを生成する検索用コード振り分け手段と、
前記第１のコードに演算を行って前記第１のコードを起点とする複数のコードを取得する、演算手段と、
現時点で検索すべき文字列に関する前記取得された複数のコードを配列のアドレスとして用いて、過去に出現した文字列に関する前記第２のコードが予め登録された第１の配列テーブルから、複数の配列内容を取得する、配列内容取得手段と、
前記取得した複数の配列内容と前記第２のコードとを照合する照合手段と、
前記照合結果が一致の場合、前記演算手段で得られたコードを配列のアドレスとして用いて、予め過去の文字列の出現位置に関する情報が登録された第２の配列テーブルから前記設定された文字列の過去の出現位置に関する情報を取得する出現位置情報取得手段と、を備える、データ圧縮装置。
【請求項１６】
前記演算手段における演算は、掛け算またはシフト演算の何れか一方である、請求項１５に記載のデータ圧縮装置。
【請求項１７】
さらに、前記取得された出現位置情報を符号化して出力する符号化手段を備える、請求項１３乃至１６の何れか１項に記載のデータ圧縮装置。
【請求項１８】
前記符号化手段は、
前記出現位置情報取得手段において前記文字列に対する過去の出現位置にかかる情報を取得できたときにコピー符号を出力するコピー符号生成手段と、
前記出現位置情報取得手段において前記文字列に対する過去の出現位置にかかる情報を取得できなかったときにリテラル符号を出力するリテラル符号生成手段とを有する、請求項１７に記載のデータ圧縮装置。
【請求項１９】
前記コピー符号生成手段は、
前記出現位置情報取得手段において得られた前記設定された文字列の出現位置を起点として当該起点以降のアドレスに対応する配列の内容と前記設定された文字列以降の文字列とが連続して一致する文字列長を一致長情報として求める一致長算出手段と、
前記過去の出現位置情報と前記一致長情報とを符号化して出力する符号化出力手段とを有する、請求項１８に記載のデータ圧縮装置。
【請求項２０】
前記リテラル符号生成手段は、前記設定された文字列の最初の文字の入力データをそのまままたは符号化して出力する手段を有する、請求項１８または１９に記載のデータ圧縮装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、文字コードや画像データ等の、様々な種類のデータ中に含まれる冗長な部分を省いてデータ量を圧縮する、データ圧縮方法及びデータ圧縮装置に関する。さらに特定すると、圧縮処理対象となるデータ列の類似性を利用する辞書型符号化方式を利用した、データ圧縮方法及びデータ圧縮装置に関する。
【０００２】
【従来の技術】
近年、文字コード、画像データ等の、様々な種類のデータがコンピュータ等の情報処理装置で扱われるように成っている。その結果、情報処理装置で取り扱われるデータ量も増大している。このような大量のデータには、多くの場合冗長なデータ列が含まれており、この冗長な部分を省くための圧縮処理を実行することにより、情報処理装置においてデータ保存のための記憶容量を減らすことができる。また圧縮されたデータを用いることにより情報処理装置におけるデータ転送容量を低減できるので、データ転送時間を短縮することができる。
【０００３】
辞書型符号化方式を用いたデータ圧縮の代表的な方法として、ＬＺ７７圧縮方法とＬＺ７８圧縮方法が知られている。ＬＺ７７圧縮方法では、ＬＺ７８圧縮方法に比べて簡単な処理で充分な圧縮率が得られる。そのため、実際の使用ではＬＺ７７圧縮方法が主流となっている。以下では、従ってＬＺ７７圧縮方法について説明を行う。
【０００４】
なお本発明の分野は文字コードの圧縮に限らず、様々なデータに適用できるが、以下では情報理論に基づきデータの１ワード（ＷＯＲＤ）単位を文字（アルファベット）といい、データが任意ワードつながったものを文字列と呼ぶようにする。
ＬＺ７７圧縮方法では、図１に示すように、まず一定の容量（図示の例では１６文字）を持つスライドバッファ１を設け、このバッファ内に既に符号化し圧縮した文字列２ａ（ｄｅｆａｂｑａａａａｃａｂｃｄｅ）を格納しておく。次に、格納された文字列２ａと、これから圧縮する入力文字列２ｂ（ａｂｃｄａａａｑ…）との間で、最大一致する文字列２ｃ（ａｂｃｄ）を検索し、検索した最大一致する文字列の位置の相対アドレス５（入力文字列の最初の文字から過去にさかのぼって５文字目）とその文字列長である一致長４を符号化し、符号（５，４）で最大一致した入力文字列２ｃ（ａｂｃｄ）を置換し、圧縮する。
【０００５】
次にスライドバッファ１を４文字スライドして、バッファ内の文字列２ａをｂｑａａａａｃａｂｃｄｅａｂｃｄとし、次の入力文字列２ｂ（ａａａｑ…）に対する検索を上記と同様にして行う。この結果、最大一致文字列２ｃ（ａａａ）の一致が見いだされるので、この文字列ａａａのバッファ１内での出現位置１３（入力文字列ａａａの最初のａから過去にさかのぼって１３文字目）と最大一致長３を（１３，３）の形式で符号化し置換する。
【０００６】
このようにＬＺ７７圧縮方法は、符号化を進めるにつれてスライドバッファをスライドしていくことから、スライド辞書法とも呼ばれている。
ところがこの様なＬＺ７７圧縮方法では、スライドバッファの容量を上げれば最大一致する文字列も長くなり、圧縮率が向上するが、バッファの容量が上がるに連れて検索に要する文字列の組み合わせが膨大な量となり、バッファ内を順に検索していくと、検索に要する手間と時間が膨大なものとなる。従って実際のＬＺ７７法では、バッファ内の全ての文字列と入力文字列とを照合するのではなく、入力文字列の最初の２〜４文字程度の文字列（接頭部）とその出現位置をテーブルに随時登録して行き、入力文字列の接頭部とテーブルに登録された文字列とを照合する方法を取っている。この方法によって、検索に要する時間は大幅に短縮される。
【０００７】
この様な検索に使用するテーブルに、ルックアップテーブル（Ｌｏｏｋ  ＵｐＴａｂｌｅ）とハッシュテーブル（Ｈａｓｈ  Ｔａｂｌｅ）がある。ルックアップテーブルを使用する方法は、図２に示す様に、検索文字列２ｄをルックアップテーブル３のアドレスに一対一で対応させる。対応するアドレスの内容には、その文字列の過去の出現位置（相対アドレス）が登録されている。この方法によれば、一回のテーブル引きで、検索文字列２ｄ（ａｂ）を検索して、その過去の出現位置を知ることができる。そのため、検索を非常に高速で行う事ができると言う利点を有している。
【０００８】
しかしながら検索文字列が長い場合、文字列の組み合わせが累乗的に増加するので、ルックアップテーブルを構成するためのアドレス数が膨大となる。そのためこのような数のアドレスを確保するのに、非常に大きなメモリ領域が必要となる欠点を有している。例えば、文字数が１（１文字８ビット）の場合、２8*1 ＝２５６個の記憶領域が必要である。２文字の場合は、２8*2 ≒６４キロ、３文字の場合で、２8*3 ≒１６メガとなり、実際には２文字が限界である。しかも、検索する文字列が長くなると、実際に使用される（すなわち、ルックアップテーブルに登録される）領域は一部分だけで、ルックアップテーブル内がまばらな状態になり、テーブルの利用効率が低くなると言う欠点も有している。
【０００９】
ハッシュテーブルを用いた文字列検索方法では、図３に示す様に、検索文字列２ｄのコードに対してそのビット数を減らすようなマスク処理を行って（縮退をかける）、ハッシュコード６を生成し（４）、縮退状態が共通である複数の文字列でハッシュテーブル５の一つの領域７を共有するようにしている。このため、ルックアップテーブルを用いた文字列検索方法に比べて、同等の検索領域でより長い文字列を検索することができるといった特徴を備えている。
【００１０】
しかしながら、この様にして得たハッシュテーブルでは、検索文字列に対して縮退処理を行っているので、検索文字列２ｄ（ａｂｃ）と縮退状態が共通である異なる文字列が、ハッシュテーブル内の同じ領域７に登録される場合があると言う問題（衝突問題）が発生する。
この衝突問題を解決するために、検索で見つかった文字列と検索文字列中の各文字とを照合して（８）、検索された文字列が実際に検索している文字列であるか否かをチェックする作業が新たに必要となる。
【００１１】
【発明が解決しようとする課題】
以上に説明したように、ＬＺ７７圧縮方法におけるルックアップテーブルを用いた文字列検索方法の場合、ルックアップテーブルに対する一回のテーブルびきのみで、高速に検索対象の文字列を探し出すことができる反面、テーブルサイズが検索文字数の増加と共に累乗的に増加して膨大となるため、検索のための文字数を余り多く取る（事実上２文字が限界）ことができない。その結果圧縮率をあまり高くすることが出来ないと言う欠点を有している。
【００１２】
一方、前述のハッシュテーブルを用いた文字列検索方法の場合、ルックアップテーブルを用いた文字列検索方法に比べて必要なテーブルサイズが小さく、リーズナブルなテーブルサイズの使用で早い検索をすることができるが、衝突問題を解決するための照合作業が新たに必要となる欠点を有している。なおこの照合作業は、各検索文字について行う必要があるため、かなりの手間を要する。
【００１３】
本発明は、このような従来技術の問題点を解決することを課題としており、特に衝突問題を避けるために検索文字列に対して、各文字を照合する処理を行う事無く、しかも３文字、４文字の長い文字列に対する検索であっても、ハッシュテーブルを用いた文字列検索方法と同程度のテーブルサイズで文字列検索が可能な、データ圧縮方法およびデータ圧縮装置を実現することを課題としている。
【００１４】
【課題を解決するための手段】
本発明の第１の特徴によれば、上記課題を解決するために、被圧縮データ列に圧縮処理を行って圧縮データを作成するデータ圧縮方法において、被圧縮データ列内の連続する複数の文字を検索する文字列に設定する文字列設定工程と、前記文字列を表現するビット列中の各ビットを少なくとも２個のコードに振り分けて第１、第２の検索用コードを生成する検索用コード振り分け工程と、前記第１、第２の検索用コードをそれぞれ配列のアドレスとして用いて予め過去の文字列の出現位置に関する情報が登録された第１、第２の配列テーブルから第１、第２の配列内容を取得する、配列内容取得工程と、前記取得した第１、第２の配列内容を照合する照合工程と、前記照合した第１、第２の配列内容が一致したとき、前記第１または第２の配列内容に基づいて前記文字列に対する過去の出現位置情報を取得する出現位置情報取得工程、を備えるデータ圧縮方法を提供する。
【００１５】
本発明の第２の特徴によれば、被圧縮データ列に圧縮処理を行って圧縮データを作成するデータ圧縮方法において、被圧縮データ列内の連続する複数の文字を検索する文字列に設定する文字列設定工程と、前記文字列を表現するビット列中の各ビットを２個のコードに振り分けて検索用の第１のコードと該第１のコードの相補コードである第２のコードを生成する検索用コード振り分け工程と、現時点で検索すべき文字列に関する前記第１のコードを配列のアドレスとして用いて、過去に出現した文字列に関する前記第２のコードが予め登録された第１の配列テーブルから、配列の内容を取得する、配列内容取得工程と、前記取得した配列内容と前記第２のコードを照合する照合工程と、前記照合結果が一致の場合、前記第１のコードを配列のアドレスとして用いて予め過去の文字列の出現位置に関する情報が登録された第２の配列テーブルから前記設定された文字列の過去の出現位置に関する情報を取得する出現位置情報取得工程、を備えるデータ圧縮方法を提供する。
【００１６】
本発明の第３の特徴によれば、被圧縮データ列に圧縮処理を行って圧縮データを作成するデータ圧縮方法において、被圧縮データ列内の連続する複数の文字を検索する文字列に設定する文字列設定工程と、前記文字列を表現するビット列中の各ビットを２個のコードに振り分けて検索用の第１のコードと該第１のコードの相補コードである第２のコードを生成する検索用コード振り分け工程と、前記第１のコードに演算を行って前記第１のコードを起点とする複数のコードを取得する、演算工程と、現時点で圧縮すべき文字列に関する前記取得された複数のコードを配列のアドレスとして用いて過去に出現した文字列に関する前記第２のコードが予め登録された第１の配列テーブルから複数の配列内容を取得する、配列内容取得工程と、前記取得した複数の配列内容と前記第２のコードとを照合する照合工程と、前記照合結果が一致の場合、前記演算工程で得られたコードを配列のアドレスとして用いて予め過去の文字列の出現位置に関する情報が登録された第２の配列テーブルから前記設定された文字列の過去の出現位置に関する情報を取得する出現位置情報取得工程を備える、データ圧縮方法を提供する。
【００１７】
上記各構成のデータ圧縮方法では、圧縮すべき文字列を表現するビット列中の各ビットを、少なくとも２個のコードに振り分け、各コード別々にテーブル引きを行い、その結果を互いに照合することによって、その文字列が過去に出現し、テーブル内にその過去の出現位置に関する情報が登録されているか否かが検出される。従って、文字列を少なくとも２個のコードに振り分けてアドレスを構成したことによって、各コードのテーブル引きに要するテーブルのサイズが、文字列を表すビット列をそのままの状態でアドレスとした場合（ルックアップテーブルを用いた場合）に比べて、大幅に減少する。
【００１８】
従って、設定する文字列を比較的長い文字列（例えば３文字、４文字等）に設定した場合であっても、必要な記憶領域は従来の物に比べてそれ程増大しない。さらに、テーブル引き後の一致確認の作業も、配列内容の一致を確認するのみであるので、検索文字列の各文字に対する一致確認が必要な従来のハッシュ方法に比べて、その作業が大幅に軽減される。
【００１９】
【発明の実施の形態】
以下に本発明のデータ圧縮方法および装置を、その実施形態を説明するための図面を参照しながら、詳細に説明する。
図４は本発明の第１の実施形態にかかるデータ圧縮方法およびそのための装置の動作原理の説明に提供するブロック図である。この実施形態では、スライドバッファの代わりに入力バッファ１０を用いて、この中に入力された文字列に対してポインタを順次移動させて行き、ポインタで指示される位置を先頭とする文字列について検索を実行する方法を取る。今ポインタが入力バッファ１０の位置ｔ（Ｉｎｂｕｆ〔ｔ〕）にあり、これに連続する位置（Ｉｎｂｕｆ〔ｔ＋１〕，Ｉｎｂｕｆ〔ｔ＋２〕）にある３個の文字列ｘ１ｘ２ｘ３が過去に出現したか否かを検索する場合を例にして、本実施形態の構成を説明する。
【００２０】
まず、取得された文字列ｘ１ｘ２ｘ３をビットの振り分け部１１に入力して、この文字列の全ビット（１文字を８ビットとすると、２４ビット）を例えば１２個づつの第１、第２のビットコードＳ１、Ｓ２に振り分ける。本実施形態では、元の文字列の特徴を示すビットが、コードＳ１、Ｓ２になるべく均等に分散されるように、ビットの振り分けを行うことが望ましい。この振り分けの方法については後述する。
【００２１】
１２、１３は第１、第２のアドレステーブルであり、各テーブル中にはビットの振り分け部１１によって形成された第１、第２のビットコードＳ１、Ｓ２を配列のアドレスとして使用して、過去に出現した文字列の先頭部の出現位置、即ち入力バッファ１０内のアドレスが予め登録されている。従って今、位置ｔから始まる３文字の文字列について形成された第１、第２のビットコードＳ１、Ｓ２を配列のアドレスとして使用して、テーブル引きを行うと、その文字列が過去に出現していた場合は、各テーブル１２、１３から得られた内容ａｄｄｒｅｓｓ１〔Ｓ１〕とａｄｄｒｅｓｓ２〔Ｓ２〕は互いに一致する。
【００２２】
照合（一致検出）部１４は、ａｄｄｒｅｓｓ１〔Ｓ１〕とａｄｄｒｅｓｓ２〔Ｓ２〕の一致を確認するための手段である。若し両者が一致しない場合（ａｄｄｒｅｓｓ１〔Ｓ１〕≠ａｄｄｒｅｓｓ２〔Ｓ２〕）は、その文字列が過去に出現していないこと（未登録であること）を示す。一致した場合（ａｄｄｒｅｓｓ１〔Ｓ１〕＝ａｄｄｒｅｓｓ２〔Ｓ２〕）は、ａｄｄｒｅｓｓ１〔Ｓ１〕またはａｄｄｒｅｓｓ２〔Ｓ２〕が検索文字列ｘ１ｘ２ｘ３の、入力バッファ１０における過去の出現位置を示す。
【００２３】
本実施形態では、以上の様に、文字列をそれぞれ１２ビットずつの第１、第２のビットコードに分け、そのそれぞれについてアドレステーブルを作成しているため、各アドレステーブルのサイズは、２12となる。したがって２個のアドレステーブル全体で２×２12＝２13個のメモリ領域を必要とするのみで良く、メモリ領域が従来の方法に比べて大幅に削減される。なお、図１に示す従来の方法では、この場合必要とされるメモリ領域は、２24個である。
【００２４】
また、各ビットコードＳ１、Ｓ２に対して、対応するテーブルのアドレスは一対一の関係にあるため、互いに一回のテーブル引きで検索結果を確定できる。そのため、図１に示した従来の方法と同程度の非常に早い検索スピードを獲得することができる。
図４に示す実施形態では、アドレステーブル１２、１３の内容として、直接過去の入力バッファ１０内のアドレスを入れ、符号として相対アドレスを出力している。しかしながら、図５に示す様に、ビットコードＳ１、Ｓ２を配列のアドレスとする内容にインデックス（ｉｎｄｅｘ）値を入れた、第１、第２のインデックステーブル１５、１６を利用する事も可能である。この場合、各テーブル１５、１６から得られた内容ｉｎｄｅｘ１〔Ｓ１〕とｉｎｄｅｘ２〔Ｓ２〕の一致を、照合（一致検出）部１４で確認し、一致（ｉｎｄｅｘ１〔Ｓ１〕＝ｉｎｄｅｘ２〔Ｓ２〕）が確認されたら、アドレステーブル１７から過去に出現したアドレスを獲得する。ｉｎｄｅｘ１〔Ｓ１〕≠ｉｎｄｅｘ２〔Ｓ２〕（衝突）の場合は、その検索文字列が未登録であることを示す。この方法によれば、メモリ領域が更に効率的に使用される。
【００２５】
また、その詳細については後述するが、ビットコードの振り分けに当たって、必ずしも２種類のコードに分解する必要はなく、２個以上であれば良い。さらに、各ビットコードについて、必ずしも同じ数のビットに分解する必要もない。また、振り分けられたビットコードＳ１、Ｓ２が、元の文字列の同じビット（例えば各文字の最下位ビット）を共通して含んでいてもよい。
【００２６】
図６は、上記実施形態の圧縮方法を実行する装置のブロック図である。図示する様に本データ圧縮装置６０は、文字列設定手段６１、検索用コード振り分け手段６２、配列内容取得手段６３、照合手段６４、出現位置情報取得手段６５、コピー符号生成部６６ａ及びリテラル符号生成部６６ｂとを備えた符号化手段６６を中心とするハードウェア構成になっている。
【００２７】
文字列設定手段６１、検索用コード振り分け手段６２、配列内容取得手段６３、照合手段６４、出現位置情報取得手段６５および符号化手段６６は、図４または５に示したデータ圧縮方法を記述したプログラムコードを実行できるマイクロプロセッサーを中心にして構成されている。
文字列設定手段６１は、圧縮処理対象としてバッファＩｎｂｕｆ内に蓄えられている被圧縮データ列内の連続する複数の文字Ｉｎｂｕｆ〔ｔ〕，Ｉｎｂｕｆ〔ｔ＋１〕，Ｉｎｂｕｆ〔ｔ＋２〕を検索文字列に設定する機能を有し、後述する検索用コード振り分け手段６２に文字を受け渡す工程を主に実行する手段である。本実施形態では、バッファＩｎｂｕｆ内に蓄えられている被圧縮データ列内の連続する８ビット構成の３文字Ｉｎｂｕｆ〔ｔ〕，Ｉｎｂｕｆ〔ｔ＋１〕，Ｉｎｂｕｆ〔ｔ＋２〕を２４ビット構成の検索文字列に設定している。
【００２８】
検索用コード振り分け手段６２は、文字列設定手段６１が求めた検索文字列を表現するビット列中の各ビットを複数個の検索用コードに振り分ける機能を有し、後述する検索用コード振り分け工程を主に実行する手段である。
本実施形態では、文字列設定手段６１が求めた２４ビット構成の検索文字列を表現するビット列中の各ビットを、２個の検索用コードＳ１，Ｓ２に各々振り分けている。
【００２９】
２４ビット構成の検索文字列に対して検索用コードＳ１と検索用コードＳ２を定める場合、例えば、検索用コードＳ１のビット数を２０ビットとし、検出用コードＳ２のビット数を４ビットにすることや、検索用コードＳ１のビット数と検出用コードＳ２のビット数とを共に１２ビットにすること、更に検索文字列を表現したビット列の一部のビットを複数の検索用コードに重複して包含する事も可能である。本実施形態では、検索用コードＳ１のビット数を１２ビットとし、検出用コードＳ２のビット数を１２ビットとしている。
【００３０】
配列内容取得手段６３は、検索用コード振り分け手段６２で定めた検索用コードを配列アドレスとし、インデックステーブルあるいはアドレステーブルから配列内容を取得する。照合手段６４はこの様にして得た各々の配列内容が一致するか否かを照合する処理を実行する。
出現位置情報取得手段６５は、照合した配列内容が一致したときに一致した配列内容またはそれに準ずるものに基づいて検索文字列に対する過去出現位置情報を取得する機能を有している。
【００３１】
符号化手段６６は、検索文字列に対する過去出現位置情報が取得できたときにコピー符号を出力するコピー符号生成部６６ａと、検索文字列に対する過去出現位置情報が取得できなかったときにリテラル符号を出力するリテラル符号生成部６６ｂとを有しており、後述するコピー符号生成工程、リテラル符号生成工程を主に実行する手段である。
【００３２】
コピー符号生成部６６ａは、過去の出現アドレスを起点として、起点以降のアドレスに対応する配列の内容と入力データとが連続して一致する文字列長を一致長情報ＦＬとして求める一致長算出処理、過去の出現アドレス情報として、入力バッファ内のアドレス（Ａｄｒｅｓｓ〔Ｉｎｄｅｘ〔Ｓ１〕〕）、または現入力位置との相対アドレス（Ａｄｒｅｓｓ〔Ｉｎｄｅｘ〔Ｓ１〕〕−ｔ）を出力する処理、過去の出現アドレス情報として、テーブルに過去に登録した登録番号Ｉｎｄｅｘ１〔Ｓ１〕、または現在の登録番号との相対番号（Ｃｏｕｎｔｅｒ−Ｉｎｄｅｘ１〔Ｓ１〕）を出力する処理、過去の出現アドレス情報と一致長情報ＦＬとを符号化して出力する符号化出力処理を実行する。
【００３３】
リテラル符号生成部６６ｂは、バッファＩｎｂｕｆ内に蓄えられている被圧縮データ列をそのまま、または被圧縮データ列に準ずる（例えば、被圧縮データ列を符号化したもの）データを出力する符号化出力処理を実行できる。
図７は、本発明の第１の実施形態である、データ圧縮方法の基本的工程を説明する工程図であり、図８はプログラミングのための基本フローチャートである。
【００３４】
なお、以下の説明では、前述の辞書型符号化方法を実行する際に過去の出現位置を検索するために本発明のデータ圧縮方法を適用した実施形態を説明するが、本発明は辞書型符号化方法等の圧縮技術に限定されるものではなく、一般の文字列検索に用いることができる。
第１実施形態のデータ圧縮方法は、図７に示す様に、初期化工程７０、文字列設定工程７１、検索用コード振り分け工程７２、配列内容取得工程７３、照合工程７４、出現位置情報取得工程７５、符号化工程７６および圧縮データの出力工程７７を中心とする論理構成になっており、前述のマイクロプロセッサーで実行可能なプログラムコードで記述されている。
【００３５】
初期化工程７０は、図８のフローチャートにおいて例えばステップＴ１およびＴ２で示され、ｉｎｄｅｘ１を初期化しかつ入力バッファＩｎｂｕｆ内のこれから圧縮する位置を示すｔを０に、文字列登録数カウンタを１に設定する。文字列設定工程７１は、バッファＩｎｂｕｆ内に蓄えられている被圧縮データ列の現符号化位置ｔを起点として連続する複数の文字Ｉｎｂｕｆ〔ｔ〕，Ｉｎｂｕｆ〔ｔ＋１〕，Ｉｎｂｕｆ〔ｔ＋２〕を検索文字列（８ビット×３＝２４ビット）に設定する。
【００３６】
検索用コード振り分け工程７２は、前工程で得られた検索文字列を表現するビット列を構成する各ビットを複数個の検索用コードに振り分ける工程であり、検索用コード振り分け手段６２が中心となって実行する工程である。本実施形態では２４ビット構成の検索文字列を表現するビット列を構成する各ビットを２個の検索用コードＳ１，Ｓ２に各々振り分けている。なお図８のフローチャートでは、この工程はステップＴ３に示されている。
【００３７】
配列内容取得工程７３は、前工程で構成された検索用コードＳ１、Ｓ２を配列のアドレスとして、インデックステーブルあるいは直接アドレステーブルから配列内容ｉｎｄｅｘ１〔Ｓ１〕、ｉｎｄｅｘ２〔Ｓ２〕あるいはａｄｄｒｅｓｓ１〔Ｓ１〕、ａｄｄｒｅｓｓ２〔Ｓ２〕を取得する工程である。工程７３は、配列内容取得手段６３が主として実行する。
【００３８】
照合工程７４は、前工程７３で取得した各々の配列内容ｉｎｄｅｘ１〔Ｓ１〕、配列内容ｉｎｄｅｘ２〔Ｓ２〕若しくはａｄｄｒｅｓｓ１〔Ｓ１〕、ａｄｄｒｅｓｓ２〔Ｓ２〕とが一致するか否かを照合する工程であり、照合手段６４が中心となって実行する工程である。図８のフローチャートでは、ステップＴ４によって主として実行されている。
【００３９】
出現位置情報取得工程７４は、前工程で照合された配列内容ｉｎｄｅｘ１〔Ｓ１〕もしくは配列内容ｉｎｄｅｘ２〔Ｓ２〕とが一致したとき（ステップＴ４のＹＥＳ）、あるいは配列内容ａｄｄｒｅｓｓ１〔Ｓ１〕、ａｄｄｒｅｓｓ２〔Ｓ２〕とが一致したときに、配列内容に基づいて、検索文字列に対する過去出現位置情報を取得する工程である。図４の例では、取得された過去出現位置情報は、ａｄｄｒｅｓｓ１〔Ｓ１〕またはａｄｄｒｅｓｓ２〔Ｓ２〕（両者は一致する）であり、図５の例では、ａｄｄｒｅｓｓ〔Ｉｎｄｅｘ〔Ｓ１またはＳ２〕〕である。
【００４０】
なお、図８に示すフローチャートでは、ステップＴ５において、取得された配列内容ｉｎｄｅｘ１〔Ｓ１〕、ｉｎｄｅｘ２〔Ｓ２〕が最近出現しているか否か（Ｃｏｕｎｔｅｒ−Ｉｎｄｅｘ１〔Ｓ１〕＜２12）が、更に出現位置情報の一部として取得されている（ステップＴ５）。
符号化工程７６は、出現位置情報取得工程７４において出現位置情報が得られた場合（ステップＴ５のＹＥＳ）コピー符号を生成するコピー符号生成工程と、出現位置情報が得られない場合（ステップＴ４またはステップＴ５のＮＯ）にリテラル符号を生成するリテラル符号生成工程とを有している。コピー符号生成工程は、図８のフローチャートにおいてステップＴ６以下ステップＴ１５迄を示し、リテラル符号生成工程はステップＴ５−１からステップＴ５−２（またはステップＴ５−３）までを示す。
【００４１】
コピー符号生成工程は、図６のコピー符号生成部６６ａが中心となって実行する工程であり、リテラル符号生成工程は、リテラル符号生成部６６ｂが中心となって実行する工程である。出力工程７７は、得られたコピー符号から圧縮データを出力するか、またはリテラル符号を出力する。
以下に上記図８のフローチャートの動作について、更に説明を加える。例えば図５に示す例において、配列内容Ｉｎｄｅｘ１〔Ｓ１〕もしくは配列内容Ｉｎｄｅｘ２〔Ｓ２〕が等しい場合（ステップＴ４のＹＥＳ）、Ｉｎｂｕｆ〔ｔ〕，Ｉｎｂｕｆ〔ｔ＋１〕，Ｉｎｂｕｆ〔ｔ＋２〕の検索文字列が過去に出現していることが分かる。このとき、図５に示すＩｎｄｅｘテーブルに保持されている配列内容Ｉｎｄｅｘ１〔Ｓ１〕または配列内容Ｉｎｄｅｘ２〔Ｓ２〕をアドレスとして、検索文字列に対する過去の検索において出現していたアドレスを図５に示すＡｄｒｅｓｓテーブルから得る（ステップＴ７）。
【００４２】
なお、ステップＴ７において、Ｐ１、Ｐ２はステップＴ７〜Ｔ９（Ｔ１２〜Ｔ１３）で一時的に使用する変数であり、Ｐ１には過去の出現位置を、Ｐ２には現在の位置を代入する。ステップＴ７〜ステップＴ９では、過去に出現した３バイトに続くバイトと入力データＩｎｂｕｆ〔ｔ＋３〕以降とが続けて一致する長さＦＬ（一致長）を調べ、その一致長情報ＦＬを求めている。現在の位置Ｐ２として、ｔ＋３としているのは、先頭の３文字の一致確認は既にステップＴ３からＴ４で済ませている為である。
【００４３】
こうして求めた一致長情報ＦＬと相対アドレス情報（Ｃｏｕｎｔ−Ｉｎｄｅｘ１〔Ｓ１〕）を出力（ステップＴ１１とステップＴ９−１）する。ステップＴ５でＮＯの場合は、リテラルモードを指定する符号（ｌｉｔｅｒａｌ符号）及びそのときのＩｎｂｕｆ〔ｔ〕とを出力する（ステップＴ５−１）。
本実施形態では、一致長情報が２4 −１以上の場合（ステップＴ１０のＹＥＳ）、続けて８ビットを一致長符号に割り当てる（ステップＴ１５）。リテラルモードの場合には、１バイト分、そのまま生で出力する（ステップＴ５−１）。
【００４４】
一方、リテラル符号生成工程（ステップＴ５−１，Ｔ５−２）では、バッファＩｎｂｕｆ（ｔ）内に蓄えられている被圧縮データ列をそのまま、または被圧縮データ列に準ずるデータを符号化して出力する。
以上の検索及び符号化工程（ステップＴ１、…、ステップＴ１６）は、入力されたファイルに対する圧縮作業が終了するまで繰り返される。
【００４５】
以上説明したように、本発明の第１の実施形態のデータ圧縮方法及びデータ圧縮装置では、ハッシュテーブルを使用した場合と同等の少ないテーブルの記憶領域でルックアップテーブルを用いた場合と同様の検索スピードにより、文字の検索を実行し、データを圧縮することができる。
また、ハッシュテーブルを用いた場合に必要である各文字についての照合は、本実施形態では必要ではないので、一致確認の簡素化を図ることができる。
【００４６】
図９は、本発明にかかるデータ圧縮方法の第２実施形態の基本動作を説明するための概念図であり、図１０はこのデータ圧縮方法を実現するための装置の構成を示すブロック図、図１１はこの実施形態の基本的工程を説明する工程図、さらに図１２はプログラミングのための基本フローチャートである。
以下に、本発明の第２の実施形態の構成および動作を、上記図９〜１２を参照して詳細に説明する。
【００４７】
本実施形態では、図９に示す様に、まず入力された文字列Ｉｎｂｕｆ〔ｔ〕，Ｉｎｂｕｆ〔ｔ＋１〕，Ｉｎｂｕｆ〔ｔ＋２〕を、ビットコード振り分け部１１において、Ｓ１、Ｓ２のビットコードに振り分ける。コードＳ１、Ｓ２は、第１の実施形態とは異なって、各文字の特徴を表すビットがなるべくコードＳ１に振り分けられる様にする。
【００４８】
また、コードＳ１、Ｓ２は、振り分けられる前のビット列に対して互いに相補的である。即ち、コードＳ２は、元のビット列からコードＳ１を取り除いた残りのビット（Ｒｅｍａｉｎｂｉｔ）で構成される。
本実施形態では、過去に出現した文字列で構成されたコードＳ１、Ｓ２において、コードＳ１を配列のアドレスとし、配列の内容にコードＳ２を登録したテーブル（Ｒｅｍａｉｎｂｉｔ  Ｔａｂｌｅ）２０が用意されている。
【００４９】
データ圧縮を行う場合、入力された文字列Ｉｎｂｕｆ〔ｔ〕，Ｉｎｂｕｆ〔ｔ＋１〕，Ｉｎｂｕｆ〔ｔ＋２〕から構成したコードＳ１を配列のアドレスとしてテーブル引きを行い、配列の内容を取得する。この配列の内容をコードＳ２と照合し、両者が一致すればその文字列が過去に出現していたことが分かる。従って、コードＳ１を配列のアドレスとしてインデックステーブル２１を参照する事によって、あるいは直接アドレステーブル２２を参照することによって、第１の実施形態と同様に入力文字列の過去の出現位置が取得される。
【００５０】
上記第２の実施形態に対して、図９に示す様に、コードＳ１に演算を行って複数（ｈ個、ｈは任意の整数）のアドレスを形成することにより、リメインビットテーブル２０において一致候補を複数取得する変形例も可能である。この場合、複数の一致候補とコードＳ２を照合することにより、一致の確率が向上する。なおｈを１と見做せば、上記第２の実施形態は、この変形例に含まれるので、以降、両者を同じと見なして説明する。
【００５１】
上記第２実施形態のデータ圧縮方法は、辞書型符号化方法における文字列検索を高速かつ簡便に行うことができるといった特徴を有し、図１１において示す様に初期化工程９０（図１２のフローチャートではステップＲ１，Ｒ２，Ｒ４）、文字列設定工程９１（ステップＲ３）、検索用コード振り分け工程９２（ステップＲ３）、演算工程９３、配列内容取得工程９４、照合工程９５（ステップＲ５）、出現位置情報取得工程９６、符号化工程９７および出力工程９８を中心とする論理構成になっており、前述のマイクロプロセッサーで実行可能なプログラムコードで記述されている。
【００５２】
文字列設定工程９１（ステップＲ３）は、バッファＩｎｂｕｆ内に蓄えられている被圧縮データ列内の文字検索開始位置ｔを起点として連続する複数の文字Ｉｎｂｕｆ〔ｔ〕，Ｉｎｂｕｆ〔ｔ＋１〕，Ｉｎｂｕｆ〔ｔ＋２〕を検索文字列に設定する工程であり、図１０の文字列設定手段８１が中心となって実行する工程である。本実施形態では、前述の第１実施形態のデータ圧縮方法と同様に、３文字Ｉｎｂｕｆ〔ｔ〕，Ｉｎｂｕｆ〔ｔ＋１〕，Ｉｎｂｕｆ〔ｔ＋２〕を検索文字列に設定している。
【００５３】
検索用コード振り分け工程９２（ステップＲ３）は、前工程で得られた検索文字列を表現するビット列を構成する各ビットを２つの検索用コードＳ１，Ｓ２に振り分け、その一方を検索用コードＳ１とすると同時に、その他方を検出用コードＳ２とする工程であり、検索用コード振り分け手段９２が中心となって実行する工程である。なお本実施形態の一つの特徴は、上述したように、コードＳ１とＳ２が検索文字列に対して相補コードを形成することである。
【００５４】
即ち、２４ビット構成の検索文字列に対して検索用コードＳ１と検出用コードＳ２を定める場合、検索用コードＳ１のビット数と検出用コードＳ２のビット数との和が２４ビットであれば良い。例えば、検索用コードＳ１のビット数を２０ビットとし、検出用コードＳ２のビット数を４ビットにすることや、検索用コードＳ１のビット数と検出用コードＳ２のビット数とを共に１２ビットにするといったように、合計が２４ビットであれば、検索用コードＳ１のビット数と検出用コードＳ２のビット数との組み合わせは任意である。コードＳ１とＳ２が元の２４ビットコードのそれぞれのビットに一対一で対応すれば良い。
【００５５】
本実施形態では、検索用コードＳ１のビット数を１２ビットとし、検出用コードＳ２のビット数を１２ビットとしている。更に本実施形態では、検索用コードＳ１に、なるべく元のビット列の特徴となる部分が集中する様にしている。
本実施形態では、図９に示す様に、検索用コードＳ１に演算を行って、検索用コードＳ１からｈ個の配列のアドレスを形成している。このｈ個のアドレスに基づいて、リメインビットテーブル２０の予め登録されている配列の内容を取得する。この様にして得たｈ個の一致候補を検出用コードＳ２そのものと照合する。照合の結果、検出用コードＳ２がテーブル２０のｈ個の一致候補の何れかと一致すれば、その検索文字列が過去に出現していたことが分かる。従って、コードＳ１に演算を行ったものを配列アドレスとしてインデックステーブル２１から配列の内容を取得し、更にアドレステーブル２２からその文字列の過去の出現位置を取得する。
【００５６】
演算工程９３は、上述した様に、コード振り分け工程９２で得られた検索用コードＳ１に対して、掛け算またはシフト演算のいずれか一方の演算を実行し、ｈ個のコードＳ１×ｈ、・・・（Ｓ１＋１）×（ｈ−１）を得る工程であり、演算手段８３が中心となって実行する工程である。例えば、検索用コードＳ１において、ｈを４としたとき、検索用コードＳ１を２ビット分だけシフト演算して、図９に示す様にｈ個のコードを得る。
【００５７】
配列内容取得工程９４は、前工程９３で得られたｈ個のコードを配列のアドレスとして、リメインビットテーブル２０からそれらのアドレスに予め登録されている配列内容Ｒｅｍａｉｎｂｉｔ〔Ｓ１×ｈ〕，…，Ｒｅｍａｉｎｂｉｔ〔（Ｓ１＋１）×ｈ−１〕を得る工程であり、図１０の配列内容取得手段が中心となって実行する工程である。
【００５８】
照合工程９５（図１２のフローチャートのステップＲ５、Ｒ５−１、Ｒ５−２に相当）は、前工程で取得した配列内容Ｒｅｍａｉｎｂｉｔ〔Ｓ１×ｈ〕，…，Ｒｅｍａｉｎｂｉｔ〔（Ｓ１＋１）×ｈ−１〕と前工程で得られた検出用コードＳ２とが一致しているか否かを照合する工程であり、照合手段８５が中心となって実行する工程である。
【００５９】
照合工程９５において一致が検出されると、即ちＲｅｍａｉｎｂｉｔ〔Ｓ１×ｈ＋ｏｒｄ〕が検出用コードＳ２と一致すると、出現位置情報取得工程９６においてインデックステーブル２１およびアドレステーブル２２を参照して、現検出文字列の過去の出現位置に関する情報を取得する。即ち、図９に示すインデックステーブルに記録されているＩｎｄｅｘ１〔Ｓ１〕を参照し、アドレステーブル２２から過去の出現位置Ａｄｒｅｓｓ〔Ｉｎｄｅｘ〔Ｓ１〕〕を得ることができる。
【００６０】
なお、図１２のフローチャートには記載されていないが、ステップＲ５以降に第１の実施形態の場合（図８のフローチャート参照）と同様に、この検索文字列が最近出現したか否かを検出するステップ（Ｃｏｕｎｔ−Ｉｎｄｅｘ〔Ｓ１〕＜２12）を設けても良いことは勿論である。
出現位置情報取得工程９６は、図１０の出現位置情報取得手段８６が主に実行する工程である。
【００６１】
符号化工程９７は、コピー符号生成工程とリテラル符号生成工程と備えている。ここでコピー符号生成工程は、辞書型符号化方法における検索文字列に対する過去出現位置情報を取得できたときにコピーモードを指定する符号（Ｃｏｐｙ符号）を出力する工程であり、コピー符号生成部８７ａが中心となって実行する工程である。
【００６２】
なお、ステップＲ６以下のコピー符号生成工程は、第１の実施形態において説明したコピー符号生成工程（図８のフローチャートにおけるステップＴ６以下）と同じであるため、詳細な説明は省略する。
照合工程９５で一致が得られない場合は、符号化工程９７において、入力された検索文字列からリテラル符号を生成する。リテラル符号の生成は、図１０の符号化手段８７におけるリテラル符号生成部８７ｂが主となって実行する工程である。図１２に示すフローチャートの場合は、リテラル符号出力としてステップＲ−３で、そのときのＩｎｂｕｆ〔ｔ〕を出力する。
【００６３】
なお、図１２のフローチャートにおけるリテラル符号形成のための各ステップについては、これが単に一例であるため、ここで詳細には説明しない。
このような工程を設けた結果、第２実施形態のデータ圧縮方法及びデータ圧縮装置では、ハッシュテーブルを使用した場合と同等の少ないテーブルの記憶領域でルックアップテーブルを用いた場合と同様の検索スピードにより、文字の検索を実行し、データを圧縮することができる。
【００６４】
また、ハッシュテーブルを用いた場合に必要である各文字についての照合は、本実施形態では必要ではないので、一致確認の簡素化を図ることができる。
なお、データ圧縮方法の第１実施形態または第２実施形態は、過去の出現位置として相対番号を符号化して出力しているが、直接過去の入力バッファＩｎｂｕｆのアドレスをそのまま、もしくは符号化して出力してもよい。またこれらの実施形態は、辞書型符号化方法に文字列検索を適用しているが、辞書型符号化方法に囚われず、文字列検索に用いることができる。
【００６５】
また、第１の実施形態の説明の部分では述べていないが、第１の実施形態においても、コードＳ１またはコードＳ２に演算を行って、一致候補を複数個形成することも可能であることに注意されたい。
次に、上述のデータ圧縮方法の各実施形態で使用可能な検索コード（または検出コード）Ｓ１，Ｓ２の作成方法について、実例を挙げて説明する。
【００６６】
図１３は、検索文字列を表現するビット列の特徴的なビットを検索用コードＳ１，Ｓ２の各々になるべく均一に振り分ける場合を示す。これは、特に第１の実施形態に適するコードの振り分け方法である。通常、特徴的なビットは、下位のビットであるため、各文字コードの下位ビットを成るべく検索用コードＳ１、Ｓ２に均等に成るように振り分ける。従って図示する様に、検索文字Ｉｎｂｕｆ〔ｔ〕、Ｉｎｂｕｆ〔ｔ＋２〕の偶数ビットと検索文字Ｉｎｂｕｆ〔ｔ＋１〕の奇数ビットを組み合わせて検索用コードＳ１を形成する。また、検索文字Ｉｎｂｕｆ〔ｔ〕、Ｉｎｂｕｆ〔ｔ＋２〕の奇数ビットと、検索文字Ｉｎｂｕｆ〔ｔ＋１〕の偶数ビットを組み合わせて検索用コードＳ２を形成する。
【００６７】
これにより、検索用コードＳ１には一個の最下位ビット（格子状にハッチングされている）が、検索用コードＳ２には２個の最下位ビットが含まれる様になり、文字コードの特徴が比較的均等にコードＳ１、Ｓ２に分配される。
図１４は、図１３のコード振り分け方法に類似の方法を示す。この振り分け方法では、検索用コードＳ１、Ｓ２の下位８ビットを検索文字Ｉｎｂｕｆ〔ｔ＋１〕とＩｎｂｕｆ〔ｔ＋２〕の各ビットを交互に配置することにより、形成している。上位４ビットは、検索文字Ｉｎｂｕｆ〔ｔ〕の各ビットで構成されている。図から明らかなように、コードＳ１には１個の最下位ビットが、コードＳ２には２個の最下位ビットが含まれ、何れかのコードに最下位ビットが集中することは避けられる。
【００６８】
図１５に示す例は、図１３に示す例と同様に、検索文字Ｉｎｂｕｆ〔ｔ〕、Ｉｎｂｕｆ〔ｔ＋２〕の偶数ビットと検索文字Ｉｎｂｕｆ〔ｔ＋１〕の奇数ビットを組み合わせて検索用コードＳ１を形成するが、この場合各検索文字の最下位ビットをコードＳ１に含ませている。更に、検索文字Ｉｎｂｕｆ〔ｔ〕、Ｉｎｂｕｆ〔ｔ＋２〕の奇数ビットと検索文字Ｉｎｂｕｆ〔ｔ＋１〕の偶数ビットを組み合わせて検索用コードＳ２を形成するが、この時も同様に各検索文字の最下位ビットを含ませている。
【００６９】
この様にして、各検索文字の特徴を共通に含む、１４ビットのコードＳ１と、１３ビットのコードＳ２が形成される。
なお、図１３および１４に示したコードの振り分け方法は、本発明の第１の実施形態に適した方法であるが、第２の実施形態にも適用可能である。しかしながら図１５に示した方法は、コードＳ１、Ｓ２が相補コードではないため（コードＳ１は１４ビット、コードＳ２は１３ビットであるため）、第２の実施形態には適用することが出来ない。
【００７０】
図１６に示すコードの振り分け方法は、特に第２の実施形態に適した振り分け方法である。即ちこの方法では、各検索文字Ｉｎｂｕｆ〔ｔ〕，Ｉｎｂｕｆ〔ｔ＋１〕，Ｉｎｂｕｆ〔ｔ＋２〕の下位４ビットで、検索用コードＳ１を形成することによって、コードＳ１に文字の特徴を表すビットを集中させる。一方、各検索文字Ｉｎｂｕｆ〔ｔ〕，Ｉｎｂｕｆ〔ｔ＋１〕，Ｉｎｂｕｆ〔ｔ＋２〕の上位４ビットで、検出用コードＳ２を形成することによって、文字の特徴をあまり含まない検出用コードＳ２が作成される。
【００７１】
なお、図１６に示す振り分け方法もまた第１の実施形態に適用できることは勿論であるが、しかしながら第１の実施形態にはあまり好ましくない振り分け方法である。
【００７２】
【発明の効果】
本発明によれば、辞書型符号化方法で実行される文字列の過去の出現位置検出がリーズナブルなテーブル領域でかつ高速に検索できるようになる。即ち、ルックアップテーブルを用いた文字列検索方法のように、出現可能な検索文字列に１対１に対応したテーブルサイズを必要とせず、３文字、４文字といった長い検索文字列に対する文字検索であっても、検索作業に必要なテーブル領域の低減化を図ることができるようになる。
【００７３】
またハッシュテーブルを用いた文字列検索方法のような、候補文字列と検索文字列とを一対一で照合してそれが実際に検索している検索文字列であるか否かをチェックする作業が必要ではないので、一致確認の作業を大幅に簡素化することができる。
【図面の簡単な説明】
【図１】辞書型符号化方法を用いた従来のデータ圧縮方法の基本動作を説明するための概念図である。
【図２】図１のデータ圧縮方法において、ルックアップテーブルを用いた文字列検索方法の基本動作を説明するための概念図である。
【図３】図１のデータ圧縮方法において、ハッシュテーブルを用いた文字列検索方法の基本動作を説明するための概念図である。
【図４】本発明のデータ圧縮方法にかかる第１の実施形態の基本原理を説明するための機能ブロック図である。
【図５】図４に示す第１の実施形態の変形例を示す機能ブロック図である。
【図６】本発明の第１の実施形態にかかるデータ圧縮方法を実行するための装置の構成を示すブロック図である。
【図７】本発明の第１の実施形態にかかるデータ圧縮方法を実行するための工程を示すブロック図である。
【図８】本発明の第１の実施形態をプログラミングによって実現する場合の基本フローチャートの一例を示す図である。
【図９】本発明のデータ圧縮方法にかかる第２の実施形態の基本原理を説明するための機能ブロック図である。
【図１０】本発明の第２の実施形態にかかるデータ圧縮方法を実行するための装置の構成を示すブロック図である。
【図１１】本発明の第２の実施形態にかかるデータ圧縮方法を実行するための工程を示すブロック図である。
【図１２】本発明の第２の実施形態をプログラミングによって実現する場合の基本フローチャートの一例を示す図である。
【図１３】本発明のデータ圧縮方法における検索用（または検出用）コードの１作成方法を示す概念図である。
【図１４】本発明のデータ圧縮方法における検索用（または検出用）コードのその他の作成方法を示す概念図である。
【図１５】本発明のデータ圧縮方法における検索用（または検出用）コードの更にその他の作成方法を示す概念図である。
【図１６】本発明のデータ圧縮方法における検索用（または検出用）コードの更にその他の作成方法を示す概念図である。
【符号の説明】
１０…入力バッファ
１１…ビット振り分け部
１２、１３…アドレステーブル
１４…照合部
１５、１６…インデックステーブル
１７…アドレステーブル
２０…リメインビットテーブル
２１…インデックステーブル
２２…アドレステーブル
６０…データ圧縮装置
６１…文字列設定手段
６２…検索用コード振り分け手段
６３…配列内容取得手段
６４…照合手段
６５…出現位置情報取得手段
６６…符号化手段
６６ａ…コピー符号生成部
６６ｂ…リテラル符号生成部
８０…データ圧縮装置
８１…文字列設定手段
８２…検索用コード振り分け手段
８３…演算手段
８４…配列内容取得手段
８５…照合手段
８６…出現位置情報取得手段
８７…符号化手段
８７ａ…コピー符号生成部
８７ｂ…リテラル符号生成部
Ｓ１、Ｓ２…第１、第２のコード
【図１】
0004242970.tif 000002
【図２】
0004242970.tif 000003
【図３】
0004242970.tif 000004
【図４】
0004242970.tif 000005
【図５】
0004242970.tif 000006
【図６】
0004242970.tif 000007
【図７】
0004242970.tif 000008
【図８】
0004242970.tif 000009
【図９】
0004242970.tif 000010
【図１０】
0004242970.tif 000011
【図１１】
0004242970.tif 000012
【図１２】
0004242970.tif 000013
【図１３】
0004242970.tif 000014
【図１４】
0004242970.tif 000015
【図１５】
0004242970.tif 000016
【図１６】
0004242970.tif 000017