(57)【要約】  データ圧縮装置が提供される。データ圧縮装置は、圧縮前のデータの文字列中の第１の文字列の後に、前記第１の文字列と同一である第２の文字列を一致列として抽出し、前記一致列の長さと、前記第１の文字列が前記第２の文字列の幾つ前のアドレスの位置から開始されるかを示す相対位置を決定する一致列検索部と、前記一致列検索部で抽出された前記第２の文字列から、長さが前記相対位置より小さい第３の文字列を抽出する一致列分割部と、前記第３の文字列の長さを検出し、符号化する一致長符号化部と、前記相対位置を符号化する一致位置符号化部と、を含むことを特徴とする。
2015029224.tif 000002
【特許請求の範囲】
【請求項１】
圧縮前のデータの文字列中の第１の文字列の後に、前記第１の文字列と同一である第２の文字列を一致列として抽出し、前記一致列の長さと、前記第１の文字列が前記第２の文字列の幾つ前のアドレスの位置から開始されるかを示す相対位置を決定する一致列検索部と、
前記一致列検索部で抽出された前記第２の文字列から、長さが前記相対位置より小さい第３の文字列を抽出する一致列分割部と、
前記第３の文字列の長さを符号化する一致長符号化部と、
前記相対位置を符号化する一致位置符号化部と、
を含む、データ圧縮装置。
【請求項２】
前記相対距離が所定の値より小さいとき、前記第２の文字列から前記第３の文字列を抽出する、請求項１に記載のデータ圧縮装置。
【請求項３】
さらに、前記一致列検索部は、圧縮前のデータの文字列中の第１の文字列の後に、前記第１の文字列と同一である第２の文字列が存在しない、または第２の文字列が所定の長さより短い文字列を非一致列として抽出し、
前記一致列分割部は、前記第３の文字列の長さが所定の値より小さいとき、前記第３の文字列の長さの倍数であって、前記所定の値を超えない最大の値を前記非一致列またはその一部として抽出する、請求項１または２に記載のデータ圧縮装置。
【請求項４】
前記一致列分割部は、前記一致列内の循環文字列における循環の最小単位をカートンと定義し、前記第２の文字列の先頭から、カートンの整数倍の位置の全てまたは一部で前記第２の文字列を分割する、請求項１〜３のいずれか一項に記載のデータ圧縮装置。
【請求項５】
前記一致列分割部は、前記第２の文字列の先頭から前記カートンを単位として、２ｍ−１（ｍを整数）の位置の全てまたは一部で前記第２の文字列を分割する、請求項４に記載のデータ圧縮装置。
【請求項６】
前記一致列分割部は、ｌｅｎｇｔｈを前記一致長、ｃａｒｔｏｎを前記カートンの長さとしてｎ＝（ｌｅｎｇｔｈ＋ｃａｒｔｏｎ−１）÷ｃａｒｔｏｎとしたとき、前記第２の文字列の先頭から前記カートンを単位として、ｎ÷２ｍ（ｍを整数）の位置の全てまたは一部で前記第２の文字列を分割する、請求項４に記載のデータ圧縮装置。
【請求項７】
コンピュータで処理されるデータ圧縮方法であって、
圧縮前のデータの文字列中の第１の文字列の後に、前記第１の文字列と同一である第２の文字列を一致列として抽出し、前記一致列の長さと、前記第１の文字列が前記第２の文字列の幾つ前のアドレスの位置から開始されるかを示す相対位置を決定することと、
前記一致列検索部で抽出された前記第２の文字列から、長さが前記相対位置より小さい第３の文字列を抽出することと、
前記第３の文字列の長さを符号化することと、
前記相対位置を符号化することと、
を含む、データ圧縮方法。
【請求項８】
圧縮前のデータの文字列中の第１の文字列の後に、前記第１の文字列と同一である第２の文字列を一致列として抽出し、前記一致列の長さと、前記第１の文字列が前記第２の文字列の幾つ前のアドレスの位置から開始されるかを示す相対位置を決定させと、
前記一致列検索部で抽出された前記第２の文字列から、長さが前記相対位置より小さい第３の文字列を抽出させと、
前記第３の文字列の長さを検出し、符号化させと、
前記相対位置符号化させる、
処理をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ圧縮装置、方法およびプログラムに関するものである。
【背景技術】
【０００２】
データ圧縮アルゴリズムとして、１９７７年にＡｂｒａｈａｍ  Ｌｅｍｐｅｌ氏とＪａｃｏｂ  Ｚｉｖ氏が発表したＬＺ７７方式が知られている。ＬＺ７７方式は辞書式圧縮法の一つで、スライド辞書法とも呼ばれ、データを先頭から順番に符号化していく。スライド辞書法は、現在注目している位置から始まるシンボル列が、それ以前に出現していたかを探す。もし出現していたならば、シンボル列をその出現位置と長さのポインタに置き換える。スライド辞書法の名前は、シンボル列を探す範囲をスライド窓と呼び、これを辞書として使用することに由来する。【０００３】
ＬＺ７７方式では、繰返し出現するデータ列を過去に出現したシンボル列の長さと出現位置に置き換えることでデータ量を削減する。復元の際には、過去の位置から一致長分のシンボル列をコピーすることで元のデータに復元できる。また、繰返しが見つからなかったときに、見つからなかった長さと見つからなかったシンボル列を符号化する方法が示されている。【０００４】
また、中央処理装置（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、ＣＰＵ）のオペレーティングシステム（ＯＳ）によっては、１命令で複数データを扱うＳｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ（ＳＩＭＤ）命令が用意されており、１６バイト、３２バイト単位でのメモリ間のデータコピーを高速に行うことができる。ＳＩＭＤ命令を復元時のコピー処理において用いると復元処理の高速化を実現することができる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｆｉａｌａ，Ｅ．  ａｎｄ  Ｇｒｅｅｎｅ，Ｄ．（１９８９）“Ｄａｔａ  ｃｏｍｐｒｅｓｓｉｏｎ  ｗｉｔｈ  ｆｉｎｉｔｅ  ｗｉｎｄｏｗｓ” Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ ｔｈｅ ＡＣＭ、３２（４）ｐｐ． ４９０−５０５
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＬＺ７７方式では、コピー元の文字列の最後尾のアドレスがコピー先の文字列の先頭のアドレスより後方になることがある。このことを以下では、単に「コピー元とコピー先が重なる」という。たとえば、同じ文字が「aaaa…」と続くケースだと、コピー元の文字列はアドレス「1,2,3,4…」で、コピー先の文字列はアドレス「2,3,4,…」となり、アドレス「2,3,4,…」において重なりを持つ。このようなケースでは、復元処理において、ステップ１で、第１バイトを第２バイトにコピーし、ステップ２で第２バイトを第３バイトにコピーする、という手順でそれ以前に出現した文字列をコピーする。この場合、ステップ１の処理が終わっていないとステップ２の処理を行うことができない。つまり、ＬＺ７７方式は、繰返し出現するデータ列を過去に出現したデータ列の長さと出現位置に置き換えているため、単純なコピー処理で復元できるにも関わらず、コピー元とコピー先が重なっているときは、１バイトずつのコピー処理が必要となることがある。このため、復元時に高速な多バイトコピーを使用するには、まずコピー元とコピー先が重なるか否か確認する必要があり、また、重なっている場合は、１バイトずつのコピーを行う煩雑な処理が必要であるという問題がある。【０００７】
よって、本発明は、多バイトコピーを用いて復元を行う上で不都合な重なりを制限した一致列を選択して圧縮することで、高速に復元できる圧縮データを生成するデータ圧縮装置、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
データ圧縮装置が提供される。データ圧縮装置は、圧縮前のデータの文字列中の第１の文字列の後に、前記第１の文字列と同一である第２の文字列を一致列として抽出し、前記一致列の長さと、前記第１の文字列が前記第２の文字列の幾つ前のアドレスの位置から開始されるかを示す相対位置を決定する一致列検索部と、前記一致列検索部で抽出された前記第２の文字列から、長さが前記相対位置より小さい第３の文字列を抽出する一致列分割部と、前記第２または第３の文字列の長さを符号化する一致長符号化部と、前記相対位置を符号化する一致位置符号化部と、を含むことを特徴とする。
【発明の効果】
【０００９】
多バイト単位で圧縮データの復元を実現するために、元データ中で繰り返し出現する一致列を再分割してから圧縮することで、高速に復元できる圧縮データを生成することができる。
【図面の簡単な説明】
【００１０】
【図１】ＬＺ７７方式の概略を説明する図である。
【図２】比較例におけるデータ圧縮装置の機能ブロック図の例を示す図である。
【図３】比較例におけるデータ圧縮装置での圧縮処理の流れの例を示す図である。
【図４】比較例における元データと圧縮データの例を示す図である。
【図５】比較例における復元処理の流れの例を示す図である。
【図６Ａ】比較例におけるデータ圧縮装置での圧縮処理の例を示す図である。
【図６Ｂ】比較例における復元処理の例を示す図である。
【図７】実施形態におけるデータ圧縮装置の機能ブロック図の例を示す図である。
【図８】実施形態におけるデータ圧縮装置での圧縮処理の流れの例を示す図である。
【図９】実施形態における復元処理の流れの例を示す図である。
【図１０】実施例におけるデータ圧縮装置での圧縮処理の流れの例を示す図である。
【図１１】実施例における先頭位置調整処理の流れの例を示す図である。
【図１２Ａ】実施例における一致列分割処理の流れの例を示す図である。
【図１２Ｂ】実施例における一致列分割処理の流れの別の例を示す図である。
【図１３】実施例における一致長調整処理の流れの例を示す図である。
【図１４】Ｐ（１）、Ｐ（３）、…、Ｐ（２ｍ−１）で分割する例を示す図である。
【図１５】Ｐ（ｎ÷２）、Ｐ（ｎ÷４）、…、Ｐ（ｎ÷２ｍ）で分割する例を示す図である。
【図１６】Ｐ（１）、Ｐ（３）、…、Ｐ（２ｍ−１）で分割する別の例を示す図である。
【図１７】Ｐ（１）、Ｐ（３）、…、Ｐ（２ｍ−１）で分割するさらに別の例を示す図である。
【図１８】コンピュータの構成の例を示す図である。
【発明を実施するための形態】
【００１１】
以下、図面を参照して、まず、比較例について説明し、その後、実施形態について説明する。
【００１２】
また、以下ではＬＺ７７方式を用いたデータ圧縮装置、方法およびプログラムについて説明するが、もちろん、データ圧縮方法はＬＺ７７方式には限定されず、繰返し出現するデータ列を過去に出現したデータ列の長さと出現位置に置き換えることでデータ量を削減するような圧縮方法であれば適用可能である。
【００１３】
ＬＺ７７方式では、繰り返し現われる文字列を検索し、２回目以降にその文字列が現われるとき、その文字列を、出現位置と長さに関するデータに置き換えることにより、圧縮する。ここで、出現位置とは、ある文字列が複数回目に現われるとき、複数回目に現れたときの先頭位置と、以前に現れたときの先頭位置のアドレスの差であり得る。
【００１４】
以下では、次のような表記規則を用いる。
（規則１）一致列は、（一致長、一致列の開始位置）で表す、
（規則２）非一致列は、｛非一致長、非一致文字列｝で表す。
ここで、一致列の開始位置は、幾つ前のアドレスに同一の文字列があるか、を示す。一致列の開始位置は、一致位置、相対位置とも呼ぶ。一致列の開始位置（相対位置）は、ある文字列が複数回目に現われるとき、複数回目に現れたときの先頭位置と、以前に現れたときの先頭位置のアドレスの差で、すなわち、相対距離の大きさであり得る。たとえば、一致列の開始位置が、“１４”である場合、複数回目に現れたときの先頭位置は、以前に現れたときの先頭位置より１４アドレス分だけ後方に位置することを意味しても良い。元データの文字列中の一致列を（一致長、一致列の開始位置）のような形式の圧縮データに符号化するとも言う。同様に、元データの文字列中の非一致列を｛非一致長、非一致文字列｝のような形式の圧縮データに符号化するとも言う。
【００１５】
＜比較例＞
図１〜６Ｂを参照して、比較例について説明する。以下の比較例の説明は、ＬＺ７７方式の概略の説明でもある。
【００１６】
図１は、ＬＺ７７方式の概略を説明する図である。
例えば、図１に示されている第１〜３４番目のアドレスの位置に格納されている圧縮前のデータ（以下、単に元データと呼ぶことがある）では、第１〜１４番目のアドレスの位置に“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”という文字列が格納されており、第１５〜２２番目のアドレスの位置に“ｃｏｍｐｒｅｓｓ”という文字列が格納されており、第２３番目のアドレスの位置には“＿”（アンダーバー）が、第２４〜３４番目のアドレスの位置には“ｃｏｍｐｒｅｓｓｉｏｎ”という文字列が格納されている。よって、圧縮データは、まず、第１〜１４番目のアドレスの位置に“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”は非一致列であり、非一致長は１４であるので、圧縮データでは、“｛１４、ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ｝”と表される。元データの第１５〜２２番目のアドレスの位置に“ｃｏｍｐｒｅｓｓ”とあるが、これは第１〜８番目のアドレスの位置の文字列と同一である。“ｃｏｍｐｒｅｓｓ”は８文字であり、一致文字列が開始されるアドレスの位置は１４アドレス前であるので、一致列の開始位置は１４である。よって、元データの第１５〜２２番目のアドレスのデータは、圧縮データでは “（８、１４）”と符号化される。元データの第２３番目のアドレスの位置に格納されている“＿”（アンダーバー）は、それ以前には出現していないので、圧縮データでは“｛１、＿｝”と符号化される。元データの第２４〜３４番目のアドレスの位置に“ｃｏｍｐｒｅｓｓｉｏｎ”とあるが、これは第１〜８番目のアドレスの位置の文字列と同一である。“ｃｏｍｐｒｅｓｓ”は８文字であり、一致文字列が開始されるアドレスの位置は２３アドレス前であるので、一致列の開始位置は２３である。よって、元データの第２４〜３４番目のアドレスのデータは、圧縮データでは “（１１、２３）”と符号化される。
【００１７】
このように、図１に示されている元データの文字列は、圧縮データでは、“｛１４、ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ｝（８、１４）｛１、＿｝１１、２３）”のように表される。
【００１８】
図２は、ＬＺ７７方式を用いて元データを圧縮し、圧縮データを生成する圧縮装置の機能ブロック図の例である。
【００１９】
圧縮装置１０は、入力バッファ部１１、一致列検索部１２、一致長符号化部１３、一致位置符号化部１４、非一致長符号化部１５、非一致列符号化部１６、および出力バッファ部１７を含む。
【００２０】
入力バッファ部１１は、例えば、図１に示されている第１〜３４番目のアドレスの位置に格納されているような圧縮前のデータ（元データ）を外部から受信し、必要に応じて、一時的に格納する。図１に示されている例では、元データは、“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅｃｏｍｐｒｅｓｓｉｏｎ＿ｃｏｍｐｒｅｓｓｉｏｎ．”である。
【００２１】
一致列検索部１２は、入力バッファ部１１に格納された元データの文字列に、繰り返し出現する文字列（一致列）が存在するかどうかを検索、抽出する。また、一致列検索部１２は、一致列が存在する場合は、その一致列を決定する。例えば、図１に示されている例では、“ｃｏｍｐｒｅｓｓ”なる文字列や、“ｃｏｍｐｒｅｓｓｉｏｎ” なる文字列は複数回出現するので、一致列である。
【００２２】
一致長符号化部１３は、一致列検索部１２で検索され、抽出された一致列の長さを抽出し、規則１に従って、一致列を（一致長、一致列の開始位置）と表すときの、第１要素を決定する。例えば、図１に示されている例では、元データの第１５〜２２番目のアドレスの位置にある“ｃｏｍｐｒｅｓｓ”なる文字列は、第１〜８番目のアドレスの位置の文字列と同一であり、８文字である。よって、一致長符号化部１３によって、一致長は８と符号化される。
【００２３】
一致位置符号化部１４は、一致列検索部１２で検索され、抽出された一致列が幾つ前のアドレスの位置から開始されるかを検出し、規則１に従って、一致列を（一致長、一致列の開始位置）と表すときの、第２要素を決定する。例えば、図１に示されている例では、元データの第１５〜２２番目のアドレスの位置にある“ｃｏｍｐｒｅｓｓ”なる文字列は、第１〜８番目のアドレスの位置の文字列と同一であり、一致文字列が開始されるアドレスの位置は１４アドレス前である。よって、一致長符号化部１３によって、一致列の開始位置は１４と符号化される。
【００２４】
非一致長符号化部１５は、一致列検索部１２では一致列として抽出されなかった非一致列の長さを抽出し、規則２に従って、非一致列を｛非一致長、非一致文字列｝と表すときの、第１要素を決定する。例えば、図１に示されている例では、第１〜１４番目のアドレスの位置に“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”は非一致列であり、１４文字である。よって、非一致長符号化部１５によって、非一致長は１４と符号化される。
【００２５】
非一致列符号化部１６は、一致列検索部１２では一致列として抽出されなかった非一致列を抽出し、規則２に従って、非一致列を｛非一致長、非一致文字列｝と表すときの、第２要素を決定する。例えば、図１に示されている例では、第１〜１４番目のアドレスの位置に“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”は非一致列である。よって、非一致長符号化部１５によって、非一致文字列は“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”と符号化される。
【００２６】
出力バッファ部１７は、一致長符号化部１３、一致位置符号化部１４、非一致長符号化部１５、および非一致列符号化部１６の結果を用いて、元データを符号化、圧縮した結果である圧縮データを生成し、必要に応じて、一時的に格納する。たとえば、図１に示されている例では、元データである文字列“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅｃｏｍｐｒｅｓｓｉｏｎ＿ｃｏｍｐｒｅｓｓｉｏｎ．”は、“｛１４、ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ｝（８、１４）｛１、＿｝（１１、２３）”と符号化される。
【００２７】
図３は、比較例におけるデータ圧縮装置での圧縮処理の流れの例を示す図である。
処理が開始されるとＳ１００で一致列検索部１２は、元データの文字列に、繰り返し出現する文字列である一致列が存在するかどうかを検索する。本ステップの処理が終了すると、処理はＳ１０２に進む。元データの文字列は、入力バッファ部１１に格納されているものであっても良い。
【００２８】
Ｓ１０２で一致列検索部１２は、一致列が見つかったかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、一致列が見つかった場合には、処理はＳ１０４に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、一致列が見つからなかった場合には、処理はＳ１１２に進む。
【００２９】
Ｓ１０４で一致列検索部１２は、Ｓ１０２で見つかった一致列の最初の文字のアドレスの位置の直前の文字列が非一致列かどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、直前の文字列が非一致列である場合には、処理はＳ１０６に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、直前の文字列が非一致列ではない場合には、処理はＳ１０８に進む。
【００３０】
Ｓ１０６で非一致長符号化部１５と非一致列符号化部１６は、Ｓ１０２で見つかった一致列の直前の非一致列を符号化する。符号化の例は、図１に示されている。本ステップの処理が終了すると、処理はＳ１０８に進む。
【００３１】
Ｓ１０８で一致長符号化部１３と一致位置符号化部１４は、Ｓ１０２で見つかった一致列を符号化する。符号化の例は、図１に示されている。本ステップの処理が終了すると、処理はＳ１１０に進む。
【００３２】
Ｓ１１０では出力バッファ部１７は、圧縮すべき全ての元データを処理したかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、全ての元データを処理した場合には、圧縮処理を終了する。また、もしこの判定の結果が“ＮＯ”、すなわち、全ての元データを処理していない場合には、処理はＳ１００に戻る。
【００３３】
Ｓ１０２で一致列が見つからなかった場合は、Ｓ１１２に進む。
Ｓ１１２で非一致長符号化部１５と非一致列符号化部１６はそれぞれ、一致が見つからなかった非一致列の長さと文字列を抽出する。そして、非一致列の長さおよび文字列に関する情報をそれぞれ、非一致長符号化部１５と非一致列符号化部１６内に一時的に記憶する。この情報は、Ｓ１０６で用いられる。本ステップの処理が終了すると、処理はＳ１００に戻る。
【００３４】
図４は、比較例における元データと圧縮データの例を示す図である。
図４では、元データが循環文字列である場合を取り上げている。循環文字列の長さをｃａｒｔｏｎ（カートン）と呼ぶ。図６においても、上記規則１、２を用いる。
【００３５】
また、図４において、Ｐ（ｎ）（ｎは整数）は、ｃａｒｔｏｎの区切りを示す。
ｃａｒｔｏｎ＝１の場合の例として、図４には、元データが“ａａａａａａａａａａｂ”の場合が示されている。
【００３６】
この場合、第１番目のアドレスの位置の“ａ”が非一致列であり、第２〜１０番目のアドレスの位置の“ａａａａａａａａａ”が一致列である。
【００３７】
元データが“ａａａａａａａａａａｂ”の場合、圧縮データは “｛１、ａ｝、（９、１）、｛１、ｂ｝”となる。ここで、圧縮データ中の一致列を示す部分“（９、１）”の第２要素の１は、ｃａｒｔｏｎ（カートン）に一致する。
【００３８】
ｃａｒｔｏｎ＝２の場合の例として、図４には、元データが“ａｂａｂａｂａｂａｂｃ”の場合が示されている。この場合、第１〜２番目のアドレスの位置の“ａｂ”が非一致列であり、第３〜１０番目のアドレスの位置の“ａｂａｂａｂａｂ”が一致列である。第１１番目のアドレスの位置の文字“ｃ”は非一致列である。循環文字列の長さが２であるので、第２〜１０番目のアドレスは２文字ずつ分割され、第４番目のアドレスの位置がＰ（１）、第６番目のアドレスの位置がＰ（２）のように分割される。
【００３９】
元データが“ａｂａｂａｂａｂａｂｃ”の場合、圧縮データは “｛２、ａｂ｝、（１０、２）、｛１、ｃ｝”となる。
【００４０】
ｃａｒｔｏｎ＝３の場合の例として、図４には、元データが“ａｂｃａｂｃａｂｃａｂｃｄ”の場合が示されている。この場合、第１〜３番目のアドレスの位置の“ａｂｃ”が非一致列であり、第４〜１２番目のアドレスの位置の“ａｂｃａｂｃａｂｃ”が一致列である。第１３番目のアドレスの位置の文字“ｄ”は非一致列である。
【００４１】
元データが“ａｂｃａｂｃａｂｃａｂｃｄ”の場合、圧縮データは “｛３、ａｂｃ｝、（９、３）、｛１、ｄ｝”となる。
【００４２】
ｃａｒｔｏｎ＝４の場合の例として、図４には、元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｄｅ”の場合が示されている。この場合、第１〜４番目のアドレスの位置の“ａｂｃｄ”が非一致列であり、第５〜１６番目のアドレスの位置の“ａｂｃｄａｂｃｄａｂｃｄ”が一致列である。第１７番目のアドレスの位置の文字“ｅ”は非一致列である。
【００４３】
元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｄｅ”の場合、圧縮データは “｛４、ａｂｃｄ｝、（１２、４）、｛１、ｅ｝”となる。
【００４４】
ｃａｒｔｏｎ＝７の場合の例として、図４には、元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｇｈ”の場合が示されている。この場合、第１〜７番目のアドレスの位置の“ａｂｃｄｅｆｇ”が非一致列であり、第８〜２１番目のアドレスの位置の“ａｂｃｄｅｆｇａｂｃｄｅｆｇ”が一致列である。第２２番目のアドレスの位置の文字“ｈ”は非一致列である。
【００４５】
元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｇｈ”の場合、圧縮データは“｛７、ａｂｃｄｅｆｇ｝、（１４、７）、｛１、ｈ｝”となる。
【００４６】
ｃａｒｔｏｎ＝８の場合の例として、図４には、元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈｉ”の場合が示されている。この場合、第１〜８番目のアドレスの位置の“ａｂｃｄｅｆｇｈ”が非一致列であり、第９〜２４番目のアドレスの位置の“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈ”が一致列である。第２５番目のアドレスの位置の文字“ｉ”は非一致列である。
【００４７】
元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈｉ”の場合、圧縮データは “｛８、ａｂｃｄｅｆｇｈ｝、（１６、８）、｛１、ｉ｝”となる。
【００４８】
ここで、図３のような処理によって圧縮されたデータの復元処理について図５を参照して説明する。
【００４９】
図５の処理は、たとえば、図１５のような構成を有するコンピュータよって処理され得る。図１５に示されているコンピュータ１００は、中央処理装置（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ））１０２と、メモリ、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）１０４、及びＲａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）１０６を備えている。
【００５０】
処理が開始される前に、圧縮データがＲＡＭ１０６に格納されているものとする。処理は、圧縮データの列、たとえば図１の例では、圧縮データ“｛１４、ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ｝（８、１４）｛１、＿｝（１１、２３）”を括弧単位で順次、復元処理を行う。
【００５１】
処理が開始されるとＳ２００でＣＰＵ１０２は、現在処理しているデータが一致列であるかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、現在処理しているデータが一致列である場合には、処理はＳ２０２に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、現在処理しているデータが一致列ではない場合には、処理はＳ２１０に進む。
【００５２】
Ｓ２０２でＣＰＵ１０２は、規則１に従って、一致列の圧縮データから一致長と一致列の開始位置を読み取る。本ステップの処理が終了すると、処理はＳ２０４に進む。
【００５３】
Ｓ２０４でＣＰＵ１０２は、コピー元とコピー先に重なりがあるかどうかを判定する。
ここで、図６Ａ、６Ｂを参照して、コピー元とコピー先に重なりがある例について説明する。
【００５４】
図６Ａに示されているように、元データの文字列は、文字“ａ”が１０個並んだ文字列、“ａａａａａａａａａａ”で開始される文字列であるとする。この元データの文字列を、上記規則１、２に従って圧縮すると、次のようになる。
【００５５】
すなわち、第１番目のアドレスに位置する文字列“ａaa”は、それ以前には文字がないので非一致列である。よって、仮の非一致列として”{1, a}が抽出される。
【００５６】
第２〜９番目のアドレスに位置する文字列“ａａａａａａａａａ”の処理では、この文字列は、第１番目のアドレスに位置する文字列“ａａａａａａａａａ”と一致するので、一致列であると判定される（図３のＳ１０２を参照）。さらに仮の非一致列を保有しているかどうかを判定し（図３のＳ１０４を参照）、保有しているので、非一致列{1,a}の符号化が行われる（Ｓ１０６）。また、第２〜９番目のアドレスに位置する文字列「ａａａａａａａａａ」の符号化が行われる。上記規則１に従うと、一致列は、（一致長、一致列の開始位置）で表され、今の場合、一致長は第２番目から第９番目のアドレスまでの９、一致列の開始位置は第１番目のアドレスであり、第２番目のアドレスの１つ前であるので、一致列の開始位置は１である。よって、元データは、図６Ａに示されているように、“｛１、ａ｝（９、１）”と符号化される。よって、圧縮データは、“｛１、ａ｝（９、１）”となる。
【００５７】
図６Ｂは、圧縮データ“｛１、ａ｝（９、１）”の復元処理の概略を説明する図である。
【００５８】
圧縮データ“｛１、ａ｝（９、１）”の復元では、まず、“｛１、ａ｝”の部分を復元する。結果は、第１番目のアドレスの位置に文字“ａ”が格納される。
【００５９】
次に、“（９、１）”の部分の復元では、各アドレスにおいて、１つ前のアドレスに格納された文字を自身のアドレスにコピーする操作を行う。つまり、第３番目のアドレスの復元は、第２番目のアドレスに格納された文字を第３番目のアドレスの位置に格納する操作を含む。逆に言うと、第３番目のアドレスを復元するためには、第１番目のアドレスに格納された文字を第２番目のアドレスにコピーする操作の終了を待つ必要がある。
【００６０】
また、図１に示されている例では、圧縮データ中の“（８、１４）”の部分の復元では、１４アドレス前から８文字分コピーをして、第１５〜２２番目のアドレスの位置にコピーをするが、この場合は、コピー元とコピー先に重なりはない。
【００６１】
このようにＳ２０４でＣＰＵ１０２は、たとえば、図５Ｂに示されているように、復元処理において、コピー元とコピー先に重なりがあるかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、コピー元とコピー先に重なりがある場合には、処理はＳ２０６に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、コピー元とコピー先に重なりがない場合には、処理はＳ２０８に進む。
【００６２】
Ｓ２０６でＣＰＵ１０２は、一致列の開始位置から一致長分をコピーする。本ステップの処理が終了すると、処理はＳ２１４に進む。
【００６３】
Ｓ２０８でＣＰＵ１０２は、重ならない範囲で、一致列の開始位置から順に一致長分をコピーする。図６Ｂに示されている例では、一致列の開始位置から１文字分の「ａ」をコピーする。
【００６４】
Ｓ２００で現在処理しているデータが一致列ではないと判定された場合には、Ｓ２１０に進む。
【００６５】
Ｓ２１０でＣＰＵ１０２は、規則２に従って非一致列の圧縮データから非一致長を読み取り復元する。本ステップの処理が終了すると、処理はＳ２１２に進む。
【００６６】
Ｓ２１２でＣＰＵ１０２は、規則２に従って非一致列の圧縮データから非一致文字列を読み取り復元する。
【００６７】
たとえば、圧縮データ“｛１４、ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ｝（８、１４）｛１、＿｝１１、２３）”中の“｛１４、ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ｝”の部分から、非一致長１４、非一致文字列“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”と読み取ることができる。そして、第１〜１４番目のアドレスの位置に“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”と格納する。本ステップの処理が終了すると、処理はＳ２１４に進む。
【００６８】
Ｓ２１４でＣＰＵ１０２は、復元すべき全ての元データを処理したかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、全ての圧縮データを処理した場合には、復元処理を終了する。また、もしこの判定の結果が“ＮＯ”、すなわち、全ての圧縮データを処理していない場合には、処理はＳ２００に戻る。
【００６９】
このように、比較例では、たとえば図６Ｂに示すようにコピー元とコピー先が重なることがある。図６Ｂの例では、＜ステップ１：第１バイトを第２バイトにコピー＞、＜ステップ２：第２バイトを第３バイトにコピー＞の手順でコピーすることになり、ステップ１の処理が終わっていないとステップ２の処理が行えず、カートン以下の長さ単位での、たとえば１バイトずつのコピー処理が必要となる。このように、復元時に高速な多バイトコピーを使用するには、まずコピー元とコピー先が重なるか否か確認する必要があり、また、重なっている場合は、カートン以下の長さ単位での、たとえば１バイトずつでコピーを行う煩雑な処理が必要である。
【００７０】
＜実施形態＞
以下で説明する実施形態では、たとえばＬＺ７７方式において、相対位置をｏｆｆｓｅｔ、一致長をｌｅｎｇｔｈとしたときに、相対位置が一致長より大きくなる、すなわちｏｆｆｓｅｔ＞ｌｅｎｇｔｈとなるように一致列を分割して符号化する。このように圧縮することによって、一致列の分割によりコピー元とコピー先が重ならなくなるため、復元処理の際に条件分岐がなく、高速な復元処理を実現することができる圧縮データを生成することができる。すなわち、多バイト単位で圧縮データの復元を実現するために、元データ中で繰り返し出現する一致列を、復元時にコピー元とコピー先が重ならないように再分割してから圧縮することで、高速に復元できる圧縮データを生成することができる。
ここで、「重なり」とは、コピー元の文字列の最後尾のアドレスがコピー先の文字列の先頭のアドレスより後方になることを意味し得る。
【００７１】
図７は、元データを圧縮し、圧縮データを生成する圧縮装置の機能ブロック図の例である。
【００７２】
圧縮装置２０は、入力バッファ部２１、一致列検索部２２、一致長符号化部２３、一致位置符号化部２４、非一致長符号化部２５、非一致列符号化部２６、出力バッファ部２７、および一致列分割部２８を含む。比較例の圧縮装置１０とは、一致列分割部２８が含まれている点で異なっている。
【００７３】
入力バッファ部２１は、例えば、圧縮前のデータ（元データ）を外部から受信し、必要に応じて、一時的に格納する。
【００７４】
一致列検索部２２は、入力バッファ部１１に格納された元データの文字列に、繰り返し出現する文字列（一致列）が存在するかどうかを検索、抽出する。また、一致列検索部２２は、一致列が存在する場合は、その一致列を決定する。例えば、図１に示されている例では、“ｃｏｍｐｒｅｓｓ”なる文字列や、“ｃｏｍｐｒｅｓｓｉｏｎ” なる文字列は複数回出現するので、一致列である。
【００７５】
このように一致列検索部２２は、圧縮前のデータの文字列中の第１の文字列の後に、第１の文字列と同一である第２の文字列を一致列として抽出し、一致列の長さと、第１の文字列が第２の文字列の幾つ前のアドレスの位置から開始されるかを示す相対位置を決定する。
そして一致列分割部２８は、相対位置が一致長以上、すなわちｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなるように一致列を分割する。
【００７６】
このように一致列分割部２８は、一致列検索部で抽出された第２の文字列から、長さが相対位置より小さい第３の文字列を抽出する。
【００７７】
たとえば、元データが“ａａａａａａａａａａｂ”である例をあげる。この例では、第１〜１０番目のアドレスの位置に文字“ａ”が格納され、第１１番目のアドレスの位置に文字“ｂ”が格納されている。
【００７８】
このとき、たとえば、図１４のように、元データの文字列“ａａａａａａａａａａｂ”の第２〜１０番目のアドレスの位置の文字列“ａａａａａａａａａ”（９個の“ａ”）を、“ａ”＋“ａａ”＋“ａａａａ”＋“ａａ”と分割することができる。つまり、図４のＰ（１）、Ｐ（３）、Ｐ（７）の位置、つまりＰ（２ｍ−１）の位置で分割する。すると、元データ“ａａａａａａａａａａｂ”の第２番目のアドレスの一致列“ａ”に対しては、一致長ｌｅｎｇｔｈが１、相対位置ｏｆｆｓｅｔが１なので、ｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。第３〜４番目の一致列“ａａ”については、一致長ｌｅｎｇｔｈが２、相対位置ｏｆｆｓｅｔが２なのでｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。第５〜８番目の一致列“ａａａａ”については、一致長ｌｅｎｇｔｈが４、相対位置ｏｆｆｓｅｔが４なのでｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。
【００７９】
また、たとえば、図１４に示されているように、元データの文字列“ａａａａａａａａａａｂ”の第２〜１０番目のアドレスの位置の文字列“ａａａａａａａａａ”（９個の“ａ”）を“ａ”＋“ａ”＋“ａａ”＋“ａａａａａａ”と分割することができる。つまり、図４のＰ（１）、Ｐ（２）、Ｐ（４）の位置、つまり、ｎ＝(一致長列＋ｃａｒｔｏｎ−１)÷ｃａｒｔｏｎとし、Ｐ(ｎ÷２)、 Ｐ(ｎ÷４)、…、Ｐ(ｎ÷２ｍ)の位置で分割する。すると、元データ“ａａａａａａａａａａｂ”の第２番目のアドレスの一致列“ａ”に対しては、一致長ｌｅｎｇｔｈが１、相対位置ｏｆｆｓｅｔが１なので、ｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。第３番目の一致列“ａ”については、一致長ｌｅｎｇｔｈが１、相対位置ｏｆｆｓｅｔが２なのでｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。第３〜５番目の一致列“ａａ”については、一致長ｌｅｎｇｔｈが２、相対位置ｏｆｆｓｅｔが３なのでｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。第６〜１０番目の一致列“ａａａａａ”については、一致長ｌｅｎｇｔｈが５、相対位置ｏｆｆｓｅｔが５なのでｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。
【００８０】
一致長符号化部２３および一致位置符号化部２４は、一致列分割部２８で分割された一致列に対し、規則１に従って、一致列を（一致長、一致列の開始位置）と表すときの、第１要素および第2要素をそれぞれ符号化する。
【００８１】
たとえば、図１４のように、元データの文字列“ａａａａａａａａａａｂ”の第２〜１０番目のアドレスの位置の一致列“ａａａａａａａａａａ” （９個の“ａ”）を、“ａ”＋“ａａ”＋“ａａａａ”＋“ａａ”と分割すると、一致列は、“（１、１）（２、２）（４、４）（２、８）”と符号化される。
【００８２】
また、たとえば、図１５に示されているように、元データの文字列“ａａａａａａａａａａｂ”の第２〜１０番目のアドレスの位置の一致列“ａａａａａａａａａ”（９個の“ａ”）を“ａ”＋“ａ”＋“ａａ”＋“ａａａａａａ”と分割すると、一致列は、“（１、１）（１、２）（２、３）（５、５）” と符号化される。
【００８３】
非一致長符号化部２５は、一致列検索部２２では一致列として抽出されなかった非一致列の長さを抽出し、規則２に従って、非一致列を｛非一致長、非一致文字列｝と表すときの、第１要素を符号化する。
【００８４】
非一致列符号化部２６は、一致列検索部２２では一致列として抽出されなかった非一致列を抽出し、規則２に従って、非一致列を｛非一致長、非一致文字列｝と表すときの、第２要素を符号化する。
【００８５】
出力バッファ部２７は、一致長符号化部２３、一致位置符号化部２４、非一致長符号化部２５、および非一致列符号化部２６の結果を用いて、元データを符号化、圧縮した結果である圧縮データを生成し、必要に応じて、一時的に格納する。
【００８６】
図１５は実施形態のデータ圧縮装置２００の構成の例を示す図である。
このコンピュータ１００は、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ）１０２、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）１０４、及びＲａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）１０６を備えている。コンピュータ５００は、さらに、ハードディスク装置１０８、入力装置１１０、表示装置１１２、インタフェース装置１１４、及び記録媒体駆動装置１１６を備えている。なお、これらの構成要素はバスライン１２０を介して接続されており、ＣＰＵ１０２の管理の下で各種のデータを相互に授受することができる。
【００８７】
Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ）１０２は、このコンピュータ１００全体の動作を制御する演算処理装置であり、コンピュータ１００の制御処理部として機能する。
【００８８】
Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）１０４は、所定の基本制御プログラムが予め記録されている読み出し専用半導体メモリである。ＣＰＵ１０２は、この基本制御プログラムをコンピュータ１００の起動時に読み出して実行することにより、このコンピュータ１００の各構成要素の動作制御が可能になる。
【００８９】
Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）１０６は、ＣＰＵ１０２が各種の制御プログラムを実行する際に、必要に応じて作業用記憶領域として使用する、随時書き込み読み出し可能な半導体メモリである。
【００９０】
ハードディスク装置１０８は、ＣＰＵ１０２によって実行される各種の制御プログラムや各種のデータを記憶しておく記憶装置である。ＭＰＵ５０２は、ハードディスク装置１０８に記憶されている所定の制御プログラムを読み出して実行することにより、後述する各種の制御処理を行えるようになる。
【００９１】
入力装置１１０は、例えばマウス装置やキーボード装置であり、情報処理装置のユーザにより操作されると、その操作内容に対応付けられている各種情報の入力を取得し、取得した入力情報をＣＰＵ１０２に送付する。
【００９２】
表示装置５１２は例えば液晶ディスプレイであり、ＭＰＵ５０２から送付される表示データに応じて各種のテキストや画像を表示する。
【００９３】
インタフェース装置１１４は、このコンピュータ１００に接続される各種機器との間での各種情報の授受の管理を行う。
【００９４】
記録媒体駆動装置１１６は、可搬型記録媒体１１８に記録されている各種の制御プログラムやデータの読み出しを行う装置である。ＣＰＵ１０２は、可搬型記録媒体１１８に記録されている所定の制御プログラムを、記録媒体駆動装置１１６を介して読み出して実行することによって、後述する各種の制御処理を行うようにすることもできる。なお、可搬型記録媒体１１８としては、例えばＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）規格のコネクタが備えられているフラッシュメモリ、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ−ＲＯＭ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などがある。
【００９５】
このようなコンピュータ１００を用いて情報処理装置を構成するには、例えば、上述の各処理部における処理をＣＰＵ１０２に行わせるための制御プログラムを作成する。作成された制御プログラムはハードディスク装置１０８若しくは可搬型記録媒体１１８に予め格納しておく。そして、ＣＰＵ１０２に所定の指示を与えてこの制御プログラムを読み出させて実行させる。こうすることで、情報処理装置が備えている機能がＣＰＵ１０２により提供される。
【００９６】
図８は、実施形態におけるデータ圧縮装置２０での圧縮処理の流れの例を示す図である。
【００９７】
また、データ圧縮装置２０が図１５に示されているような汎用コンピュータ１００である場合には、下記の説明は、そのような処理を行う制御プログラムを定義する。すなわち、以下では、下記に説明する処理を汎用コンピュータに行わせる制御プログラムの説明でもある。
【００９８】
処理が開始されるとＳ３００で一致列検索部２２は、元データの文字列に、繰り返し出現する文字列である一致列が存在するかどうかを検索する。本ステップの処理が終了すると、処理はＳ３０２に進む。元データの文字列は、入力バッファ部２１に格納されているものであっても良い。
【００９９】
Ｓ３０２で一致列検索部２２は、一致列が見つかったかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、一致列が見つかった場合には、処理はＳ３０４に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、一致列が見つからなかった場合には、処理はＳ３０６に進む。
【０１００】
Ｓ３０４で非一致長符号化部２５と非一致列符号化部２６はそれぞれ、一致が見つからなかった非一致列の長さと文字列を抽出する。そして、非一致列の長さおよび文字列に関する情報をそれぞれ、非一致長符号化部２５と非一致列符号化部２６内に一時的に記憶する。この情報は、Ｓ１０６で用いられる。本ステップの処理が終了すると、処理はＳ１００に戻る。
【０１０１】
Ｓ３０２で一致列が見つからなかった場合には、処理はＳ３０６に進む。
Ｓ３０６で一致列分割部２８は、一致列の長さ、つまり一致長と、その一致列が幾つ前のアドレスの位置から開始されるか、つまり相対位置を検出する。そしてＳ３０６で一致列分割部２８は、相対位置が一致長以上、すなわち相対位置ｏｆｆｓｅｔ≧一致長ｌｅｎｇｔｈとなるように一致列を分割する。
【０１０２】
相対位置が一致長以上である、すなわち相対位置ｏｆｆｓｅｔ≧一致長ｌｅｎｇｔｈを満たす場合には、このステップでの処理は行われない。
【０１０３】
Ｓ３０８で一致列分割部２８は、分割した一致列の最初の文字のアドレスの位置の直前の文字列が非一致列かどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、直前の文字列が非一致列である場合には、処理はＳ３１０に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、直前の文字列が非一致列ではない場合には、処理はＳ３１２に進む。
【０１０４】
Ｓ３１０で非一致長符号化部２５と非一致列符号化部２６は、Ｓ３０６で必要に応じて分割された一致列の直前の非一致列を符号化する。本ステップの処理が終了すると、処理はＳ３１２に進む。
【０１０５】
Ｓ３１２で一致長符号化部２３と一致位置符号化部２４は、Ｓ３０６で必要に応じて分割された一致列を符号化する。本ステップの処理が終了すると、処理はＳ３１４に進む。
【０１０６】
Ｓ３１４で出力バッファ２７は圧縮すべき全ての元データを処理したかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、全ての元データを処理した場合には、圧縮処理を終了する。また、もしこの判定の結果が“ＮＯ”、すなわち、全ての元データを処理していない場合には、処理はＳ３００に戻る。
【０１０７】
ここで、図８のような処理によって圧縮されたデータの復元処理について図９を参照して説明する。
【０１０８】
図９の処理は、たとえば、図１５のような構成を有するコンピュータよって処理され得る。
【０１０９】
処理が開始される前に、圧縮データがＲＡＭ１０６に格納されているものとする。
処理が開始されるとＳ４００でＣＰＵ１０２は、現在処理しているデータが一致列であるかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、現在処理しているデータが一致列である場合には、処理はＳ４０２に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、現在処理しているデータが一致列ではない場合には、処理はＳ４０６に進む。
【０１１０】
Ｓ４０２でＣＰＵ１０２は、規則１に従って、一致列の圧縮データから一致長と一致列の開始位置を読み取る。本ステップの処理が終了すると、処理はＳ４０４に進む。
【０１１１】
Ｓ４０４でＣＰＵ１０２は、一致列の開始位置から一致長分をコピーする。本ステップの処理が終了すると、処理はＳ４１０に進む。
【０１１２】
Ｓ４００で現在処理しているデータが一致列ではないと判定された場合には、Ｓ４０６に進む。
【０１１３】
Ｓ４０６でＣＰＵ１０２は、規則２に従って非一致列の圧縮データから非一致長を読み取り復元する。本ステップの処理が終了すると、処理はＳ４０８に進む。
【０１１４】
Ｓ４０８でＣＰＵ１０２は、規則２に従って非一致列の圧縮データから非一致文字列を読み取り復元する。
【０１１５】
本ステップの処理が終了すると、処理はＳ４１０に進む。
Ｓ４１０でＣＰＵ１０２は、復元すべき全ての元データを処理したかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、全ての圧縮データを処理した場合には、復元処理を終了する。また、もしこの判定の結果が“ＮＯ”、すなわち、全ての圧縮データを処理していない場合には、処理はＳ４００に戻る。
【０１１６】
このように、図８のような処理によって圧縮されたデータの復元処理は、図４に示されている復元処理に比べると単純化されており、よって、高速に処理することができる。
【０１１７】
＜実施例＞
コピー元とコピー先の重なりは、同じ１文字、２文字列、３文字列、・・・のいずれかが続けて繰返す循環文字列において発生する。ＬＺ７７方式において、一致列を検索して相対位置ｏｆｆｓｅｔ、一致長ｌｅｎｇｔｈが得られたとする。ｏｆｆｓｅｔ＜ｌｅｎｇｔｈのとき、コピー元とコピー先が重なるため一致列を分割して符号化する。また、ｏｆｆｓｅｔ＜ｌｅｎｇｔｈであれば常に分割を行うのではなく、重なりの最小距離を予めＸと定め、ｏｆｆｓｅｔ＜Ｘのときのみ分割を行うようにしてもよい。
【０１１８】
分割の仕方には、いくつか考えられる。以下では、次のような場合について説明する。
（Ｅｘ１）Ｐ（１）、Ｐ（３）、Ｐ（７）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する、
（Ｅｘ２）ｎ＝（一致長＋ｃａｒｔｏｎ−１）÷ｃａｒｔｏｎとし、Ｐ（ｎ÷２）、Ｐ（ｎ÷４） 、Ｐ（ｎ÷８）、・・・、Ｐ（ｎ÷２ｍ））（ただしｎ÷２ｍ＞１）で分割する、
（Ｅｘ３）重なりの最小距離Ｘ, 一致長の最小値Ｎを定めた上で、Ｐ（１）、Ｐ（１＋２）、Ｐ（１＋２＋４）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する、
（Ｅｘ４）一致長の最小値をＮとし、循環の１セットがＮ以上になるように調節した上で、上記（Ｅｘ１）〜（Ｅｘ３）の分割をする。
【０１１９】
以下では上記（Ｅｘ１）〜（Ｅｘ４）について、説明する。
図１０は、実施例におけるデータ圧縮装置での圧縮処理の流れの例を示す図である。
【０１２０】
また、データ圧縮装置２０が図１５に示されているような汎用コンピュータ１００である場合には、下記の説明は、そのような処理を行う制御プログラムを定義する。すなわち、以下では、下記に説明する処理を汎用コンピュータに行わせる制御プログラムの説明でもある。
【０１２１】
処理が開始されるとＳ５００で入力バッファ部２１は、現在のアドレスの位置ｐ＿ｃｕｒと、非一致乗長ｎ＿ｌｅｎをリセットする。たとえば、ｐ＿ｃｕｒ＝０、ｎ＿ｌｅｎ＝０とする。本ステップの処理が終了すると、処理はＳ５０２に進む。
【０１２２】
次のＳ５０２で一致列検索部２２は、一致列を検索する。具体的には、一致長ｌｅｎと相対位置ｏｆｆｓｅｔを求める。本ステップの処理が終了すると、処理はＳ５０４に進む。
【０１２３】
Ｓ５０４で一致列検索部２２は、一致列が見つかったかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、一致列が見つかった場合には、処理はＳ５０６に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、一致列が見つからなかった場合には、処理はＳ５３２に進む。
【０１２４】
Ｓ５０６で一致列検索部２２は、現在のアドレスの位置ｐ＿ｃｕｒと、非一致乗長ｎ＿ｌｅｎを更新する。たとえば、現在のアドレスの位置ｐ＿ｃｕｒと、非一致乗長ｎ＿ｌｅｎをそれぞれ、１だけ増加させる。
【０１２５】
Ｓ５０６では、先頭位置調整処理が行われる。
図１１を参照して、先頭位置調整処理について説明する。この処理では、一致長の最小値Ｎが定められているとする。
【０１２６】
処理が開始されるとＳ６００で一致列検索部２２は、相対位置ｏｆｆｓｅｔを変数ｉに代入する。本ステップの処理が終了すると、処理はＳ６０２に進む。
【０１２７】
Ｓ６０２で一致列検索部２２は、変数ｉが一致長の最小値Ｎ以上であるかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、変数ｉが一致長の最小値Ｎ以上である場合には、処理はＳ６０６に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、変数ｉが一致長の最小値Ｎ以上ではない場合には、処理はＳ６０４に進む。
【０１２８】
Ｓ６０６で一致列検索部２２は、非一致長ｎ＿ｌｅｎに（ｉ−ｏｆｆｓｅｔ）の値を加え、現在のアドレスの位置ｐ＿ｃｕｒに（ｉ−ｏｆｆｓｅｔ）の値を加える。さらに、一致列の一致長ｌｅｎから（ｉ−ｏｆｆｓｅｔ）の値を引く。本ステップの処理が終了すると、先頭位置調整処理は終了する。
【０１２９】
Ｓ６０４で一致列検索部２２は、変数ｉにｏｆｆｓｅｔの値を加える。
図１０に戻って、Ｓ５０６の次のＳ５０８で一致列分割部２８は、一致列分割処理を行う。
【０１３０】
図１２Ａ、１２Ｂを参照して、一致列分割処理について説明する。
図１２Ａは、上記Ｅｘ１のように、Ｐ（１）、Ｐ（３）、Ｐ（７）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する場合の処理を示す図である。
【０１３１】
処理を開始すると、Ｓ７００で一致列分割部２８は、分割した一致列の後尾番号ｅ＿ｎｕｍの値をリセットし、一致列の一致長の変数ｌｅｎ２に一致列の一致長ｌｅｎの値を代入する。本ステップの処理が終了すると、処理はＳ７０２に進む。
【０１３２】
Ｓ７０２で一致列分割部２８は、ｏｆｆｓｅｔ＞Ｘまたはｏｆｆｓｅｔ＞ｌｅｎ２であるかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、ｏｆｆｓｅｔ＞Ｘまたはｏｆｆｓｅｔ＞ｌｅｎ２である場合には、処理はＳ７０４に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、ｏｆｆｓｅｔ≦Ｘかつｏｆｆｓｅｔ≦ｌｅｎ２の場合には、処理はＳ７０６に進む。
【０１３３】
Ｓ７０４で一致列分割部２８は、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｅ＿ｎｕｍ］にｏｆｆｓｅｔの値を代入し、分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ］にｌｅｎ２の値を代入する。本ステップの処理が終了すると、処理はＳ７０６に進む。
【０１３４】
Ｓ７０６で一致列分割部２８は、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｅ＿ｎｕｍ］にｏｆｆｓｅｔの値を代入し、分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ］にｌｅｎ２の値を代入する。さらに、ｅ＿ｎｕｍの値を更新する。たとえば、ｅ＿ｎｕｍの値を１だけ増やす。ｌｅｎ２の値からｏｆｆｓｅｔの値を引き、ｏｆｆｓｅｔの値を更新する。ｏｆｆｓｅｔの値の更新は、たとえば、値を２倍にする。本ステップの処理が終了すると、処理はＳ７０２に戻る。
【０１３５】
図１２Ｂは、上記Ｅｘ２のように、ｎ＝（一致長＋ｃａｒｔｏｎ−１）÷相対位置とし、Ｐ（ｎ÷２）、Ｐ（ｎ÷４） 、Ｐ（ｎ÷８）、・・・、Ｐ（ｎ÷２ｍ））（ただしｎ÷２ｍ＞１）で分割する場合の処理を示す図である。
【０１３６】
処理を開始すると、Ｓ８００で一致列分割部２８は、一致長をｌｅｎ、相対位置をｏｆｆｓｅｔとして、ｎ＝（ｌｅｎ＋ｃａｒｔｏｎ−１）÷ｏｆｆｓｅｔで算出する。さらに、ダミー変数ｉをリセットし、ｉ＝０とする。本ステップの処理が終了すると、処理はＳ８０２に進む。
【０１３７】
Ｓ８０２で一致列分割部２８は、Ｓ８００で算出されたｎの値が１以下であるかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、ｎの値が１以下である場合には、処理はＳ８０６に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、ｎの値が１より大きいの場合には、処理はＳ８０４に進む。
【０１３８】
Ｓ８０４で一致列分割部２８は、ｎの値を更新する。たとえば、値を半分にする。さらに、分割位置Ｐ（ｉ）にｎの値を代入し、さらにダミー変数ｉの値を１増やす。本ステップの処理が終了すると、処理はＳ８０２に戻る。
【０１３９】
Ｓ８０６で一致列分割部２８は、一致列の一致長の変数ｌｅｎ２と、分割した一致列の後尾番号ｅ＿ｎｕｍの値をリセットする。ｌｅｎ２＝０、ｅ＿ｎｕｍ＝０とする。本ステップの処理が終了すると、処理はＳ８０８に進む。
【０１４０】
Ｓ８０８で一致列分割部２８は、ダミー変数ｉの値が１より小さいかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、ダミー変数ｉの値が１より小さい場合には、処理はＳ８１０に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、ダミー変数ｉの値が１以上の場合には、処理はＳ８１２に進む。
【０１４１】
Ｓ８１０で一致列分割部２８は、分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ］に（ｌｅｎ−ｌｅｎ２）の値を代入する。また分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｅ＿ｎｕｍ］に（Ｐ（０）＋１）×ｏｆｆｓｅｔの値を代入する。本ステップの処理が終了すると、一致列分割処理を終了する。
【０１４２】
Ｓ８１２で一致列分割部２８は、ダミー変数ｉの値を１減らす。また、ダミー変数ｔｍｐに分割位置Ｐ（ｉ）と相対位置ｏｆｆｓｅｔの積、Ｐ（ｉ）×ｏｆｆｓｅｔを代入し、このダミー変数ｔｍｐを分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ］と、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｅ＿ｎｕｍ］に代入する。ｌｅｎ２の値にｔｍｐの値を加え、ｅ＿ｎｕｍの値を１増やす。本ステップの処理が終了すると、処理はＳ８０８に戻る。
【０１４３】
図１０に戻り、Ｓ５１０で一致列分割部２８は、分割した一致列の先導番号ｆ＿ｎｕｍと分割した一致列の非一致長ｎ＿ｌｅｎ２をリセットする。ｆ＿ｎｕｍ＝０、ｎ＿ｌｅｎ２＝０とする。本ステップの処理が終了すると、Ｓ５１２に進む。
【０１４４】
Ｓ５１２で一致列分割部２８は、一致長調整処理を行う。
一致長調整処理について、図１３を参照して説明する。
【０１４５】
処理を開始するとＳ９００で一致列分割部２８は、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｆ＿ｎｕｍ］が一致長の最小値Ｎ以上であるかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｆ＿ｎｕｍ］が一致長の最小値Ｎ以上である場合には、処理はＳ９０４に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｆ＿ｎｕｍ］が一致長の最小値Ｎより小さい場合には、処理はＳ９０２に進む。
【０１４６】
Ｓ９０２で一致列分割部２８は、分割した一致列の非一致長ｎ＿ｌｅｎの値にＡ＿ｏｆｆｓｅｔ［ｆ＿ｎｕｍ］の値を加える。また、ｆ＿ｎｕｍの値を１増やす。本ステップの処理が終了すると、処理はＳ９００に戻る。
【０１４７】
Ｓ９００およびＳ９０２の処理で、先頭の分割列の調整を行う。
Ｓ９０４で一致列分割部２８は、分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ−１］が一致長の最小値Ｎ以上であるか、またはｅ＿ｎｕｍの値がｆ＿ｎｕｍの値より小さいかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ−１］が一致長の最小値Ｎ以上であるか、またはｅ＿ｎｕｍの値がｆ＿ｎｕｍの値より小さい場合には、一致長調整処理を終了する。また、もしこの判定の結果が“ＮＯ”、すなわち、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｅ＿ｎｕｍ−１］が一致長の最小値Ｎより小さく、かつｅ＿ｎｕｍの値がｆ＿ｎｕｍの値以上である場合には、処理はＳ９０６に進む。
【０１４８】
Ｓ９０６で一致列分割部２８は、分割した一致列の非一致長ｎ＿ｌｅｎ２の値に分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ−１］の値を加え、ｅ＿ｎｕｍの値を１減らす。
【０１４９】
図１０に戻って、Ｓ５１４で一致列分割部２８は、非一致長ｎ＿ｌｅｎが０かどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、非一致長ｎ＿ｌｅｎが０である場合には、処理はＳ５１８に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、非一致長ｎ＿ｌｅｎが０でない場合には、処理はＳ５１６に進む。
【０１５０】
Ｓ５１６で非一致長符号化部２５と非一致列符号化部２６は、非一致列の符号化を行う。つまり、非一致長ｎ＿ｌｅｎと、非圧縮データＩｎＢｕｆ［（ｐ＿ｃｕｒ−ｎ＿ｌｅｎ）、…、（ｐ＿ｃｕｒ−１）］の符号化を行う。本ステップの処理が終了すると、処理はＳ５１８に進む。
【０１５１】
Ｓ５１８で一致列分割部２８は、分割した一致列の先頭のアドレス番号ｆ＿ｎｕｍが分割した一致列の後尾のアドレス番号ｅ＿ｎｕｍの値より大きいかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、ｆ＿ｎｕｍ＞ｅ＿ｎｕｍである場合には、処理はＳ５２０に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、ｆ＿ｎｕｍ≦ｅ＿ｎｕｍである場合には、処理はＳ５２４に進む。
【０１５２】
Ｓ５２４で一致長符号化部２３と一致位置符号化部２４は、一致列の符号化を行う。つまり、一致列の一致長Ａ＿ｌｅｎ［ｆ＿ｎｕｍ］およびＡ＿ｏｆｆｓｅｔ［ｆ＿ｎｕｍ］の符号化を行う。本ステップの処理が終了すると、処理はＳ５２６に進む。
【０１５３】
Ｓ５２６で一致長符号化部２３と一致位置符号化部２４は、分割した一致列の先頭のアドレス番号ｆ＿ｎｕｍの値を１増やす。本ステップの処理が終了すると、処理はＳ５１８に戻る。
【０１５４】
Ｓ５２０で一致列分割部２８は、非一致長ｎ＿ｌｅｎに分割した一致列の非一致長ｎ＿ｌｅｎ２の値を代入し、現在位置ｐ＿ｃｕｒに一致長ｌｅｎの値を加える。本ステップの処理が終了すると、処理はＳ５２２に進む。
【０１５５】
Ｓ５２２で出力バッファ２７は圧縮すべき全ての元データを処理したかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、全ての元データを処理した場合には、Ｓ５２４に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、全ての元データを処理していない場合には、処理はＳ５０２に戻る。
【０１５６】
Ｓ５２４で一致列分割部２８は、非一致長ｎ＿ｌｅｎが０かどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、非一致長ｎ＿ｌｅｎが０である場合には、処理を終了すうｒ。また、もしこの判定の結果が“ＮＯ”、すなわち、非一致長ｎ＿ｌｅｎが０でない場合には、処理はＳ５２６に進む。
【０１５７】
Ｓ５２６で非一致長符号化部２５と非一致列符号化部２６は、非一致列の符号化を行う。つまり、非一致長ｎ＿ｌｅｎと、非圧縮データＩｎＢｕｆ［（ｐ＿ｃｕｒ−ｎ＿ｌｅｎ）、…、（ｐ＿ｃｕｒ−１）］の符号化を行う。本ステップの処理が終了すると、処理は終了する。
【０１５８】
圧縮装置２０および上記の圧縮方法では、ＬＺ７７方式において、ある一致列の相対位置ｏｆｆｓｅｔと一致長ｌｅｎｇｔｈであるとき、ｏｆｆｓｅｔ＜ｌｅｎｇｔｈのとき、コピー元とコピー先が重なるため一致列を分割して符号化する。
【０１５９】
また、重なりの最小距離を予めＸと定め、ｏｆｆｓｅｔ＜Ｘのときのみ分割を行うようにしてもよい。
【０１６０】
また、コピー元とコピー先の重なりは、同じ１文字、２文字列、３文字列、・・・のいずれかが続けて繰返す循環文字列において発生する。循環の１セットの長さはコピー元とコピー先の相対位置（相対距離）と一致する。初回の１セットは別符号で符号化され、２回目以降の循環において重なりが発生する。
【０１６１】
そこで、循環の１セットの長さをｃａｒｔｏｎ（カートン）とし、一致文字列の先頭からＰ（１）＝ｃａｒｔｏｎ、Ｐ（２）＝ｃａｒｔｏｎ×２、・・・、Ｐ（ｎ）＝ｃａｒｔｏｎ×ｎ（ただＰ(ｎ)はｌｅｎｇｔｈより小さい）の位置の全てまたはいずれかで分割することで、コピー元とコピー先が重ならないようにする。
【０１６２】
図１４に、Ｐ（１）、Ｐ（３）、Ｐ（７）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する例を、図１５に、ｎ＝（一致長＋ｃａｒｔｏｎ−１）÷ｃａｒｔｏｎとし、Ｐ（ｎ÷２）、Ｐ（ｎ÷４） 、Ｐ（ｎ÷８）、・・・、Ｐ（ｎ÷２ｍ））（ただしｎ÷２ｍ＞１）で分割する例を示した。また、一致長の最小値をＮを予め定め、一致文字列を分割することで一致長がＮ以下となる部分は非一致列として扱ってもよい。
【０１６３】
図１６では、重なりの最小距離Ｘ, 一致長の最小値Ｎを定めた上で、Ｐ（１）、Ｐ（１＋２）、Ｐ（１＋２＋４）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する例において、重なりの最小距離Ｘ＝８、一致長の最小値Ｎ＝３の場合が示されている。この場合、一致文字列を分割することで一致長がＮ以下となる部分は非一致列として扱う。
【０１６４】
また、一致長の最小値をＮとしているとき、循環の１セットがＮ以上になるように調節した上で、上記分割を行っても良い。具体的には、相対位置ｏｆｆｓｅｔ＜Ｎのとき、Ｎ≦ｏｆｆｓｅｔ×ｉ（ただし、ｉは整数値）となる最大の「ｏｆｆｓｅｔ×ｉ」の長さの分、一致列の先頭位置を後ろへずらしても良い。
【０１６５】
例えば、図１７には、一致長の最小値Ｎ＝３として、循環の１セットがＮ以上になるように調整した上で、Ｐ（１）、Ｐ（１＋２）、Ｐ（１＋２＋４）、・・・、Ｐ（２ｍ−１）（ただし （ただし （２ｍ−１）＜ｎ）の分割を行った例が示されている。
【０１６６】
また、Ｐ（１）、Ｐ（２）, ・・・、Ｐ（ｎ）の全て、および図１４〜１７に示す分割から最も符号量が小さくなるものを選択してもよい。
【０１６７】
＜＜第１実施例（Ｅｘ１）＞＞
図１４は、Ｐ（１）、Ｐ（３）、Ｐ（７）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する例を示す図である。
【０１６８】
ｃａｒｔｏｎ＝１の場合の例として、図１４には、元データが“ａａａａａａａａａａｂ”の場合が示されている。
【０１６９】
この場合、第１番目のアドレスの位置の“ａ”が非一致列であり、第２〜１０番目のアドレスの位置の“ａａａａａａａａａ”が一致列である。第１１番目のアドレスの位置の文字“ｂ”は非一致列である。第２〜１０番目のアドレスの位置の一致列“ａａａａａａａａａ”を１文字目、３文字目、７文字目で分割する。すなわち、一致列“ａａａａａａａａａ”を、「“ａ”＋“ａａ”＋”ａａａａ”＋残り」と分割する。
【０１７０】
元データが“ａａａａａａａａａａｂ”の場合、圧縮データは “｛１、ａ｝（１、１）（２、２）（４、４）（２、８）｛１、ｂ｝”となる。
【０１７１】
ｃａｒｔｏｎ＝２の場合の例として、図１４には、元データが“ａｂａｂａｂａｂａｃ”の場合が示されている。この場合、第１〜２番目のアドレスの位置の“ａｂ”が非一致列であり、第３〜１０番目のアドレスの位置の“ａｂａｂａｂａ”が一致列である。第１１番目のアドレスの位置の文字“ｃ”は非一致列である。第３〜９番目のアドレスの位置の“ａｂａｂａｂａ”を１カートン目、３カートン目で分割する。すなわち、一致列“ａｂａｂａｂａｂ”を、「“ａｂ”＋“ａｂａｂ”＋残り」と分割する。
【０１７２】
元データが“ａｂａｂａｂａｂａｃ”の場合、圧縮データは “｛２、ａｂ｝、（２、２）（４、４）（３、８）｛１、ｃ｝”となる。
【０１７３】
ｃａｒｔｏｎ＝３の場合の例として、図１４には、元データが“ａｂｃａｂｃａｂｃａｂｄ”の場合が示されている。この場合、第１〜３番目のアドレスの位置の“ａｂｃ”が非一致列であり、第４〜１１番目のアドレスの位置の“ａｂｃａｂｃａｂ”が一致列である。第１２番目のアドレスの位置の文字“ｄ”は非一致列である。第４〜１１番目のアドレスの位置の“ａｂｃａｂｃａｂ” を１カートン目で分割する。すなわち、一致列“ａｂｃａｂｃａｂｃ”を、「“ａｂｃ”＋残り」と分割する。
【０１７４】
元データが“ａｂｃａｂｃａｂｃａｂｄ”の場合、圧縮データは “｛３、ａｂｃ｝（３、３）（５、６）｛１、ｄ｝”となる。
【０１７５】
ｃａｒｔｏｎ＝４の場合の例として、図１４には、元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｅ”の場合が示されている。この場合、第１〜４番目のアドレスの位置の“ａｂｃｄ”が非一致列であり、第５〜１５番目のアドレスの位置の“ａｂｃｄａｂｃｄａｂｃｄ”が一致列である。第１７番目のアドレスの位置の文字“ｅ”は非一致列である。第５〜１５番目のアドレスの位置の“ａｂｃｄａｂｃｄａｂｃ” を１カートン目で分割する。すなわち、一致列“ａｂｃｄａｂｃｄａｂｃ”を、「“ａｂｃｄ”＋残り」と分割する。
【０１７６】
元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｄｅ”の場合、圧縮データは “｛４、ａｂｃｄ｝（４、４）（７、８）｛１、ｅ｝”となる。
【０１７７】
ｃａｒｔｏｎ＝７の場合の例として、図１４には、元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｈ”の場合が示されている。この場合、第１〜７番目のアドレスの位置の“ａｂｃｄｅｆｇ”が非一致列であり、第８〜２０番目のアドレスの位置の“ａｂｃｄｅｆｇａｂｃｄｅｆ”が一致列である。第２１番目のアドレスの位置の文字“ｈ”は非一致列である。第８〜２０番目のアドレスの位置の“ａｂｃｄｅｆｇａｂｃｄｅｆ” を１カートン目で分割する。すなわち、一致列“ａｂｃｄｅｆｇａｂｃｄｅｆ”を、「“ａｂｃｄｅｆｇ”＋残り」と分割する。
【０１７８】
元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｈ”の場合、圧縮データは “｛７、ａｂｃｄｅｆｇ｝（７、７）（６、１４）｛１、ｈ｝”となる。
【０１７９】
ｃａｒｔｏｎ＝８の場合の例として、図１４には、元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｉ”の場合が示されている。この場合、第１〜８番目のアドレスの位置の“ａｂｃｄｅｆｇｈ”が非一致列であり、第９〜２４番目のアドレスの位置の“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇ”が一致列である。第２５番目のアドレスの位置の文字“ｉ”は非一致列である。第９〜２３番目のアドレスの位置の“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇ” を１カートン目で分割する。すなわち、一致列“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇ”を、「“ａｂｃｄｅｆｇｈ”＋残り」と分割する。
【０１８０】
元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｉ”の場合、圧縮データは “｛８、ａｂｃｄｅｆｇｈ｝（８、８）（７、１６）｛１、ｉ｝”となる。
【０１８１】
＜＜第２実施例（Ｅｘ２）＞＞
図１５は、ｎ＝（一致長＋ｃａｒｔｏｎ−１）÷ｃａｒｔｏｎとし、Ｐ（ｎ÷２）、Ｐ（ｎ÷４） 、Ｐ（ｎ÷８）、・・・、Ｐ（ｎ÷２ｍ））（ただしｎ÷２ｍ＞１）で分割する例を示す図である。
【０１８２】
ｃａｒｔｏｎ＝１の場合の例として、図１５には、元データが“ａａａａａａａａａａｂ”の場合が示されている。
【０１８３】
第２〜１０番目のアドレスの位置の一致列“ａａａａａａａａａ”を分割するが、この場合ｎ＝（９＋１−１）÷１＝９であるので、Ｐ（４）、Ｐ（２）、Ｐ（１）で分割する。すなわち、一致列“ａａａａａａａａａ”を「“ａ”＋“ａ”＋“ａａ”＋残り」と分割する。
【０１８４】
元データが“ａａａａａａａａａａｂ”の場合、圧縮データは “｛１、ａ｝（１、１）（１、２）（２、３）（５、５）｛１、ｂ｝”となる。
【０１８５】
ｃａｒｔｏｎ＝２の場合の例として、図１５には、元データが“ａｂａｂａｂａｂａｂａｂｃ”の場合が示されている。この場合、第１〜２番目のアドレスの位置の“ａｂ”が非一致列であり、第３〜１１番目のアドレスの位置の“ａｂａｂａｂａｂａ”が一致列である。第１２番目のアドレスの位置の文字“ｃ”は非一致列である。この場合、ｎ＝（９＋２−１）÷２＝５であるので、Ｐ（２）、Ｐ（１）で分割する。すなわち、一致列“ａｂａｂａｂａｂａｂ”を、「“ａｂ”＋“ａｂ”＋残り」と分割する。
【０１８６】
元データが“ａｂａｂａｂａｂａｂａｂｃ”の場合、圧縮データは “｛２、ａｂ｝、（２、２）（２、４）（５、４）｛１、ｃ｝”となる。
【０１８７】
ｃａｒｔｏｎ＝３の場合の例として、図１５には、元データが“ａｂｃａｂｃａｂｃａｂｄ”の場合が示されている。この場合、第１〜３番目のアドレスの位置の“ａｂｃ”が非一致列であり、第４〜１１番目のアドレスの位置の“ａｂｃａｂｃａｂ”が一致列である。第１２番目のアドレスの位置の文字“ｄ”は非一致列である。この場合、ｎ＝（８＋３−１）÷３＝３であるので、Ｐ（１）で分割する。すなわち、一致列“ａｂｃａｂｃａｂ”を、「“ａｂｃ”＋残り」と分割する。
【０１８８】
元データが“ａｂｃａｂｃａｂｃａｂｄ”の場合、圧縮データは “｛３、ａｂｃ｝（３、３）（５、６）｛１、ｄ｝”となる。
【０１８９】
ｃａｒｔｏｎ＝４の場合の例として、図１５には、元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｅ”の場合が示されている。この場合、第１〜４番目のアドレスの位置の“ａｂｃｄ”が非一致列であり、第５〜１５番目のアドレスの位置の“ａｂｃｄａｂｃｄａｂｃ”が一致列である。第１６番目のアドレスの位置の文字“ｅ”は非一致列である。この場合、ｎ＝（１１＋４−１）÷４＝３であるので、Ｐ（１）で分割する。すなわち、一致列“ａｂｃｄａｂｃｄａｂｃ”を「“ａｂｃｄ”＋残り」と分割する。
【０１９０】
元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｅ”の場合、圧縮データは “｛４、ａｂｃｄ｝（４、４）（７、８）｛１、ｅ｝”となる。
【０１９１】
ｃａｒｔｏｎ＝７の場合の例として、図１５には、元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｈ”の場合が示されている。この場合、ｎ＝（１１＋７−１）÷７＝２であるので、一致列“ａｂｃｄｅｆｇａｂｃｄｅｆ”を、「“ａｂｃｄｅｆｇ”＋残り」と分割する。
【０１９２】
元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｈ”の場合、圧縮データは “｛７、ａｂｃｄｅｆｇ｝（７、７）（６、１４）｛１、ｈ｝”となる。
【０１９３】
ｃａｒｔｏｎ＝８の場合の例として、図１５には、元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｉ”の場合が示されている。この場合、第１〜８番目のアドレスの位置の“ａｂｃｄｅｆｇｈ”が非一致列であり、第９〜２３番目のアドレスの位置の“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇ”が一致列である。第２４番目のアドレスの位置の文字“ｉ”は非一致列である。この場合、ｎ＝（１５＋８−１）÷８〜２であるので、一致列“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈ”を、「“ａｂｃｄｅｆｇｈ”＋残り」と分割する。
【０１９４】
元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｉ”の場合、圧縮データは “｛８、ａｂｃｄｅｆｇｈ｝（８、８）（７、１６）｛１、ｉ｝”となる。
【０１９５】
＜＜第３実施例（Ｅｘ３）＞＞
図１６は、重なりの最小距離Ｘ, 一致長の最小値Ｎを定めた上で、Ｐ（１）、Ｐ（１＋２）、Ｐ（１＋２＋４）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する例を示す図である。図１６では、重なりの最小距離Ｘ＝８、一致長の最小値Ｎ＝３の場合が示されている。この場合、一致文字列を分割することで一致長がＮ以下となる部分は非一致列として扱う。
【０１９６】
ｃａｒｔｏｎ＝１の場合の例として、図１６には、元データが“ａａａａａａａａａａｂ”の場合が示されている。
【０１９７】
この場合、第１番目のアドレスの位置の“ａ”が非一致列であり、第２〜１０番目のアドレスの位置の“ａａａａａａａａａ”が一致列である。第１１番目のアドレスの位置の文字“ｂ”は非一致列である。第２〜１０番目のアドレスの位置の一致列“ａａａａａａａａａ”を１文字目、３文字目、７文字目で分割するが、一致長の最小値Ｎ＝３とするためには、元データ “ａａａａａａａａａａｂ”を「“ａａａａ”＋“ａａａａ”＋“ａａｂ”」と分割する。
【０１９８】
よって、圧縮データは “｛４、ａａａａ｝（４、４）｛３、ａａｂ｝”となる。
ｃａｒｔｏｎ＝２の場合の例として、図１４には、元データが“ａｂａｂａｂａｂａｂｃ”の場合が示されている。この場合、第１〜２番目のアドレスの位置の“ａｂ”が非一致列であり、第３〜１０番目のアドレスの位置の“ａｂａｂａｂａｂ”が一致列である。第１１番目のアドレスの位置の文字“ｃ”は非一致列である。第３〜１０番目のアドレスの位置の“ａｂａｂａｂａｂ”を１カートン目、３カートン目で分割するが、一致長の最小値Ｎ＝３とするためには、元データ “ａｂａｂａｂａｂａｂｃ”を、「“ａｂａｂ”＋“ａｂａｂ”＋“ａｂａｂ”＋“ｃ”」と分割する。
【０１９９】
よって圧縮データは、“｛４、ａｂａｂ｝（４、４）（４、８）｛１、ｃ｝”となる。
ｃａｒｔｏｎ＝３の場合の例として、図１６には、元データが“ａｂｃａｂｃａｂｃａｂｃｄ”の場合が示されている。この場合、第１〜３番目のアドレスの位置の“ａｂｃ”が非一致列であり、第４〜１２番目のアドレスの位置の“ａｂｃａｂｃａｂｃ”が一致列である。第１３番目のアドレスの位置の文字“ｄ”は非一致列である。第４〜１２番目のアドレスの位置の“ａｂｃａｂｃａｂｃ” を１カートン目で分割するが、一致長の最小値Ｎ＝３とするためには、元データ “ａｂｃａｂｃａｂｃａｂｃｄ”を、「“ａｂｃ”＋“ａｂｃ”＋“ａｂｃ”＋“ｄ”」と分割する。
【０２００】
よって、圧縮データは、“｛３、ａｂｃ｝（３、３）（６、６）｛１、ｄ｝”となる。
ｃａｒｔｏｎ＝４の場合の例として、図１６には、元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｄｅ”の場合が示されている。この場合、第１〜４番目のアドレスの位置の“ａｂｃｄ”が非一致列であり、第５〜１６番目のアドレスの位置の“ａｂｃｄａｂｃｄａｂｃｄ”が一致列である。第１７番目のアドレスの位置の文字“ｅ”は非一致列である。第５〜１６番目のアドレスの位置の“ａｂｃｄａｂｃｄａｂｃｄ” を１カートン目で分割するが、一致長の最小値Ｎ＝３とするためには、元データ“ａｂｃｄａｂｃｄａｂｃｄａｂｃｄｅ”を、「“ａｂｃｄ”＋“ａｂｃｄ”＋“ａｂｃｄａｂｃｄ”＋“ｅ”」と分割する。よって、圧縮データは “｛４、ａｂｃｄ｝（４、４）（８、８）｛１、ｅ｝”となる。
【０２０１】
ｃａｒｔｏｎ＝７の場合の例として、図１６には、元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｈ”の場合が示されている。この場合、第１〜７番目のアドレスの位置の“ａｂｃｄｅｆｇ”が非一致列であり、第８〜２１番目のアドレスの位置の“ａｂｃｄｅｆｇａｂｃｄｅｆｇ”が一致列である。第２２番目のアドレスの位置の文字“ｈ”は非一致列である。第８〜２１番目のアドレスの位置の“ａｂｃｄｅｆｇａｂｃｄｅｆ”
を１カートン目で分割するが、一致長の最小値Ｎ＝３とするためには、元データ“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｇｈ”を、「“ａｂｃｄｅｆｇ”＋“ａｂｃｄｅｆｇ”＋“ａｂｃｄｅｆ”＋“ｈ”」と分割する。
【０２０２】
よって、圧縮データは “｛７、ａｂｃｄｅｆｇ｝（７、７）（６、１４）｛１、ｈ｝”となる。
【０２０３】
ｃａｒｔｏｎ＝８の場合の例として、図１６には、元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｉ”の場合が示されている。この場合、第１〜８番目のアドレスの位置の“ａｂｃｄｅｆｇｈ”が非一致列であり、第９〜２３番目のアドレスの位置の“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇ”が一致列である。第２４番目のアドレスの位置の文字“ｉ”は非一致列である。この場合、ｃａｒｔｏｎ＝８は重なりの最小距離以上のため分割しない。
【０２０４】
よって、圧縮データは “｛８、ａｂｃｄｅｆｇｈ｝（１５、８）｛１、ｉ｝”となる。
【０２０５】
＜＜第４実施例（Ｅｘ４）＞＞
図１７は、循環の１セットが一致長の最小値Ｎ＝３以上になるように先頭を調整する例を示す図である。
【０２０６】
ｃａｒｔｏｎ＝１の場合は、ｃａｒｔｏｎ＝３となるように一致列の先頭のアドレスの位置を調整する。
【０２０７】
元データ “ａａａａａａａａａａｂ”を「“ａａａ”＋“ａａａ”＋“ａａａａ”＋“ｂ”」と分割する。
【０２０８】
よって、圧縮データは、“｛３、ａａａ｝（３、３）（４、６）｛１、ｂ｝”となる。
ｃａｒｔｏｎ＝２の場合は、ｃａｒｔｏｎ＝４となるように一致列の先頭のアドレスの位置を調整する。
【０２０９】
元データが“ａｂａｂａｂａｂａｃ”の場合、「“ａｂａｂ”＋“ａｂａｂ”＋“ａｂａ”＋“ｃ”」と分割する。
【０２１０】
よって、圧縮データは、“｛４、ａｂａｂ｝（４、４）（３、８）｛１、ｃ｝”となる。
【０２１１】
ｃａｒｔｏｎ＝３の場合は、ｃａｒｔｏｎ＝３は一致長の最小値以上であるので、政党距離は調整しない。
【０２１２】
元データが“ａｂｃａｂｃａｂｃａｂｄ”の場合、圧縮データは、“｛３、ａｂｃ｝（３、３）（５、６）｛１、ｄ｝”となる。
【符号の説明】
【０２１３】
１０、２０  データ圧縮装置
１１、２１  入力バッファ部
１２、２２  一致列検索部
１３、２３  一致長符号化部
１４、２４  一致位置符号化部
１５、２５  非一致長符号化部
１６、２６  非一致位置符号化部
１７、２７  出力バッファ部
２８  一致列分割部
【図１】
2015029224.tif 000003
【図２】
2015029224.tif 000004
【図３】
2015029224.tif 000005
【図４】
2015029224.tif 000006
【図５】
2015029224.tif 000007
【図６Ａ】
2015029224.tif 000008
【図６Ｂ】
2015029224.tif 000009
【図７】
2015029224.tif 000010
【図８】
2015029224.tif 000011
【図９】
2015029224.tif 000012
【図１０】
2015029224.tif 000013
【図１１】
2015029224.tif 000014
【図１２Ａ】
2015029224.tif 000015
【図１２Ｂ】
2015029224.tif 000016
【図１３】
2015029224.tif 000017
【図１４】
2015029224.tif 000018
【図１５】
2015029224.tif 000019
【図１６】
2015029224.tif 000020
【図１７】
2015029224.tif 000021
【図１８】
2015029224.tif 000022
【手続補正書】
【提出日】平成28年3月31日(2016.3.31)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ圧縮装置、方法およびプログラムに関するものである。
【背景技術】
【０００２】
データ圧縮アルゴリズムとして、１９７７年にＡｂｒａｈａｍ  Ｌｅｍｐｅｌ氏とＪａｃｏｂ  Ｚｉｖ氏が発表したＬＺ７７方式が知られている。ＬＺ７７方式は辞書式圧縮法の一つで、スライド辞書法とも呼ばれ、データを先頭から順番に符号化していく。スライド辞書法は、現在注目している位置から始まるシンボル列が、それ以前に出現していたかを探す。もし出現していたならば、シンボル列をその出現位置と長さのポインタに置き換える。スライド辞書法の名前は、シンボル列を探す範囲をスライド窓と呼び、これを辞書として使用することに由来する。
【０００３】
ＬＺ７７方式では、繰返し出現するデータ列を過去に出現したシンボル列の長さと出現位置に置き換えることでデータ量を削減する。復元の際には、過去の位置から一致長分のシンボル列をコピーすることで元のデータに復元できる。また、繰返しが見つからなかったときに、見つからなかった長さと見つからなかったシンボル列を符号化する方法が示されている。
【０００４】
また、中央処理装置（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、ＣＰＵ）のオペレーティングシステム（ＯＳ）によっては、１命令で複数データを扱うＳｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ（ＳＩＭＤ）命令が用意されており、１６バイト、３２バイト単位でのメモリ間のデータコピーを高速に行うことができる。ＳＩＭＤ命令を復元時のコピー処理において用いると復元処理の高速化を実現することができる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｆｉａｌａ，Ｅ．  ａｎｄ  Ｇｒｅｅｎｅ，Ｄ．（１９８９）“Ｄａｔａ  ｃｏｍｐｒｅｓｓｉｏｎ  ｗｉｔｈ  ｆｉｎｉｔｅ  ｗｉｎｄｏｗｓ” Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ ｔｈｅ ＡＣＭ、３２（４）ｐｐ． ４９０−５０５
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＬＺ７７方式では、コピー元の文字列の最後尾のアドレスがコピー先の文字列の先頭のアドレスより後方になることがある。このことを以下では、単に「コピー元とコピー先が重なる」という。たとえば、同じ文字が「aaaa…」と続くケースだと、コピー元の文字列はアドレス「1,2,3,4…」で、コピー先の文字列はアドレス「2,3,4,…」となり、アドレス「2,3,4,…」において重なりを持つ。このようなケースでは、復元処理において、ステップ１で、第１バイトを第２バイトにコピーし、ステップ２で第２バイトを第３バイトにコピーする、という手順でそれ以前に出現した文字列をコピーする。この場合、ステップ１の処理が終わっていないとステップ２の処理を行うことができない。つまり、ＬＺ７７方式は、繰返し出現するデータ列を過去に出現したデータ列の長さと出現位置に置き換えているため、単純なコピー処理で復元できるにも関わらず、コピー元とコピー先が重なっているときは、１バイトずつのコピー処理が必要となることがある。このため、復元時に高速な多バイトコピーを使用するには、まずコピー元とコピー先が重なるか否か確認する必要があり、また、重なっている場合は、１バイトずつのコピーを行う煩雑な処理が必要であるという問題がある。
【０００７】
よって、本発明は、多バイトコピーを用いて復元を行う上で不都合な重なりを制限した一致列を選択して圧縮することで、高速に復元できる圧縮データを生成するデータ圧縮装置、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
データ圧縮装置が提供される。データ圧縮装置は、圧縮前のデータの文字列中の第１の文字列の後に、前記第１の文字列と同一である第２の文字列を一致列として抽出し、前記一致列の長さと、前記第１の文字列が前記第２の文字列の幾つ前のアドレスの位置から開始されるかを示す相対位置を決定する一致列検索部と、前記一致列検索部で抽出された前記第２の文字列から、長さが前記相対位置より小さい第３の文字列を抽出する一致列分割部と、前記第２または第３の文字列の長さを符号化する一致長符号化部と、前記相対位置を符号化する一致位置符号化部と、
を含むことを特徴とする。
【発明の効果】
【０００９】
多バイト単位で圧縮データの復元を実現するために、元データ中で繰り返し出現する一致列を再分割してから圧縮することで、高速に復元できる圧縮データを生成することができる。
【図面の簡単な説明】
【００１０】
【図１】ＬＺ７７方式の概略を説明する図である。
【図２】比較例におけるデータ圧縮装置の機能ブロック図の例を示す図である。
【図３】比較例におけるデータ圧縮装置での圧縮処理の流れの例を示す図である。
【図４】比較例における元データと圧縮データの例を示す図である。
【図５】比較例における復元処理の流れの例を示す図である。
【図６Ａ】比較例におけるデータ圧縮装置での圧縮処理の例を示す図である。
【図６Ｂ】比較例における復元処理の例を示す図である。
【図７】実施形態におけるデータ圧縮装置の機能ブロック図の例を示す図である。
【図８】実施形態におけるデータ圧縮装置での圧縮処理の流れの例を示す図である。
【図９】実施形態における復元処理の流れの例を示す図である。
【図１０】実施例におけるデータ圧縮装置での圧縮処理の流れの例を示す図である。
【図１１】実施例における先頭位置調整処理の流れの例を示す図である。
【図１２Ａ】実施例における一致列分割処理の流れの例を示す図である。
【図１２Ｂ】実施例における一致列分割処理の流れの別の例を示す図である。
【図１３】実施例における一致長調整処理の流れの例を示す図である。
【図１４】Ｐ（１）、Ｐ（３）、…、Ｐ（２ｍ−１）で分割する例を示す図である。
【図１５】Ｐ（ｎ÷２）、Ｐ（ｎ÷４）、…、Ｐ（ｎ÷２ｍ）で分割する例を示す図である。
【図１６】Ｐ（１）、Ｐ（３）、…、Ｐ（２ｍ−１）で分割する別の例を示す図である。
【図１７】Ｐ（１）、Ｐ（３）、…、Ｐ（２ｍ−１）で分割するさらに別の例を示す図である。
【図１８】コンピュータの構成の例を示す図である。
【発明を実施するための形態】
【００１１】
以下、図面を参照して、まず、比較例について説明し、その後、実施形態について説明する。
【００１２】
また、以下ではＬＺ７７方式を用いたデータ圧縮装置、方法およびプログラムについて説明するが、もちろん、データ圧縮方法はＬＺ７７方式には限定されず、繰返し出現するデータ列を過去に出現したデータ列の長さと出現位置に置き換えることでデータ量を削減するような圧縮方法であれば適用可能である。
【００１３】
ＬＺ７７方式では、繰り返し現われる文字列を検索し、２回目以降にその文字列が現われるとき、その文字列を、出現位置と長さに関するデータに置き換えることにより、圧縮する。ここで、出現位置とは、ある文字列が複数回目に現われるとき、複数回目に現れたときの先頭位置と、以前に現れたときの先頭位置のアドレスの差であり得る。
【００１４】
以下では、次のような表記規則を用いる。
（規則１）一致列は、（一致長、一致列の開始位置）で表す、
（規則２）非一致列は、｛非一致長、非一致文字列｝で表す。
ここで、一致列の開始位置は、幾つ前のアドレスに同一の文字列があるか、を示す。一致列の開始位置は、一致位置、相対位置とも呼ぶ。一致列の開始位置（相対位置）は、ある文字列が複数回目に現われるとき、複数回目に現れたときの先頭位置と、以前に現れたときの先頭位置のアドレスの差で、すなわち、相対距離の大きさであり得る。たとえば、一致列の開始位置が、“１４”である場合、複数回目に現れたときの先頭位置は、以前に現れたときの先頭位置より１４アドレス分だけ後方に位置することを意味しても良い。元データの文字列中の一致列を（一致長、一致列の開始位置）のような形式の圧縮データに符号化するとも言う。同様に、元データの文字列中の非一致列を｛非一致長、非一致文字列｝のような形式の圧縮データに符号化するとも言う。
【００１５】
＜比較例＞
図１〜６Ｂを参照して、比較例について説明する。以下の比較例の説明は、ＬＺ７７方式の概略の説明でもある。
【００１６】
図１は、ＬＺ７７方式の概略を説明する図である。
例えば、図１に示されている第１〜３４番目のアドレスの位置に格納されている圧縮前のデータ（以下、単に元データと呼ぶことがある）では、第１〜１４番目のアドレスの位置に“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”という文字列が格納されており、第１５〜２２番目のアドレスの位置に“ｃｏｍｐｒｅｓｓ”という文字列が格納されており、第２３番目のアドレスの位置には“＿”（アンダーバー）が、第２４〜３４番目のアドレスの位置には“ｃｏｍｐｒｅｓｓｉｏｎ”という文字列が格納されている。よって、圧縮データは、まず、第１〜１４番目のアドレスの位置に“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”は非一致列であり、非一致長は１４であるので、圧縮データでは、“｛１４、ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ｝”と表される。元データの第１５〜２２番目のアドレスの位置に“ｃｏｍｐｒｅｓｓ”とあるが、これは第１〜８番目のアドレスの位置の文字列と同一である。“ｃｏｍｐｒｅｓｓ”は８文字であり、一致文字列が開始されるアドレスの位置は１４アドレス前であるので、一致列の開始位置は１４である。よって、元データの第１５〜２２番目のアドレスのデータは、圧縮データでは “（８、１４）”と符号化される。元データの第２３番目のアドレスの位置に格納されている“＿”（アンダーバー）は、それ以前には出現していないので、圧縮データでは“｛１、＿｝”と符号化される。元データの第２４〜３４番目のアドレスの位置に“ｃｏｍｐｒｅｓｓｉｏｎ”とあるが、これは第１〜８番目のアドレスの位置の文字列と同一である。“ｃｏｍｐｒｅｓｓ”は８文字であり、一致文字列が開始されるアドレスの位置は２３アドレス前であるので、一致列の開始位置は２３である。よって、元データの第２４〜３４番目のアドレスのデータは、圧縮データでは “（１１、２３）”と符号化される。
【００１７】
このように、図１に示されている元データの文字列は、圧縮データでは、“｛１４、ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ｝（８、１４）｛１、＿｝（１１、２３）”のように表される。
【００１８】
図２は、ＬＺ７７方式を用いて元データを圧縮し、圧縮データを生成する圧縮装置の機能ブロック図の例である。
【００１９】
圧縮装置１０は、入力バッファ部１１、一致列検索部１２、一致長符号化部１３、一致位置符号化部１４、非一致長符号化部１５、非一致列符号化部１６、および出力バッファ部１７を含む。
【００２０】
入力バッファ部１１は、例えば、図１に示されている第１〜３４番目のアドレスの位置に格納されているような圧縮前のデータ（元データ）を外部から受信し、必要に応じて、一時的に格納する。図１に示されている例では、元データは、“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅｃｏｍｐｒｅｓｓｉｏｎ＿ｃｏｍｐｒｅｓｓｉｏｎ．”である。
【００２１】
一致列検索部１２は、入力バッファ部１１に格納された元データの文字列に、繰り返し出現する文字列（一致列）が存在するかどうかを検索、抽出する。また、一致列検索部１２は、一致列が存在する場合は、その一致列を決定する。例えば、図１に示されている例では、“ｃｏｍｐｒｅｓｓ”なる文字列や、“ｃｏｍｐｒｅｓｓｉｏｎ” なる文字列は複数回出現するので、一致列である。
【００２２】
一致長符号化部１３は、一致列検索部１２で検索され、抽出された一致列の長さを抽出し、規則１に従って、一致列を（一致長、一致列の開始位置）と表すときの、第１要素を決定する。例えば、図１に示されている例では、元データの第１５〜２２番目のアドレスの位置にある“ｃｏｍｐｒｅｓｓ”なる文字列は、第１〜８番目のアドレスの位置の文字列と同一であり、８文字である。よって、一致長符号化部１３によって、一致長は８と符号化される。
【００２３】
一致位置符号化部１４は、一致列検索部１２で検索され、抽出された一致列が幾つ前のアドレスの位置から開始されるかを検出し、規則１に従って、一致列を（一致長、一致列の開始位置）と表すときの、第２要素を決定する。例えば、図１に示されている例では、元データの第１５〜２２番目のアドレスの位置にある“ｃｏｍｐｒｅｓｓ”なる文字列は、第１〜８番目のアドレスの位置の文字列と同一であり、一致文字列が開始されるアドレスの位置は１４アドレス前である。よって、一致長符号化部１３によって、一致列の開始位置は１４と符号化される。
【００２４】
非一致長符号化部１５は、一致列検索部１２では一致列として抽出されなかった非一致列の長さを抽出し、規則２に従って、非一致列を｛非一致長、非一致文字列｝と表すときの、第１要素を決定する。例えば、図１に示されている例では、第１〜１４番目のアドレスの位置に“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”は非一致列であり、１４文字である。よって、非一致長符号化部１５によって、非一致長は１４と符号化される。
【００２５】
非一致列符号化部１６は、一致列検索部１２では一致列として抽出されなかった非一致列を抽出し、規則２に従って、非一致列を｛非一致長、非一致文字列｝と表すときの、第２要素を決定する。例えば、図１に示されている例では、第１〜１４番目のアドレスの位置に“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”は非一致列である。よって、非一致長符号化部１５によって、非一致文字列は“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”と符号化される。
【００２６】
出力バッファ部１７は、一致長符号化部１３、一致位置符号化部１４、非一致長符号化部１５、および非一致列符号化部１６の結果を用いて、元データを符号化、圧縮した結果である圧縮データを生成し、必要に応じて、一時的に格納する。たとえば、図１に示されている例では、元データである文字列“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅｃｏｍｐｒｅｓｓｉｏｎ＿ｃｏｍｐｒｅｓｓｉｏｎ．”は、“｛１４、ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ｝（８、１４）｛１、＿｝（１１、２３）”と符号化される。
【００２７】
図３は、比較例におけるデータ圧縮装置での圧縮処理の流れの例を示す図である。
処理が開始されるとＳ１００で一致列検索部１２は、元データの文字列に、繰り返し出現する文字列である一致列が存在するかどうかを検索する。本ステップの処理が終了すると、処理はＳ１０２に進む。元データの文字列は、入力バッファ部１１に格納されているものであっても良い。
【００２８】
Ｓ１０２で一致列検索部１２は、一致列が見つかったかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、一致列が見つかった場合には、処理はＳ１０４に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、一致列が見つからなかった場合には、処理はＳ１１２に進む。
【００２９】
Ｓ１０４で一致列検索部１２は、Ｓ１０２で見つかった一致列の最初の文字のアドレスの位置の直前の文字列が非一致列かどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、直前の文字列が非一致列である場合には、処理はＳ１０６に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、直前の文字列が非一致列ではない場合には、処理はＳ１０８に進む。
【００３０】
Ｓ１０６で非一致長符号化部１５と非一致列符号化部１６は、Ｓ１０２で見つかった一致列の直前の非一致列を符号化する。符号化の例は、図１に示されている。本ステップの処理が終了すると、処理はＳ１０８に進む。
【００３１】
Ｓ１０８で一致長符号化部１３と一致位置符号化部１４は、Ｓ１０２で見つかった一致列を符号化する。符号化の例は、図１に示されている。本ステップの処理が終了すると、処理はＳ１１０に進む。
【００３２】
Ｓ１１０では出力バッファ部１７は、圧縮すべき全ての元データを処理したかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、全ての元データを処理した場合には、圧縮処理を終了する。また、もしこの判定の結果が“ＮＯ”、すなわち、全ての元データを処理していない場合には、処理はＳ１００に戻る。
【００３３】
Ｓ１０２で一致列が見つからなかった場合は、Ｓ１１２に進む。
Ｓ１１２で非一致長符号化部１５と非一致列符号化部１６はそれぞれ、一致が見つからなかった非一致列の長さと文字列を抽出する。そして、非一致列の長さおよび文字列に関する情報をそれぞれ、非一致長符号化部１５と非一致列符号化部１６内に一時的に記憶する。この情報は、Ｓ１０６で用いられる。本ステップの処理が終了すると、処理はＳ１００に戻る。
【００３４】
図４は、比較例における元データと圧縮データの例を示す図である。
図４では、元データが循環文字列である場合を取り上げている。循環文字列の長さをｃａｒｔｏｎ（カートン）と呼ぶ。図６においても、上記規則１、２を用いる。
【００３５】
また、図４において、Ｐ（ｎ）（ｎは整数）は、ｃａｒｔｏｎの区切りを示す。
ｃａｒｔｏｎ＝１の場合の例として、図４には、元データが“ａａａａａａａａａａｂ”の場合が示されている。
【００３６】
この場合、第１番目のアドレスの位置の“ａ”が非一致列であり、第２〜１０番目のアドレスの位置の“ａａａａａａａａａ”が一致列である。
【００３７】
元データが“ａａａａａａａａａａｂ”の場合、圧縮データは “｛１、ａ｝、（９、１）、｛１、ｂ｝”となる。ここで、圧縮データ中の一致列を示す部分“（９、１）”の第２要素の１は、ｃａｒｔｏｎ（カートン）に一致する。
【００３８】
ｃａｒｔｏｎ＝２の場合の例として、図４には、元データが“ａｂａｂａｂａｂａｂｃ”の場合が示されている。この場合、第１〜２番目のアドレスの位置の“ａｂ”が非一致列であり、第３〜１０番目のアドレスの位置の“ａｂａｂａｂａｂ”が一致列である。第１１番目のアドレスの位置の文字“ｃ”は非一致列である。循環文字列の長さが２であるので、第２〜１０番目のアドレスは２文字ずつ分割され、第４番目のアドレスの位置がＰ（１）、第６番目のアドレスの位置がＰ（２）のように分割される。
【００３９】
元データが“ａｂａｂａｂａｂａｂｃ”の場合、圧縮データは “｛２、ａｂ｝、（１０、２）、｛１、ｃ｝”となる。
【００４０】
ｃａｒｔｏｎ＝３の場合の例として、図４には、元データが“ａｂｃａｂｃａｂｃａｂｃｄ”の場合が示されている。この場合、第１〜３番目のアドレスの位置の“ａｂｃ”が非一致列であり、第４〜１２番目のアドレスの位置の“ａｂｃａｂｃａｂｃ”が一致列である。第１３番目のアドレスの位置の文字“ｄ”は非一致列である。
【００４１】
元データが“ａｂｃａｂｃａｂｃａｂｃｄ”の場合、圧縮データは “｛３、ａｂｃ｝、（９、３）、｛１、ｄ｝”となる。
【００４２】
ｃａｒｔｏｎ＝４の場合の例として、図４には、元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｄｅ”の場合が示されている。この場合、第１〜４番目のアドレスの位置の“ａｂｃｄ”が非一致列であり、第５〜１６番目のアドレスの位置の“ａｂｃｄａｂｃｄａｂｃｄ”が一致列である。第１７番目のアドレスの位置の文字“ｅ”は非一致列である。
【００４３】
元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｄｅ”の場合、圧縮データは “｛４、ａｂｃｄ｝、（１２、４）、｛１、ｅ｝”となる。
【００４４】
ｃａｒｔｏｎ＝７の場合の例として、図４には、元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｇｈ”の場合が示されている。この場合、第１〜７番目のアドレスの位置の“ａｂｃｄｅｆｇ”が非一致列であり、第８〜２１番目のアドレスの位置の“ａｂｃｄｅｆｇａｂｃｄｅｆｇ”が一致列である。第２２番目のアドレスの位置の文字“ｈ”は非一致列である。
【００４５】
元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｇｈ”の場合、圧縮データは “｛７、ａｂｃｄｅｆｇ｝、（１４、７）、｛１、ｈ｝”となる。
【００４６】
ｃａｒｔｏｎ＝８の場合の例として、図４には、元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈｉ”の場合が示されている。この場合、第１〜８番目のアドレスの位置の“ａｂｃｄｅｆｇｈ”が非一致列であり、第９〜２４番目のアドレスの位置の“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈ”が一致列である。第２５番目のアドレスの位置の文字“ｉ”は非一致列である。
【００４７】
元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈｉ”の場合、圧縮データは “｛８、ａｂｃｄｅｆｇｈ｝、（１６、８）、｛１、ｉ｝”となる。
【００４８】
ここで、図３のような処理によって圧縮されたデータの復元処理について図５を参照して説明する。
【００４９】
図５の処理は、たとえば、図１８のような構成を有するコンピュータよって処理され得る。図１８に示されているコンピュータ１００は、中央処理装置（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ））１０２と、メモリ、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）１０４、及びＲａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）１０６を備えている。
【００５０】
処理が開始される前に、圧縮データがＲＡＭ１０６に格納されているものとする。処理は、圧縮データの列、たとえば図１の例では、圧縮データ“｛１４、ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ｝（８、１４）｛１、＿｝（１１、２３）”を括弧単位で順次、復元処理を行う。
【００５１】
処理が開始されるとＳ２００でＣＰＵ１０２は、現在処理しているデータが一致列であるかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、現在処理しているデータが一致列である場合には、処理はＳ２０２に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、現在処理しているデータが一致列ではない場合には、処理はＳ２１０に進む。
【００５２】
Ｓ２０２でＣＰＵ１０２は、規則１に従って、一致列の圧縮データから一致長と一致列の開始位置を読み取る。本ステップの処理が終了すると、処理はＳ２０４に進む。
【００５３】
Ｓ２０４でＣＰＵ１０２は、コピー元とコピー先に重なりがあるかどうかを判定する。
ここで、図６Ａ、６Ｂを参照して、コピー元とコピー先に重なりがある例について説明する。
【００５４】
図６Ａに示されているように、元データの文字列は、文字“ａ”が１０個並んだ文字列、“ａａａａａａａａａａ”で開始される文字列であるとする。この元データの文字列を、上記規則１、２に従って圧縮すると、次のようになる。
【００５５】
すなわち、第１番目のアドレスに位置する文字列“ａaa”は、それ以前には文字がないので非一致列である。よって、仮の非一致列として”{1, a}が抽出される。
【００５６】
第２〜９番目のアドレスに位置する文字列“ａａａａａａａａａ”の処理では、この文字列は、第１番目のアドレスに位置する文字列“ａａａａａａａａａ”と一致するので、一致列であると判定される（図３のＳ１０２を参照）。さらに仮の非一致列を保有しているかどうかを判定し（図３のＳ１０４を参照）、保有しているので、非一致列{1,a}の符号化が行われる（Ｓ１０６）。また、第２〜９番目のアドレスに位置する文字列「ａａａａａａａａａ」の符号化が行われる。上記規則１に従うと、一致列は、（一致長、一致列の開始位置）で表され、今の場合、一致長は第２番目から第９番目のアドレスまでの９、一致列の開始位置は第１番目のアドレスであり、第２番目のアドレスの１つ前であるので、一致列の開始位置は１である。よって、元データは、図６Ａに示されているように、“｛１、ａ｝（９、１）”と符号化される。よって、圧縮データは、“｛１、ａ｝（９、１）”となる。
【００５７】
図６Ｂは、圧縮データ“｛１、ａ｝（９、１）”の復元処理の概略を説明する図である。
【００５８】
圧縮データ“｛１、ａ｝（９、１）”の復元では、まず、“｛１、ａ｝”の部分を復元する。結果は、第１番目のアドレスの位置に文字“ａ”が格納される。
【００５９】
次に、“（９、１）”の部分の復元では、各アドレスにおいて、１つ前のアドレスに格納された文字を自身のアドレスにコピーする操作を行う。つまり、第３番目のアドレスの復元は、第２番目のアドレスに格納された文字を第３番目のアドレスの位置に格納する操作を含む。逆に言うと、第３番目のアドレスを復元するためには、第１番目のアドレスに格納された文字を第２番目のアドレスにコピーする操作の終了を待つ必要がある。
【００６０】
また、図１に示されている例では、圧縮データ中の“（８、１４）”の部分の復元では、１４アドレス前から８文字分コピーをして、第１５〜２２番目のアドレスの位置にコピーをするが、この場合は、コピー元とコピー先に重なりはない。
【００６１】
このようにＳ２０４でＣＰＵ１０２は、たとえば、図６Ｂに示されているように、復元処理において、コピー元とコピー先に重なりがあるかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、コピー元とコピー先に重なりがある場合には、処理はＳ２０６に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、コピー元とコピー先に重なりがない場合には、処理はＳ２０８に進む。
【００６２】
Ｓ２０６でＣＰＵ１０２は、一致列の開始位置から一致長分をコピーする。本ステップの処理が終了すると、処理はＳ２１４に進む。
【００６３】
Ｓ２０８でＣＰＵ１０２は、重ならない範囲で、一致列の開始位置から順に一致長分をコピーする。図６Ｂに示されている例では、一致列の開始位置から１文字分の「ａ」をコピーする。
【００６４】
Ｓ２００で現在処理しているデータが一致列ではないと判定された場合には、Ｓ２１０に進む。
【００６５】
Ｓ２１０でＣＰＵ１０２は、規則２に従って非一致列の圧縮データから非一致長を読み取り復元する。本ステップの処理が終了すると、処理はＳ２１２に進む。
【００６６】
Ｓ２１２でＣＰＵ１０２は、規則２に従って非一致列の圧縮データから非一致文字列を読み取り復元する。
【００６７】
たとえば、圧縮データ“｛１４、ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ｝（８、１４）｛１、＿｝（１１、２３）”中の“｛１４、ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ｝”の部分から、非一致長１４、非一致文字列“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”と読み取ることができる。そして、第１〜１４番目のアドレスの位置に“ｃｏｍｐｒｅｓｓｉｏｎ＿ｄｅ”と格納する。本ステップの処理が終了すると、処理はＳ２１４に進む。
【００６８】
Ｓ２１４でＣＰＵ１０２は、復元すべき全ての元データを処理したかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、全ての圧縮データを処理した場合には、復元処理を終了する。また、もしこの判定の結果が“ＮＯ”、すなわち、全ての圧縮データを処理していない場合には、処理はＳ２００に戻る。
【００６９】
このように、比較例では、たとえば図６Ｂに示すようにコピー元とコピー先が重なることがある。図６Ｂの例では、＜ステップ１：第１バイトを第２バイトにコピー＞、＜ステップ２：第２バイトを第３バイトにコピー＞の手順でコピーすることになり、ステップ１の処理が終わっていないとステップ２の処理が行えず、カートン以下の長さ単位での、たとえば１バイトずつのコピー処理が必要となる。このように、復元時に高速な多バイトコピーを使用するには、まずコピー元とコピー先が重なるか否か確認する必要があり、また、重なっている場合は、カートン以下の長さ単位での、たとえば１バイトずつでコピーを行う煩雑な処理が必要である。
【００７０】
＜実施形態＞
以下で説明する実施形態では、たとえばＬＺ７７方式において、相対位置をｏｆｆｓｅｔ、一致長をｌｅｎｇｔｈとしたときに、相対位置が一致長より大きくなる、すなわちｏｆｆｓｅｔ＞ｌｅｎｇｔｈとなるように一致列を分割して符号化する。このように圧縮することによって、一致列の分割によりコピー元とコピー先が重ならなくなるため、復元処理の際に条件分岐がなく、高速な復元処理を実現することができる圧縮データを生成することができる。すなわち、多バイト単位で圧縮データの復元を実現するために、元データ中で繰り返し出現する一致列を、復元時にコピー元とコピー先が重ならないように再分割してから圧縮することで、高速に復元できる圧縮データを生成することができる。
【００７１】
ここで、「重なり」とは、コピー元の文字列の最後尾のアドレスがコピー先の文字列の先頭のアドレスより後方になることを意味し得る。
【００７２】
図７は、元データを圧縮し、圧縮データを生成する圧縮装置の機能ブロック図の例である。
【００７３】
圧縮装置２０は、入力バッファ部２１、一致列検索部２２、一致長符号化部２３、一致位置符号化部２４、非一致長符号化部２５、非一致列符号化部２６、出力バッファ部２７、および一致列分割部２８を含む。比較例の圧縮装置１０とは、一致列分割部２８が含まれている点で異なっている。
【００７４】
入力バッファ部２１は、例えば、圧縮前のデータ（元データ）を外部から受信し、必要に応じて、一時的に格納する。
【００７５】
一致列検索部２２は、入力バッファ部１１に格納された元データの文字列に、繰り返し出現する文字列（一致列）が存在するかどうかを検索、抽出する。また、一致列検索部２２は、一致列が存在する場合は、その一致列を決定する。例えば、図１に示されている例では、“ｃｏｍｐｒｅｓｓ”なる文字列や、“ｃｏｍｐｒｅｓｓｉｏｎ” なる文字列は複数回出現するので、一致列である。
【００７６】
このように一致列検索部２２は、圧縮前のデータの文字列中の第１の文字列の後に、第１の文字列と同一である第２の文字列を一致列として抽出し、一致列の長さと、第１の文字列が第２の文字列の幾つ前のアドレスの位置から開始されるかを示す相対位置を決定する。
そして一致列分割部２８は、相対位置が一致長以上、すなわちｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなるように一致列を分割する。
【００７７】
このように一致列分割部２８は、一致列検索部で抽出された第２の文字列から、長さが相対位置より小さい第３の文字列を抽出する。
【００７８】
たとえば、元データが“ａａａａａａａａａａｂ”である例をあげる。この例では、第１〜１０番目のアドレスの位置に文字“ａ”が格納され、第１１番目のアドレスの位置に文字“ｂ”が格納されている。
【００７９】
このとき、たとえば、図１４のように、元データの文字列“ａａａａａａａａａａｂ”の第２〜１０番目のアドレスの位置の文字列“ａａａａａａａａａ”（９個の“ａ”）を、“ａ”＋“ａａ”＋“ａａａａ”＋“ａａ”と分割することができる。つまり、図４のＰ（１）、Ｐ（３）、Ｐ（７）の位置、つまりＰ（２ｍ−１）の位置で分割する。すると、元データ“ａａａａａａａａａａｂ”の第２番目のアドレスの一致列“ａ”に対しては、一致長ｌｅｎｇｔｈが１、相対位置ｏｆｆｓｅｔが１なので、ｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。第３〜４番目の一致列“ａａ”については、一致長ｌｅｎｇｔｈが２、相対位置ｏｆｆｓｅｔが２なのでｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。第５〜８番目の一致列“ａａａａ”については、一致長ｌｅｎｇｔｈが４、相対位置ｏｆｆｓｅｔが４なのでｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。
【００８０】
また、たとえば、図１４に示されているように、元データの文字列“ａａａａａａａａａａｂ”の第２〜１０番目のアドレスの位置の文字列“ａａａａａａａａａ”（９個の“ａ”）を“ａ”＋“ａ”＋“ａａ”＋“ａａａａａａ”と分割することができる。つまり、図４のＰ（１）、Ｐ（２）、Ｐ（４）の位置、つまり、ｎ＝(一致長列＋ｃａｒｔｏｎ−１)÷ｃａｒｔｏｎとし、Ｐ(ｎ÷２)、 Ｐ(ｎ÷４)、…、Ｐ(ｎ÷２ｍ)の位置で分割する。すると、元データ“ａａａａａａａａａａｂ”の第２番目のアドレスの一致列“ａ”に対しては、一致長ｌｅｎｇｔｈが１、相対位置ｏｆｆｓｅｔが１なので、ｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。第３番目の一致列“ａ”については、一致長ｌｅｎｇｔｈが１、相対位置ｏｆｆｓｅｔが２なのでｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。第３〜５番目の一致列“ａａ”については、一致長ｌｅｎｇｔｈが２、相対位置ｏｆｆｓｅｔが３なのでｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。第６〜１０番目の一致列“ａａａａａ”については、一致長ｌｅｎｇｔｈが５、相対位置ｏｆｆｓｅｔが５なのでｏｆｆｓｅｔ≧ｌｅｎｇｔｈとなる。
【００８１】
一致長符号化部２３および一致位置符号化部２４は、一致列分割部２８で分割された一致列に対し、規則１に従って、一致列を（一致長、一致列の開始位置）と表すときの、第１要素および第2要素をそれぞれ符号化する。
【００８２】
たとえば、図１４のように、元データの文字列“ａａａａａａａａａａｂ”の第２〜１０番目のアドレスの位置の一致列“ａａａａａａａａａａ” （９個の“ａ”）を、“ａ”＋“ａａ”＋“ａａａａ”＋“ａａ”と分割すると、一致列は、“（１、１）（２、２）（４、４）（２、８）”と符号化される。
【００８３】
また、たとえば、図１５に示されているように、元データの文字列“ａａａａａａａａａａｂ”の第２〜１０番目のアドレスの位置の一致列“ａａａａａａａａａ”（９個の“ａ”）を“ａ”＋“ａ”＋“ａａ”＋“ａａａａａａ”と分割すると、一致列は、“（１、１）（１、２）（２、３）（５、５）” と符号化される。
【００８４】
非一致長符号化部２５は、一致列検索部２２では一致列として抽出されなかった非一致列の長さを抽出し、規則２に従って、非一致列を｛非一致長、非一致文字列｝と表すときの、第１要素を符号化する。
【００８５】
非一致列符号化部２６は、一致列検索部２２では一致列として抽出されなかった非一致列を抽出し、規則２に従って、非一致列を｛非一致長、非一致文字列｝と表すときの、第２要素を符号化する。
【００８６】
出力バッファ部２７は、一致長符号化部２３、一致位置符号化部２４、非一致長符号化部２５、および非一致列符号化部２６の結果を用いて、元データを符号化、圧縮した結果である圧縮データを生成し、必要に応じて、一時的に格納する。
【００８７】
図１８は実施形態のデータ圧縮装置２００の構成の例を示す図である。
このコンピュータ１００は、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ）１０２、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）１０４、及びＲａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）１０６を備えている。コンピュータ１００は、さらに、ハードディスク装置１０８、入力装置１１０、表示装置１１２、インタフェース装置１１４、及び記録媒体駆動装置１１６を備えている。なお、これらの構成要素はバスライン１１８を介して接続されており、ＣＰＵ１０２の管理の下で各種のデータを相互に授受することができる。
【００８８】
Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ）１０２は、このコンピュータ１００全体の動作を制御する演算処理装置であり、コンピュータ１００の制御処理部として機能する。
【００８９】
Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）１０４は、所定の基本制御プログラムが予め記録されている読み出し専用半導体メモリである。ＣＰＵ１０２は、この基本制御プログラムをコンピュータ１００の起動時に読み出して実行することにより、このコンピュータ１００の各構成要素の動作制御が可能になる。
【００９０】
Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）１０６は、ＣＰＵ１０２が各種の制御プログラムを実行する際に、必要に応じて作業用記憶領域として使用する、随時書き込み読み出し可能な半導体メモリである。
【００９１】
ハードディスク装置１０８は、ＣＰＵ１０２によって実行される各種の制御プログラムや各種のデータを記憶しておく記憶装置である。ＣＰＵ１０２は、ハードディスク装置１０８に記憶されている所定の制御プログラムを読み出して実行することにより、後述する各種の制御処理を行えるようになる。
【００９２】
入力装置１１０は、例えばマウス装置やキーボード装置であり、情報処理装置のユーザにより操作されると、その操作内容に対応付けられている各種情報の入力を取得し、取得した入力情報をＣＰＵ１０２に送付する。
【００９３】
表示装置５１２は例えば液晶ディスプレイであり、ＣＰＵ１０２から送付される表示データに応じて各種のテキストや画像を表示する。
【００９４】
インタフェース装置１１４は、このコンピュータ１００に接続される各種機器との間での各種情報の授受の管理を行う。
【００９５】
記録媒体駆動装置１１６は、可搬型記録媒体１２０に記録されている各種の制御プログラムやデータの読み出しを行う装置である。ＣＰＵ１０２は、可搬型記録媒体１２０に記録されている所定の制御プログラムを、記録媒体駆動装置１１６を介して読み出して実行することによって、後述する各種の制御処理を行うようにすることもできる。なお、可搬型記録媒体１２０としては、例えばＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）規格のコネクタが備えられているフラッシュメモリ、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ−ＲＯＭ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などがある。
【００９６】
このようなコンピュータ１００を用いて情報処理装置を構成するには、例えば、上述の各処理部における処理をＣＰＵ１０２に行わせるための制御プログラムを作成する。作成された制御プログラムはハードディスク装置１０８若しくは可搬型記録媒体１２０に予め格納しておく。そして、ＣＰＵ１０２に所定の指示を与えてこの制御プログラムを読み出させて実行させる。こうすることで、情報処理装置が備えている機能がＣＰＵ１０２により提供される。
【００９７】
図８は、実施形態におけるデータ圧縮装置２０での圧縮処理の流れの例を示す図である。
【００９８】
また、データ圧縮装置２０が図１８に示されているような汎用コンピュータ１００である場合には、下記の説明は、そのような処理を行う制御プログラムを定義する。すなわち、以下では、下記に説明する処理を汎用コンピュータに行わせる制御プログラムの説明でもある。
【００９９】
処理が開始されるとＳ３００で一致列検索部２２は、元データの文字列に、繰り返し出現する文字列である一致列が存在するかどうかを検索する。本ステップの処理が終了すると、処理はＳ３０２に進む。元データの文字列は、入力バッファ部２１に格納されているものであっても良い。
【０１００】
Ｓ３０２で一致列検索部２２は、一致列が見つかったかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、一致列が見つかった場合には、処理はＳ３０４に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、一致列が見つからなかった場合には、処理はＳ３０６に進む。
【０１０１】
Ｓ３０４で非一致長符号化部２５と非一致列符号化部２６はそれぞれ、一致が見つからなかった非一致列の長さと文字列を抽出する。そして、非一致列の長さおよび文字列に関する情報をそれぞれ、非一致長符号化部２５と非一致列符号化部２６内に一時的に記憶する。この情報は、Ｓ１０６で用いられる。本ステップの処理が終了すると、処理はＳ１００に戻る。
【０１０２】
Ｓ３０２で一致列が見つからなかった場合には、処理はＳ３０６に進む。
Ｓ３０６で一致列分割部２８は、一致列の長さ、つまり一致長と、その一致列が幾つ前のアドレスの位置から開始されるか、つまり相対位置を検出する。そしてＳ３０６で一致列分割部２８は、相対位置が一致長以上、すなわち相対位置ｏｆｆｓｅｔ≧一致長ｌｅｎｇｔｈとなるように一致列を分割する。
【０１０３】
相対位置が一致長以上である、すなわち相対位置ｏｆｆｓｅｔ≧一致長ｌｅｎｇｔｈを満たす場合には、このステップでの処理は行われない。
【０１０４】
Ｓ３０８で一致列分割部２８は、分割した一致列の最初の文字のアドレスの位置の直前の文字列が非一致列かどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、直前の文字列が非一致列である場合には、処理はＳ３１０に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、直前の文字列が非一致列ではない場合には、処理はＳ３１２に進む。
【０１０５】
Ｓ３１０で非一致長符号化部２５と非一致列符号化部２６は、Ｓ３０６で必要に応じて分割された一致列の直前の非一致列を符号化する。本ステップの処理が終了すると、処理はＳ３１２に進む。
【０１０６】
Ｓ３１２で一致長符号化部２３と一致位置符号化部２４は、Ｓ３０６で必要に応じて分割された一致列を符号化する。本ステップの処理が終了すると、処理はＳ３１４に進む。
【０１０７】
Ｓ３１４で出力バッファ２７は圧縮すべき全ての元データを処理したかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、全ての元データを処理した場合には、圧縮処理を終了する。また、もしこの判定の結果が“ＮＯ”、すなわち、全ての元データを処理していない場合には、処理はＳ３００に戻る。
【０１０８】
ここで、図８のような処理によって圧縮されたデータの復元処理について図９を参照して説明する。
【０１０９】
図９の処理は、たとえば、図１８のような構成を有するコンピュータよって処理され得る。
【０１１０】
処理が開始される前に、圧縮データがＲＡＭ１０６に格納されているものとする。
処理が開始されるとＳ４００でＣＰＵ１０２は、現在処理しているデータが一致列であるかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、現在処理しているデータが一致列である場合には、処理はＳ４０２に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、現在処理しているデータが一致列ではない場合には、処理はＳ４０６に進む。
【０１１１】
Ｓ４０２でＣＰＵ１０２は、規則１に従って、一致列の圧縮データから一致長と一致列の開始位置を読み取る。本ステップの処理が終了すると、処理はＳ４０４に進む。
【０１１２】
Ｓ４０４でＣＰＵ１０２は、一致列の開始位置から一致長分をコピーする。本ステップの処理が終了すると、処理はＳ４１０に進む。
【０１１３】
Ｓ４００で現在処理しているデータが一致列ではないと判定された場合には、Ｓ４０６に進む。
【０１１４】
Ｓ４０６でＣＰＵ１０２は、規則２に従って非一致列の圧縮データから非一致長を読み取り復元する。本ステップの処理が終了すると、処理はＳ４０８に進む。
【０１１５】
Ｓ４０８でＣＰＵ１０２は、規則２に従って非一致列の圧縮データから非一致文字列を読み取り復元する。
【０１１６】
本ステップの処理が終了すると、処理はＳ４１０に進む。
Ｓ４１０でＣＰＵ１０２は、復元すべき全ての元データを処理したかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、全ての圧縮データを処理した場合には、復元処理を終了する。また、もしこの判定の結果が“ＮＯ”、すなわち、全ての圧縮データを処理していない場合には、処理はＳ４００に戻る。
【０１１７】
このように、図８のような処理によって圧縮されたデータの復元処理は、図４に示されている復元処理に比べると単純化されており、よって、高速に処理することができる。
【０１１８】
＜実施例＞
コピー元とコピー先の重なりは、同じ１文字、２文字列、３文字列、・・・のいずれかが続けて繰返す循環文字列において発生する。ＬＺ７７方式において、一致列を検索して相対位置ｏｆｆｓｅｔ、一致長ｌｅｎｇｔｈが得られたとする。ｏｆｆｓｅｔ＜ｌｅｎｇｔｈのとき、コピー元とコピー先が重なるため一致列を分割して符号化する。また、ｏｆｆｓｅｔ＜ｌｅｎｇｔｈであれば常に分割を行うのではなく、重なりの最小距離を予めＸと定め、ｏｆｆｓｅｔ＜Ｘのときのみ分割を行うようにしてもよい。
【０１１９】
分割の仕方には、いくつか考えられる。以下では、次のような場合について説明する。
（Ｅｘ１）Ｐ（１）、Ｐ（３）、Ｐ（７）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する、
（Ｅｘ２）ｎ＝（一致長＋ｃａｒｔｏｎ−１）÷ｃａｒｔｏｎとし、Ｐ（ｎ÷２）、Ｐ（ｎ÷４） 、Ｐ（ｎ÷８）、・・・、Ｐ（ｎ÷２ｍ））（ただしｎ÷２ｍ＞１）で分割する、
（Ｅｘ３）重なりの最小距離Ｘ, 一致長の最小値Ｎを定めた上で、Ｐ（１）、Ｐ（１＋２）、Ｐ（１＋２＋４）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する、
（Ｅｘ４）一致長の最小値をＮとし、循環の１セットがＮ以上になるように調節した上で、上記（Ｅｘ１）〜（Ｅｘ３）の分割をする。
【０１２０】
以下では上記（Ｅｘ１）〜（Ｅｘ４）について、説明する。
図１０は、実施例におけるデータ圧縮装置での圧縮処理の流れの例を示す図である。
【０１２１】
また、データ圧縮装置２０が図１８に示されているような汎用コンピュータ１００である場合には、下記の説明は、そのような処理を行う制御プログラムを定義する。すなわち、以下では、下記に説明する処理を汎用コンピュータに行わせる制御プログラムの説明でもある。
【０１２２】
処理が開始されるとＳ５００で入力バッファ部２１は、現在のアドレスの位置ｐ＿ｃｕｒと、非一致長ｎ＿ｌｅｎをリセットする。たとえば、ｐ＿ｃｕｒ＝０、ｎ＿ｌｅｎ＝０とする。本ステップの処理が終了すると、処理はＳ５０２に進む。
【０１２３】
次のＳ５０２で一致列検索部２２は、一致列を検索する。具体的には、一致長ｌｅｎと相対位置ｏｆｆｓｅｔを求める。本ステップの処理が終了すると、処理はＳ５０４に進む。
【０１２４】
Ｓ５０４で一致列検索部２２は、一致列が見つかったかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、一致列が見つかった場合には、処理はＳ５０６に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、一致列が見つからなかった場合には、処理はＳ５３２に進む。
【０１２５】
Ｓ５０６で一致列検索部２２は、現在のアドレスの位置ｐ＿ｃｕｒと、非一致長ｎ＿ｌｅｎを更新する。たとえば、現在のアドレスの位置ｐ＿ｃｕｒと、非一致長ｎ＿ｌｅｎをそれぞれ、１だけ増加させる。
【０１２６】
Ｓ５０６では、先頭位置調整処理が行われる。
図１１を参照して、先頭位置調整処理について説明する。この処理では、一致長の最小値Ｎが定められているとする。
【０１２７】
処理が開始されるとＳ６００で一致列検索部２２は、相対位置ｏｆｆｓｅｔを変数ｉに代入する。本ステップの処理が終了すると、処理はＳ６０２に進む。
【０１２８】
Ｓ６０２で一致列検索部２２は、変数ｉが一致長の最小値Ｎ以上であるかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、変数ｉが一致長の最小値Ｎ以上である場合には、処理はＳ６０６に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、変数ｉが一致長の最小値Ｎ以上ではない場合には、処理はＳ６０４に進む。
【０１２９】
Ｓ６０６で一致列検索部２２は、非一致長ｎ＿ｌｅｎに（ｉ−ｏｆｆｓｅｔ）の値を加え、現在のアドレスの位置ｐ＿ｃｕｒに（ｉ−ｏｆｆｓｅｔ）の値を加える。さらに、一致列の一致長ｌｅｎから（ｉ−ｏｆｆｓｅｔ）の値を引く。本ステップの処理が終了すると、先頭位置調整処理は終了する。
【０１３０】
Ｓ６０４で一致列検索部２２は、変数ｉにｏｆｆｓｅｔの値を加える。
図１０に戻って、Ｓ５０６の次のＳ５０８で一致列分割部２８は、一致列分割処理を行う。
【０１３１】
図１２Ａ、１２Ｂを参照して、一致列分割処理について説明する。
図１２Ａは、上記Ｅｘ１のように、Ｐ（１）、Ｐ（３）、Ｐ（７）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する場合の処理を示す図である。
【０１３２】
処理を開始すると、Ｓ７００で一致列分割部２８は、分割した一致列の後尾番号ｅ＿ｎｕｍの値をリセットし、一致列の一致長の変数ｌｅｎ２に一致列の一致長ｌｅｎの値を代入する。本ステップの処理が終了すると、処理はＳ７０２に進む。
【０１３３】
Ｓ７０２で一致列分割部２８は、ｏｆｆｓｅｔ＞Ｘまたはｏｆｆｓｅｔ＞ｌｅｎ２であるかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、ｏｆｆｓｅｔ＞Ｘまたはｏｆｆｓｅｔ＞ｌｅｎ２である場合には、処理はＳ７０４に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、ｏｆｆｓｅｔ≦Ｘかつｏｆｆｓｅｔ≦ｌｅｎ２の場合には、処理はＳ７０６に進む。
【０１３４】
Ｓ７０４で一致列分割部２８は、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｅ＿ｎｕｍ］にｏｆｆｓｅｔの値を代入し、分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ］にｌｅｎ２の値を代入する。本ステップの処理が終了すると、処理はＳ７０６に進む。
【０１３５】
Ｓ７０６で一致列分割部２８は、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｅ＿ｎｕｍ］にｏｆｆｓｅｔの値を代入し、分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ］にｌｅｎ２の値を代入する。さらに、ｅ＿ｎｕｍの値を更新する。たとえば、ｅ＿ｎｕｍの値を１だけ増やす。ｌｅｎ２の値からｏｆｆｓｅｔの値を引き、ｏｆｆｓｅｔの値を更新する。ｏｆｆｓｅｔの値の更新は、たとえば、値を２倍にする。本ステップの処理が終了すると、処理はＳ７０２に戻る。
【０１３６】
図１２Ｂは、上記Ｅｘ２のように、ｎ＝（一致長＋ｃａｒｔｏｎ−１）÷相対位置とし、Ｐ（ｎ÷２）、Ｐ（ｎ÷４） 、Ｐ（ｎ÷８）、・・・、Ｐ（ｎ÷２ｍ））（ただしｎ÷２ｍ＞１）で分割する場合の処理を示す図である。
【０１３７】
処理を開始すると、Ｓ８００で一致列分割部２８は、一致長をｌｅｎ、相対位置をｏｆｆｓｅｔとして、ｎ＝（ｌｅｎ＋ｃａｒｔｏｎ−１）÷ｏｆｆｓｅｔで算出する。さらに、ダミー変数ｉをリセットし、ｉ＝０とする。本ステップの処理が終了すると、処理はＳ８０２に進む。
【０１３８】
Ｓ８０２で一致列分割部２８は、Ｓ８００で算出されたｎの値が１以下であるかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、ｎの値が１以下である場合には、処理はＳ８０６に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、ｎの値が１より大きいの場合には、処理はＳ８０４に進む。
【０１３９】
Ｓ８０４で一致列分割部２８は、ｎの値を更新する。たとえば、値を半分にする。さらに、分割位置Ｐ（ｉ）にｎの値を代入し、さらにダミー変数ｉの値を１増やす。本ステップの処理が終了すると、処理はＳ８０２に戻る。
【０１４０】
Ｓ８０６で一致列分割部２８は、一致列の一致長の変数ｌｅｎ２と、分割した一致列の後尾番号ｅ＿ｎｕｍの値をリセットする。ｌｅｎ２＝０、ｅ＿ｎｕｍ＝０とする。本ステップの処理が終了すると、処理はＳ８０８に進む。
【０１４１】
Ｓ８０８で一致列分割部２８は、ダミー変数ｉの値が１より小さいかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、ダミー変数ｉの値が１より小さい場合には、処理はＳ８１０に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、ダミー変数ｉの値が１以上の場合には、処理はＳ８１２に進む。
【０１４２】
Ｓ８１０で一致列分割部２８は、分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ］に（ｌｅｎ−ｌｅｎ２）の値を代入する。また分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｅ＿ｎｕｍ］に（Ｐ（０）＋１）×ｏｆｆｓｅｔの値を代入する。本ステップの処理が終了すると、一致列分割処理を終了する。
【０１４３】
Ｓ８１２で一致列分割部２８は、ダミー変数ｉの値を１減らす。また、ダミー変数ｔｍｐに分割位置Ｐ（ｉ）と相対位置ｏｆｆｓｅｔの積、Ｐ（ｉ）×ｏｆｆｓｅｔを代入し、このダミー変数ｔｍｐを分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ］と、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｅ＿ｎｕｍ］に代入する。ｌｅｎ２の値にｔｍｐの値を加え、ｅ＿ｎｕｍの値を１増やす。本ステップの処理が終了すると、処理はＳ８０８に戻る。
【０１４４】
図１０に戻り、Ｓ５１０で一致列分割部２８は、分割した一致列の先頭番号ｆ＿ｎｕｍと分割した一致列の非一致長ｎ＿ｌｅｎ２をリセットする。ｆ＿ｎｕｍ＝０、ｎ＿ｌｅｎ２＝０とする。本ステップの処理が終了すると、Ｓ５１２に進む。
【０１４５】
Ｓ５１２で一致列分割部２８は、一致長調整処理を行う。
一致長調整処理について、図１３を参照して説明する。
【０１４６】
処理を開始するとＳ９００で一致列分割部２８は、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｆ＿ｎｕｍ］が一致長の最小値Ｎ以上であるかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｆ＿ｎｕｍ］が一致長の最小値Ｎ以上である場合には、処理はＳ９０４に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｆ＿ｎｕｍ］が一致長の最小値Ｎより小さい場合には、処理はＳ９０２に進む。
【０１４７】
Ｓ９０２で一致列分割部２８は、分割した一致列の非一致長ｎ＿ｌｅｎの値にＡ＿ｏｆｆｓｅｔ［ｆ＿ｎｕｍ］の値を加える。また、ｆ＿ｎｕｍの値を１増やす。本ステップの処理が終了すると、処理はＳ９００に戻る。
【０１４８】
Ｓ９００およびＳ９０２の処理で、先頭の分割列の調整を行う。
Ｓ９０４で一致列分割部２８は、分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ−１］が一致長の最小値Ｎ以上であるか、またはｅ＿ｎｕｍの値がｆ＿ｎｕｍの値より小さいかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ−１］が一致長の最小値Ｎ以上であるか、またはｅ＿ｎｕｍの値がｆ＿ｎｕｍの値より小さい場合には、一致長調整処理を終了する。また、もしこの判定の結果が“ＮＯ”、すなわち、分割した一致列の一致位置Ａ＿ｏｆｆｓｅｔ［ｅ＿ｎｕｍ−１］が一致長の最小値Ｎより小さく、かつｅ＿ｎｕｍの値がｆ＿ｎｕｍの値以上である場合には、処理はＳ９０６に進む。
【０１４９】
Ｓ９０６で一致列分割部２８は、分割した一致列の非一致長ｎ＿ｌｅｎ２の値に分割した一致列の一致長Ａ＿ｌｅｎ［ｅ＿ｎｕｍ−１］の値を加え、ｅ＿ｎｕｍの値を１減らす。
【０１５０】
図１０に戻って、Ｓ５１４で一致列分割部２８は、非一致長ｎ＿ｌｅｎが０かどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、非一致長ｎ＿ｌｅｎが０である場合には、処理はＳ５１８に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、非一致長ｎ＿ｌｅｎが０でない場合には、処理はＳ５１６に進む。
【０１５１】
Ｓ５１６で非一致長符号化部２５と非一致列符号化部２６は、非一致列の符号化を行う。つまり、非一致長ｎ＿ｌｅｎと、非圧縮データＩｎＢｕｆ［（ｐ＿ｃｕｒ−ｎ＿ｌｅｎ）、…、（ｐ＿ｃｕｒ−１）］の符号化を行う。本ステップの処理が終了すると、処理はＳ５１８に進む。
【０１５２】
Ｓ５１８で一致列分割部２８は、分割した一致列の先頭のアドレス番号ｆ＿ｎｕｍが分割した一致列の後尾のアドレス番号ｅ＿ｎｕｍの値より大きいかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、ｆ＿ｎｕｍ＞ｅ＿ｎｕｍである場合には、処理はＳ５２０に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、ｆ＿ｎｕｍ≦ｅ＿ｎｕｍである場合には、処理はＳ５２４に進む。
【０１５３】
Ｓ５２４で一致長符号化部２３と一致位置符号化部２４は、一致列の符号化を行う。つまり、一致列の一致長Ａ＿ｌｅｎ［ｆ＿ｎｕｍ］およびＡ＿ｏｆｆｓｅｔ［ｆ＿ｎｕｍ］の符号化を行う。本ステップの処理が終了すると、処理はＳ５２６に進む。
【０１５４】
Ｓ５２６で一致長符号化部２３と一致位置符号化部２４は、分割した一致列の先頭のアドレス番号ｆ＿ｎｕｍの値を１増やす。本ステップの処理が終了すると、処理はＳ５１８に戻る。
【０１５５】
Ｓ５２０で一致列分割部２８は、非一致長ｎ＿ｌｅｎに分割した一致列の非一致長ｎ＿ｌｅｎ２の値を代入し、現在位置ｐ＿ｃｕｒに一致長ｌｅｎの値を加える。本ステップの処理が終了すると、処理はＳ５２２に進む。
【０１５６】
Ｓ５２２で出力バッファ２７は圧縮すべき全ての元データを処理したかどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、全ての元データを処理した場合には、Ｓ５２４に進む。また、もしこの判定の結果が“ＮＯ”、すなわち、全ての元データを処理していない場合には、処理はＳ５０２に戻る。
【０１５７】
Ｓ５２４で一致列分割部２８は、非一致長ｎ＿ｌｅｎが０かどうかを判定する。もしこの判定の結果が“ＹＥＳ”、すなわち、非一致長ｎ＿ｌｅｎが０である場合には、処理を終了する。また、もしこの判定の結果が“ＮＯ”、すなわち、非一致長ｎ＿ｌｅｎが０でない場合には、処理はＳ５２６に進む。
【０１５８】
Ｓ５２６で非一致長符号化部２５と非一致列符号化部２６は、非一致列の符号化を行う。つまり、非一致長ｎ＿ｌｅｎと、非圧縮データＩｎＢｕｆ［（ｐ＿ｃｕｒ−ｎ＿ｌｅｎ）、…、（ｐ＿ｃｕｒ−１）］の符号化を行う。本ステップの処理が終了すると、処理は終了する。
【０１５９】
圧縮装置２０および上記の圧縮方法では、ＬＺ７７方式において、ある一致列の相対位置ｏｆｆｓｅｔと一致長ｌｅｎｇｔｈであるとき、ｏｆｆｓｅｔ＜ｌｅｎｇｔｈのとき、コピー元とコピー先が重なるため一致列を分割して符号化する。
【０１６０】
また、重なりの最小距離を予めＸと定め、ｏｆｆｓｅｔ＜Ｘのときのみ分割を行うようにしてもよい。
【０１６１】
また、コピー元とコピー先の重なりは、同じ１文字、２文字列、３文字列、・・・のいずれかが続けて繰返す循環文字列において発生する。循環の１セットの長さはコピー元とコピー先の相対位置（相対距離）と一致する。初回の１セットは別符号で符号化され、２回目以降の循環において重なりが発生する。
【０１６２】
そこで、循環の１セットの長さをｃａｒｔｏｎ（カートン）とし、一致文字列の先頭からＰ（１）＝ｃａｒｔｏｎ、Ｐ（２）＝ｃａｒｔｏｎ×２、・・・、Ｐ（ｎ）＝ｃａｒｔｏｎ×ｎ（ただＰ(ｎ)はｌｅｎｇｔｈより小さい）の位置の全てまたはいずれかで分割することで、コピー元とコピー先が重ならないようにする。
【０１６３】
図１４に、Ｐ（１）、Ｐ（３）、Ｐ（７）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する例を、図１５に、ｎ＝（一致長＋ｃａｒｔｏｎ−１）÷ｃａｒｔｏｎとし、Ｐ（ｎ÷２）、Ｐ（ｎ÷４） 、Ｐ（ｎ÷８）、・・・、Ｐ（ｎ÷２ｍ））（ただしｎ÷２ｍ＞１）で分割する例を示した。また、一致長の最小値をＮを予め定め、一致文字列を分割することで一致長がＮ以下となる部分は非一致列として扱ってもよい。
【０１６４】
図１６では、重なりの最小距離Ｘ, 一致長の最小値Ｎを定めた上で、Ｐ（１）、Ｐ（１＋２）、Ｐ（１＋２＋４）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する例において、重なりの最小距離Ｘ＝８、一致長の最小値Ｎ＝３の場合が示されている。この場合、一致文字列を分割することで一致長がＮ以下となる部分は非一致列として扱う。
【０１６５】
また、一致長の最小値をＮとしているとき、循環の１セットがＮ以上になるように調節した上で、上記分割を行っても良い。具体的には、相対位置ｏｆｆｓｅｔ＜Ｎのとき、Ｎ≦ｏｆｆｓｅｔ×ｉ（ただし、ｉは整数値）となる最大の「ｏｆｆｓｅｔ×ｉ」の長さの分、一致列の先頭位置を後ろへずらしても良い。
【０１６６】
例えば、図１７には、一致長の最小値Ｎ＝３として、循環の１セットがＮ以上になるように調整した上で、Ｐ（１）、Ｐ（１＋２）、Ｐ（１＋２＋４）、・・・、Ｐ（２ｍ−１）（ただし （ただし （２ｍ−１）＜ｎ）の分割を行った例が示されている。
【０１６７】
また、Ｐ（１）、Ｐ（２）, ・・・、Ｐ（ｎ）の全て、および図１４〜１７に示す分割から最も符号量が小さくなるものを選択してもよい。
【０１６８】
＜＜第１実施例（Ｅｘ１）＞＞
図１４は、Ｐ（１）、Ｐ（３）、Ｐ（７）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する例を示す図である。
【０１６９】
ｃａｒｔｏｎ＝１の場合の例として、図１４には、元データが“ａａａａａａａａａａｂ”の場合が示されている。
【０１７０】
この場合、第１番目のアドレスの位置の“ａ”が非一致列であり、第２〜１０番目のアドレスの位置の“ａａａａａａａａａ”が一致列である。第１１番目のアドレスの位置の文字“ｂ”は非一致列である。第２〜１０番目のアドレスの位置の一致列“ａａａａａａａａａ”を１文字目、３文字目、７文字目で分割する。すなわち、一致列“ａａａａａａａａａ”を、「“ａ”＋“ａａ”＋”ａａａａ”＋残り」と分割する。
【０１７１】
元データが“ａａａａａａａａａａｂ”の場合、圧縮データは “｛１、ａ｝（１、１）（２、２）（４、４）（２、８）｛１、ｂ｝”となる。
【０１７２】
ｃａｒｔｏｎ＝２の場合の例として、図１４には、元データが“ａｂａｂａｂａｂａｃ”の場合が示されている。この場合、第１〜２番目のアドレスの位置の“ａｂ”が非一致列であり、第３〜１０番目のアドレスの位置の“ａｂａｂａｂａ”が一致列である。第１１番目のアドレスの位置の文字“ｃ”は非一致列である。第３〜９番目のアドレスの位置の“ａｂａｂａｂａ”を１カートン目、３カートン目で分割する。すなわち、一致列“ａｂａｂａｂａｂ”を、「“ａｂ”＋“ａｂａｂ”＋残り」と分割する。
【０１７３】
元データが“ａｂａｂａｂａｂａｃ”の場合、圧縮データは “｛２、ａｂ｝、（２、２）（４、４）（３、８）｛１、ｃ｝”となる。
【０１７４】
ｃａｒｔｏｎ＝３の場合の例として、図１４には、元データが“ａｂｃａｂｃａｂｃａｂｄ”の場合が示されている。この場合、第１〜３番目のアドレスの位置の“ａｂｃ”が非一致列であり、第４〜１１番目のアドレスの位置の“ａｂｃａｂｃａｂ”が一致列である。第１２番目のアドレスの位置の文字“ｄ”は非一致列である。第４〜１１番目のアドレスの位置の“ａｂｃａｂｃａｂ” を１カートン目で分割する。すなわち、一致列“ａｂｃａｂｃａｂｃ”を、「“ａｂｃ”＋残り」と分割する。
【０１７５】
元データが“ａｂｃａｂｃａｂｃａｂｄ”の場合、圧縮データは “｛３、ａｂｃ｝（３、３）（５、６）｛１、ｄ｝”となる。
【０１７６】
ｃａｒｔｏｎ＝４の場合の例として、図１４には、元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｅ”の場合が示されている。この場合、第１〜４番目のアドレスの位置の“ａｂｃｄ”が非一致列であり、第５〜１５番目のアドレスの位置の“ａｂｃｄａｂｃｄａｂｃｄ”が一致列である。第１７番目のアドレスの位置の文字“ｅ”は非一致列である。第５〜１５番目のアドレスの位置の“ａｂｃｄａｂｃｄａｂｃ” を１カートン目で分割する。すなわち、一致列“ａｂｃｄａｂｃｄａｂｃ”を、「“ａｂｃｄ”＋残り」と分割する。
【０１７７】
元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｄｅ”の場合、圧縮データは “｛４、ａｂｃｄ｝（４、４）（７、８）｛１、ｅ｝”となる。
【０１７８】
ｃａｒｔｏｎ＝７の場合の例として、図１４には、元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｈ”の場合が示されている。この場合、第１〜７番目のアドレスの位置の“ａｂｃｄｅｆｇ”が非一致列であり、第８〜２０番目のアドレスの位置の“ａｂｃｄｅｆｇａｂｃｄｅｆ”が一致列である。第２１番目のアドレスの位置の文字“ｈ”は非一致列である。第８〜２０番目のアドレスの位置の“ａｂｃｄｅｆｇａｂｃｄｅｆ” を１カートン目で分割する。すなわち、一致列“ａｂｃｄｅｆｇａｂｃｄｅｆ”を、「“ａｂｃｄｅｆｇ”＋残り」と分割する。
【０１７９】
元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｈ”の場合、圧縮データは “｛７、ａｂｃｄｅｆｇ｝（７、７）（６、１４）｛１、ｈ｝”となる。
【０１８０】
ｃａｒｔｏｎ＝８の場合の例として、図１４には、元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｉ”の場合が示されている。この場合、第１〜８番目のアドレスの位置の“ａｂｃｄｅｆｇｈ”が非一致列であり、第９〜２４番目のアドレスの位置の“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇ”が一致列である。第２５番目のアドレスの位置の文字“ｉ”は非一致列である。第９〜２３番目のアドレスの位置の“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇ” を１カートン目で分割する。すなわち、一致列“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇ”を、「“ａｂｃｄｅｆｇｈ”＋残り」と分割する。
【０１８１】
元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｉ”の場合、圧縮データは “｛８、ａｂｃｄｅｆｇｈ｝（８、８）（７、１６）｛１、ｉ｝”となる。
【０１８２】
＜＜第２実施例（Ｅｘ２）＞＞
図１５は、ｎ＝（一致長＋ｃａｒｔｏｎ−１）÷ｃａｒｔｏｎとし、（Ｐ（ｎ÷２）、Ｐ（ｎ÷４） 、Ｐ（ｎ÷８）、・・・、Ｐ（ｎ÷２ｍ））（ただしｎ÷２ｍ＞１）で分割する例を示す図である。
【０１８３】
ｃａｒｔｏｎ＝１の場合の例として、図１５には、元データが“ａａａａａａａａａａｂ”の場合が示されている。
【０１８４】
第２〜１０番目のアドレスの位置の一致列“ａａａａａａａａａ”を分割するが、この場合ｎ＝（９＋１−１）÷１＝９であるので、Ｐ（４）、Ｐ（２）、Ｐ（１）で分割する。すなわち、一致列“ａａａａａａａａａ”を「“ａ”＋“ａ”＋“ａａ”＋残り」と分割する。
【０１８５】
元データが“ａａａａａａａａａａｂ”の場合、圧縮データは “｛１、ａ｝（１、１）（１、２）（２、３）（５、５）｛１、ｂ｝”となる。
【０１８６】
ｃａｒｔｏｎ＝２の場合の例として、図１５には、元データが“ａｂａｂａｂａｂａｂａｂｃ”の場合が示されている。この場合、第１〜２番目のアドレスの位置の“ａｂ”が非一致列であり、第３〜１１番目のアドレスの位置の“ａｂａｂａｂａｂａ”が一致列である。第１２番目のアドレスの位置の文字“ｃ”は非一致列である。この場合、ｎ＝（９＋２−１）÷２＝５であるので、Ｐ（２）、Ｐ（１）で分割する。すなわち、一致列“ａｂａｂａｂａｂａｂ”を、「“ａｂ”＋“ａｂ”＋残り」と分割する。
【０１８７】
元データが“ａｂａｂａｂａｂａｂａｂｃ”の場合、圧縮データは “｛２、ａｂ｝、（２、２）（２、４）（５、４）｛１、ｃ｝”となる。
【０１８８】
ｃａｒｔｏｎ＝３の場合の例として、図１５には、元データが“ａｂｃａｂｃａｂｃａｂｄ”の場合が示されている。この場合、第１〜３番目のアドレスの位置の“ａｂｃ”が非一致列であり、第４〜１１番目のアドレスの位置の“ａｂｃａｂｃａｂ”が一致列である。第１２番目のアドレスの位置の文字“ｄ”は非一致列である。この場合、ｎ＝（８＋３−１）÷３＝３であるので、Ｐ（１）で分割する。すなわち、一致列“ａｂｃａｂｃａｂ”を、「“ａｂｃ”＋残り」と分割する。
【０１８９】
元データが“ａｂｃａｂｃａｂｃａｂｄ”の場合、圧縮データは “｛３、ａｂｃ｝（３、３）（５、６）｛１、ｄ｝”となる。
【０１９０】
ｃａｒｔｏｎ＝４の場合の例として、図１５には、元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｅ”の場合が示されている。この場合、第１〜４番目のアドレスの位置の“ａｂｃｄ”が非一致列であり、第５〜１５番目のアドレスの位置の“ａｂｃｄａｂｃｄａｂｃ”が一致列である。第１６番目のアドレスの位置の文字“ｅ”は非一致列である。この場合、ｎ＝（１１＋４−１）÷４＝３であるので、Ｐ（１）で分割する。すなわち、一致列“ａｂｃｄａｂｃｄａｂｃ”を「“ａｂｃｄ”＋残り」と分割する。
【０１９１】
元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｅ”の場合、圧縮データは “｛４、ａｂｃｄ｝（４、４）（７、８）｛１、ｅ｝”となる。
【０１９２】
ｃａｒｔｏｎ＝７の場合の例として、図１５には、元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｈ”の場合が示されている。この場合、ｎ＝（１１＋７−１）÷７＝２であるので、一致列“ａｂｃｄｅｆｇａｂｃｄｅｆ”を、「“ａｂｃｄｅｆｇ”＋残り」と分割する。
【０１９３】
元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｈ”の場合、圧縮データは “｛７、ａｂｃｄｅｆｇ｝（７、７）（６、１４）｛１、ｈ｝”となる。
【０１９４】
ｃａｒｔｏｎ＝８の場合の例として、図１５には、元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｉ”の場合が示されている。この場合、第１〜８番目のアドレスの位置の“ａｂｃｄｅｆｇｈ”が非一致列であり、第９〜２３番目のアドレスの位置の“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇ”が一致列である。第２４番目のアドレスの位置の文字“ｉ”は非一致列である。この場合、ｎ＝（１５＋８−１）÷８〜２であるので、一致列“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈ”を、「“ａｂｃｄｅｆｇｈ”＋残り」と分割する。
【０１９５】
元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｉ”の場合、圧縮データは “｛８、ａｂｃｄｅｆｇｈ｝（８、８）（７、１６）｛１、ｉ｝”となる。
【０１９６】
＜＜第３実施例（Ｅｘ３）＞＞
図１６は、重なりの最小距離Ｘ, 一致長の最小値Ｎを定めた上で、Ｐ（１）、Ｐ（１＋２）、Ｐ（１＋２＋４）、・・・、Ｐ（２ｍ−１）（ただし （２ｍ−１）＜ｎ）で分割する例を示す図である。図１６では、重なりの最小距離Ｘ＝８、一致長の最小値Ｎ＝３の場合が示されている。この場合、一致文字列を分割することで一致長がＮ以下となる部分は非一致列として扱う。
【０１９７】
ｃａｒｔｏｎ＝１の場合の例として、図１６には、元データが“ａａａａａａａａａａｂ”の場合が示されている。
【０１９８】
この場合、第１番目のアドレスの位置の“ａ”が非一致列であり、第２〜１０番目のアドレスの位置の“ａａａａａａａａａ”が一致列である。第１１番目のアドレスの位置の文字“ｂ”は非一致列である。第２〜１０番目のアドレスの位置の一致列“ａａａａａａａａａ”を１文字目、３文字目、７文字目で分割するが、一致長の最小値Ｎ＝３とするためには、元データ “ａａａａａａａａａａｂ”を「“ａａａａ”＋“ａａａａ”＋“ａａｂ”」と分割する。
【０１９９】
よって、圧縮データは “｛４、ａａａａ｝（４、４）｛３、ａａｂ｝”となる。
ｃａｒｔｏｎ＝２の場合の例として、図１６には、元データが“ａｂａｂａｂａｂａｂｃ”の場合が示されている。この場合、第１〜２番目のアドレスの位置の“ａｂ”が非一致列であり、第３〜１０番目のアドレスの位置の“ａｂａｂａｂａｂ”が一致列である。第１１番目のアドレスの位置の文字“ｃ”は非一致列である。第３〜１０番目のアドレスの位置の“ａｂａｂａｂａｂ”を１カートン目、３カートン目で分割するが、一致長の最小値Ｎ＝３とするためには、元データ “ａｂａｂａｂａｂａｂｃ”を、「“ａｂａｂ”＋“ａｂａｂ”＋“ａｂａｂ”＋“ｃ”」と分割する。
【０２００】
よって圧縮データは、“｛４、ａｂａｂ｝（４、４）（４、８）｛１、ｃ｝”となる。
ｃａｒｔｏｎ＝３の場合の例として、図１６には、元データが“ａｂｃａｂｃａｂｃａｂｃｄ”の場合が示されている。この場合、第１〜３番目のアドレスの位置の“ａｂｃ”が非一致列であり、第４〜１２番目のアドレスの位置の“ａｂｃａｂｃａｂｃ”が一致列である。第１３番目のアドレスの位置の文字“ｄ”は非一致列である。第４〜１２番目のアドレスの位置の“ａｂｃａｂｃａｂｃ” を１カートン目で分割するが、一致長の最小値Ｎ＝３とするためには、元データ “ａｂｃａｂｃａｂｃａｂｃｄ”を、「“ａｂｃ”＋“ａｂｃ”＋“ａｂｃ”＋“ｄ”」と分割する。
【０２０１】
よって、圧縮データは、“｛３、ａｂｃ｝（３、３）（６、６）｛１、ｄ｝”となる。
ｃａｒｔｏｎ＝４の場合の例として、図１６には、元データが“ａｂｃｄａｂｃｄａｂｃｄａｂｃｄｅ”の場合が示されている。この場合、第１〜４番目のアドレスの位置の“ａｂｃｄ”が非一致列であり、第５〜１６番目のアドレスの位置の“ａｂｃｄａｂｃｄａｂｃｄ”が一致列である。第１７番目のアドレスの位置の文字“ｅ”は非一致列である。第５〜１６番目のアドレスの位置の“ａｂｃｄａｂｃｄａｂｃｄ” を１カートン目で分割するが、一致長の最小値Ｎ＝３とするためには、元データ“ａｂｃｄａｂｃｄａｂｃｄａｂｃｄｅ”を、「“ａｂｃｄ”＋“ａｂｃｄ”＋“ａｂｃｄａｂｃｄ”＋“ｅ”」と分割する。よって、圧縮データは “｛４、ａｂｃｄ｝（４、４）（８、８）｛１、ｅ｝”となる。
【０２０２】
ｃａｒｔｏｎ＝７の場合の例として、図１６には、元データが“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｈ”の場合が示されている。この場合、第１〜７番目のアドレスの位置の“ａｂｃｄｅｆｇ”が非一致列であり、第８〜２１番目のアドレスの位置の“ａｂｃｄｅｆｇａｂｃｄｅｆｇ”が一致列である。第２２番目のアドレスの位置の文字“ｈ”は非一致列である。第８〜２１番目のアドレスの位置の“ａｂｃｄｅｆｇａｂｃｄｅｆ” を１カートン目で分割するが、一致長の最小値Ｎ＝３とするためには、元データ“ａｂｃｄｅｆｇａｂｃｄｅｆｇａｂｃｄｅｆｇｈ”を、「“ａｂｃｄｅｆｇ”＋“ａｂｃｄｅｆｇ”＋“ａｂｃｄｅｆ”＋“ｈ”」と分割する。
【０２０３】
よって、圧縮データは “｛７、ａｂｃｄｅｆｇ｝（７、７）（６、１４）｛１、ｈ｝”となる。
【０２０４】
ｃａｒｔｏｎ＝８の場合の例として、図１６には、元データが“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇｈａｂｃｄｅｆｇｉ”の場合が示されている。この場合、第１〜８番目のアドレスの位置の“ａｂｃｄｅｆｇｈ”が非一致列であり、第９〜２３番目のアドレスの位置の“ａｂｃｄｅｆｇｈａｂｃｄｅｆｇ”が一致列である。第２４番目のアドレスの位置の文字“ｉ”は非一致列である。この場合、ｃａｒｔｏｎ＝８は重なりの最小距離以上のため分割しない。
【０２０５】
よって、圧縮データは “｛８、ａｂｃｄｅｆｇｈ｝（１５、８）｛１、ｉ｝”となる。
【０２０６】
＜＜第４実施例（Ｅｘ４）＞＞
図１７は、循環の１セットが一致長の最小値Ｎ＝３以上になるように先頭を調整する例を示す図である。
【０２０７】
ｃａｒｔｏｎ＝１の場合は、ｃａｒｔｏｎ＝３となるように一致列の先頭のアドレスの位置を調整する。
【０２０８】
元データ “ａａａａａａａａａａｂ”を「“ａａａ”＋“ａａａ”＋“ａａａａ”＋“ｂ”」と分割する。
【０２０９】
よって、圧縮データは、“｛３、ａａａ｝（３、３）（４、６）｛１、ｂ｝”となる。
ｃａｒｔｏｎ＝２の場合は、ｃａｒｔｏｎ＝４となるように一致列の先頭のアドレスの位置を調整する。
【０２１０】
元データが“ａｂａｂａｂａｂａｃ”の場合、「“ａｂａｂ”＋“ａｂａｂ”＋“ａｂａ”＋“ｃ”」と分割する。
【０２１１】
よって、圧縮データは、“｛４、ａｂａｂ｝（４、４）（３、８）｛１、ｃ｝”となる。
【０２１２】
ｃａｒｔｏｎ＝３の場合は、ｃａｒｔｏｎ＝３は一致長の最小値以上であるので、先頭位置は調整しない。
【０２１３】
元データが“ａｂｃａｂｃａｂｃａｂｄ”の場合、圧縮データは、“｛３、ａｂｃ｝（３、３）（５、６）｛１、ｄ｝”となる。
【符号の説明】
【０２１４】
１０、２０  データ圧縮装置
１１、２１  入力バッファ部
１２、２２  一致列検索部
１３、２３  一致長符号化部
１４、２４  一致位置符号化部
１５、２５  非一致長符号化部
１６、２６  非一致位置符号化部
１７、２７  出力バッファ部
２８  一致列分割部
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
圧縮前のデータの文字列中の第１の文字列の後に、前記第１の文字列と同一である第２の文字列を一致列として抽出し、前記一致列の長さと、前記第１の文字列が前記第２の文字列の幾つ前のアドレスの位置から開始されるかを示す相対位置を決定する一致列検索部と、
前記一致列検索部で抽出された前記第２の文字列から、長さが前記相対位置より小さい第３の文字列を抽出する一致列分割部と、
前記第３の文字列の長さを符号化する一致長符号化部と、
前記相対位置を符号化する一致位置符号化部と、
を含む、データ圧縮装置。
【請求項２】
前記相対位置が所定の値より小さいとき、前記第２の文字列から前記第３の文字列を抽出する、請求項１に記載のデータ圧縮装置。
【請求項３】
さらに、前記一致列検索部は、圧縮前のデータの文字列中の第１の文字列の後に、前記第１の文字列と同一である第２の文字列が存在しない、または第２の文字列が所定の長さより短い文字列を非一致列として抽出し、
前記一致列分割部は、前記第３の文字列の長さが所定の値より小さいとき、前記第３の文字列の長さの倍数であって、前記所定の値を超えない最大の値を前記非一致列またはその一部として抽出する、請求項１または２に記載のデータ圧縮装置。
【請求項４】
前記一致列分割部は、前記一致列内の循環文字列における循環の最小単位をカートンと定義し、前記第２の文字列の先頭から、カートンの整数倍の位置の全てまたは一部で前記第２の文字列を分割する、請求項１〜３のいずれか一項に記載のデータ圧縮装置。
【請求項５】
前記一致列分割部は、前記第２の文字列の先頭から前記カートンを単位として、２ｍ−１（ｍを整数）の位置の全てまたは一部で前記第２の文字列を分割する、請求項４に記載のデータ圧縮装置。
【請求項６】
前記一致列分割部は、ｌｅｎｇｔｈを一致長、ｃａｒｔｏｎを前記カートンの長さとしてｎ＝（ｌｅｎｇｔｈ＋ｃａｒｔｏｎ−１）÷ｃａｒｔｏｎとしたとき、前記第２の文字列の先頭から前記カートンを単位として、ｎ÷２ｍ（ｍを整数）の位置の全てまたは一部で前記第２の文字列を分割する、請求項４に記載のデータ圧縮装置。
【請求項７】
コンピュータで処理されるデータ圧縮方法であって、
圧縮前のデータの文字列中の第１の文字列の後に、前記第１の文字列と同一である第２の文字列を一致列として抽出し、前記一致列の長さと、前記第１の文字列が前記第２の文字列の幾つ前のアドレスの位置から開始されるかを示す相対位置を決定し、
抽出された前記第２の文字列から、長さが前記相対位置より小さい第３の文字列を抽出し、
前記第３の文字列の長さを符号化し、
前記相対位置を符号化する、
データ圧縮方法。
【請求項８】
圧縮前のデータの文字列中の第１の文字列の後に、前記第１の文字列と同一である第２の文字列を一致列として抽出し、前記一致列の長さと、前記第１の文字列が前記第２の文字列の幾つ前のアドレスの位置から開始されるかを示す相対位置を決定し、
抽出された前記第２の文字列から、長さが前記相対位置より小さい第３の文字列を抽出し、
前記第３の文字列の長さを符号化し、
前記相対位置を符号化させる、
処理をコンピュータに実行させることを特徴とするプログラム。
【国際調査報告】
2015029224.tif 000023
2015029224.tif 000024
2015029224.tif 000025
2015029224.tif 000026