(57)【特許請求の範囲】
【請求項１】
圧縮すべき文字列データを格納するデータ格納手段と、
前記データ格納手段内の複数のアドレスの各々を始点とする各文字列を、各文字列に含まれる所定文字数の接頭部を用いて、複数の同じ接頭部が互いに隣接するように並べ換えるソート手段と、
並べ換えられた文字列の順序で、前記データ格納手段内の各文字列のアドレスを表すアドレス情報を格納する出現位置格納手段と、
前記出現位置格納手段に格納されたアドレス情報に基づいて、前記データ格納手段に格納された文字列データに含まれる繰返し文字列を検出する検出手段と、
検出された繰返し文字列を符号化して出力する符号化手段と
を備えることを特徴とするデータ圧縮装置。
【請求項２】
前記ソート手段は、基底法を用いて、前記文字列を並べ換えることを特徴とする請求項１記載のデータ圧縮装置。
【請求項３】
符号化対象文字列のアドレスから、前記出現位置格納手段における該符号化対象文字列の順位を求めるための情報を格納する逆引き手段をさらに備え、前記検出手段は、該逆引き手段から得られた順位より上の順位に格納されたアドレス情報に対応する文字列を一致候補とし、該符号化対象文字列と該一致候補とを照合して一致長を求め、前記符号化手段は、該一致候補の位置を示す情報と該一致長とを用いて、該符号化対象文字列を符号化することを特徴とする請求項１又は２記載のデータ圧縮装置。
【請求項４】
各文字列のアドレスに対応して、最近出現した同じ文字列のアドレス情報を格納する一致位置格納手段をさらに備え、前記検出手段は、前記出現位置格納手段に格納されたアドレス情報から、該一致位置格納手段に格納されるアドレス情報を生成し、該一致位置格納手段の隣接するアドレス情報を比較して、アドレス情報が連続している連続領域を検出し、前記符号化手段は、該連続領域の位置に対応する文字列を符号化対象文字列とし、該連続領域に格納されたアドレス情報と該連続領域の長さとを用いて、該符号化対象文字列を符号化することを特徴とする請求項１又は２記載のデータ圧縮装置。
【請求項５】
前記検出手段は、前記出現位置格納手段の１つの順位に注目し、注目する順位の文字列の接頭部が１つ上の順位の文字列の接頭部と同じであるとき、前記一致位置格納手段において、該注目する順位に格納されたアドレス情報に対応する位置に、該１つ上の順位に格納されたアドレス情報を格納することを特徴とする請求項４記載のデータ圧縮装置。
【請求項６】
前記検出手段は、前記一致位置格納手段内で２つ以上の連続領域が繋がっている部分を検出し、該２つ以上の連続領域に格納されたアドレス情報に基づいて複数の一致候補の文字列を求め、前記符号化手段は、該複数の一致候補のうち最も長い一致長を有する一致候補の位置を示す情報と、該最も長い一致長とを用いて、前記符号化対象文字列を符号化することを特徴とする請求項４記載のデータ圧縮装置。
【請求項７】
符号化対象文字列に含まれる所定文字数の接頭部から、前記出現位置格納手段における同じ接頭部を含む文字列の順位を求めるための情報を格納する検索手段をさらに備え、前記検出手段は、該検索手段から得られた順位に格納されたアドレス情報に対応する文字列を一致候補とし、該符号化対象文字列と該一致候補とを照合して一致長を求め、前記符号化手段は、該一致候補の位置を示す情報と該一致長とを用いて、該符号化対象文字列を符号化することを特徴とする請求項１又は２記載のデータ圧縮装置。
【請求項８】
前記検出手段は、前記所定文字数の接頭部に対応して前記検索手段から得られる順位が、最近出現した同じ接頭部を含む文字列の順位になるように、該検索手段に格納された情報を更新することを特徴とする請求項７記載のデータ圧縮装置。
【請求項９】
コンピュータのためのプログラムを記録した記録媒体であって、
前記プログラムは、
圧縮すべき文字列データが有する複数のアドレスの各々を始点とする各文字列を、各文字列に含まれる所定文字数の接頭部を用いて、複数の同じ接頭部が互いに隣接するように並べ換え、
並べ換えられた文字列の順序で、前記圧縮すべき文字列データに含まれる各文字列のアドレスを表すアドレス情報を記録し、
記録されたアドレス情報に基づいて、前記圧縮すべき文字列データに含まれる繰返し文字列を検出し、
検出された繰返し文字列を符号化する
処理を前記コンピュータに実行させることを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１０】
圧縮すべき文字列データが有する複数のアドレスの各々を始点とする各文字列を、各文字列に含まれる所定文字数の接頭部を用いて、複数の同じ接頭部が互いに隣接するように並べ換え、
並べ換えられた文字列の順序で、前記圧縮すべき文字列データに含まれる各文字列のアドレスを表すアドレス情報を記録し、
記録されたアドレス情報に基づいて、前記圧縮すべき文字列データに含まれる繰返し文字列を検出し、
検出された繰返し文字列を符号化する
ことを特徴とするデータ圧縮方法。
【請求項１１】
圧縮すべき文字列データが有する複数のアドレスの各々を始点とする各文字列を、各文字列に含まれる所定文字数の接頭部を用いて、複数の同じ接頭部が互いに隣接するように並べ換え、
並べ換えられた文字列の順序で、前記圧縮すべき文字列データに含まれる各文字列のアドレスを表すアドレス情報を記録し、
記録されたアドレス情報に基づいて、前記圧縮すべき文字列データに含まれる繰返し文字列を検出し、
検出された繰返し文字列を符号化する
処理をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、被圧縮データ列から生成される辞書を用いて、そのデータ列を圧縮する装置および方法に関する。本発明は、文字コードの圧縮に限らず、様々なデータの圧縮に適用できるが、以下では情報理論に基づき、データ列をワード単位に分割し、１ワードのデータを文字と呼び、任意のワード数のデータ列を文字列と呼ぶことにする。
【０００２】
【従来の技術】
近年、文字コード、画像データ等の様々な種類のデータがコンピュータで扱われるようになるのに伴い、取り扱われるデータ量も増大している。そのような大量のデータを扱う場合、データ中の冗長な部分を省いて圧縮することにより、必要な記憶容量を減らしたり、遠隔地へ高速に伝送したりすることができる。
【０００３】
従来のデータ圧縮技術には、データ系列の類似性を利用した辞書型符号化と、データ列の出現頻度を利用した確率統計型符号化とがある。このうち、前者の辞書型符号化の代表的な方法として、ＬＺ７７符号化とＬＺ７８符号化が知られている（植松友彦（うえまつ  ともひこ）著、“文書データ圧縮アルゴリズム入門”、ＣＱ出版、ｐｐ．１３１−２０８、１９９５年）。ＬＺ７７符号化とＬＺ７８符号化では、ＬＺ７７符号化の方が、簡単な処理で充分な圧縮率が得られることから、実際の使用では主流となっている。
【０００４】
ＬＺ７７符号化では、図２１に示すように、一定サイズのスライドバッファ１を設け、このバッファ１内で入力文字列と最長一致する文字列を検索し、その位置と長さを用いて入力文字列を符号化する。符号化が進むにつれてバッファ１をスライドさせていくことから、この符号化方法は、スライド辞書法とも呼ばれる。
【０００５】
図２１では、バッファ１の右隣の入力文字列“ａｂｃｄａａａｑ．．．”が符号化されるとき、バッファ１内で一致する文字列のうち最長のものは“ａｂｃｄ”である。そこで、この最長一致文字列の先頭位置と入力文字列の先頭位置の相対アドレス“５（バイト）”を一致位置とし、最長一致文字列の長さ“４（バイト）”を一致長として、（一致位置，一致長）＝（５，４）のような符号を生成する。これにより、入力文字列の先頭の“ａｂｃｄ”が（５，４）に置き換えられる。同様にして、次の文字列“ａａａ”は、符号（１３，３）に置き換えられる。
【０００６】
しかし、実際に用いられるスライドバッファはもっと長く、最長一致する文字列を発見するためにバッファ内の文字列を順に検索していくと、膨大な時間を要する。このため、実際には、バッファ内のすべての文字列と照合するのではなく、文字列の接頭部（２〜４文字程度）の出現位置を随時テーブルに登録し、テーブルに保持されている位置の文字列のみと照合している。このような検索に使用されるテーブルとしては、ルックアップテーブル（Look Up Table ，ＬＵＴ）とハッシュテーブル（Hash Table）とがある。
【０００７】
図２２は、ＬＵＴを用いた文字列検索を示している。図２２のＬＵＴ２は、バッファ１内の文字列の接頭部をアドレスとして、その文字列のバッファ１内における出現位置（アドレスまたはポインタ）を格納している。そして、検索時には、入力文字列の接頭部をアドレスとして、ＬＵＴ２の領域にアクセスし、対応する文字列の位置を取得する。
【０００８】
同じ接頭部の文字列がバッファ１内に複数存在する場合は、リンクドリスト３の形式で複数の出現位置が保持される。したがって、ＬＵＴ２に１回アクセスするだけで、バッファ１内のすべての対応する文字列の位置を取得することができる。ここでは、２文字分の接頭部が用いられており、入力文字列の接頭部“ａｂ”に対応するＬＵＴ２の領域は、リンクドリスト３を利用して２つの出現位置を保持している。
【０００９】
このように、ＬＵＴは、検索する文字列をテーブルの領域に１対１に対応させ、１回のテーブル引きのみで必要な情報を取得できるため、非常に高速な検索を行うことができる。しかし、長い文字列を検索する場合、テーブルに必要な領域の数は出現可能な文字の数の巾乗で増えるため、必要な領域が膨大になる。例えば、出現可能な文字の数を２8 ＝２５６とすると、ｎ文字の接頭部に対して２５６n 個の領域が必要となる。
【００１０】
ところが、検索する文字列が多少長くなると、用意された領域のうち実際に使用される（登録される）部分は一部分のみに止まり、テーブル内はまばらな状態になる。したがって、長い文字列を検索する場合には、メモリの使用効率が悪化する。
【００１１】
そこで、ハッシュテーブルでは、検索文字列を縮退させて、複数の文字列が１つの領域を共有するようにしている。このため、テーブル引きの後で、得られた文字列が実際に検索している文字列かどうかをチェックする必要があるが、ＬＵＴに比べて、同等のテーブル領域でより長い文字列を検索することができる。
【００１２】
図２３は、ハッシュテーブルを用いた文字列検索を示している。図２３のハッシュコード生成部４は、入力文字列の接頭部“ａｂｃ”からハッシュコード５を生成し、それをアドレスとしてハッシュテーブル６にアクセスする。ハッシュテーブル６には、ハッシュコード５に対応するバッファ１内の位置が格納されており、その位置にある文字列“ａｂｃｄｅ”と入力文字列を照合することで、両者の接頭部が一致するかどうかがチェックされる。そして、それらが一致すれば、入力文字列と一致する文字列がバッファ１内に存在すると判断される。
【００１３】
ハッシュテーブルの場合も、ＬＵＴの場合と同様に、バッファ１内の同じ接頭部を持つ複数の文字列に対しては、リンクドリストの形式で複数の出現位置が保持される。いずれの場合も、リンクドリストは、最長一致文字列を検索するために用いられる。
【００１４】
【発明が解決しようとする課題】
しかしながら、上述した従来のデータ圧縮技術には、次のような問題がある。
ＬＵＴを用いて長い文字列を検索する場合、上述したように、膨大な領域を持つテーブルを用意しても、その一部分のみしか使用されないので、テーブル内はまばらな状態になる。ハッシュテーブルでは、ＬＵＴと比べるとテーブルサイズが小さくなるが、入力データが少なければ、同じようにテーブル内がまばらな状態になる。したがって、メモリが必ずしも有効に利用されないという問題がある。
【００１５】
また、最長一致文字列を検索する際、リンクドリストに保持された複数の出現位置を一つ一つ辿らなければならず、同じ接頭部を持つ文字列が多くなると、検索処理に時間がかかるという問題もある。
【００１６】
本発明の課題は、辞書型符号化に基づくデータ圧縮において、入力データに応じたリーズナブルなメモリ量で文字列検索を実現し、最長一致検索を効率よく行うデータ圧縮装置およびその方法を提供することである。
【００１７】
【課題を解決するための手段】
図１は、本発明のデータ圧縮装置の原理図である。図１のデータ圧縮装置は、データ格納手段１１、ソート手段１２、出現位置格納手段１３、検出手段１４、および符号化手段１５を備える。
【００１８】
データ格納手段１１は、圧縮すべき文字列データを格納し、ソート手段１２は、データ格納手段１１内の複数のアドレスの各々を始点とする各文字列を、各文字列の内容に基づいて並べ換える。出現位置格納手段１３は、並べ換えられた文字列の順序で、各文字列のアドレスを表すアドレス情報を格納する。検出手段１４は、出現位置格納手段１３に格納されたアドレス情報に基づいて、繰返し文字列を検出し、符号化手段１５は、検出された繰返し文字列を符号化して出力する。
【００１９】
まず、データ格納手段１１内の複数のアドレスの各々に、圧縮すべき文字列データに含まれる各文字が格納される。次に、ソート手段１２は、それらのアドレスをそれぞれ始点とする複数の文字列を、各文字列の内容に基づいて所定の順序で並べ換え、各文字列のアドレス情報を、その順序で出現位置格納手段１３に格納する。
【００２０】
次に、検出手段１４は、出現位置格納手段１３に格納された各アドレス情報と、出現位置格納手段１３内におけるそのアドレス情報の順位（格納位置）との関係を参照して、データ格納手段１１内で繰り返し出現する文字列を検出する。そして、符号化手段１５は、２回目以降に出現した繰返し文字列を符号化して出力する。
【００２１】
このようなデータ圧縮装置によれば、データ格納手段１１内に出現する複数の文字列が、その内容に応じて規則的に並べ換えられて、出現位置格納手段１３に格納される。このため、出現位置格納手段１３を参照すれば、同じ文字列が出現する複数の位置を容易に見つけることができ、文字列検索が効率化される。このとき、複数の同じ文字列が互いに隣接するように文字列を並べ換えることで、最長一致検索をさらに効率化することができる。
【００２２】
また、出現位置格納手段１３内のアドレス情報の数は、被圧縮データを格納するデータ格納手段１１内のアドレスの数とほぼ同じになるため、入力データにほぼ比例するメモリ量で文字列検索を行うことができる。
【００２３】
例えば、図１のデータ格納手段１１、ソート手段１２、出現位置格納手段１３、および検出手段１４は、それぞれ、後述する図５の入力バッファ２１、ソート部２５、出現位置保持部２６、および一致検出部２２に対応し、図１の符号化手段１５は、図５の符号生成部２３および符号出力部２４に対応する。
【００２４】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施の形態を詳細に説明する。
本実施形態では、入力文字列を保持する入力バッファを設け、バッファ中の各アドレスを始点とする各文字列を、文字列の内容に従って並びかえて、順位リストを生成する。そして、この順位リストを辞書として利用して文字列検索を行い、一致位置と一致長を求める。
【００２５】
例えば、図２のような入力バッファを設けた場合、まず、バッファ内の各アドレスを始点とする各文字列から、それぞれ、３文字分の接頭部を抽出し、図３のような順位リストを生成する。図３の順位リストは、図２の入力バッファとほぼ同じ数の要素（レコード）を有するテーブルに対応し、各レコードには、図２の入力バッファにおいて、各接頭部が出現する位置のアドレスが格納される。
【００２６】
ここでは、入力バッファに、“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅｃｏｍｐｒｅｓｓ＿ｃｏｍｐｒｅｓｓｉｏｎ”という３４バイトの入力文字列が保持されており、アドレス１、２、および３からは、それぞれ、“ｃｏｍ”、“ｏｍｐ”、および“ｍｐｒ”という接頭部が抽出されている。他のアドレスからも、同様にして、３文字の接頭部が抽出される。ただし、記号“＿”はスペースを表す。そして、順位リストには、これらの接頭部の出現位置に対応する“１”〜“３２”のアドレスが格納される。
【００２７】
次に、この順位リストに保持されたアドレスを、対応する接頭部の各文字のコード順に並べ換えて、図４のような順位リストを生成する。図４の順位リストは、図３の順位リストと同じ数のレコードを有し、並べ換えられた順序で、各接頭部のアドレスを保持している。
【００２８】
ここでは、“ｃｏｍ”や“ｓｓｉ”のように、入力バッファ内に含まれる複数の同じ接頭部が、出現順に隣接して並んでいる。このため、ある文字列と同じ接頭部を持つ文字列のうちで、最近出現したもののアドレスは、必ずその文字列のアドレスが格納されたレコードの直前（１つ上の順位）のレコードに格納されている。したがって、入力バッファ内の符号化対象の文字列を、直前のレコードに保持されたアドレスの文字列と比較すれば、一致する文字列を容易に検索することができる。
【００２９】
また、他の一致候補のアドレスも連続して格納されているため、最長一致検索の場合は、符号化対象の文字列を、連続して格納された複数のアドレスに対応する複数の文字列と比較すればよく、最長一致検索が高速化される。さらに、入力バッファと順位リストは、ほぼ同じ程度の長さになるため、入力バッファの長さにほぼ比例したサイズのメモリ量で、検索に必要な情報を格納することができる。
【００３０】
次に、図５から図１８までを参照しながら、図４に示した順位リストを用いた圧縮処理について、より詳細に説明する。
図５は、本実施形態のデータ圧縮装置の構成図である。図５のデータ圧縮装置は、例えば、コンピュータを用いて構成され、入力バッファ２１、一致検出部２２、符号生成部２３、符号出力部２４、ソート部２５、および出現位置保持部２６を備える。
【００３１】
入力バッファ２１は、入力された文字列を被圧縮データ列として保持する。ソート部２５は、入力バッファ２１内の各アドレスを始点とする文字列を、文字列の内容に従って並べ換え、並べ換えられた順序で文字列のアドレスを保持する順位リスト２７を生成する。出現位置保持部２６は、順位リストを出現位置情報として保持する。
【００３２】
一致検出部２２は、順位リスト２７の情報に基づいて、入力バッファ２１内の繰返し文字列を検出し、他の文字列とともに符号生成部２３に渡す。符号生成部２３は、一致検出部２２から受け取った文字列の符号を生成し、符号出力部２４は、生成された符号を圧縮データとして出力する。順位リスト２７を利用した繰返し文字列の検索方法としては、次の３つが考えられる。
（１）逆引きテーブル（逆引きリスト）を用いる方法
（２）一致位置テーブル（一致位置リスト）を用いる方法
（３）検索テーブル（ハッシュテーブル）を用いる方法
まず、図６から図９までは、逆引きリストを用いたデータ圧縮処理を示している。
【００３３】
この場合、一致検出部２２は、図６に示すように、逆引きリスト３１と照合部３２を備える。逆引きリスト３１は、入力バッファ２１内の符号化対象の文字列のアドレスから、順位リスト２７におけるその文字列の順位を求めるための情報を格納する。そして、一致検出部２２は、逆引きリスト３１から得られた順位より上の順位のアドレスから始まる文字列を、一致候補として採用する。
【００３４】
照合部３２は、符号化対象の文字列と一致候補の文字列とを照合し、一致した文字列の長さを求める。そして、符号生成部２３は、得られた長さを一致長とし、一致した文字列のアドレスを一致位置として、文字列を符号化する。最長一致検索を行う場合は、複数の一致候補のうち最も長い一致長を有するものを符号化する。
【００３５】
例えば、図２の入力文字列からは、図７のような逆引きリストと順位リストが生成される。図７の順位リストＯｄｒ２Ｐ［］は、図４の順位リストと同様である。逆引きリストＰ２Ｏｄｒ［］は、順位リストＯｄｒ２Ｐ［］に保持された各アドレスの順位を表す番号を、それぞれ、そのアドレスに対応するレコードに格納していくことで、容易に生成される。例えば、順位リストＯｄｒ２Ｐ［］の１番目のアドレス“２３”に対しては、逆引きリストＰ２Ｏｄｒ［］のアドレス“２３”のレコードに、順位番号“１”が格納されている。
【００３６】
繰返し文字列を検出するとき、一致検出部２２は、符号化対象の文字列のアドレスに基づいて、逆引きリストＰ２Ｏｄｒ［］と順位リストＯｄｒ２Ｐ［］にアクセスし、一致候補の文字列を求める。
【００３７】
例えば、入力バッファＩｎＢｕｆ［］のアドレス“２４”を始点とする文字列“ｃｏｍｐｒｅｓｓｉｏｎ”が符号化対象であれば、逆引きリストＰ２Ｏｄｒ［］のアドレス“２４”に保持された順位番号“５”を取得し、順位リストＯｄｒ２Ｐ［］のその順位にアクセスする。次に、それより上の順位“３”および“４”に保持されたアドレス“１”および“１５”を取得する。そして、それらのアドレスを始点とする文字列“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅｃｏｍ．．．”および“ｄｅｃｏｍｐｒｅｓｓ＿ｃｏｍ．．．”を一致候補とする。
【００３８】
最長一致検索を行わない場合は、１つ上の順位の文字列“ｄｅｃｏｍｐｒｅｓｓ＿ｃｏｍ．．．”のみが一致候補となり、最長一致検索を行う場合は、両方の文字列が一致候補となる。
【００３９】
このように、逆引きリストを設けることで、容易に順位リストにアクセスすることができ、文字列検索が効率化される。また、逆引きリストは順位リストと同じ長さなので、これらを合わせても、入力バッファの長さにほぼ比例するメモリ量で、必要な情報を格納することができる。
【００４０】
図８は、図６の一致検出部を用いたデータ圧縮処理のフローチャートである。この処理では、最長一致検索は行われず、最近出現した一致候補のみが検索される。
【００４１】
データ圧縮装置は、まず、入力バッファＩｎＢｕｆ［］に、所定のサイズＢＵＦＳＩＺＥ分のデータを入力し、符号化位置を表す変数ｔを１とおく（ステップＳ１）。また、ＩｎＢｕｆ［］の各アドレスを始点とする３文字の文字列をアルファベット順に並べて、順位リストＯｄｒ２Ｐ［］を作成し、Ｏｄｒ２Ｐ［］用の逆引きリストＰ２Ｏｄｒ［］を作成する。
【００４２】
次に、アドレスｔを始点とする文字列がｔより前に出現しているかどうかをチェックする。ここでは、まず、最近出現した一致候補の順位を表す変数ｏｄｒを、Ｐ２Ｏｄｒ［ｔ］−１とおき、一致位置のアドレスを表す変数ｐを、Ｏｄｒ２Ｐ［ｏｄｒ］とおく（ステップＳ２）。ｏｄｒは、Ｏｄｒ２Ｐ［］において、符号化位置を始点とする文字列の順位の１つ上の順位に対応する。
【００４３】
次に、アドレスｔを始点とする３文字の文字列Ｃｔ＝（ＩｎＢｕｆ［ｔ］，ＩｎＢｕｆ［ｔ＋１］，ＩｎＢｕｆ［ｔ＋２］）と、アドレスｐを始点とする３文字の文字列Ｃｐとを比較する（ステップＳ３）。
【００４４】
ＣｔとＣｐが一致すれば、Ｃｐで始まる文字列を一致候補として、次に、一致長を求める。ここでは、まず、一致長を表す変数ｓを３とおき（ステップＳ４）、ＩｎＢｕｆ［ｔ＋ｓ］とＩｎＢｕｆ［ｐ＋ｓ］を比較する（ステップＳ５）。これらが一致すれば、ｓ＝ｓ＋１とおいて（ステップＳ６）、ステップＳ５の処理を繰り返す。
【００４５】
ステップＳ５において、ＩｎＢｕｆ［ｔ＋ｓ］とＩｎＢｕｆ［ｐ＋ｓ］が一致しなければ、（ｐ，ｓ）を符号として出力し、ｔ＝ｔ＋ｓとおいて（ステップＳ７）、ｔとＢＵＦＳＩＺＥを比較する（ステップＳ８）。そして、ｔ＜ＢＵＦＳＩＺＥであれば、ステップＳ２以降の処理を繰り返す。
【００４６】
ステップＳ８において、ｔ≧ＢＵＦＳＩＺＥとなれば、次に、被圧縮データが終了したかどうかをチェックする（ステップＳ９）。被圧縮データが残っていれば、ステップＳ１以降の処理を繰り返し、被圧縮データがなくなれば、処理を終了する。
【００４７】
また、ステップＳ３において、ＣｔとＣｐが一致しなければ、一致候補が存在しないので、Ｃｔの先頭文字ＩｎＢｕｆ［ｔ］をそのまま符号として出力し、ｔ＝ｔ＋１とおいて（ステップＳ１０）、ステップＳ８以降の処理を行う。
【００４８】
例えば、図７の被圧縮データの場合は、図８の処理により、“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ（１，８）＿（１５，８）（９，３）”のような圧縮データが生成される。
【００４９】
図９は、最長一致検索を行う場合のデータ圧縮処理のフローチャートである。図９のステップＳ１１、Ｓ１３〜Ｓ１６、およびＳ２２〜Ｓ２４の処理は、図８のステップＳ１、Ｓ３〜Ｓ６、およびＳ８〜Ｓ１０の処理と同様である。
【００５０】
ステップＳ１１において、Ｏｄｒ２Ｐ［］とＰ２Ｏｄｒ［］を作成すると、データ圧縮装置は、次に、ｏｄｒ＝Ｐ２Ｏｄｒ［ｔ］−１、ｐ＝Ｏｄｒ２Ｐ［ｏｄｒ］とおく（ステップＳ１２）。このとき、さらに、最長一致文字列の一致位置を表す変数ｐｒｅをｐとおき、その一致長を表す変数ｌｅｎを０とおく。そして、ステップＳ３〜Ｓ６の処理により、最近出現した一致候補の一致長ｓを求める。
【００５１】
次に、ｓとｌｅｎを比較し（ステップＳ１７）、ｓ＞ｌｅｎであれば、ｌｅｎ＝ｓ、ｐｒｅ＝ｐとおく（ステップＳ１８）。そして、より長い一致候補を求めるために、ｏｄｒ＝ｏｄｒ−１、ｐ＝Ｏｄｒ２Ｐ［ｏｄｒ］とおいて（ステップＳ１９）、ＣｔとＣｐを比較する（ステップＳ２０）。ステップＳ１７において、ｓ≦ｌｅｎであれば、ｌｅｎとｐｒｅを更新せずに、ステップＳ１９以降の処理を行う。
【００５２】
ＣｔとＣｐが一致すれば、新たな一致候補が見つかったので、ステップＳ１４以降の処理を繰り返し、その候補の一致長がｌｅｎより長ければ、ｌｅｎとｐｒｅを更新する。
【００５３】
そして、ステップＳ２０において、ＣｔとＣｐが一致しなくなると、（ｐｒｅ，ｌｅｎ）を符号として出力し、ｔ＝ｔ＋ｌｅｎとおいて（ステップＳ２１）、ステップＳ２２以降の処理を行う。こうして、最終的に、一致長が最も長い文字列の位置と長さが符号として出力される。
【００５４】
例えば、図７の被圧縮データの場合は、図９の処理により、“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ（１，８）＿（１，１１）”のような圧縮データが生成される。
次に、図１０から図１３までは、一致位置リストを用いたデータ圧縮処理を示している。この処理では、入力データは、一旦、一致位置リストに変換されてから圧縮される。
【００５５】
この場合、一致検出部２２は、図１０に示すように、一致位置リスト４１、領域検出部４２、および照合部４３を備える。一致位置リスト４１は、順位リスト２７から生成され、入力バッファ２１内の各文字列のアドレスから最近出現した同じ文字列の位置（一致位置）を求めるための情報を格納する。
【００５６】
例えば、図７の順位リストＯｄｒ２Ｐ［］は、図１１のような一致位置リストＰ２ＰｒｅＰ［］に変換される。この一致位置リストＰ２ＰｒｅＰ［］は、入力バッファの要素と同じ数のレコードからなる。そして、各アドレスのレコードには、順位リストＯｄｒ２Ｐ［］において、そのアドレスを始点とする接頭部の順位の１つ上の順位に保持されたアドレスが、一致位置として格納されている。ただし、１つ上の順位に登録された接頭部が異なる場合は、一致候補が存在しないことを表す記号“Ｎ”が格納される。
【００５７】
一致位置リストＰ２ＰｒｅＰ［］の生成時に、一致検出部２２は、順位リストＯｄｒ２Ｐ［］に保持されたアドレスを上位から順に見ていく。そして、注目する順位に登録された接頭部が１つ上の順位に登録された接頭部と同じであれば、前者の順位に保持されたアドレスに対応するレコードに、後者の順位に保持されたアドレスを格納する。
【００５８】
また、注目する順位に登録された接頭部が１つ上の順位に登録された接頭部と異なれば、前者の順位に保持されたアドレスに対応するレコードに、記号“Ｎ”を格納する。このような操作を繰返すことで、一致位置リストＰ２ＰｒｅＰ［］が容易に生成される。
【００５９】
例えば、順位リストＯｄｒ２Ｐ［］の１番目のアドレス“２３”に対しては、１つ上の順位のレコードが存在しない。そこで、一致位置リストＰ２ＰｒｅＰ［］のアドレス“２３”には、記号“Ｎ”が格納される。また、順位リストＯｄｒ２Ｐ［］の５番目のアドレス“２４”に対しては、４番目のアドレス“１５”のレコードが同じ接頭部“ｃｏｍ”に対応する。そこで、一致位置リストＰ２ＰｒｅＰ［］のアドレス“２４”には、４番目のレコードに保持されたアドレス“１５”が格納される。
【００６０】
図１０の領域検出部４２は、このような一致位置リスト４１の隣接するレコードの値（アドレス）を比較して、一致位置を示す値が連続して１ずつ増えているような領域を検出する。そして、符号生成部２３は、その領域の先頭の値を一致位置とし、値が連続している長さから一致長を求めて、文字列を符号化する。
【００６１】
例えば、図１１の一致位置リストＰ２ＰｒｅＰ［］では、アドレス“１５”〜“２０”の領域において、レコードの値が“１”から“６”まで連続して１ずつ増えている。そこで、この領域の長さ“６”に、順位リストに登録された接頭部の長さ“３”を加え、“１”を引いた結果“８（＝６＋３−１）”を、一致長とする。そして、先頭のレコードの値“１”を一致位置として、（１，８）のような符号が生成される。
【００６２】
また、最長一致検索を行う場合、領域検出部４２は、一致位置リスト４１において、値が連続している領域が２つ以上繋がっている部分を検出する。そして、一致検出部２２は、検出された複数の連続領域に保持されているアドレスを分析して、複数の一致候補の位置を求める。
【００６３】
次に、照合部３２は、符号化対象の文字列と各一致候補の文字列とを照合し、一致した文字列の長さを求める。そして、符号生成部２３は、複数の一致候補のうち、一致した長さが最も長いものの一致位置と一致長を用いて、文字列を符号化する。
【００６４】
例えば、図１１の一致位置リストＰ２ＰｒｅＰ［］では、アドレス“２４”〜“２９”の領域において、レコードの値が“１５”から“２０”まで連続して増えており、アドレス“３０”〜“３２”の領域において、レコードの値が“７”から“９”まで連続して増えている。これらの２つの連続領域は繋がっているため、アドレス“２４”を始点とする文字列“ｃｏｍｐｒｅｓｓｉｏｎ”を符号化対象として、最長一致検索が行われる。
【００６５】
この場合、２番目の連続領域“３０”〜“３２”の値に基づいて、１番目の連続領域のアドレス“２４”には、アドレス“１５”の一致候補より長いアドレス“１”の候補があることが分かる。その一致長は、２つの連続領域の長さ“９”に、接頭部の長さ“３”を加え、“１”を引くことで求められ、“１１（＝９＋３−１）”となる。こうして、（１，１１）のような符号が生成される。
【００６６】
３個以上の連続領域が繋がっている場合も、同様にして、最長一致文字列の一致位置と一致長を表す符号が生成される。一般に、ｎ個の連続領域が繋がっている場合は、少なくともｎ個の一致候補が存在し、それらの中に最長一致文字列が含まれている。
【００６７】
このように、順位リストを一致位置リストに変換することで、一致位置と一致長が容易に求められるようになり、文字列検索が効率化される。また、一致位置リストは入力バッファと同じ長さなので、入力バッファの長さに比例するメモリ量で、必要な情報を格納することができる。図１１では、一致位置のアドレスそのものを一致位置リストに格納しているが、各アドレスから一致位置までの相対アドレスを格納してもよい。
【００６８】
図１２は、図１０の一致検出部を用いたデータ圧縮処理のフローチャートである。この処理では、最長一致検索は行われず、最近出現した一致候補のみが検索される。
【００６９】
データ圧縮装置は、まず、入力バッファＩｎＢｕｆ［］に、ＢＵＦＳＩＺＥ分のデータを入力し、変数ｔを１とおく（ステップＳ３１）。また、ＩｎＢｕｆ［］のデータから順位リストＯｄｒ２Ｐ［］を作成し、Ｏｄｒ２Ｐ［］から一致位置リストＰ２ＰｒｅＰ［］を作成する。
【００７０】
次に、Ｐ２ＰｒｅＰ［ｔ］を“Ｎ”と比較して、アドレスｔを始点とする文字列の一致候補が存在するかどうかをチェックする（ステップＳ３２）。そして、その値が“Ｎ”でなければ、一致候補が存在するので、“連続領域の長さ−１”を表す変数ｓを０とおいて、Ｐ２ＰｒｅＰ［ｔ＋ｓ］とＰ２ＰｒｅＰ［ｔ＋ｓ＋１］−１とを比較する（ステップＳ３４）。
【００７１】
Ｐ２ＰｒｅＰ［ｔ＋ｓ］とＰ２ＰｒｅＰ［ｔ＋ｓ＋１］−１が一致すれば、Ｐ２ＰｒｅＰ［ｔ＋ｓ＋１］は“Ｎ”ではなく、Ｐ２ＰｒｅＰ［ｔ＋ｓ］より１だけ大きい値を表す。そこで、ｓ＝ｓ＋１とおいて（ステップＳ３５）、ステップＳ３４の処理を繰り返す。
【００７２】
ステップＳ３４において、Ｐ２ＰｒｅＰ［ｔ＋ｓ］とＰ２ＰｒｅＰ［ｔ＋ｓ＋１］−１が一致しなければ、Ｐ２ＰｒｅＰ［ｔ］を一致位置とし、ｓ＋３を一致長として、符号（Ｐ２ＰｒｅＰ［ｔ］，（ｓ＋３））を出力する（ステップＳ３６）。そして、ｔ＝ｔ＋ｓ＋３とおいて、ｔとＢＵＦＳＩＺＥを比較する（ステップＳ３７）。そして、ｔ＜ＢＵＦＳＩＺＥであれば、ステップＳ３２以降の処理を繰り返す。
【００７３】
ステップＳ３７において、ｔ≧ＢＵＦＳＩＺＥとなれば、次に、被圧縮データが終了したかどうかをチェックする（ステップＳ３８）。被圧縮データが残っていれば、ステップＳ３１以降の処理を繰り返し、被圧縮データがなくなれば、処理を終了する。
【００７４】
また、ステップＳ３２において、Ｐ２ＰｒｅＰ［ｔ］が“Ｎ”であれば、一致候補が存在しないので、ＩｎＢｕｆ［ｔ］をそのまま符号として出力し、ｔ＝ｔ＋１とおいて（ステップＳ３９）、ステップＳ３７以降の処理を行う。
【００７５】
例えば、図７の被圧縮データの場合は、図１２の処理により、“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ（１，８）＿（１５，８）（９，３）”のような圧縮データが生成される。
【００７６】
図１３は、最長一致検索を行う場合のデータ圧縮処理のフローチャートである。図１３のステップＳ４１〜Ｓ４２、Ｓ４４〜Ｓ４５、およびＳ５０〜Ｓ５２の処理は、図１２のステップＳ３１〜Ｓ３２、Ｓ３４〜Ｓ３５、およびＳ３７〜Ｓ３９の処理と同様である。
【００７７】
ステップＳ４２において、Ｐ２ＰｒｅＰ［ｔ］が“Ｎ”でなければ、データ圧縮装置は、次に、ｓ＝０とおき、最長一致文字列の一致位置を表す変数ｐをＰ２ＰｒｅＰ［ｔ］とおく（ステップＳ４３）。そして、ステップＳ４４〜Ｓ４５の処理により、ｓの値を更新する。
【００７８】
ステップＳ４４において、Ｐ２ＰｒｅＰ［ｔ＋ｓ］とＰ２ＰｒｅＰ［ｔ＋ｓ＋１］−１が一致しなければ、次に、Ｐ２ＰｒｅＰ［ｔ＋ｓ＋１］と“Ｎ”を比較して、最初の連続領域と繋がった次の連続領域が存在するかどうかをチェックする（ステップＳ４６）。
【００７９】
例えば、図１１の場合は、ｔ＝２４、ｓ＝５のときに、Ｐ２ＰｒｅＰ［２４＋５］＝２０となり、Ｐ２ＰｒｅＰ［２４＋５＋１］−１＝７−１＝６となって、両者が一致しないので、Ｐ２ＰｒｅＰ［３０］＝７が“Ｎ”と比較される。
【００８０】
Ｐ２ＰｒｅＰ［ｔ＋ｓ＋１］が“Ｎ”でなければ、次の連続領域が存在することが分かる。そこで、その領域の先頭の値Ｐ２ＰｒｅＰ［ｔ＋ｓ＋１］から求められるアドレスＰ２ＰｒｅＰ［ｔ＋ｓ＋１］−（ｓ＋１）を新たな一致候補の位置として、その文字列と符号化対象の文字列とを比較する。
【００８１】
ここでは、まず、アドレスｔを始点とする長さｓ＋１の文字列をＳｔｒ（ｔ，ｓ）＝（ＩｎＢｕｆ［ｔ］，ＩｎＢｕｆ［ｔ＋１］，．．．，ＩｎＢｕｆ［ｔ＋ｓ］）とおいて、Ｓｔｒ（Ｐ２ＰｒｅＰ［ｔ＋ｓ＋１］−（ｓ＋１），ｓ）とＳｔｒ（ｔ，ｓ）とを比較する（ステップＳ４７）。
【００８２】
これらの文字列が一致すれば、新たな一致候補を最長一致文字列とみなして、ｓ＝ｓ＋１とおき、ｐ＝Ｐ２ＰｒｅＰ［ｔ＋ｓ＋１］−（ｓ＋１）とおいて（ステップＳ４８）、ステップＳ４４以降の処理を繰り返す。
【００８３】
そして、ステップＳ４７において、２つの文字列が一致しなくなると、（ｐ，（ｓ＋３））を符号として出力し、ｔ＝ｔ＋ｓ＋３とおいて（ステップＳ４９）、ステップＳ５０以降の処理を行う。
【００８４】
また、ステップＳ４６において、Ｐ２ＰｒｅＰ［ｔ＋ｓ＋１］が“Ｎ”であれば、次の連続領域が存在しないので、そのままステップＳ４９以降の処理を行う。こうして、最終的に、一致長が最も長い文字列の位置と長さが符号として出力される。
【００８５】
図１１の場合は、ステップＳ４７において、Ｓｔｒ（Ｐ２ＰｒｅＰ［２４＋５＋１］−（５＋１），５）＝Ｓｔｒ（１，５）とＳｔｒ（２４，５）が比較される。これらの文字列はともに“ｃｏｍｐｒｅ”を表すので、次に、ｓ＝６、ｐ＝１とおいて、ステップＳ４４以降の処理が繰り返される。
【００８６】
そして、ｓ＝８のとき、ステップＳ４６において、Ｐ２ＰｒｅＰ［２４＋８＋１］＝Ｎとなるので、（１，（８＋３））＝（１，１１）のような符号が生成される。したがって、最終的には、“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ（１，８）＿（１，１１）”のような圧縮データが生成される。
【００８７】
次に、図１４から図１６までは、ハッシュテーブルを用いたデータ圧縮処理を示している。この処理では、図７の逆引きリストの代わりに、ハッシュテーブルを用いて、順位リストがアクセスされる。
【００８８】
この場合、一致検出部２２は、図１４に示すように、ハッシュテーブル５１、照合部５２、および更新部５３を備える。ハッシュテーブル５１は、入力バッファ２１内の符号化対象の文字列の接頭部から、順位リスト２７における同じ接頭部を有する文字列の順位を求めるための情報を格納する。そして、一致検出部２２は、ハッシュテーブル５１から得られた順位、または、それより上の順位のアドレスから始まる文字列を、一致候補として採用する。
【００８９】
照合部５２は、符号化対象の文字列と一致候補の文字列とを照合し、一致した文字列の長さを求める。そして、符号生成部２３は、得られた長さを一致長とし、一致した文字列のアドレスを一致位置として、文字列を符号化する。最長一致検索を行う場合は、複数の一致候補のうち最も長い一致長を有するものを符号化する。また、更新部５３は、ハッシュテーブル５１から得られる順位を、最近出現した、同じ接頭部を有する文字列の順位に変更する。
【００９０】
図１５は、このようなハッシュテーブルを用いて順位リストにアクセスする処理の例を示している。図１５の順位リストＯｄｒ２Ｐ［］は、図４の順位リストと同様である。ハッシュテーブルｈａｓｈ２Ｏｄｒ［］は、ハッシュ値をアドレスとして、順位リストＯｄｒ２Ｐ［］における順位番号を格納する。このテーブルにアクセスするためのハッシュ値は、例えば、図２３に示したようなハッシュコード生成部４により、ハッシュ関数Ｈを用いて生成される。また、このテーブルのサイズは一般に２M であり、整数Ｍにより指定される。
【００９１】
順位リストＯｄｒ２Ｐ［］に複数の同じ接頭部が登録されている場合、初期状態のハッシュテーブルｈａｓｈ２Ｏｄｒ［］には、その接頭部から得られるハッシュ値に対応して、それらの接頭部のブロックの１つ上の順位番号が保持される。例えば、３文字の接頭部“ｃｏｍ”は、順位リストＯｄｒ２Ｐ［］の３番目、４番目、および５番目に登録されているが、圧縮処理の開始時には、“ｃｏｍ”のハッシュ値Ｈ（“ｃｏｍ”）に対応するアドレスに、順位番号“２”が格納される。
【００９２】
繰返し文字列を検出するとき、一致検出部２２は、符号化対象の文字列の３文字の接頭部に基づいて、ハッシュテーブルｈａｓｈ２Ｏｄｒ［］と順位リストＯｄｒ２Ｐ［］にアクセスし、一致候補の文字列を求める。
【００９３】
例えば、入力バッファＩｎＢｕｆ［］のアドレス“１”を始点とする文字列“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅｃｏｍ．．．”が符号化対象であれば、まず、３文字の接頭部“ｃｏｍ”からハッシュ値Ｈ（“ｃｏｍ”）を生成する。次に、ハッシュテーブルｈａｓｈ２Ｏｄｒ［］において、そのハッシュ値のアドレスに保持された順位番号“２”を取得し、順位リストＯｄｒ２Ｐ［］のその順位にアクセスする。
【００９４】
この場合、その順位には同じ接頭部が登録されていないので、一致候補は存在しない。そこで、先頭文字“ｃ”をそのまま出力して、ハッシュテーブルｈａｓｈ２Ｏｄｒ［］のアドレスＨ（“ｃｏｍ”）に保持された順位番号“２”に１を加算する。これにより、接頭部“ｃｏｍ”から得られる順位“２”が、１つ下の順位“３”に変更される。
【００９５】
その後、アドレス“１５”を始点とする文字列“ｃｏｍｐｒｅｓｓ＿ｃｏｍ．．．”が符号化対象になったとき、接頭部“ｃｏｍ”のハッシュ値に基づき、ハッシュテーブルｈａｓｈ２Ｏｄｒ［］から、更新された順位番号“３”を取得する。そして、順位リストＯｄｒ２Ｐ［］のその順位にアクセスする。
【００９６】
次に、その順位“３”に保持されたアドレス“１”を取得し、そのアドレスを始点とする文字列“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅｃｏｍ．．．”を一致候補とする。そして、一致位置と一致長の符号を出力し、再び、ハッシュテーブルｈａｓｈ２Ｏｄｒ［］の値を更新する。これにより、接頭部“ｃｏｍ”から得られる順位“３”が、１つ下の順位“４”に変更される。
【００９７】
その後、アドレス“２４”を始点とする文字列“ｃｏｍｐｒｅｓｓｉｏｎ”が符号化対象になったとき、ハッシュテーブルｈａｓｈ２Ｏｄｒ［］から、更新された順位番号“４”を取得し、順位リストＯｄｒ２Ｐ［］のその順位にアクセスする。
【００９８】
次に、その順位“３”と、その１つ上の順位“４”に保持されたアドレス“１”、“１５”を取得する。そして、それらのアドレスを始点とする文字列“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅｃｏｍ．．．”および“ｄｅｃｏｍｐｒｅｓｓ＿ｃｏｍ．．．”を一致候補とする。ここで、最長一致検索を行わない場合は、順位“３”の文字列“ｄｅｃｏｍｐｒｅｓｓ＿ｃｏｍ．．．”のみが一致候補となり、最長一致検索を行う場合は、両方の文字列が一致候補となる。
【００９９】
このように、ハッシュテーブルを設けることで、容易に順位リストにアクセスすることができ、文字列検索が効率化される。また、ハッシュテーブルの長さは順位リストの長さ以下にすることができるので、これらを合わせても、入力バッファの長さに比例するメモリ量以内で、必要な情報を格納することができる。また、符号化が行われる度に、ハッシュテーブルが指す順位を１つずつ下にシフトすることにより、最近出現した一致候補の順位を保持することができ、最長一致検索が効率化される。
【０１００】
図１６は、図１４の一致検出部を用いたデータ圧縮処理のフローチャートである。この処理では、最長一致検索は行われず、最近出現した一致候補のみが検索される。図１６のステップＳ６３〜Ｓ６７およびＳ６９〜Ｓ７１の処理は、図８のステップＳ３〜Ｓ７およびＳ８〜Ｓ１０の処理と同様である。
【０１０１】
データ圧縮装置は、まず、入力バッファＩｎＢｕｆ［］に、ＢＵＦＳＩＺＥ分のデータを入力し、変数ｔを１とおく（ステップＳ６１）。また、ＩｎＢｕｆ［］のデータから順位リストＯｄｒ２Ｐ［］を作成し、Ｏｄｒ２Ｐ［］用のハッシュテーブルｈａｓｈ２Ｏｄｒ［］を作成する。
【０１０２】
次に、ここでは、まず、アドレスｔを始点とする３文字の文字列をＣｔ＝（ＩｎＢｕｆ［ｔ］，ＩｎＢｕｆ［ｔ＋１］，ＩｎＢｕｆ［ｔ＋２］）として、ハッシュ値を表す変数ｈａｓｈをＨ（Ｃｔ）とおく（ステップＳ６２）。また、最近出現した一致候補の順位を表す変数ｏｄｒを、ｈａｓｈ２Ｏｄｒ［ｈａｓｈ］とおき、一致位置を表す変数ｐを、Ｏｄｒ２Ｐ［ｏｄｒ］とおく。
【０１０３】
次に、ステップＳ６３〜Ｓ６７の処理により、アドレスｔを始点とする文字列がｔより前に出現しているかどうかをチェックし、そのような文字列が出現していれば、一致位置と一致長を符号として出力する。そして、ｈａｓｈ２Ｏｄｒ［ｈａｓｈ］に１を加算して、ｈａｓｈに対応する順位を１つ下にシフトし（ステップＳ６８）、ステップＳ６９以降の処理を行う。また、ステップＳ７１において、ＩｎＢｕｆ［ｔ］を符号として出力し、ｔ＝ｔ＋１とおいた後は、ステップＳ６８以降の処理を行う。
【０１０４】
図１６の処理による圧縮結果は、図８の処理による結果と同様である。また、最長一致検索を行う場合は、図１６の処理に対して、図９と同様の変更を加えればよい。
【０１０５】
ところで、上述した順位リストは、入力バッファ内の各アドレスを始点とする文字列の接頭部を、各文字のコード順にソートして、各文字列の出現位置のアドレスを並べ換えることにより、生成される。このとき、基底法（radix sort）、クイックソート、バブルソート等の任意のソート方法を用いることができる。
【０１０６】
例えば、基底法では、Ｎ文字（Ｎバイト）の接頭部に含まれるｋ番目（ｋ＝１，．．．，Ｎ）の文字に注目してビンソート（bin sort）を行う操作を、Ｎ番目の文字から順に繰り返すことで、ソート処理が行われる。また、クイックソートでは、Ｎ文字の接頭部の集合を１つの接頭部を基準にして２つに分割する操作を繰り返すことで、ソート処理が行われる。また、バブルソートでは、隣接する２つの接頭部を比較して、その結果からそれらの接頭部を交換する操作を繰り返すことで、ソート処理が行われる。
【０１０７】
図１７および図１８は、基底法に基づく順位リスト生成処理のフローチャートである。ここでは、図５のソート部２５により、３文字の接頭部の各文字についてビンソートが行われる。実験的には、接頭部を３文字に限定してソートすることで、最長一致検索が効率化されることが分かっている。
【０１０８】
ビンソートにおいては、０〜２５５の各値（文字コード）の出現回数がカウントされ、各カウント値を元にして、その文字コード未満の文字コードの個数が計算される。これにより、出現した各文字コードが最終的に配列のどの位置に納まるべきかが決定される。
【０１０９】
入力バッファＩｎＢｕｆ［］にＢＵＦＳＩＺＥ分のデータが入力されると、ソート部２５は、まず、０〜２５５の文字コードの出現回数を表す配列Ｃｏｕｎｔｅｒ［２５６］の各要素を０に初期化し、変数ｔを１とおく（ステップＳ８１）。
【０１１０】
次に、Ｃｏｕｎｔｅｒ［ＩｎＢｕｆ［ｔ］］に１を加算して、ＩｎＢｕｆ［ｔ］に保持された文字コードの出現回数をインクリメントする（ステップＳ８２）。そして、ｔに１を加算して、ｔとＢＵＦＳＩＺＥを比較する（ステップＳ８３）。ｔ＜ＢＵＦＳＩＺＥであれば、ステップＳ８２の処理を繰り返し、ｔがＢＵＦＳＩＺＥに達すると、ｔ＝１、Ｓｕｍ［０］＝０とおく（ステップＳ８４）。
【０１１１】
次に、Ｓｕｍ［ｔ］＝Ｃｏｕｎｔｅｒ［ｔ−１］＋Ｓｕｍ［ｔ−１］とおき、ｔに１を加算して（ステップＳ８５）、ｔと２５６を比較する（ステップＳ８６）。ここで、Ｓｕｍ［ｔ］は、０〜ｔ−１までの文字コードの出現回数の総和を表す。ｔ≦２５６であれば、ステップＳ８５の処理を繰り返し、ｔが２５６を越えると、次に、図１８の処理を行う。
【０１１２】
図１８では、ソート部２５は、まず、接頭部の３番目の文字でビンソートを行う。この場合、まず、ｔ＝１とおき、ＳｔａｃｋＰ［］にＳｕｍ［］をコピーする（ステップＳ８７）。ここで、配列Ａ［］は、ＩｎＢｕｆ［］のアドレスｔを始点とする文字列の３番目の文字でソートしたアドレスを格納する。３番目の文字が値ｘである場合、ＳｔａｃｋＰ［ｘ］は、ソート結果として格納されるべき配列Ａ［］の添字を格納する。
【０１１３】
次に、Ａ［ＳｔａｃｋＰ［ＩｎＢｕｆ［ｔ＋２］］］＝ｔとおき、ＳｔａｃｋＰ［ＩｎＢｕｆ［ｔ＋２］］に１を加算し、ｔに１を加算する（ステップＳ８８）。ここで、ＳｔａｃｋＰ［ＩｎＢｕｆ［ｔ＋２］］は、アドレスｔを始点とする接頭部の３番目の文字に対応するＡ［］の添字を表し、Ａ［ＳｔａｃｋＰ［ＩｎＢｕｆ［ｔ＋２］］］は、その接頭部のアドレスを表す。次に、ｔとＢＵＦＳＩＺＥを比較し（ステップＳ８９）、ｔ＜ＢＵＦＳＩＺＥであれば、ステップＳ８８の処理を繰り返す。
【０１１４】
そして、ｔがＢＵＦＳＩＺＥに達すると、次に、生成された配列Ａ［］を、接頭部の２番目の文字でビンソートする。この場合、まず、ｔ＝１とおき、ＳｔａｃｋＰ［］にＳｕｍ［］をコピーする（ステップＳ９０）。ここで、配列ＳｔａｃｋＰ［］は、ソート結果を格納する配列Ｂ［］の添字を格納する。
【０１１５】
次に、Ｂ［ＳｔａｃｋＰ［ＩｎＢｕｆ［Ａ［ｔ］＋１］］］＝ｔとおき、ＳｔａｃｋＰ［ＩｎＢｕｆ［Ａ［ｔ］＋１］］に１を加算し、ｔに１を加算する（ステップＳ９１）。ここで、ＳｔａｃｋＰ［ＩｎＢｕｆ［Ａ［ｔ］＋１］］は、配列Ａ［］の添字ｔの位置に格納された接頭部の２番目の文字に対応するＢ［］の添字を表し、Ｂ［ＳｔａｃｋＰ［ＩｎＢｕｆ［Ａ［ｔ］＋１］］］は、その接頭部のアドレスを表す。次に、ｔとＢＵＦＳＩＺＥを比較し（ステップＳ９２）、ｔ＜ＢＵＦＳＩＺＥであれば、ステップＳ９１の処理を繰り返す。
【０１１６】
そして、ｔがＢＵＦＳＩＺＥに達すると、次に、生成された配列Ｂ［］を、接頭部の１番目の文字でビンソートする。この場合、まず、ｔ＝１とおき、ＳｔａｃｋＰ［］にＳｕｍ［］をコピーする（ステップＳ９３）。ここで、配列ＳｔａｃｋＰ［］は、ソート結果を格納する順位リストＯｄｒ２Ｐ［］の添字（順位番号）を格納する。
【０１１７】
次に、Ｏｄｒ２Ｐ［ＳｔａｃｋＰ［ＩｎＢｕｆ［Ｂ［ｔ］］］］＝ｔとおき、ＳｔａｃｋＰ［ＩｎＢｕｆ［Ｂ［ｔ］］］に１を加算し、ｔに１を加算する（ステップＳ９４）。ここで、ＳｔａｃｋＰ［ＩｎＢｕｆ［Ｂ［ｔ］］］は、配列Ｂ［］の添字ｔの位置に格納された接頭部の１番目の文字の順位を表し、Ｏｄｒ２Ｐ［ＳｔａｃｋＰ［ＩｎＢｕｆ［Ｂ［ｔ］］］］は、その接頭部のアドレスを表す。
【０１１８】
次に、ｔとＢＵＦＳＩＺＥを比較し（ステップＳ９５）、ｔ＜ＢＵＦＳＩＺＥであれば、ステップＳ９４の処理を繰り返す。そして、ｔがＢＵＦＳＩＺＥに達すると、処理を終了する。こうして、順位リストＯｄｒ２Ｐ［］が生成される。
【０１１９】
上述の実施形態では、順位リストを生成するときに、各文字列の固定長（Ｎ文字）の接頭部を比較することで文字列をソートしているが、その代わりに、可変長の接頭部を比較するようにしてもよい。また、上述の実施形態では、ＬＺ７７符号化における文字列検索について説明したが、本発明は、ＬＺ７７符号化に限らず、任意の符号化における文字列検索に適用することができる。
【０１２０】
図５のデータ圧縮装置は、例えば、図１９に示すような情報処理装置（コンピュータ）を用いて構成することができる。図１９の情報処理装置は、ＣＰＵ（中央処理装置）６１、メモリ６２、入力装置６３、出力装置６４、外部記憶装置６５、媒体駆動装置６６、およびネットワーク接続装置６７を備え、それらはバス６８により互いに接続されている。
【０１２１】
メモリ６２は、例えば、ＲＯＭ（read only memory）、ＲＡＭ（random access memory）等を含み、処理に用いられるプログラムとデータを格納する。ＣＰＵ６１は、メモリ６２を利用してプログラムを実行することにより、必要な処理を行う。
【０１２２】
例えば、図５の入力バッファ２１、出現位置保持部２６、図６の逆引きリスト３１、図１０の一致位置リスト４１、および図１４のハッシュテーブル５１は、メモリ６２内に設けられる。また、図５の一致検出部２２、符号生成部２３、符号出力部２４、ソート部２５、図６の照合部３２、図１０の領域検出部４２、照合部４３、図１４の照合部５２および更新部５３は、プログラムにより記述されたソフトウェアコンポーネントとしてメモリ６２に格納される。
【０１２３】
入力装置６３は、例えば、キーボード、ポインティングデバイス、タッチパネル等であり、ユーザからの指示や情報の入力に用いられる。出力装置６４は、例えば、ディスプレイ、プリンタ、スピーカ等であり、ユーザへの問い合わせや処理結果の出力に用いられる。
【０１２４】
外部記憶装置６５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク（magneto-optical disk）装置、テープ装置等である。情報処理装置は、この外部記憶装置６５に、上述のプログラムとデータを保存しておき、必要に応じて、それらをメモリ６２にロードして使用する。
【０１２５】
媒体駆動装置６６は、可搬記録媒体６９を駆動し、その記録内容にアクセスする。可搬記録媒体６９としては、メモリカード、フロッピーディスク、ＣＤ−ＲＯＭ（compact disk read only memory ）、光ディスク、光磁気ディスク等、任意のコンピュータ読み取り可能な記録媒体が用いられる。ユーザは、この可搬記録媒体６９に上述のプログラムとデータを格納しておき、必要に応じて、それらをメモリ６２にロードして使用する。
【０１２６】
ネットワーク接続装置６７は、ＬＡＮ（Local Area Network）等の任意の通信ネットワークに接続され、通信に伴うデータ変換を行う。また、情報処理装置は、上述のプログラムとデータをネットワーク接続装置６７を介して他の装置から受け取り、必要に応じて、それらをメモリ６２にロードして使用する。
【０１２７】
図２０は、図１９の情報処理装置にプログラムとデータを供給することのできるコンピュータ読み取り可能な記録媒体を示している。可搬記録媒体６９や外部のデータベース７０に保存されたプログラムとデータは、メモリ６２にロードされる。そして、ＣＰＵ６１は、そのデータを用いてそのプログラムを実行し、必要な処理を行う。
【０１２８】
（付記１）  圧縮すべき文字列データを格納するデータ格納手段と、
前記データ格納手段内の複数のアドレスの各々を始点とする各文字列を、各文字列の内容に基づいて並べ換えるソート手段と、
並べ換えられた文字列の順序で、各文字列のアドレスを表すアドレス情報を格納する出現位置格納手段と、
前記出現位置格納手段に格納されたアドレス情報に基づいて、繰返し文字列を検出する検出手段と、
検出された繰返し文字列を符号化して出力する符号化手段と
を備えることを特徴とするデータ圧縮装置。
（付記２）  前記ソート手段は、各文字列に含まれる所定文字数の接頭部を用いて、文字列を並べ換えることを特徴とする付記１記載のデータ圧縮装置。
（付記３）  前記ソート手段は、各文字列に含まれる３文字の接頭部を用いて、前記文字列を並べ換えることを特徴とする付記２記載のデータ圧縮装置。
（付記４）  前記ソート手段は、複数の同じ接頭部が互いに隣接するように、前記文字列を並べ換えることを特徴とする付記２記載のデータ圧縮装置。
（付記５）  前記ソート手段は、基底法を用いて、前記文字列を並べ換えることを特徴とする付記２記載のデータ圧縮装置。
（付記６）  前記ソート手段は、クイックソートを用いて、前記文字列を並べ換えることを特徴とする付記２記載のデータ圧縮装置。
（付記７）  符号化対象文字列のアドレスから、前記出現位置格納手段における該符号化対象文字列の順位を求めるための情報を格納する逆引き手段をさらに備え、前記検出手段は、該逆引き手段から得られた順位より上の順位に格納されたアドレス情報に対応する文字列を一致候補とし、該符号化対象文字列と該一致候補とを照合して一致長を求め、前記符号化手段は、該一致候補の位置を示す情報と該一致長とを用いて、該符号化対象文字列を符号化することを特徴とする付記１記載のデータ圧縮装置。
（付記８）  各文字列のアドレスに対応して、最近出現した同じ文字列のアドレス情報を格納する一致位置格納手段をさらに備え、前記検出手段は、前記出現位置格納手段に格納されたアドレス情報から、該一致位置格納手段に格納されるアドレス情報を生成し、該一致位置格納手段の隣接するアドレス情報を比較して、アドレス情報が連続している連続領域を検出し、前記符号化手段は、該連続領域の位置に対応する文字列を符号化対象文字列とし、該連続領域に格納されたアドレス情報と該連続領域の長さとを用いて、該符号化対象文字列を符号化することを特徴とする付記１記載のデータ圧縮装置。
（付記９）  前記検出手段は、前記出現位置格納手段の１つの順位に注目し、注目する順位の文字列の接頭部が１つ上の順位の文字列の接頭部と同じであるとき、前記一致位置格納手段において、該注目する順位に格納されたアドレス情報に対応する位置に、該１つ上の順位に格納されたアドレス情報を格納することを特徴とする付記８記載のデータ圧縮装置。
（付記１０）  前記検出手段は、前記一致位置格納手段内で２つ以上の連続領域が繋がっている部分を検出し、該２つ以上の連続領域に格納されたアドレス情報に基づいて複数の一致候補の文字列を求め、前記符号化手段は、該複数の一致候補のうち最も長い一致長を有する一致候補の位置を示す情報と、該最も長い一致長とを用いて、前記符号化対象文字列を符号化することを特徴とする付記８記載のデータ圧縮装置。
（付記１１）  符号化対象文字列に含まれる所定文字数の接頭部から、前記出現位置格納手段における同じ接頭部を含む文字列の順位を求めるための情報を格納する検索手段をさらに備え、前記検出手段は、該検索手段から得られた順位に格納されたアドレス情報に対応する文字列を一致候補とし、該符号化対象文字列と該一致候補とを照合して一致長を求め、前記符号化手段は、該一致候補の位置を示す情報と該一致長とを用いて、該符号化対象文字列を符号化することを特徴とする付記１記載のデータ圧縮装置。
（付記１２）  前記検出手段は、前記所定文字数の接頭部に対応して前記検索手段から得られる順位が、最近出現した同じ接頭部を含む文字列の順位になるように、該検索手段に格納された情報を更新することを特徴とする付記１１記載のデータ圧縮装置。
（付記１３）  コンピュータのためのプログラムを記録した記録媒体であって、前記プログラムは、
圧縮すべき文字列データが有する複数のアドレスの各々を始点とする各文字列を、各文字列の内容に基づいて並べ換え、
並べ換えられた文字列の順序で、各文字列のアドレスを表すアドレス情報を記録し、
記録されたアドレス情報に基づいて、繰返し文字列を検出し、
検出された繰返し文字列を符号化する
処理を前記コンピュータに実行させることを特徴とするコンピュータ読み取り可能な記録媒体。
（付記１４）  圧縮すべき文字列データが有する複数のアドレスの各々を始点とする各文字列を、各文字列の内容に基づいて並べ換え、
並べ換えられた文字列の順序で、各文字列のアドレスを表すアドレス情報を記録し、
記録されたアドレス情報に基づいて、繰返し文字列を検出し、
検出された繰返し文字列を符号化する
ことを特徴とするデータ圧縮方法。
（付記１５）  圧縮すべき文字列データが有する複数のアドレスの各々を始点とする各文字列を、各文字列の内容に基づいて並べ換え、
並べ換えられた文字列の順序で、各文字列のアドレスを表すアドレス情報を記録し、
記録されたアドレス情報に基づいて、繰返し文字列を検出し、
検出された繰返し文字列を符号化する
処理をコンピュータに実行させるためのプログラム。
【０１２９】
【発明の効果】
本発明によれば、データを圧縮するとき、入力データにほぼ比例したメモリ量で文字列検索を行うことができ、特に、少量のデータを圧縮する場合、既存の方法より少ないメモリ量で済む。また、最長一致文字列の検索の負荷が低いため、高い圧縮率の処理を高速に行うことが可能となる。
【図面の簡単な説明】
【図１】本発明のデータ圧縮装置の原理図である。
【図２】入力バッファを示す図である。
【図３】第１の順位リストを示す図である。
【図４】第２の順位リストを示す図である。
【図５】データ圧縮装置の構成図である。
【図６】第１の一致検出部の構成図である。
【図７】逆引きリストと順位リストを示す図である。
【図８】第１の圧縮処理のフローチャートである。
【図９】第２の圧縮処理のフローチャートである。
【図１０】第２の一致検出部の構成図である。
【図１１】順位リストと一致位置リストを示す図である。
【図１２】第３の圧縮処理のフローチャートである。
【図１３】第４の圧縮処理のフローチャートである。
【図１４】第３の一致検出部の構成図である。
【図１５】ハッシュテーブルと順位リストを示す図である。
【図１６】第５の圧縮処理のフローチャートである。
【図１７】順位リスト生成処理のフローチャート（その１）である。
【図１８】順位リスト生成処理のフローチャート（その２）である。
【図１９】情報処理装置の構成図である。
【図２０】記録媒体を示す図である。
【図２１】従来の圧縮方法を示す図である。
【図２２】ＬＵＴによる検索を示す図である。
【図２３】ハッシュテーブルによる検索を示す図である。
【符号の説明】
１  スライドバッファ
２  ＬＵＴ
３  リンクドリスト
４  ハッシュコード生成部
５  ハッシュ値
６、５１  ハッシュテーブル
１１  データ格納手段
１２  ソート手段
１３  出現位置格納手段
１４  検出手段
１５  符号化手段
２１  入力バッファ
２２  一致検出部
２３  符号生成部
２４  符号出力部
２５  ソート部
２６  出現位置保持部
２７  順位リスト
３１  逆引きリスト
３２、４３、５２  照合部
４１  一致位置リスト
４２  領域検出部
５３  更新部
６１  ＣＰＵ
６２  メモリ
６３  入力装置
６４  出力装置
６５  外部記憶装置
６６  媒体駆動装置
６７  ネットワーク接続装置
６８  バス
６９  可搬記録媒体
７０  データベース
【図１】
0004261779.tif 000002
【図２】
0004261779.tif 000003
【図３】
0004261779.tif 000004
【図４】
0004261779.tif 000005
【図５】
0004261779.tif 000006
【図６】
0004261779.tif 000007
【図７】
0004261779.tif 000008
【図８】
0004261779.tif 000009
【図９】
0004261779.tif 000010
【図１０】
0004261779.tif 000011
【図１１】
0004261779.tif 000012
【図１２】
0004261779.tif 000013
【図１３】
0004261779.tif 000014
【図１４】
0004261779.tif 000015
【図１５】
0004261779.tif 000016
【図１６】
0004261779.tif 000017
【図１７】
0004261779.tif 000018
【図１８】
0004261779.tif 000019
【図１９】
0004261779.tif 000020
【図２０】
0004261779.tif 000021
【図２１】
0004261779.tif 000022
【図２２】
0004261779.tif 000023
【図２３】
0004261779.tif 000024