(57)【要約】【課題】一定のデータ単位ごとに相関を有するデータを効率良く圧縮・復元する。【解決手段】圧縮アルゴリズム実行部２は入力データ列と、その入力データ列と相関する位置のデータ列を比較し、一致した位置を固定ビット幅の符号に符号化してその符号と一致しない位置のデータ列を合成して圧縮データとして圧縮する。復元アルゴリズム実行部１２は圧縮データ列内の符号を復号して一致しない位置のデータ列を合成する。【選択図】        図１
2004343459.tif 000002
【特許請求の範囲】
【請求項１】
入力データのうち圧縮対象となるデータを所定の圧縮単位ビット数の入力データ列に分割する手段と、
前記入力データ列の比較対象となる一度入力された入力データ列を登録データ列として記憶する記憶手段と、
前記所定の圧縮単位ビット数に分割された入力データ列を更に任意のビット数幅に分割した各分割データ列と、前記記憶手段に記憶されている当該分割データ列と相関する位置の分割データ列を比較し、一致した位置の分割データ列を固定ビット幅の符号に符号化して、その符号と一致しない位置の分割データ列を合成して圧縮データとして圧縮するとともに、前記入力データ列を次の登録データ列として前記記憶手段に登録する圧縮手段とを、
有するデータ圧縮システム。
【請求項２】
請求項１に記載のデータ圧縮システムにより圧縮されたデータを復元するデータ復元システムであって、前の復元データ列を登録データ列として記憶する記憶手段と、
前記データ圧縮システムにより圧縮された圧縮データ列内の符号化データに基づいて前記記憶手段に記憶されている分割復元データ列を抽出し、抽出した分割復元データ列と前記一致しない位置の分割データ列を合成して復元データ列を生成するとともに、前記生成した復元データ列を次の登録データ列として前記記憶手段に登録する復元手段とを、
有するデータ復元システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一定のデータ単位ごとに相関を有するデータを高能率に符号化して圧縮するデータ圧縮システム及びそのデータ圧縮システムにより圧縮されたデータを復元するためのデータ復元システムに関する。
【０００２】
【従来の技術】
大容量の情報をできるだけ少ない容量で記憶し、あるいは転送するための技術として、高能率符号化技術が知られており、例えば、ハフマン符号化法のように出現率の高いものには短い符号を割り当て、出現率の低いものには長い符号を割り当てるＦＶ（Ｆｉｘｅｄ−ｔｏ−Ｖａｒｉａｂｌｅ）符号化法や、ＬＺ（Ｌｅｍｐｅｌ−Ｚｉｖ）符号化法（下記の特許文献１を参照）やＬＺＷ（Ｌｅｍｐｅｌ−ＺｉｖＷｉｌｃｈ）符号化法（下記の特許文献２を参照）のように過去に出現したデータ列とこれから圧縮しようとしているデータ列の一致性を利用して圧縮する方式などが知られている。
【０００３】
【特許文献１】
米国特許第４，４６４，６５０号明細書
【特許文献２】
米国特許第４，５５８，３０２号明細書
【０００４】
【発明が解決しようとする課題】
しかしながら、従来のデータ圧縮技術は、データ圧縮の際に圧縮対象となるすべてのデータをいったんスキャンする必要があるために、データを入力しながら圧縮処理を実行することができず、すべてのデータの圧縮処理が完了するまでに多くの時間を要するなどの問題がある。
【０００５】
そこで、このような問題を解決するためにデータを入力しながら圧縮処理を行うゼロ圧縮法や連長圧縮法などのいわゆる１パス圧縮・復元法が提案されている。しかしながら、これらの１パス圧縮・復元法は、圧縮対象であるデータが特定ワードの繰り返し構造を有する場合には高い圧縮率を達成することができるが、例えば画像データの水平方向や垂直方向などのように一定のデータ単位ごとに相関を有するデータを圧縮するには効率のよい圧縮方法とは言えない。
【０００６】
ここで、一定のデータ単位ごとに相関を有するデータとは、図７に例示するように、例えば１ワード（３２ビット：ｂｉｔ）単位のデータが１行にｎ列（図７に示した例では８列）配列され、隣接する行の間でそれぞれの列ごとに相関（類似性）を有するようなデータ構造を持つデータをいう。具体的に一例を挙げると、図７におけるｂ行目２列目のワードは、ａ行目２列目のワードと相関関係にあり、ｃ行目２列目のワードとも相関関係にある。
【０００７】
本発明は、以上に述べた状況を鑑みて成されたものであり、一定のデータ単位ごとに相関を有するデータを効率良く圧縮・復元することができるデータ圧縮システム及びデータ復元システムを提供することを目的とする。
【０００８】
【課題を解決するための手段】
本発明は上記目的を達成するために、入力データ列と、その入力データ列と相関する位置のデータ列を比較し、一致した位置を固定ビット幅の符号に符号化してその符号と一致しない位置のデータ列を合成して圧縮するようにしたものである。
【０００９】
すなわち本発明によれば、入力データのうち圧縮対象となるデータを所定の圧縮単位ビット数の入力データ列に分割する手段と、
前記入力データ列の比較対象となる一度入力された入力データ列を登録データ列として記憶する記憶手段と、
前記所定の圧縮単位ビット数に分割された入力データ列を更に任意のビット数幅に分割した各分割データ列と、前記記憶手段に記憶されている当該分割データ列と相関する位置の分割データ列を比較し、一致した位置の分割データ列を固定ビット幅の符号に符号化して、その符号と一致しない位置の分割データ列を合成して圧縮データとして圧縮するとともに、前記入力データ列を次の登録データ列として前記記憶手段に登録する圧縮手段とを、
有するデータ圧縮システムが提供される。
【００１０】
また本発明によれば、請求項１に記載のデータ圧縮システムにより圧縮されたデータを復元するデータ復元システムであって、前の復元データ列を登録データ列として記憶する記憶手段と、
前記データ圧縮システムにより圧縮された圧縮データ列内の符号化データに基づいて前記記憶手段に記憶されている分割復元データ列を抽出し、抽出した分割復元データ列と前記一致しない位置の分割データ列を合成して復元データ列を生成するとともに、前記生成した復元データ列を次の登録データ列として前記記憶手段に登録する復元手段とを、
有するデータ復元システムが提供される。
【００１１】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態について説明する。図１は本発明に係るデータ圧縮システムの一実施の形態を示すブロック図、図２は図１の圧縮アルゴリズム実行部の圧縮アルゴリズムを説明するためのフローチャート、図３は図１の圧縮アルゴリズム実行部の圧縮アルゴリズムを示す説明図、図４は符号化例を示す説明図である。
【００１２】
＜データ圧縮システム＞
図１に示すように、本実施の形態によるデータ圧縮システムは、圧縮対象となる入力データを所定の圧縮ビット数幅の列に分割して入力するデータ入力部１と、入力データと比較対象となる登録データを上述の所定ビット数幅の列に分割して記憶する登録データ列メモリ３と、入力データに対して圧縮処理を行う圧縮アルゴリズム実行部２と、圧縮されたデータを出力するデータ出力部４を有する。
【００１３】
圧縮アルゴリズム実行部２は、データ入力部１から入力された入力データ列と、この入力データ列と相関する列配置に記憶されている登録データ列とを比較する。そして、入力データ列を更に任意に分割設定した複数のデータ幅における入力データ列と登録データ列との一致するデータ列を判定し、判定した結果に応じた固定幅符号を固定幅符号テーブル５から取得し、取得した固定幅符号と、一致データ幅以外の入力データ列のビット部分とを入力データの圧縮データとしてデータ出力部４に出力する。さらに、圧縮アルゴリズム実行部２は、圧縮前の入力データ列を次の比較対象となる登録データとして登録データ列メモリ３の対応する列位置に登録する。
【００１４】
次に、図２を参照しながら圧縮アルゴリズム実行部２が実行するデータ圧縮処理について説明する。ステップＳ０の処理において、圧縮アルゴリズム実行部２は初期設定処理を行う。具体的には、内部カウンタである登録データカウンタＮをリセット（Ｎに１をセット）し、さらに、比較対象となる登録データを所定ビット数幅の列に分割して登録データ列メモリ３に記憶する。ここで「登録データカウンタＮ」は、データ入力部１に入力される入力データ列の列番号を示すインデックスであり、第１列目の入力データを処理する際にはＮ＝１であり、第２列目の入力データを処理する際にはＮ＝２，．．．，第ｎ列目の入力データを入力する際にはＮ＝ｎと推移していく。
【００１５】
また、このステップＳ０の処理において登録データ列メモリ３に登録する登録データとしては、入力データの第１行目のデータを所定ビット数幅の列に分割して登録し、入力データの第２行目データから圧縮処理を開始し、入力データの第１行目のデータは圧縮しないままデータ出力部４に出力する。もしくは、圧縮対象となる入力データの第１行目のデータから処理を開始できるようにするために、所定のダミーデータを登録データ列メモリ３に登録するようにしてもよい。
【００１６】
圧縮アルゴリズム実行部２は、次のステップＳ１の処理においてデータ入力部１により入力された圧縮対象の第Ｎ列目の入力データ列を取得し、続くステップＳ２の処理において登録データカウンタＮの値に対応する登録データ列メモリ３の比較対象の第Ｎ列目に格納されている登録データ列を取得する。圧縮アルゴリズム実行部２は、続くステップＳ３の処理において、取得した第Ｎ列目の入力データ列及び登録データ列を、あらかじめ設定した複数の任意の幅のデータにそれぞれ分割し、続くステップＳ４の処理においてステップＳ３の処理により分割した分割後入力データ、分割後登録データの対応するデータ同士の一致を判定する。
【００１７】
圧縮アルゴリズム実行部２は続くステップＳ５の処理において、図３に例示するように、登録データ列ａ、入力データ列ｂをそれぞれステップＳ３で任意の幅に分割した分割後登録データ（ｃ、ｄ、ｅ）、分割後入力データ（ｆ、ｇ、ｈ）における対応するデータ同士の一致、不一致判定結果に応じた固定幅符号を図４に示すような固定幅符号テーブル５から取得する。
【００１８】
図３及び図４に示した例は、３２ｂｉｔ（ビット）の登録データ列ａと３２ｂｉｔの入力データ列ｂをそれぞれ４ｂｉｔ、８ｂｉｔ、２０ｂｉｔに分割した分割後登録データｃ、ｄ、ｅ、分割後入力データｆ、ｇ、ｈにおける同じ位置のｃとｆ、ｄとｇ、ｅとｈの一致判定に応じた４ｂｉｔの固定幅符号の判定例（ｂｉｔ値を１６進数表記）を示しており、例えば、
・分割後登録データｃと分割後入力データｆが一致し、分割後データｃ、ｆ以外は一致しない場合には４ｂｉｔの固定幅符号「４」を設定し、
・分割後登録データｃと分割後入力データｆが一致し、分割後登録データｄと分割後入力データｇが一致し、分割後データ（ｃ、ｆ）、（ｄ、ｇ）以外は一致しない場合には４ｂｉｔの固定幅符号「７」を設定し、
・分割後登録データｃ、ｄ、ｅが分割後入力データｆ、ｇ、ｈとすべて一致しない場合には４ｂｉｔの固定幅符号「１」を設定する。
【００１９】
ステップＳ６の処理において、圧縮アルゴリズム実行部２は、取得した固定幅符号と、ステップＳ４の処理において一致しなかった分割後入力データとを合成し、第Ｎ列目の入力データの圧縮データとしてデータ出力部４に出力する。
【００２０】
例えば、図３に示した例では、
・分割後登録データｃ、ｄ、ｅが分割後入力データｆ、ｇ、ｈとすべて一致しない場合には、４ｂｉｔの固定幅符号「１」と不一致部分の分割後入力データｆ、ｇ、ｈを出力し、
・分割後登録データｃと分割後入力データｆが一致し、分割後データｃ、ｆ以外は一致しない場合には、４ｂｉｔの固定幅符号「４」と不一致部分の分割後入力データｇ、ｈを出力し、
・分割後登録データｃ、ｄ、ｅが分割後入力データｆ、ｇ、ｈとすべて一致した場合には、４ｂｉｔの固定幅符号「８」のみを出力する。つまり、一致する分割後データが多いほど（相関度が高いほど）圧縮効率が高くなる。
【００２１】
圧縮アルゴリズム実行部２は、ステップＳ７の処理において、登録データ列メモリ３の第Ｎ列に圧縮対象であった入力データ列を登録し、続くステップＳ８の処理において登録データカウンタＮの値が登録データ列メモリ３の最大アドレス値ｎ（最大列数ｎ）であるか否かを判別する。そして、判別の結果、登録データ列Ｎの値が最大アドレス値ｎでない場合、圧縮アルゴリズム実行部２は、ステップＳ９の処理として登録データカウンタＮの値に１を加算して、ステップＳ１の処理に戻り、次の入力データ列に対する処理に移行する。
【００２２】
一方、ステップＳ８の判別の結果、登録データ列Ｎの値が最大アドレス値ｎ（最大列数ｎ）である場合は、圧縮アルゴリズム実行部２は、ステップＳａの処理として登録データカウンタＮの値を１にリセットして、ステップＳ１の処理に戻り、次の行の第１列の入力データ列に対する処理に移行する。圧縮アルゴリズム実行部２は、以上の処理をデータ入力部１が入力するすべての入力データについて実行する。
【００２３】
以上の説明から明らかなように、本実施の形態によるデータ圧縮システムにおいては、圧縮アルゴリズム実行部２が、入力データ列と相関位置関係にある登録データ列とを比較し、任意に分割設定した複数のデータ幅における入力データ列と登録データ列との、個々の一致を判定した判定結果に応じた固定幅符号と不一致部分のビット列とを圧縮データとして出力し、圧縮前の入力データ列を、次の比較対象となる登録データ列として対応する列位置に登録する。このような構成によれば、一定のデータ単位ごとに相関を有するデータであっても、データを入力しながら、効率良く高速に圧縮することができる。
【００２４】
＜データ復元システム＞
次に図５、図６を参照して、本実施の形態によるデータ復元システムの構成について説明する。図５に示すように、データ復元システムは、上記の実施の形態によるデータ圧縮システムにより圧縮された圧縮データ列を含むデータを入力するデータ入力部１１と、比較対象となる登録データを所定の幅の列に分割して記憶する登録データ列メモリ１３と、入力された圧縮データに対して復元処理を行う復元アルゴリズム実行部１２と、復元されたデータを出力するデータ出力部１４を有する。
【００２５】
復元アルゴリズム実行部１２は、データ入力部１１から入力した圧縮データ列に含まれる固定幅符号に基づいて固定幅符号テーブル１５から、圧縮データ列と相関する列位置に記憶されている登録データ列の、圧縮前のデータ列との、任意に分割した各データ幅における一致部分を求め、前記登録データ列から一致部分を取り出し、取り出した一致部分と当該圧縮データ列の固定幅符号以降のｂｉｔ部分とを合成して所定ビット数幅の復元データ列としてデータ出力部１４に出力する。さらに、復元アルゴリズム実行部１２は、当該復元データ列を次の比較対象となる登録データとして登録データ列メモリ１３の対応する列位置に登録する。
【００２６】
なお、図５に示すデータ復元システムは、図１に示したデータ圧縮システムとは別体のシステム構成として説明するが、例えば、データ入力部１１、登録データ列メモリ１３、固定幅符号テーブル１５、データ出力部１４などの構成要素の一部若しくは全部を、図１に示したデータ圧縮システムにおけるデータ入力部１、登録データ列メモリ３、固定幅符号テーブル５、データ出力部４などの構成要素と共通のシステムにより構成してもよい。
【００２７】
次に図６に示すフローチャートを参照しながら、復元アルゴリズム実行部１２が実行するデータ復元処理について説明する。ステップＳ１０の処理において、復元アルゴリズム実行部１２は初期設定処理として、内部カウンタである登録データカウンタをリセットしてＮに１をセットし、更に、比較対象となる登録データを所定ビット数幅の列に分割して登録データ列メモリ１３に記憶する。
【００２８】
ここで、登録データ列メモリ１３に登録する登録データとしては、図２を用いて説明したデータ圧縮システムのステップＳ０において入力データの第１行目のデータを圧縮しないまま出力していた場合には、このステップＳ１０においても未圧縮の第１行目の入力データを所定ビット数幅の列に分割して登録し、圧縮データの第２行目のデータから復元処理を開始する。また、上記データ圧縮システムのステップＳ０において所定のダミーデータを登録データ列メモリ３に登録し、入力データの第１行目から圧縮処理を行った場合には、このステップＳ１０においても所定のダミーデータを登録データ列メモリ１３に登録し、圧縮データの第１行目のデータから復元処理を行う。
【００２９】
復元アルゴリズム実行部１２は、ステップＳ１１の処理において、データ入力部１１が入力した復元対象となる圧縮データの第Ｎ列目の入力データ列を取得し、続くステップＳ１２の処理において入力された圧縮データ列から固定幅符号を抽出する。復元アルゴリズム実行部１２は続くステップＳ１３の処理において、固定幅符号テーブル１５を参照して、登録データ列メモリ１３の第Ｎ列目に格納されている登録データ列から、圧縮時に設定した複数の幅のデータにおける、取り出した固定幅符号に対応するデータを抽出し、続くステップＳ１４の処理においてステップＳ１３で抽出したデータのデータ幅に基づいて、入力データ列から不一致データ、つまり未圧縮であったデータを抽出する。
【００３０】
復元アルゴリズム実行部１２は、続くステップＳ１５の処理において、第Ｎ列目の登録データ列から抽出したデータと、入力データ列から抽出した未圧縮のデータとを合成して元のデータを復元し、続くステップＳ１６の処理において登録データ列メモリ１３の第Ｎ列に、復元したデータを登録する。
【００３１】
復元アルゴリズム実行部１２は、続くステップＳ１７の処理において、登録データカウンタＮの値が登録データ列メモリ１３の最大アドレス値ｎ（最大列数ｎ）であるか否かを判別する。そして、判別の結果、登録データ列Ｎの値がアドレス値ｎでない場合、復元アルゴリズム実行部１２は、ステップＳ１８の処理として登録データカウンタＮの値に１を加算して、ステップＳ１１の処理に戻り、次の入力データ列に対する処理に移行する。一方、判別の結果、登録データカウンタＮの値が最大アドレス値ｎ（最大列数ｎ）である場合は、復元アルゴリズム実行部１２は、ステップＳ１９の処理として登録データカウンタＮの値を１にリセットして、ステップＳ１１の処理に戻り、次の第１列の入力データ列に対する処理に移行する。
【００３２】
以上の説明から明らかなように、本実施の形態によるデータ復元システムでは、復元アルゴリズム実行部１２が、圧縮データ列に含まれる固定幅符号を参照して圧縮済のデータの符号化部分を復元し、復元したデータと入力されたデータの符号化部分以外のデータとを合成することにより、復元対象となるデータを順次復元する。このような構成によれば、本実施の形態によるデータ圧縮システムにより圧縮されたデータを効率良く、高速に復元することができる。
【００３３】
以上、本発明の実施の形態を詳細に説明したが、本発明は、その精神または主要な特徴から逸脱することなく、他の様々な形で実施することができる。例えば、本実施の形態では、３２ｂｉｔ単位のデータが１行に８列ずつ配置され、隣接する行の間でそれぞれの列ごとに相関（類似性）を有するようなデータ構造をもつデータをモデルに説明したが、圧縮対象となるデータのデータ構造はこれに限定されない。１行当たりの列数は８列未満でも８列以上でもよいし、１列のデータ長は３２ｂｉｔ未満でも３２ｂｉｔ以上であってもよい。
【００３４】
また、固定幅符号を、４ｂｉｔ、８ｂｉｔ、２０ｂｉｔ  に分割したデータ幅における一致度によって設定パターンを定めた例を示したが、例えば、分割するデータ幅は８ｂｉｔ、８ｂｉｔ、１６ｂｉｔとして、各分割データ幅における一致度によって設定パターンを定めてもよいし、固定幅符号の設定値も様々な値が想定される。
【００３５】
【発明の効果】
以上説明したように、本発明によれば入力データ列と、その入力データ列と相関する位置のデータ列を比較し、一致した位置を固定ビット幅の符号に符号化して、その符号と一致しない位置のデータ列を合成して圧縮データとして圧縮するようにしたので、一定のデータ単位ごとに相関を有するデータを効率良く圧縮・復元することができる。
【図面の簡単な説明】
【図１】本発明に係るデータ圧縮システムの一実施の形態を示すブロック図である。
【図２】図１の圧縮アルゴリズム実行部の圧縮アルゴリズムを説明するためのフローチャートである。
【図３】図１の圧縮アルゴリズム実行部の圧縮アルゴリズムを示す説明図である。
【図４】符号化例を示す説明図である。
【図５】本発明に係るデータ復元システムの一実施の形態を示すブロック図である。
【図６】図５の復元アルゴリズム実行部の復元アルゴリズムを説明するためのフローチャートである。
【図７】一定周期ごとに相関をもつデータの構成図である。
【符号の説明】
１、１１  データ入力部
２  圧縮アルゴリズム実行部
３、１３  登録データ列メモリ
４、１４  データ出力部
５、１５  固定幅符号テーブル
１２  復元アルゴリズム実行部
【図１】
2004343459.tif 000003
【図２】
2004343459.tif 000004
【図３】
2004343459.tif 000005
【図４】
2004343459.tif 000006
【図５】
2004343459.tif 000007
【図６】
2004343459.tif 000008
【図７】
2004343459.tif 000009