(57)【要約】データの可逆圧縮又は可逆伸張を行う際の処理速度を落とすことなく、圧縮率を維持すること。Ｎビット（Ｎは２以上の整数）の領域を有する第１のバッファに対して、入力されるＮビットの第１のデータ列をビット単位に格納し、第１のバッファの１以上後段に接続され、第１のバッファの各領域に対応付けられたＮビットの領域を有する第２のバッファに対して、第１のバッファへ第１のデータ列が格納された際に、当該第１のデータ列以前に入力された第２のデータ列について、当該第１のデータ列の各ビットに対応する領域へ格納し、第１のバッファに格納された第１のデータ列と、第２のバッファに格納された第２のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の前処理データ列として出力し、出力された第１の前処理データ列に対して可逆圧縮を行う。
2012095909.tif 000002
【特許請求の範囲】
【請求項１】
Ｎビット（Ｎは２以上の整数）の領域を有し、入力されるＮビットの第１のデータ列をビット単位に各領域へ格納する第１のバッファと、
前記第１のバッファの各領域に対応付けられたＮビットの領域を有し、前記第１のバッファの１以上後段に接続され、前記第１のバッファへ前記第１のデータ列が格納された際に、当該第１のデータ列以前に入力された第２のデータ列について、当該第１のデータ列の各ビットと対応する領域へ格納する第２のバッファと、
前記第１のバッファに格納された前記第１のデータ列と、前記第２のバッファに格納された前記第２のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の前処理データ列として出力する前処理手段と、
前記前処理手段から出力された第１の前処理データ列に対して可逆圧縮を行う可逆圧縮手段と、
を備えるデータ可逆圧縮装置。
【請求項２】
前記前処理手段は、前記第１のバッファの２以上後段に直列に接続されたバッファを前記第２のバッファとして、前記排他的論理和を算出することを特徴とする請求項１に記載のデータ可逆圧縮装置。
【請求項３】
前記前処理手段は、
前記第１のバッファの後段に直列に接続される複数の後段バッファに格納された各データ列と、前記第１のバッファに格納された第１のデータ列との排他的論理和の結果に対して前記可逆圧縮手段により可逆圧縮した場合の圧縮率の予測結果を算出し、
前記予測結果に基づいて前記複数の後段バッファのうち１つを前記第２のバッファとして選択し、
前記選択した第２のバッファと前記第１のバッファとに格納された各データ列についての前記排他的論理和の結果を前記第１の前処理データ列とし、前記選択したバッファの位置情報をさらに前記可逆圧縮手段へ出力し、
前記可逆圧縮手段は、前記位置情報を含めて前記第１の前処理データ列に対して可逆圧縮を行う
ことを特徴とする請求項１に記載のデータ可逆圧縮装置。
【請求項４】
前記第２のバッファは、前記第１のバッファに前記第１のデータ列の後続の第３のデータ列が格納された際に、前記第３のデータ列以前に入力された第４のデータ列を格納し、
前記前処理手段は、
前記第１のバッファに格納された前記第３のデータ列と前記第２のバッファに格納された前記第４のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の前処理データ列とし、
前記第１の前処理データ列と、当該第２の前処理データ列とから対応するビットごとに排他的論理和を算出し、前記第１の前処理データ列として前記可逆圧縮手段へ出力する
ことを特徴とする請求項１乃至３のいずれか１項に記載のデータ可逆圧縮装置。
【請求項５】
前記入力されるＮビットのデータ列は、主記憶内のプログラムデータ領域又はヒープ領域に格納された値であることを特徴とする請求項１乃至４のいずれか１項に記載のデータ可逆圧縮装置。
【請求項６】
Ｎビット（Ｎは２以上の整数）の領域を有する第１のバッファに対して、入力されるＮビットの第１のデータ列をビット単位に格納し、
前記第１のバッファの１以上後段に接続され、前記第１のバッファの各領域に対応付けられたＮビットの領域を有する第２のバッファに対して、前記第１のバッファへ前記第１のデータ列が格納された際に、当該第１のデータ列以前に入力された第２のデータ列について、当該第１のデータ列の各ビットに対応する領域へ格納し、
前記第１のバッファに格納された前記第１のデータ列と、前記第２のバッファに格納された前記第２のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の前処理データ列として出力し、
前記出力された第１の前処理データ列に対して可逆圧縮を行う
データ可逆圧縮方法。
【請求項７】
Ｎビット（Ｎは２以上の整数）の領域を有する第１の記憶部に対して、入力されるＮビットの第１のデータ列をビット単位に格納し、
前記第１の記憶部の各領域に対応付けられたＮビットの領域を有する第２の記憶部に対して、前記第１の記憶部へ前記第１のデータ列が格納された際に、当該第１のデータ列以前に入力された第２のデータ列について、当該第１のデータ列の各ビットに対応する領域へ格納し、
前記第１の記憶部に格納された前記第１のデータ列と、前記第２の記憶部に格納された前記第２のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の前処理データ列として生成し、
前記生成された第１の前処理データ列に対して可逆圧縮を行う
処理をコンピュータに実行させるデータ可逆圧縮プログラムが格納された非一時的なコンピュータ可読媒体。
【請求項８】
Ｎビット（Ｎは２以上の整数）の領域を有し、Ｎビットの第１のデータ列をビット単位に各領域へ格納する第１のバッファと、
前記第１のデータ列の後続のデータ列に対して所定の可逆圧縮が行われた第２のデータ列を入力し、当該第２のデータ列に対して可逆伸張を行った第１の復元データ列を出力する可逆伸張手段と、
前記第１のバッファの各領域に対応付けられたＮビットの領域を有し、前記第１の復元データ列をビット単位に各領域へ格納する第２のバッファと、
前記第２のバッファに格納された前記第１の復元データ列と、前記第１のバッファに格納された前記第１のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の後処理データ列として出力する後処理手段と、を備え、
前記第１のバッファは、前記後処理手段から出力される前記第１の後処理データ列を格納し、
前記可逆伸張手段は、前記第２のデータ列の後続のデータ列に対して前記所定の可逆圧縮が行われた第３のデータ列を入力し、当該第３のデータ列に対して可逆伸張を行った第２の復元データ列を前記第２のバッファへ出力し、
前記後処理手段は、前記第２のバッファに格納された前記第２の復元データ列と、前記第１のバッファに格納された前記第１の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の後処理データ列として出力する
ことを特徴とするデータ可逆伸張装置。
【請求項９】
Ｎビット（Ｎは２以上の整数）の領域を有する第１のバッファに対して、Ｎビットの第１のデータ列をビット単位に格納し、
前記第１のデータ列の後続のデータ列に対して所定の可逆圧縮が行われた第２のデータ列を入力し、
前記第２のデータ列に対して可逆伸張を行った第１の復元データ列を出力し、
前記第１のバッファの各領域に対応付けられたＮビットの領域を有する第２のバッファに対して、前記第１の復元データ列をビット単位に格納し、
前記第２のバッファに格納された前記第１の復元データ列と、前記第１のバッファに格納された前記第１のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の後処理データ列として出力し、
前記第１のバッファに対して、前記出力された第１の後処理データ列を格納し、
前記第２のデータ列の後続のデータ列に対して前記所定の可逆圧縮が行われた第３のデータ列を入力し、
前記第３のデータ列に対して可逆伸張を行った第２の復元データ列を前記第２のバッファへ出力し、
前記第２のバッファに格納された前記第２の復元データ列と、前記第１のバッファに格納された前記第１の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の後処理データ列として出力する
データ可逆伸張方法。
【請求項１０】
Ｎビット（Ｎは２以上の整数）の領域を有する第１の記憶部に対して、Ｎビットの第１のデータ列をビット単位に格納し、
前記第１のデータ列の後続のデータ列に対して所定の可逆圧縮が行われた第２のデータ列を入力し、
前記第２のデータ列に対して可逆伸張を行った第１の復元データ列を生成し、
前記第１の記憶部の各領域に対応付けられたＮビットの領域を有する第２の記憶部に対して、前記第１の復元データ列をビット単位に格納し、
前記第２の記憶部に格納された前記第１の復元データ列と、前記第１の記憶部に格納された前記第１のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の後処理データ列として出力し、
前記第１の記憶部に対して、前記出力された第１の後処理データ列を格納し、
前記第２のデータ列の後続のデータ列に対して前記所定の可逆圧縮が行われた第３のデータ列を入力し、
前記第３のデータ列に対して可逆伸張を行った第２の復元データ列を前記第２の記憶部へ出力し、
前記第２の記憶部に格納された前記第２の復元データ列と、前記第１の記憶部に格納された前記第１の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の後処理データ列として出力する
処理をコンピュータに実行させるデータ可逆伸張プログラムが格納された非一時的なコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ可逆圧縮装置、方法及びプログラム並びにデータ可逆伸張装置、方法及びプログラムに関し、特に、複数ビットのデータ列に対する可逆圧縮及び可逆伸張を効果的に行うためのデータ可逆圧縮装置、方法及びプログラム並びにデータ可逆伸張装置、方法及びプログラムに関する。
【背景技術】
【０００２】
データの可逆圧縮技術は、データ系列を完全に復元可能な状態で圧縮することで、データ量を削減する技術である。データ可逆圧縮技術は、文書やデータベースなど、伸張（復元）後にデータが元通りになる必要のあるデータ系列を圧縮する目的で、頻繁に使用されている。【０００３】
データ可逆圧縮技術は、例えば、非特許文献１乃至４に開示されている。非特許文献１乃至４に開示されるアルゴリズムは、ハフマン符号化やランレングス符号化、算術符号、ＬＺ符号及びその変形など、データ系列中の繰り返しパターンを探索するアルゴリズムが主流である。そして、非特許文献５には、ＬＺにおけるハードウェア装置向けの高速実装手法が開示されている。【０００４】
また、音声や画像などのデータは、時間軸上での直前のデータとの差分が小さいという性質が知られている。そこで、当該性質を利用して、音声又は画像データにおける時間軸上の直前のデータとの差分のみを記録することによってデータを圧縮する手法も頻繁に使用されている。特に、音声データについては、ＡＤＰＣＭ（Ａｄａｐｔｉｖｅ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｕｌｓｅ  Ｃｏｄｅ  Ｍｏｄｕｌａｔｉｏｎ）、画像データについては、フレーム間差分などがよく知られている。これらの技術については、例えば、特許文献１及び２に開示されている。【０００５】
また、計算機内の主記憶に格納されたデータについては、当該計算機の装置電源を一時オフにした時に、主記憶装置から補助記憶装置である不揮発記憶へデータを退避する処理であるハイバネーションを行うものが知られている。特許文献３乃至５には、ハイバネーションにおいて可逆圧縮や非可逆圧縮を適用することによって、退避及び復帰処理にかかる時間を短縮する技術が開示されている。また、プログラム等については可逆圧縮、画像等については非可逆圧縮を適用可能である。【０００６】
また、計算機が動作中であっても、使用頻度の低いプロセスを一時的に主記憶装置から補助記憶装置へ退避して、主記憶装置の領域を開放する処理であるいわゆるスワッピングについても、同様に適用可能である。【０００７】
特許文献６には、画像データの隣接する画素やブロックの差分を用いて圧縮を行う画像データ圧縮装置に関する技術が開示されている。また、特許文献７には、テスト用のランダムパターンデータを生成するための並列パタン圧縮器に関する技術が開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】国際公開２０００／０２１１９９号
【特許文献２】特開平１０−１７３５４１号公報
【特許文献３】特開２００４−０３８５４５号公報
【特許文献４】特開２００４−０３８５４６号公報
【特許文献５】国際公開２０００／０５４１３３号
【特許文献６】特開平０６−０６２２５４号公報
【特許文献７】特開平０６−２２４７７４号公報
【非特許文献】
【０００９】
【非特許文献１】Jacob Ziv and Abraham Lempel; "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, 23(3), pp. 337-343, May 1977.
【非特許文献２】Rissanen, Jorma (May 1976). "Generalized Kraft Inequality and Arithmetic Coding". IBM Journal of Research and Development 20 (3): 198-203.
【非特許文献３】Huffman's original article: D.A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., September 1952, pp 1098-1101.
【非特許文献４】Vitter, Jeffrey Scott, "Design and Analysis of Dynamic Huffman Coding", IEEE Foundations of Computer Science, 26th Annual Symposium on Digital Object Identifier: pp. 293-302, 1985.
【非特許文献５】森岡澄夫, 佐藤証: "100Mbyte/s高速データ圧縮エンジン", 第9回FPGA/PLD Design Conference, Jan 2002.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述した可逆圧縮手法では、データの可逆圧縮を行う際の処理速度を落とすことなく、圧縮率を維持することが困難という問題点がある。その理由は、可逆圧縮手法は、圧縮に関わる処理速度と、圧縮率との間でトレードオフの関係があるためである。特に、計算機の主記憶に格納されたデータの可逆圧縮の際に、このような問題点が顕著となる。そこで、以下に具体的に述べる。【００１１】
上述したハイバネーションやスワッピングなどを高速化するためには、計算機の主記憶に格納されたデータを圧縮することが有効である。特に、近年、主記憶の容量が著しく増大している。そのため、主記憶装置である揮発性記憶領域から補助記憶装置である不揮発性記憶領域への退避及び復帰処理には、以前に比べて長時間を要するようになった。よって、主記憶に格納するデータを圧縮する必要性が高まっている。【００１２】
ここで、計算機の主記憶に格納されたデータの内容は画像等に特定されていない。そこで、計算機主記憶の内容を圧縮する場合、汎用的な可逆圧縮手法（例えば、非特許文献１乃至５）を用いるか、又は、データ内容に応じて複数の圧縮手法を切り替えること（例えば、特許文献３及び４）が考えられる。例えば、後者の手法の例である特許文献３及び４は、対象データについて都度、圧縮の可否を判定する必要があり、判定処理の負荷が高い。そのため、データ内容に応じて複数の圧縮手法を切り替えるという手法は、処理が複雑であるため、長い処理時間を要する。また、当該手法は、データ内容の判別が困難であるため、一般的な利用には適さない。【００１３】
つまり、主記憶に格納されたデータを圧縮するには、前者の手法である汎用的な可逆圧縮手法を利用することが望ましい。しかし、単一の汎用的な可逆圧縮手法である算術符号など計算量の多いアルゴリズムでは、圧縮及び伸張に長時間かかってしまうため、ハイバネーションやスワッピングなどを高速化することができない。【００１４】
一方、汎用的な可逆圧縮手法のうちＬＺについては、上述したように非特許文献５などでハードウェア装置向けの高速実装手法が知られている。そのため、主記憶に格納されたデータを圧縮するために、ＬＺを用いることは適切と考えられる。しかし、ＬＺに限らず可逆圧縮手法は、計算速度の向上とのトレードオフで圧縮率が低下する。【００１５】
尚、特許文献１、２、５及び６は、画像データに特化した圧縮手法である。そのため、画像データ以外のデータを含み得る場合で、それらの判別をせずにこれらの技術を適用すると、圧縮率が低くなるか、場合によっては圧縮前のデータに比べてデータサイズが大きくなってしまう恐れがある。また、特許文献７は、不可逆圧縮に関する技術である。そのため、特許文献１、２、５、６及び７に記載の技術を用いても上述した問題点を解決することはできない。【００１６】
本発明は、このような問題点を解決するためになされたものであり、データの可逆圧縮又は可逆伸張を行う際の処理速度を落とすことなく、圧縮率を維持するためのデータ可逆圧縮装置、方法及びプログラム並びにデータ可逆伸張装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の第１の態様にかかるデータ可逆圧縮装置は、
Ｎビット（Ｎは２以上の整数）の領域を有し、入力されるＮビットの第１のデータ列をビット単位に各領域へ格納する第１のバッファと、
前記第１のバッファの各領域に対応付けられたＮビットの領域を有し、前記第１のバッファの１以上後段に接続され、前記第１のバッファへ前記第１のデータ列が格納された際に、当該第１のデータ列以前に入力された第２のデータ列について、当該第１のデータ列の各ビットと対応する領域へ格納する第２のバッファと、
前記第１のバッファに格納された前記第１のデータ列と、前記第２のバッファに格納された前記第２のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の前処理データ列として出力する前処理部と、
前記前処理部から出力された第１の前処理データ列に対して可逆圧縮を行う可逆圧縮部と、を備える。【００１８】
本発明の第２の態様にかかるデータ可逆圧縮方法は、
Ｎビット（Ｎは２以上の整数）の領域を有する第１のバッファに対して、入力されるＮビットの第１のデータ列をビット単位に格納し、
前記第１のバッファの１以上後段に接続され、前記第１のバッファの各領域に対応付けられたＮビットの領域を有する第２のバッファに対して、前記第１のバッファへ前記第１のデータ列が格納された際に、当該第１のデータ列以前に入力された第２のデータ列について、当該第１のデータ列の各ビットに対応する領域へ格納し、
前記第１のバッファに格納された前記第１のデータ列と、前記第２のバッファに格納された前記第２のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の前処理データ列として出力し、
前記出力された第１の前処理データ列に対して可逆圧縮を行う。【００１９】
本発明の第３の態様にかかるデータ可逆圧縮プログラムは、
Ｎビット（Ｎは２以上の整数）の領域を有する第１の記憶部に対して、入力されるＮビットの第１のデータ列をビット単位に格納し、
前記第１の記憶部の各領域に対応付けられたＮビットの領域を有する第２の記憶部に対して、前記第１の記憶部へ前記第１のデータ列が格納された際に、当該第１のデータ列以前に入力された第２のデータ列について、当該第１のデータ列の各ビットに対応する領域へ格納し、
前記第１の記憶部に格納された前記第１のデータ列と、前記第２の記憶部に格納された前記第２のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の前処理データ列として生成し、
前記生成された第１の前処理データ列に対して可逆圧縮を行う
処理をコンピュータに実行させる。【００２０】
本発明の第４の態様にかかるデータ可逆伸張装置は、
Ｎビット（Ｎは２以上の整数）の領域を有し、Ｎビットの第１のデータ列をビット単位に各領域へ格納する第１のバッファと、
前記第１のデータ列の後続のデータ列に対して所定の可逆圧縮が行われた第２のデータ列を入力し、当該第２のデータ列に対して可逆伸張を行った第１の復元データ列を出力する可逆伸張部と、
前記第１のバッファの各領域に対応付けられたＮビットの領域を有し、前記第１の復元データ列をビット単位に各領域へ格納する第２のバッファと、
前記第２のバッファに格納された前記第１の復元データ列と、前記第１のバッファに格納された前記第１のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の後処理データ列として出力する後処理部と、を備え、
前記第１のバッファは、前記後処理部から出力される前記第１の後処理データ列を格納し、
前記可逆伸張部は、前記第２のデータ列の後続のデータ列に対して前記所定の可逆圧縮が行われた第３のデータ列を入力し、当該第３のデータ列に対して可逆伸張を行った第２の復元データ列を前記第２のバッファへ出力し、
前記後処理部は、前記第２のバッファに格納された前記第２の復元データ列と、前記第１のバッファに格納された前記第１の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の後処理データ列として出力することを特徴とする。【００２１】
本発明の第５の態様にかかるデータ可逆伸張方法は、
Ｎビット（Ｎは２以上の整数）の領域を有する第１のバッファに対して、Ｎビットの第１のデータ列をビット単位に格納し、
前記第１のデータ列の後続のデータ列に対して所定の可逆圧縮が行われた第２のデータ列を入力し、
前記第２のデータ列に対して可逆伸張を行った第１の復元データ列を出力し、
前記第１のバッファの各領域に対応付けられたＮビットの領域を有する第２のバッファに対して、前記第１の復元データ列をビット単位に格納し、
前記第２のバッファに格納された前記第１の復元データ列と、前記第１のバッファに格納された前記第１のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の後処理データ列として出力し、
前記第１のバッファに対して、前記出力された第１の後処理データ列を格納し、
前記第２のデータ列の後続のデータ列に対して前記所定の可逆圧縮が行われた第３のデータ列を入力し、
前記第３のデータ列に対して可逆伸張を行った第２の復元データ列を前記第２のバッファへ出力し、
前記第２のバッファに格納された前記第２の復元データ列と、前記第１のバッファに格納された前記第１の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の後処理データ列として出力する。【００２２】
本発明の第６の態様にかかるデータ可逆伸張プログラムは、
Ｎビット（Ｎは２以上の整数）の領域を有する第１の記憶部に対して、Ｎビットの第１のデータ列をビット単位に格納し、
前記第１のデータ列の後続のデータ列に対して所定の可逆圧縮が行われた第２のデータ列を入力し、
前記第２のデータ列に対して可逆伸張を行った第１の復元データ列を生成し、
前記第１の記憶部の各領域に対応付けられたＮビットの領域を有する第２の記憶部に対して、前記第１の復元データ列をビット単位に格納し、
前記第２の記憶部に格納された前記第１の復元データ列と、前記第１の記憶部に格納された前記第１のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の後処理データ列として出力し、
前記第１の記憶部に対して、前記出力された第１の後処理データ列を格納し、
前記第２のデータ列の後続のデータ列に対して前記所定の可逆圧縮が行われた第３のデータ列を入力し、
前記第３のデータ列に対して可逆伸張を行った第２の復元データ列を前記第２の記憶部へ出力し、
前記第２の記憶部に格納された前記第２の復元データ列と、前記第１の記憶部に格納された前記第１の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の後処理データ列として出力する
処理をコンピュータに実行させる。
【発明の効果】
【００２３】
本発明により、データの可逆圧縮又は可逆伸張を行う際の処理速度を落とすことなく、圧縮率を維持するためのデータ可逆圧縮装置、方法及びプログラム並びにデータ可逆伸張装置、方法及びプログラムを提供することができる。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施の形態１にかかるデータ可逆圧縮装置の構成を示すブロック図である。
【図２】本発明の実施の形態１にかかるデータ可逆圧縮方法の処理の流れを示すフローチャートである。
【図３】本発明の実施の形態１にかかるデータ可逆伸張装置の構成を示すブロック図である。
【図４】本発明の実施の形態１にかかるデータ可逆伸張方法の処理の流れを示すフローチャートである。
【図５】本発明の実施の形態２にかかるデータ可逆圧縮装置の構成を示すブロック図である。
【図６】本発明の実施の形態２にかかるデータ可逆圧縮方法の処理の流れを示すフローチャートである。
【図７】本発明の実施の形態２にかかるデータ可逆伸張装置の構成を示すブロック図である。
【図８】本発明の実施の形態２にかかるデータ可逆伸張方法の処理の流れを示すフローチャートである。
【図９】本発明の実施の形態３にかかるデータ可逆圧縮装置の構成を示すブロック図である。
【図１０】本発明の実施の形態３にかかるデータ可逆圧縮方法の処理の流れを示すフローチャートである。
【図１１】本発明の実施の形態３にかかるデータ可逆伸張装置の構成を示すブロック図である。
【図１２】本発明の実施の形態３にかかるデータ可逆伸張方法の処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００２５】
以下では、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。各図面において、同一要素には同一の符号が付されており、説明の明確化のため、必要に応じて重複説明は省略する。
【００２６】
＜発明の実施の形態１＞
本発明の実施の形態１にかかるデータ可逆圧縮装置１００は、本発明のデータ可逆圧縮処理のための構成及び機能を、ハードウェアとして実装した場合の例を示している。
【００２７】
図１は、本発明の実施の形態１にかかるデータ可逆圧縮装置１００の構成を示すブロック図である。データ可逆圧縮装置１００は、外部から連続してＮビットデータ列Ｄ１（Ｎは２以上の整数）を入力し、所定の可逆圧縮処理を行い、可逆圧縮済みＮビットデータ列Ｄ２として出力する。データ可逆圧縮装置１００は、バッファ１０、バッファ２１、・・・、バッファ２ｍと、前処理部３０と、可逆圧縮部４０とを備える。
【００２８】
バッファ１０は、Ｎビットの領域を有し、入力されるＮビットの第１のデータ列を、ビット単位に各領域へ格納する第１のバッファである。具体的には、バッファ１０は、Ｎ個のフリップフロップであるＦＦ１０１、１０２、・・・、１０ｎを有するＮビットＦＦである。例えば、バッファ１０は、入力されるＮビットデータ列Ｄ１の第１ビットの値をＦＦ１０１に、第２ビットの値をＦＦ１０２に、・・・、第Ｎビットの値をＦＦ１０ｎへそれぞれ格納する。
【００２９】
バッファ２１〜２ｍは、それぞれバッファ１０の各領域に対応付けられたＮビットの領域を有するバッファである。バッファ２１〜２ｍは、Ｎ個のフリップフロップを有するＮビットＦＦである。すなわち、バッファ２１のＦＦ２１１、２１２、・・・、２１ｎ、・・・バッファ２ｍのＦＦ２ｍ１、２ｍ２、・・・、２ｍｎは、それぞれ、上述したバッファ１０のＦＦ１０１、１０２、・・・、１０ｎの各ＦＦに対応付けられている。また、バッファ２１〜２ｍは、バッファ１０の１以上後段に接続されている。そして、バッファ２１〜２ｍは、それぞれ直列に接続されている。言い換えると、バッファ１０及び２１〜２ｍは、前後のバッファ間で対応するビットにおけるＦＦ同士が接続されており、同一のバッファ内の異なるビット間では接続されていない。
【００３０】
また、バッファ２１〜２ｍは、バッファ１０へ第１のデータ列が格納された際に、当該第１のデータ列以前に入力された第２のデータ列について、当該第１のデータ列の各ビットと対応する領域へ格納する。このとき、バッファ２ｍを第２のバッファと呼ぶものとする。尚、図１では、ｍが２以上として記載しているが、本発明の実施の形態１に係るデータ可逆圧縮装置１００は、少なくともｍが１以上であればよい。すなわち、バッファ１０及び２１〜２ｍは、少なくとも２以上である。
【００３１】
前処理部３０は、バッファ１０に格納された第１のデータ列と、バッファ２ｍに格納された第２のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の前処理データ列として出力する。具体的には、前処理部３０は、１ビット排他的論理和３０１、３０２、・・・、３０ｎを備える。そして、１ビット排他的論理和３０１、３０２、・・・、３０ｎは、それぞれ、ＦＦ１０１、１０２、・・・、１０ｎに対応する。すなわち、１ビット排他的論理和３０１は、ＦＦ１０１とＦＦ２ｍ１とに格納された値について排他的論理和を算出する。同様に、１ビット排他的論理和３０２は、ＦＦ１０２とＦＦ２ｍ２とに格納された値について、・・・、１ビット排他的論理和３０ｎは、ＦＦ１０ｎとＦＦ２ｍｎとに格納された値について、それぞれ排他的論理和を算出する。そして、前処理部３０は、１ビット排他的論理和３０１〜３０ｎから出力された値を、この順序でＮビットの前処理データ列として、可逆圧縮部４０へ出力する。
【００３２】
可逆圧縮部４０は、前処理部３０から出力された第１の前処理データ列に対して所定の可逆圧縮処理を行う。そして、可逆圧縮部４０は、当該可逆圧縮処理の結果を可逆圧縮済みＮビットデータ列Ｄ２として出力する。尚、可逆圧縮部４０における可逆圧縮処理は、公知ものを用いても構わない。例えば、可逆圧縮部４０には、上述した非特許文献５に記載の装置を用いることができる。
【００３３】
データ可逆圧縮装置１００において、バッファ１０及び２１〜２ｍは、順次、入力されるＮビットデータ列Ｄ１をシフトしながら保持する。すなわち、バッファサイズがｍ＋１のとき、ｍ語前までのデータを保持する。そして、入力された語とｍ語前の語との排他的論理和を前処理部３０によって求め、その結果であるデータ列を可逆圧縮部４０で圧縮する。
【００３４】
図２は、本発明の実施の形態１にかかるデータ可逆圧縮方法の処理の流れを示すフローチャートである。前提として、データ可逆圧縮装置１００に入力されるＮビットデータ列Ｄ１のうち、第１番目から第ｍ番目までのデータ列については、予めバッファ１０及び２１〜２ｍ−１（不図示）に、入力順にｍ個のＮビットデータ列が格納済みであるものとする。
【００３５】
このとき、データ可逆圧縮装置１００は、入力されたＮビットデータ列Ｄ１を第１のバッファ１０に格納する（Ｓ１１）。そして、第１のバッファ１０に対する後段のバッファ２１〜２ｍは、自己の前段のバッファに格納済みのデータ列を順次、後段のバッファに格納する（Ｓ１２）。
【００３６】
ここで、前処理部３０は、後段のバッファ２１〜２ｍのうち１つ（ここでは、第２のバッファは、バッファ２ｍ）と第１のバッファ１０とに格納されたデータ列についてビットごとに排他的論理和し、前処理データ列を出力する（Ｓ１３）。その後、可逆圧縮部４０は、前処理データ列に対して可逆圧縮して（Ｓ１４）、可逆圧縮済みＮビットデータ列Ｄ２として出力する。
【００３７】
尚、バッファ１０及び２１〜２ｍに、予め全てのビット値が"０"である値が格納されている場合、入力されるＮビットデータ列Ｄ１のうち、第１番目から第ｍ番目までのデータ列についても、ステップＳ２１〜Ｓ２４が適用可能である。
【００３８】
このようにして可逆圧縮された可逆圧縮済みＮビットデータ列Ｄ２は、本発明の実施の形態１にかかるデータ可逆伸張装置２００によって元通りに伸張することができる。
【００３９】
図３は、本発明の実施の形態１にかかるデータ可逆伸張装置２００の構成を示すブロック図である。データ可逆伸張装置２００は、外部から連続して所定の可逆圧縮が行われた可逆圧縮済みＮビットデータ列Ｄ２を入力し、所定の可逆伸張処理を行い、Ｎビットデータ列Ｄ１として出力する。データ可逆伸張装置２００は、可逆伸張部５０と、バッファ６０と、バッファ７１〜７ｍと、後処理部８０とを備える。
【００４０】
可逆伸張部５０は、入力される可逆圧縮済みＮビットデータ列Ｄ２に対して、所定の可逆伸張処理を行い、復元データ列としてバッファ６０へ出力する。ここで、所定の可逆伸張処理は、可逆圧縮済みＮビットデータ列Ｄ２を可逆圧縮する際に用いられた可逆圧縮手法に対応するものとする。そのため、可逆伸張部５０における可逆伸張処理は、可逆圧縮部４０と同様に、公知ものを用いても構わない。
【００４１】
バッファ６０は、Ｎビットの領域を有し、入力される復元データ列を、ビット単位に各領域へ格納するバッファである。具体的には、バッファ６０は、Ｎ個のフリップフロップであるＦＦ６０１、６０２、・・・、６０ｎを有するＮビットＦＦである。例えば、バッファ６０は、可逆伸張部５０から出力される復元データ列の第１ビットの値をＦＦ６０１に、第２ビットの値をＦＦ６０２に、・・・、第Ｎビットの値をＦＦ６０ｎへそれぞれ格納する。
【００４２】
バッファ７１〜７ｍは、それぞれバッファ６０の各領域に対応付けられたＮビットの領域を有するバッファである。バッファ７１〜７ｍは、Ｎ個のフリップフロップを有するＮビットＦＦである。すなわち、バッファ７１のＦＦ７１１、７１２、・・・、７１ｎ、・・・バッファ７ｍのＦＦ７ｍ１、７ｍ２、・・・、７ｍｎは、それぞれ、上述したバッファ６０のＦＦ６０１、６０２、・・・、６０ｎの各ＦＦに対応付けられている。また、バッファ７１〜７ｍは、後処理部８０の１以上後段に接続されている。そして、バッファ７１〜７ｍは、それぞれ直列に接続されている。言い換えると、バッファ７１〜７ｍは、前後のバッファ間で対応するビットにおけるＦＦ同士が接続されており、同一のバッファ内の異なるビット間では接続されていない。尚、図３では、ｍが２以上として記載しているが、本発明の実施の形態１に係るデータ可逆伸張装置２００は、少なくともｍが１以上であればよい。すなわち、バッファ６０及び７１〜７ｍは、少なくとも２以上である。
【００４３】
後処理部８０は、バッファ６０に格納された復元データ列と、バッファ７ｍに格納された後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの後処理データ列として出力する。そのため、バッファ７１〜７ｍは、バッファ６０に復元データ列が格納された際に、当該復元データ列以前に後処理部８０により後処理されたＮビットの後処理データ列について、当該復元データ列の各ビットと対応する領域へ格納する。尚、データ可逆圧縮装置１００にかかるバッファ２ｍと、データ可逆伸張装置２００にかかるバッファ７ｍとは、ｍの値が一致しているものとする。
【００４４】
ここで、バッファ７ｍを第１のバッファ、バッファ６０を第２のバッファと呼ぶものとする。そして、第１のバッファ７ｍに格納される後処理データ列を第１のデータ列とする。この場合、可逆伸張部５０は、当該第１のデータ列の後続のデータ列に対して所定の可逆圧縮が行われた第２のデータ列を入力することとなる。そして、可逆伸張部５０は、当該第２のデータ列に対して可逆伸張を行った第１の復元データ列を出力する。そのため、第２のバッファ６０には、第１の復元データ列が格納される。そして、後処理部８０は、第２のバッファ６０に格納された第１の復元データ列と、第１のバッファ７ｍに格納された第１のデータ列とについて、第１の後処理データ列を生成し、出力することとなる。
【００４５】
その後、第１のバッファ７ｍは、後処理部８０から出力される第１の後処理データ列を格納する。そして、可逆伸張部５０は、第２のデータ列の後続のデータ列に対して所定の可逆圧縮が行われた第３のデータ列を入力する。これに伴い、可逆伸張部５０は、当該第３のデータ列に対して可逆伸張を行った第２の復元データ列を第２のバッファ６０へ出力する。そして、後処理部８０は、第２のバッファ６０に格納された第２の復元データ列と、第１のバッファ７ｍに格納された第１の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の後処理データ列として出力する。
【００４６】
図４は、本発明の実施の形態１にかかるデータ可逆伸張方法の処理の流れを示すフローチャートである。前提として、データ可逆伸張装置２００に入力される可逆圧縮済みＮビットデータ列Ｄ２のうち、第１番目から第ｍ番目までのデータ列については、予め可逆伸張部５０により可逆伸張され、バッファ６０及び７１〜７ｍ−１（不図示）に、入力順にｍ個のＮビットデータ列が格納済みであるものとする。
【００４７】
このとき、可逆伸張部５０は、入力された可逆圧縮済みのデータ列Ｄ２に対して可逆伸張し、復元データ列を出力する（Ｓ２１）。そして、復元データ列を第１のバッファ６０に格納する（Ｓ２２）。
【００４８】
続いて、後処理部８０は、後段のバッファ７１〜７ｍのうち１つ（ここでは、第１のバッファは、バッファ７ｍ）と第２のバッファ６０とに格納されたデータ列についてビットごとに排他的論理和し、後処理データ列を出力する（Ｓ２３）。そして、出力された後処理データ列を順次、後段のバッファ７１〜７ｍに格納する（Ｓ２４）。
【００４９】
以上のことから、Ｎビットデータ列Ｄ１は、データ可逆圧縮装置１００により可逆圧縮済みＮビットデータ列Ｄ２に変換されたが、データ可逆伸張装置２００を用いて、元のＮビットデータ列Ｄ１に復元することができる。
【００５０】
このように、本発明の実施の形態１にかかるデータ可逆圧縮装置及び方法では、前処理において簡易な排他的論理和を取ることで、可逆圧縮対象のデータ列の変化の度合いを単純な規則性を持ったものに変換するものである。そのため、本来、既存の可逆圧縮手法によりパターンマッチングでは検出することが困難であるデータ列の複雑な規則性を持ったパターンについても、排他的論理により単純な規則性を持ったパターンに変換される場合があり、可逆圧縮手法の本来の高い圧縮率を発揮することができる。特に、前処理においては、圧縮対象が画像データであるか等のデータの種別の判別をすることなく、処理の負荷の低い排他的論理和を用いているため、データ可逆圧縮装置では、全体の処理速度への影響は無視できる。それ故、可逆圧縮対象のデータ列がランダムなパターンであった場合、必ずしも単純な規則性を持ったパターンに変換できないとしても、前処理によるデータ可逆圧縮装置全体のパフォーマンスの低下は少ない。また、可逆圧縮対象のデータ列が元々単純な規則性を持ったパターンであった場合についても、排他的論理和の前処理により同様にパターンが維持されるため、やはり、前処理によるデータ可逆圧縮装置全体のパフォーマンスの低下は少ない。
【００５１】
また、本発明の実施の形態１にかかるデータ可逆伸張装置及び方法では、後処理において、簡易な排他的論理和を取り、排他的論理和後の後処理データ列を用いて、後続の可逆伸張済みデータ列との排他的論理和を取ることで、正確にデータ列を復元することができる。このときも、後処理が排他的論理和であるため、データ可逆伸張装置全体への処理負荷の影響は少なく、パフォーマンスの低下は少ない。以上のことから、本発明の実施の形態１により、データの可逆圧縮又は可逆伸張を行う際の処理速度を落とすことなく、圧縮率を維持することができる。
【００５２】
＜発明の実施の形態２＞
上述した実施の形態１にかかるデータ可逆圧縮装置１００及びデータ可逆伸張装置２００では、排他的論理和を取る位置、すなわちｍの値が静的に固定されている。しかしながら、Ｎビットデータ列Ｄ１のデータ内容又はパターンによっては、必ずしも最適な圧縮率となるとは限らない。そこで、本発明の実施の形態２では、実施の形態１に改良を加え、ｍの値を動的に決定することで、より圧縮率を高めるためのデータ可逆圧縮装置１００ａ及びデータ可逆伸張装置２００ａについて説明する。尚、以下の図５及び図７においては、ビット単位のＦＦを省略しているが、実施の形態１と同様に、前後のバッファ間でビット単位に対応付けて接続され、同一のバッファ内のＦＦ同士は接続されていないものとする。
【００５３】
図５は、本発明の実施の形態２にかかるデータ可逆圧縮装置１００ａの構成を示すブロック図である。データ可逆圧縮装置１００ａは、外部から連続してＮビットデータ列Ｄ１を入力し、所定の可逆圧縮処理を行い、可逆圧縮済みＮビットデータ列Ｄ２ａとして出力する。データ可逆圧縮装置１００ａは、バッファ１０、バッファ２１、２２、・・・、２ｍと、前処理部３０ａと、可逆圧縮部４０ａとを備える。
【００５４】
バッファ１０及び２１〜２ｍは、図１と同様の構成である。但し、バッファ１０は、各ビットのそれぞれがｍ本の信号線に分岐して前処理部３０ａへ接続されている。また、バッファ２１〜２ｍは、各ビットのそれぞれが前処理部３０ａへ接続されている。
【００５５】
前処理部３０ａは、第１のバッファ１０の後段に直列に接続される複数の後段バッファ２１〜２ｍに格納された各データ列と、第１のバッファ１０に格納された第１のデータ列との排他的論理和の結果に対して可逆圧縮部４０ａにより可逆圧縮した場合の圧縮率の予測結果を算出する。そして、前処理部３０ａは、予測結果に基づいて複数の後段バッファ２１〜２ｍのうち１つを第２のバッファとして選択する。続いて、前処理部３０ａは、選択した第２のバッファと第１のバッファ１０とに格納された各データ列についての排他的論理和の結果を第１の前処理データ列とし、選択したバッファの位置情報をさらに可逆圧縮部４０ａへ出力する。
【００５６】
具体的には、前処理部３０ａは、Ｎビット排他的論理和３１、３２、・・・、３ｍと、セレクタ３０ａ１と、パターンマッチング部３０ａ２とを備える。Ｎビット排他的論理和３１〜３ｍは、それぞれｎ個の１ビット排他的論理和を有する回路である。そして、各１ビット排他的論理和は、対応するビット同士の排他的論理和を算出する。例えば、Ｎビット排他的論理和３１は、バッファ１０とバッファ２１とのビット単位の排他的論理和を算出する。同様に、Ｎビット排他的論理和３２はバッファ１０とバッファ２２、・・・、Ｎビット排他的論理和３ｍは、バッファ１０とバッファ２ｍとのビット単位の排他的論理和を算出する。
【００５７】
パターンマッチング部３０ａ２は、Ｎビット排他的論理和３１〜３ｍのそれぞれの結果について、所定の可逆圧縮を行った場合のパターンマッチング処理を行う。そして、パターンマッチング部３０ａ２は、Ｎビット排他的論理和３１〜３ｍの各結果のうち最も圧縮率が高くなる結果がいずれであるかを判定し、判定結果を選択制御信号としてセレクタ３０ａ１へ出力する。併せて、パターンマッチング部３０ａ２は、当該選択制御信号を可逆圧縮部４０ａへ出力する。ここで、選択制御信号は、Ｎビット排他的論理和３１〜３ｍの結果のいずれかを選択させるものである。言い換えると、選択制御信号は、バッファ１０に格納されたデータ列と排他的論理和をとるべきデータ列の位置又は当該データ列が格納されたバッファの位置を示す位置情報であるということができる。
【００５８】
セレクタ３０ａ１は、パターンマッチング部３０ａ２からの選択制御信号に基づいて、Ｎビット排他的論理和３１〜３ｍの結果のいずれかを選択して、選択した結果を前処理データ列として可逆圧縮部４０ａへ出力する。
【００５９】
可逆圧縮部４０ａは、パターンマッチング部３０ａ２から出力された位置情報を含めて、セレクタ３０ａ１から出力された前処理データ列に対して所定の可逆圧縮処理を行う。そして、可逆圧縮部４０ａは、当該可逆圧縮処理の結果を可逆圧縮済みＮビットデータ列Ｄ２ａとして出力する。尚、所定の可逆圧縮処理自体は、上述した可逆圧縮部４０と同様で構わない。但し、可逆圧縮部４０ａは、例えば、前処理データ列の先頭等の所定の位置に、上述した位置情報を含めて可逆圧縮対象のデータ列とするものとする。または、可逆圧縮部４０ａは、当該位置情報と直前の位置情報との変更有無を示す情報をさらに含め、変更有の場合のみに当該位置情報を可逆圧縮対象のデータ列とするようにしてもよい。これにより、可逆圧縮対象のデータ列の増加を抑えることができる。
【００６０】
尚、上述したパターンマッチング部３０ａ２は、説明の便宜上、前処理部３０ａが内蔵するものとしたが、可逆圧縮部４０ａにおいて可逆圧縮処理のために実行されるパターンマッチング処理を行う構成要素を流用するものであっても構わない。
【００６１】
図６は、本発明の実施の形態２にかかるデータ可逆圧縮方法の処理の流れを示すフローチャートである。まず、データ可逆圧縮装置１００ａは、入力されるｍ＋１個のＮビットデータ列Ｄ１を順次、バッファ１０及び２１〜２ｍに格納する（Ｓ３１）。
【００６２】
次に、前処理部３０ａは、第１のバッファ１０と後段バッファ２１〜２ｍとのｍ個の組合せについて、格納されたデータ列同士をビットごとに排他的論理和し、ｍ個の前処理データ列を生成する（Ｓ３２）。具体的には、Ｎビット排他的論理和３１は、バッファ１０とバッファ２１との組合せを対象とし、同様に、Ｎビット排他的論理和３２は、バッファ１０とバッファ２２との組合せ、・・・Ｎビット排他的論理和３ｍは、バッファ１０とバッファ２ｍとの組合せをそれぞれ対象とする。そして、Ｎビット排他的論理和３１〜３ｍは、排他的論理和の結果として、それぞれＮビットの前処理データ列をパターンマッチング部３０ａ２及びセレクタ３０ａ１へ出力する。
【００６３】
そして、前処理部３０ａは、各前処理データ列について、最も圧縮率の高いデータ列を特定する（Ｓ３３）。これに伴い、前処理部３０ａは、選択すべきバッファの位置情報を出力する。このとき、パターンマッチング部３０ａ２は、各前処理データ列とパターンマッチングを行い、可逆圧縮をした場合にいずれの前処理データ列の圧縮率が最も高くなるかを判定する。そして、パターンマッチング部３０ａ２は、前処理データ列を出力したＮビット排他的論理和３１〜３ｍの位置又は当該Ｎビット排他的論理和に接続されたバッファ２１〜２ｍの位置を示す位置情報を選択制御信号として、セレクタ３０ａ１及び可逆圧縮部４０ａへ出力する。
【００６４】
続いて、前処理部３０ａは、特定された前処理データ列を選択して出力する（Ｓ３４）。すなわち、セレクタ３０ａ１は、選択制御信号に基づいて前処理データ列を選択して、可逆圧縮部４０ａへ出力する。
【００６５】
その後、可逆圧縮部４０ａは、選択された前処理データ列と位置情報を含めて可逆圧縮して（Ｓ３５）、可逆圧縮済みＮビットデータ列Ｄ２ａとして出力する。
【００６６】
このように、本発明の実施の形態２にかかるデータ可逆圧縮装置１００ａは、複数段ある後段バッファ２１〜２ｍのどの位置からフィードバックをかけて排他的論理和をとるかを、パターンマッチング部３０ａ２により決定し、セレクタ３０ａ１により選択する。これにより、Ｎビットデータ列Ｄ１のデータ内容又はパターンに応じて、最適な圧縮率を実現することができる。
【００６７】
図７は、本発明の実施の形態２にかかるデータ可逆伸張装置２００ａの構成を示すブロック図である。データ可逆伸張装置２００ａは、外部から連続して所定の可逆圧縮が行われた可逆圧縮済みＮビットデータ列Ｄ２ａを入力し、所定の可逆伸張処理を行い、Ｎビットデータ列Ｄ１として出力する。ここで、データ可逆伸張装置２００ａの前提となる所定の可逆圧縮とは、上述したデータ可逆圧縮装置１００ａによる可逆圧縮である。そして、所定の可逆伸張処理は、当該可逆圧縮処理に対応するものとする。そのため、可逆伸張部５０ａにおける可逆伸張処理は、可逆圧縮部４０ａに対応したものである。つまり、可逆圧縮済みＮビットデータ列Ｄ２ａには、上述した位置情報が含まれる。データ可逆伸張装置２００ａは、可逆伸張部５０ａと、バッファ６０と、バッファ７１〜７ｍと、後処理部８０ａとを備える。
【００６８】
可逆伸張部５０ａは、入力される可逆圧縮済みＮビットデータ列Ｄ２ａに対して、所定の可逆伸張処理を行い、復元データ列としてバッファ６０へ出力する。併せて、可逆伸張部５０ａは、可逆伸張を行った際に、可逆圧縮済みＮビットデータ列Ｄ２ａに含まれる位置情報を後処理部８０ａへ出力する。
【００６９】
バッファ６０及び７１〜７ｍは、図３と同様の構成である。但し、バッファ６０は、各ビットのそれぞれがｍ本の信号線に分岐して後処理部８０ａへ接続されている。また、バッファ７１〜７ｍは、各ビットのそれぞれが後処理部８０ａへ接続されている。
【００７０】
後処理部８０ａは、可逆伸張部５０ａから出力された位置情報に基づき、複数の後段バッファ７１〜７ｍのうち１つを第１のバッファとして選択する。そして、後処理部８０ａは、選択した第１のバッファと第２のバッファ６０とに格納された各データ列についての排他的論理和の結果を第１の後処理データ列として出力する。これにより、データ可逆伸張装置２００ａは、データ可逆圧縮装置１００ａによる前処理及び可逆圧縮と逆の処理を行うため、データ可逆圧縮装置１００ａの入力前のＮビットデータ列Ｄ１へ復元することができる。
【００７１】
図８は、本発明の実施の形態２にかかるデータ可逆伸張方法の処理の流れを示すフローチャートである。まず、データ可逆伸張装置２００ａは、入力された可逆圧縮済みＮビットデータ列Ｄ２に対して可逆伸張し、復元データ列と位置情報とを出力する（Ｓ４１）。具体的には、可逆伸張部５０ａは、復元データ列をバッファ６０へ出力し、位置情報を後処理部８０ａのセレクタ８０ａ１へ出力する。
【００７２】
次に、データ可逆伸張装置２００ａは、復元データ列を第１のバッファ６０に格納する（Ｓ４２）。
【００７３】
そして、後処理部８０ａは、第１のバッファ６０と後段バッファ７１〜７ｍとのｍ個の組合せについて、格納されたデータ列同士をビットごとに排他的論理和し、ｍ個の後処理データ列を生成する（Ｓ４３）。具体的には、Ｎビット排他的論理和８１は、バッファ６０とバッファ７１との組合せを対象とし、同様に、Ｎビット排他的論理和８２は、バッファ６０とバッファ７２との組合せ、・・・Ｎビット排他的論理和８ｍは、バッファ６０とバッファ７ｍとの組合せをそれぞれ対象とする。そして、Ｎビット排他的論理和８１〜８ｍは、排他的論理和の結果として、それぞれＮビットの後処理データ列をセレクタ８０ａ１へ出力する。
【００７４】
続いて、後処理部８０ａは、可逆伸張部５０ａから出力された位置情報に基づいて、ｍ個の後処理データ列のうち１つを選択して出力する（Ｓ４４）。その後、データ可逆伸張装置２００ａは、出力された後処理データ列を順次、後段バッファ７１〜７ｍに格納する（Ｓ４５）。
【００７５】
このように、本発明の実施の形態２にかかるデータ可逆伸張装置２００ａは、データ可逆圧縮装置１００ａにより排他的論理和の対象とするバッファ位置を動的に選択された場合に、正確に元のデータ列へ復元することができる。
【００７６】
＜発明の実施の形態３＞
上述した実施の形態１にかかるデータ可逆圧縮装置１００及びデータ可逆伸張装置２００では、前処理として排他的論理和を１回取るものであった。しかしながら、Ｎビットデータ列Ｄ１のデータ内容又はパターンによっては、必ずしも１回の排他的論理和により、単純な規則性を持ったパターンに変換されるとは限らない。そこで、本発明の実施の形態３では、実施の形態１に改良を加え、可逆圧縮処理の前処理における排他的論理和を２回以上行うものである。これにより、より単純な規則性を持ったパターンに変換し、より圧縮率を高めることができる。そして、以下では、説明の便宜のため、排他的論理和を２回行うデータ可逆圧縮装置１００ｂ及びデータ可逆伸張装置２００ｂについて説明する。尚、以下の図９及び図１１においては、ビット単位のＦＦを省略しているが、実施の形態１と同様に、前後のバッファ間でビット単位に対応付けて接続され、同一のバッファ内のＦＦ同士は接続されていないものとする。また、以下のその他の説明において、上述したものと同等の構成については、詳細な説明を省略する。
【００７７】
図９は、本発明の実施の形態３にかかるデータ可逆圧縮装置１００ｂの構成を示すブロック図である。データ可逆圧縮装置１００ｂは、外部から連続してＮビットデータ列Ｄ１を入力し、所定の可逆圧縮処理を行い、可逆圧縮済みＮビットデータ列Ｄ２ｂとして出力する。ここで、所定の可逆圧縮処理としては、上述した実施の形態１にかかる前処理を２回繰り返し、その後、可逆圧縮処理を行うものとする。データ可逆圧縮装置１００ｂは、バッファ１１０、１１１、・・・、１１ｉと、前処理部３０ｂと、バッファ１２０、１２１、・・・、１２ｊと、前処理部３０ｃと、可逆圧縮部４０とを備える。
【００７８】
バッファ１１０〜１１ｉ並びにバッファ１２０〜１２ｊは、それぞれ上述したバッファ１０及び２１〜２ｍと同等のものである。また、前処理部３０ｂ及び３０ｃは、それぞれ上述した前処理部３０と同等のものである。尚、ｉ及びｊは１以上の整数であり、ｉとｊとは異なる値であってもよい。
【００７９】
ここで、バッファ１１０〜１１ｉには、ｉ＋１個のデータ列が格納される。そして、前処理部３０ｂは、バッファ１１０及び１１ｉに格納されたデータ列について、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの前処理データ列として出力する。
【００８０】
また、バッファ１２０〜１２ｊには、前処理部３０ｂから出力されるｊ＋１個の前処理データ列が格納される。そして、前処理部３０ｃは、バッファ１２０及び１２ｊに格納されたデータ列について、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの前処理データ列として出力する。つまり、バッファ１２０及び１２ｊには、それぞれ１回の排他的論理和の結果である前処理データ列が格納されており、前処理部３０ｃは、前処理データ列同士について２回目の排他的論理和を算出する。これにより、Ｎビットデータ列Ｄ１の変化の度合いをより近付けることができる。そして、可逆圧縮部４０は、前処理部３０ｃから出力された前処理データ列に対して所定の可逆圧縮処理を行い、当該可逆圧縮処理の結果を可逆圧縮済みＮビットデータ列Ｄ２ｂとして出力する。
【００８１】
図１０は、本発明の実施の形態３にかかるデータ可逆圧縮方法の処理の流れを示すフローチャートである。まず、データ可逆圧縮装置１００ｂは、入力されたＮビットデータ列Ｄ１に対して前処理を行い、前処理データ列を生成する（Ｓ５１）。ここでは、前処理部３０ｂは、バッファ１１０及び１１ｉに格納されたデータ列に対して前処理を行い、生成した前処理データ列をバッファ１２０へ出力する。
【００８２】
次に、データ可逆圧縮装置１００ｂは、前処理データ列に対してさらに前処理を行い、前処理データ列として出力する（Ｓ５２）。ここでは、前処理部３０ｃは、バッファ１２０及び１２ｊに格納されたデータ列に対して前処理を行い、生成した前処理データ列を可逆圧縮部４０に格納する。
【００８３】
その後、可逆圧縮部４０は、前処理データ列に対して可逆圧縮（Ｓ５３）し、可逆圧縮済みＮビットデータ列Ｄ２ｂとして出力する。
【００８４】
尚、本発明の実施の形態３にかかる可逆圧縮処理は、次のように言い換えることもできる。まず、前処理部３０ｂは、第１のバッファ１１０に格納された第１のデータ列と第２のバッファ１１ｉに格納された第２のデータ列とから第１の前処理データ列を生成する。その結果、バッファ１２０に第１の前処理データ列が格納される。
【００８５】
次に、第１のバッファ１１０に第１のデータ列の後続の第３のデータ列が格納される。このとき、第２のバッファ１１ｉには、第３のデータ列以前に入力された第４のデータ列が格納される。尚、第４のデータ列は、第１のデータ列であってもよい。
【００８６】
そして、前処理部３０ｂは、第１のバッファ１１０に格納された第３のデータ列と第２のバッファ１１ｉに格納された第４のデータ列とから第２の前処理データ列を生成する。その結果、バッファ１２０に第２の前処理データ列が格納される。このとき、バッファ１２ｊには、第１の前処理データ列が格納される。
【００８７】
その後、前処理部３０ｃは、バッファ１２０に格納された第２の前処理データ列とバッファ１２ｊに格納された第１の前処理データ列とからさらに、前処理データ列を生成する。当該生成された前処理データ列を可逆圧縮部４０へ出力する。
【００８８】
このように、本発明の実施の形態３では、可逆圧縮処理の前処理における排他的論理和を２回以上行うことで、より単純な規則性を持ったパターンに変換し、より圧縮率を高めることができる。
【００８９】
図１１は、本発明の実施の形態３にかかるデータ可逆伸張装置２００ｂの構成を示すブロック図である。データ可逆伸張装置２００ｂは、外部から連続して所定の可逆圧縮が行われた可逆圧縮済みＮビットデータ列Ｄ２ｂを入力し、所定の可逆伸張処理を行い、Ｎビットデータ列Ｄ１として出力する。ここで、データ可逆伸張装置２００ｂの前提となる所定の可逆圧縮とは、上述したデータ可逆圧縮装置１００ｂによる可逆圧縮である。データ可逆伸張装置２００ｂは、可逆伸張部５０と、バッファ６１１と、後処理部８０ｂと、バッファ６２１〜６２ｊと、後処理部８０ｃと、バッファ６３１〜６３ｉとを備える。
【００９０】
バッファ６１１は、上述したバッファ６０と同等のものである。バッファ６２１〜６２ｊは、上述したバッファ１２０〜１２ｊに対応し、特にバッファの個数はｊ個で同数である。同様に、バッファ６３１〜６３ｉは、上述したバッファ１１０〜１１ｉに対応し、特にバッファの個数はｉ個で同数である。また、後処理部８０ｂ及び８０ｃは、それぞれ上述した後処理部８０と同等のものである。
【００９１】
ここで、バッファ６１１には、可逆伸張済みの復元データ列が格納され、バッファ６２１〜６２ｊには、ｊ個の後処理データ列が格納される。そして、後処理部８０ｂは、バッファ６１１に格納された復元データ列と、バッファ６２ｊに格納された後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの後処理データ列として出力する。
【００９２】
また、バッファ６３１〜６３ｉには、ｉ個の後処理データ列が格納される。そして、後処理部８０ｃは、バッファ６２ｊに格納された後処理データ列と、バッファ６３ｉに格納された後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットのＮビットデータ列Ｄ１として出力する。
【００９３】
つまり、後処理部８０ｂは、可逆伸張済みであるが排他的論理和前の復元データ列と、可逆伸張済みかつ１回の排他的論理和の結果である後処理データ列との排他的論理和を算出する。これにより、図９のバッファ１２０〜１２ｊに格納された前処理データ列と同等の内容に復元される。
【００９４】
そして、後処理部８０ｃは、１回の排他的論理和済みの後処理データ列と２回の排他的論理和済みの後処理データ列との排他的論理和を算出する。これにより、図９のバッファ１１０〜１１ｉに格納された前処理以前のデータ列と同等の内容に復元される。
【００９５】
図１２は、本発明の実施の形態３にかかるデータ可逆伸張方法の処理の流れを示すフローチャートである。まず、データ可逆伸張装置２００ｂは、入力された可逆圧縮済みＮビットデータ列Ｄ２ｂに対して可逆伸張し、復元データ列を出力する（Ｓ６１）。これにより、バッファ６１１に復元データ列が格納される。
【００９６】
次に、データ可逆伸張装置２００ｂは、復元データ列に対して後処理を行い、後処理データ列を生成する（Ｓ６２）。このとき、後処理部８０ｂは、１回の排他的論理和済みの後処理データ列と排他的論理和前の復元データ列との排他的論理和を算出する。
【００９７】
その後、データ可逆伸張装置２００ｂは、後処理データ列に対してさらに後処理を行い、後処理データ列として出力する（Ｓ６３）。このとき、後処理部８０ｃは、１回の排他的論理和済みの後処理データ列と２回の排他的論理和済みの後処理データ列との排他的論理和を算出する。これにより、入力前のデータ列に正確に復元することができる。
【００９８】
尚、本発明の実施の形態３では、排他的論理和の回数を３回以上とすることもできる。このように、データ列が複雑な規則性（少しずつ違うデータの並び）を有する場合に、複数回の排他的論理和により繰り返し変換することで、変化の度合いを近付けることができ、より単純な規則性をもったパターンとすることができる。このような前処理を行ったデータ列に対して可逆圧縮を行うことで、より圧縮率を高めることができる。
【００９９】
＜その他の発明の実施の形態＞
モバイル機器などでは、ハイバネーションによりに主記憶メモリ（RAM）の内容を不揮発メモリに全退避することがある。このとき、揮発性メモリに比べて、不揮発メモリへのアクセス（特に書き込み）には、時間を要する。そのため，できるだけデータ内容を可逆圧縮する必要がある。
【０１００】
汎用の可逆圧縮手法では、入力系列中の同一パターンの繰り返しを検出することにより圧縮を行う。そのため、同一パターンの繰り返しをなるべく短周期で頻繁に発生させることで、既存の可逆圧縮手法における圧縮率を向上させることができる。ここで、同一パターンの繰り返しとは、例えば、"００、００、００、００、００、００"のような同一の値の連続や、"０１、０２、０３、０１、０２、０３"のようなものを指す。
【０１０１】
そのため、このような同一パターンの繰り返しが多く出現する場合、既存の可逆圧縮手法により、高い圧縮率を達成できる。しかしながら、その他の規則性については発見できない。例えば、値がインクリメントするような場合、圧縮の効果は低い。また、圧縮アルゴリズム中に多数の規則性のパターンを組み込み、パターンマッチングする方法も考えられるが、処理が大幅に複雑化かつ低速化するので、実用的ではない。
【０１０２】
ここで、主記憶に格納されている内容は，主にプログラムコード領域、プログラムデータ領域、ヒープ領域、未使用領域などが混在している。このうち、プログラムコード領域はランダム値に近いので、圧縮の効果が低い。また、未使用領域については、００やＦＦ等の値であることが多く、圧縮の効果が高い。
【０１０３】
そして、プログラムデータ領域やヒープ領域については、アドレス値や文字コードのテーブルなどがあり、全く同じデータの繰り返しではないが類似性の高い繰り返しパターンが頻発する。例えば、プログラムデータ領域のアドレス値は、２バイトで１アドレスを構成する場合には、"４１、５０、４１、５１、４１、５２、４１、５３、・・・"というようなデータ列となる。ここで、１バイト単位でパターンマッチングを試みると、単純な規則性でないため、高い圧縮率を期待できない。しかし、１バイト置きに抽出すると、"４１、４１、４１、４１"と、"５０、５１、５２、５３"となり、単純な規則性を見出せる。
【０１０４】
そこで、本発明の実施の形態では、可逆圧縮を行う前処理として、所定の語単位に排他的論理和を取る。例えば、実施の形態１にかかるｍ＝２とすると、"４１、５０、４１、５１、４１、５２、４１、５３、・・・"については、"００、００、００、０１、００、０３、００、０１、・・・"となり、単純な規則性に変換される。このため、既存の可逆圧縮手法により前処理なく可逆圧縮した場合と比べて、同一パターンの繰り返しを検出し易くなり圧縮率を高めることができる。
【０１０５】
すなわち、実施の形態１にかかる前処理部３０は、第１のバッファの２以上後段に直列に接続されたバッファを第２のバッファとして、排他的論理和を算出することが望ましい。言い換えると、図１のバッファ２１〜２ｍは、２以上であることが望ましい。同様に、実施の形態１にかかる後処理部８０は、後処理部８０の２以上後段に直列に接続されたバッファを第２のバッファとして、排他的論理和を算出することが望ましい。言い換えると、図３のバッファ７１〜７ｍは、２以上であることが望ましい。
【０１０６】
また、本発明を未使用領域に適用した場合、"００、ＦＦ、００、ＦＦ、００、ＦＦ、・・・"のような複数値のランが"００、００、００、００、００、・・・"といった単一値のランに置換されるため、圧縮率が若干向上する。
【０１０７】
尚、プログラムコード領域に対しては、圧縮の効果は低いが、前処理をハードウェアとして実現した場合には、前処理の負荷が無視できるため、スループットの低下にはならない。
【０１０８】
そのため、本発明の実施の形態１〜３において、入力されるＮビットのデータ列が、主記憶内のプログラムデータ領域又はヒープ領域に格納された値であることにより、より効果を奏する。本発明によれば、圧縮処理の速度を低下させることなく、計算機の主記憶のデータ圧縮率を、平均３０〜４０％向上させることが可能になる。
【０１０９】
また、上述したプログラムデータ領域に対して実施の形態３を適用する場合、前処理として、隣接する語とのハミング距離（ＸＯＲ）を現在の語とするスキャン処理を二度以上繰り返す。つまり、変化の度合いを近付けることができる。このように、二回以上排他的論理和を取ることで，同一パターンの発生頻度を上げる効果を期待できる。
【０１１０】
また、本発明にかかる可逆圧縮処理及び可逆伸張処理を、コンピュータに実行させるデータ可逆圧縮プログラム及びデータ可逆伸張プログラムとして実現してもよい。その場合、データ可逆圧縮装置は、ＣＰＵ、メモリ、ハードディスク等を備えた汎用的なコンピュータを用いることができる。そして、ハードディスクにデータ可逆圧縮プログラム及びデータ可逆伸張プログラムを格納する。ここで、ＣＰＵがハードディスクからメモリへデータ可逆圧縮プログラム及びデータ可逆伸張プログラムを読み出し、実行することで、本発明にかかる可逆圧縮処理及び可逆伸張処理を実現することができる。
【０１１１】
プログラムは、様々なタイプの非一時的なコンピュータ可読媒体（non-transitory computer readable medium）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（tangible storage medium）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、CD−ROM（Read Only Memory）、CD−R、CD−R/W、半導体メモリ（例えば、マスクROM、PROM（Programmable ROM）、EPROM（Erasable PROM）、フラッシュROM、RAM（random access memory））を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（transitory computer readable medium）を用いてコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【０１１２】
さらに、本発明は上述した実施の形態のみに限定されるものではなく、既に述べた本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【０１１３】
上記の実施形態の一部又は全部は、以下の付記のようにも記載され得るが、以下には限られない。
【０１１４】
（付記１）  Ｎビット（Ｎは２以上の整数）の領域を有し、入力されるＮビットの第１のデータ列をビット単位に各領域へ格納する第１のバッファと、
前記第１のバッファの各領域に対応付けられたＮビットの領域を有し、前記第１のバッファの１以上後段に接続され、前記第１のバッファへ前記第１のデータ列が格納された際に、当該第１のデータ列以前に入力された第２のデータ列について、当該第１のデータ列の各ビットと対応する領域へ格納する第２のバッファと、
前記第１のバッファに格納された前記第１のデータ列と、前記第２のバッファに格納された前記第２のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の前処理データ列として出力する前処理部と、
前記前処理部から出力された第１の前処理データ列に対して可逆圧縮を行う可逆圧縮部と、
を備えるデータ可逆圧縮装置。
【０１１５】
（付記２）  前記前処理部は、前記第１のバッファの２以上後段に直列に接続されたバッファを前記第２のバッファとして、前記排他的論理和を算出することを特徴とする付記１に記載のデータ可逆圧縮装置。
【０１１６】
（付記３）  前記前処理部は、
前記第１のバッファの後段に直列に接続される複数の後段バッファに格納された各データ列と、前記第１のバッファに格納された第１のデータ列との排他的論理和の結果に対して前記可逆圧縮部により可逆圧縮した場合の圧縮率の予測結果を算出し、
前記予測結果に基づいて前記複数の後段バッファのうち１つを前記第２のバッファとして選択し、
前記選択した第２のバッファと前記第１のバッファとに格納された各データ列についての前記排他的論理和の結果を前記第１の前処理データ列とし、前記選択したバッファの位置情報をさらに前記可逆圧縮部へ出力し、
前記可逆圧縮部は、前記位置情報を含めて前記第１の前処理データ列に対して可逆圧縮を行う
ことを特徴とする付記１に記載のデータ可逆圧縮装置。
【０１１７】
（付記４）  前記第２のバッファは、前記第１のバッファに前記第１のデータ列の後続の第３のデータ列が格納された際に、前記第３のデータ列以前に入力された第４のデータ列を格納し、
前記前処理部は、
前記第１のバッファに格納された前記第３のデータ列と前記第２のバッファに格納された前記第４のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の前処理データ列とし、
前記第１の前処理データ列と、当該第２の前処理データ列とから対応するビットごとに排他的論理和を算出し、前記第１の前処理データ列として前記可逆圧縮部へ出力する
ことを特徴とする付記１乃至３のいずれか１項に記載のデータ可逆圧縮装置。
【０１１８】
（付記５）  前記入力されるＮビットのデータ列は、主記憶内のプログラムデータ領域又はヒープ領域に格納された値であることを特徴とする付記１乃至４のいずれか１項に記載のデータ可逆圧縮装置。
【０１１９】
（付記６）  Ｎビット（Ｎは２以上の整数）の領域を有する第１のバッファに対して、入力されるＮビットの第１のデータ列をビット単位に格納し、
前記第１のバッファの１以上後段に接続され、前記第１のバッファの各領域に対応付けられたＮビットの領域を有する第２のバッファに対して、前記第１のバッファへ前記第１のデータ列が格納された際に、当該第１のデータ列以前に入力された第２のデータ列について、当該第１のデータ列の各ビットに対応する領域へ格納し、
前記第１のバッファに格納された前記第１のデータ列と、前記第２のバッファに格納された前記第２のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の前処理データ列として出力し、
前記出力された第１の前処理データ列に対して可逆圧縮を行う
データ可逆圧縮方法。
【０１２０】
（付記７）  前記第１のバッファの２以上後段に直列に接続されたバッファを前記第２のバッファとして、前記排他的論理和を算出することを特徴とする付記６に記載のデータ可逆圧縮方法。
【０１２１】
（付記８）  前記第１のバッファの後段に直列に接続される複数の後段バッファに格納された各データ列と、前記第１のバッファに格納された第１のデータ列との排他的論理和の結果に対して前記可逆圧縮した場合の圧縮率の予測結果を算出し、
前記予測結果に基づいて前記複数の後段バッファのうち１つを前記第２のバッファとして選択し、
前記選択した第２のバッファと前記第１のバッファとに格納された各データ列についての前記排他的論理和の結果を前記第１の前処理データ列とし、前記選択したバッファの位置情報をさらに出力し、
前記出力された位置情報を含めて前記第１の前処理データ列に対して可逆圧縮を行う
ことを特徴とする付記６に記載のデータ可逆圧縮方法。
【０１２２】
（付記９）  前記第１のバッファに対して、前記第１のデータ列の後続に入力される第３のデータ列をビット単位に格納し、
前記第２のバッファに対して、前記第１のバッファへ前記第３のデータ列が格納された際に、前記第３のデータ列以前に入力された第４のデータ列をビット単位に格納し、
前記第１のバッファに格納された前記第３のデータ列と、前記第２のバッファに格納された前記第４のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の前処理データ列とし、
前記第１の前処理データ列と、当該第２の前処理データ列とから対応するビットごとに排他的論理和を算出し、前記第１の前処理データ列として出力する
ことを特徴とする付記６乃至８のいずれか１項に記載のデータ可逆圧縮方法。
【０１２３】
（付記１０）  前記入力されるＮビットの各データ列は、主記憶内のプログラムデータ領域又はヒープ領域に格納された値であることを特徴とする付記６乃至９のいずれか１項に記載のデータ可逆圧縮方法。
【０１２４】
（付記１１）  Ｎビット（Ｎは２以上の整数）の領域を有する第１の記憶部に対して、入力されるＮビットの第１のデータ列をビット単位に格納し、
前記第１の記憶部の各領域に対応付けられたＮビットの領域を有する第２の記憶部に対して、前記第１の記憶部へ前記第１のデータ列が格納された際に、当該第１のデータ列以前に入力された第２のデータ列について、当該第１のデータ列の各ビットに対応する領域へ格納し、
前記第１の記憶部に格納された前記第１のデータ列と、前記第２の記憶部に格納された前記第２のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の前処理データ列として生成し、
前記生成された第１の前処理データ列に対して可逆圧縮を行う
処理をコンピュータに実行させるデータ可逆圧縮プログラム。
【０１２５】
（付記１２）  前記第１のデータ列の２以上前に入力されたデータ列を前記第２のデータ列としてビット単位に前記第２の記憶部に格納することを特徴とする付記１１に記載のデータ可逆圧縮プログラム。
【０１２６】
（付記１３）  前記第１のデータ列以前に入力された複数のデータ列と、前記第１のデータ列との排他的論理和の結果に対して前記可逆圧縮した場合の圧縮率の予測結果を算出し、
前記予測結果に基づいて前記複数のデータ列のうち１つを前記第２のデータ列として選択し、
前記選択した第２のデータ列と前記第１のデータ列についての前記排他的論理和の結果を前記第１の前処理データ列として生成し、
前記選択した第２のデータ列が入力された順序情報を含めて前記第１の前処理データ列に対して可逆圧縮を行う
ことを特徴とする付記１１に記載のデータ可逆圧縮プログラム。
【０１２７】
（付記１４）  前記第１の記憶部に対して、前記第１のデータ列の後続に入力される第３のデータ列をビット単位に格納し、
前記第２の記憶部に対して、前記第１の記憶部へ前記第３のデータ列が格納された際に、前記第３のデータ列以前に入力された第４のデータ列をビット単位に格納し、
前記第１の記憶部に格納された前記第３のデータ列と、前記第２の記憶部に格納された前記第４のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の前処理データ列とし、
前記第１の前処理データ列と、当該第２の前処理データ列とから対応するビットごとに排他的論理和を算出し、前記第１の前処理データ列として生成する
ことを特徴とする付記１１乃至１３のいずれか１項に記載のデータ可逆圧縮プログラム。
【０１２８】
（付記１５）  前記入力されるＮビットの各データ列は、主記憶内のプログラムデータ領域又はヒープ領域に格納された値であることを特徴とする付記１１乃至１４のいずれか１項に記載のデータ可逆圧縮プログラム。
【０１２９】
（付記１６）  Ｎビット（Ｎは２以上の整数）の領域を有し、Ｎビットの第１のデータ列をビット単位に各領域へ格納する第１のバッファと、
前記第１のデータ列の後続のデータ列に対して所定の可逆圧縮が行われた第２のデータ列を入力し、当該第２のデータ列に対して可逆伸張を行った第１の復元データ列を出力する可逆伸張部と、
前記第１のバッファの各領域に対応付けられたＮビットの領域を有し、前記第１の復元データ列をビット単位に各領域へ格納する第２のバッファと、
前記第２のバッファに格納された前記第１の復元データ列と、前記第１のバッファに格納された前記第１のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の後処理データ列として出力する後処理部と、を備え、
前記第１のバッファは、前記後処理部から出力される前記第１の後処理データ列を格納し、
前記可逆伸張部は、前記第２のデータ列の後続のデータ列に対して前記所定の可逆圧縮が行われた第３のデータ列を入力し、当該第３のデータ列に対して可逆伸張を行った第２の復元データ列を前記第２のバッファへ出力し、
前記後処理部は、前記第２のバッファに格納された前記第２の復元データ列と、前記第１のバッファに格納された前記第１の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の後処理データ列として出力する
ことを特徴とするデータ可逆伸張装置。
【０１３０】
（付記１７）  前記後処理部は、前記後処理部の２以上後段に直列に接続されたバッファを前記第２のバッファとして、前記排他的論理和を算出することを特徴とする付記１６に記載のデータ可逆伸張装置。
【０１３１】
（付記１８）  前記所定の可逆圧縮が付記３に記載のデータ可逆圧縮装置による可逆圧縮であり、前記第３のデータ列に前記位置情報が含まれる場合に、
前記可逆伸張部は、前記可逆伸張を行った際に、前記第３のデータ列に含まれる前記位置情報を前記後処理部へ出力し、
前記データ可逆伸張装置は、前記後処理部の後段に直列に接続される複数の後段バッファを備え、
前記後処理部は、
前記可逆伸張部から出力された前記位置情報に基づき、前記複数の後段バッファのうち１つを前記第１のバッファとして選択し、
前記選択した第１のバッファと前記第２のバッファとに格納された各データ列についての前記排他的論理和の結果を前記第１の後処理データ列として出力する
を特徴とする付記１６に記載のデータ可逆伸張装置。
【０１３２】
（付記１９）  前記後処理部は、前記所定の可逆圧縮が付記４に記載のデータ可逆圧縮装置による可逆圧縮である場合に、前記第１の後処理データ列と、前記第２の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第３の後処理データ列として出力する
ことを特徴とする付記１６乃至１８のいずれか１項に記載のデータ可逆伸張装置。
【０１３３】
（付記２０）  Ｎビット（Ｎは２以上の整数）の領域を有する第１のバッファに対して、Ｎビットの第１のデータ列をビット単位に格納し、
前記第１のデータ列の後続のデータ列に対して所定の可逆圧縮が行われた第２のデータ列を入力し、
前記第２のデータ列に対して可逆伸張を行った第１の復元データ列を出力し、
前記第１のバッファの各領域に対応付けられたＮビットの領域を有する第２のバッファに対して、前記第１の復元データ列をビット単位に格納し、
前記第２のバッファに格納された前記第１の復元データ列と、前記第１のバッファに格納された前記第１のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の後処理データ列として出力し、
前記第１のバッファに対して、前記出力された第１の後処理データ列を格納し、
前記第２のデータ列の後続のデータ列に対して前記所定の可逆圧縮が行われた第３のデータ列を入力し、
前記第３のデータ列に対して可逆伸張を行った第２の復元データ列を前記第２のバッファへ出力し、
前記第２のバッファに格納された前記第２の復元データ列と、前記第１のバッファに格納された前記第１の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の後処理データ列として出力する
データ可逆伸張方法。
【０１３４】
（付記２１）  前記第１のデータ列は、前記第１の復元データ列の２以上前に可逆伸張されたデータ列であることを特徴とする付記２０に記載のデータ可逆伸張方法。
【０１３５】
（付記２２）  前記排他的論理和の結果を格納する複数の後段バッファを備え、
前記所定の可逆圧縮が付記８に記載のデータ可逆圧縮方法による可逆圧縮であり、前記第３のデータ列に前記位置情報が含まれる場合に、
前記可逆伸張を行った際に、前記第３のデータ列に含まれる前記位置情報を出力し、
前記出力された前記位置情報に基づき、前記複数の後段バッファのうち１つを前記第１のバッファとして選択し、
前記選択した第１のバッファと前記第２のバッファとに格納された各データ列についての前記排他的論理和の結果を前記第１の後処理データ列として出力する
ことを特徴とする付記２０に記載のデータ可逆伸張方法。
【０１３６】
（付記２３）  前記所定の可逆圧縮が付記９に記載のデータ可逆圧縮方法による可逆圧縮である場合に、前記第１の後処理データ列と、前記第２の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第３の後処理データ列として出力する
ことを特徴とする付記２０乃至２２のいずれか１項に記載のデータ可逆伸張方法。
【０１３７】
（付記２４）  Ｎビット（Ｎは２以上の整数）の領域を有する第１の記憶部に対して、Ｎビットの第１のデータ列をビット単位に格納し、
前記第１のデータ列の後続のデータ列に対して所定の可逆圧縮が行われた第２のデータ列を入力し、
前記第２のデータ列に対して可逆伸張を行った第１の復元データ列を生成し、
前記第１の記憶部の各領域に対応付けられたＮビットの領域を有する第２の記憶部に対して、前記第１の復元データ列をビット単位に格納し、
前記第２の記憶部に格納された前記第１の復元データ列と、前記第１の記憶部に格納された前記第１のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の後処理データ列として出力し、
前記第１の記憶部に対して、前記出力された第１の後処理データ列を格納し、
前記第２のデータ列の後続のデータ列に対して前記所定の可逆圧縮が行われた第３のデータ列を入力し、
前記第３のデータ列に対して可逆伸張を行った第２の復元データ列を前記第２の記憶部へ出力し、
前記第２の記憶部に格納された前記第２の復元データ列と、前記第１の記憶部に格納された前記第１の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の後処理データ列として出力する
処理をコンピュータに実行させるデータ可逆伸張プログラム。
【０１３８】
（付記２５）  前記第１のデータ列は、前記第１の復元データ列の２以上前に可逆伸張されたデータ列であることを特徴とする付記２４に記載のデータ可逆伸張プログラム。
【０１３９】
（付記２６）  前記排他的論理和の結果を格納する複数の後段記憶部を備え、
前記所定の可逆圧縮が付記１３に記載のデータ可逆圧縮プログラムによる可逆圧縮であり、前記第３のデータ列に前記位置情報が含まれる場合に、
前記可逆伸張を行った際に、前記第３のデータ列に含まれる前記位置情報を取得し、
前記取得された前記位置情報に基づき、前記複数の後段記憶部のうち１つを前記第１の記憶部として選択し、
前記選択した第１の記憶部と前記第２の記憶部とに格納された各データ列についての前記排他的論理和の結果を前記第１の後処理データ列として出力する
ことを特徴とする付記２４に記載のデータ可逆伸張プログラム。
【０１４０】
（付記２７）  前記所定の可逆圧縮が付記１４に記載のデータ可逆圧縮プログラムによる可逆圧縮である場合に、前記第１の後処理データ列と、前記第２の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第３の後処理データ列として出力する
ことを特徴とする付記２４乃至２６のいずれか１項に記載のデータ可逆伸張プログラム。
【０１４１】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記によって限定されるものではない。本願発明の構成や詳細には、発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１４２】
この出願は、２０１１年１月１３日に出願された日本出願特願２０１１−００４６７７を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１４３】
１００  データ可逆圧縮装置
１０  バッファ
１０１  ＦＦ
１０２  ＦＦ
１０ｎ  ＦＦ
２１  バッファ
２１１  ＦＦ
２１２  ＦＦ
２１ｎ  ＦＦ
２ｍ  バッファ
２ｍ１  ＦＦ
２ｍ２  ＦＦ
２ｍｎ  ＦＦ
３０  前処理部
３０１  １ビット排他的論理和
３０２  １ビット排他的論理和
３０ｎ  １ビット排他的論理和
４０  可逆圧縮部
２００  データ可逆伸張装置
５０  可逆伸張部
６０  バッファ
６０１  ＦＦ
６０２  ＦＦ
６０ｎ  ＦＦ
７１  バッファ
７１１  ＦＦ
７１２  ＦＦ
７１ｎ  ＦＦ
７２  バッファ
７ｍ  バッファ
７ｍ１  ＦＦ
７ｍ２  ＦＦ
７ｍｎ  ＦＦ
８０  後処理部
８０１  １ビット排他的論理和
８０２  １ビット排他的論理和
８０ｎ  １ビット排他的論理和
１００ａ  データ可逆圧縮装置
１０  バッファ
２１  バッファ
２２  バッファ
２ｍ  バッファ
３０ａ  前処理部
３１  Ｎビット排他的論理和
３２  Ｎビット排他的論理和
３ｍ  Ｎビット排他的論理和
３０ａ１  セレクタ
３０ａ２  パターンマッチング部
４０ａ  可逆圧縮部
２００ａ  データ可逆伸張装置
５０ａ  可逆伸張部
６０  バッファ
８０ａ  後処理部
８１  Ｎビット排他的論理和
８２  Ｎビット排他的論理和
８ｍ  Ｎビット排他的論理和
８０ａ１  セレクタ
１００ｂ  データ可逆圧縮装置
１１０  バッファ
１１１  バッファ
１１ｉ  バッファ
３０ｂ  前処理部
１２０  バッファ
１２１  バッファ
１２ｊ  バッファ
３０ｃ  前処理部
２００ｂ  データ可逆伸張装置
６１１  バッファ
８０ｂ  後処理部
６２１  バッファ
６２ｊ  バッファ
８０ｃ  後処理部
６３１  バッファ
６３ｉ  バッファ
Ｄ１  Ｎビットデータ列
Ｄ２  可逆圧縮済みＮビットデータ列
Ｄ２ａ  可逆圧縮済みＮビットデータ列
Ｄ２ｂ  可逆圧縮済みＮビットデータ列
【図１】
2012095909.tif 000003
【図２】
2012095909.tif 000004
【図３】
2012095909.tif 000005
【図４】
2012095909.tif 000006
【図５】
2012095909.tif 000007
【図６】
2012095909.tif 000008
【図７】
2012095909.tif 000009
【図８】
2012095909.tif 000010
【図９】
2012095909.tif 000011
【図１０】
2012095909.tif 000012
【図１１】
2012095909.tif 000013
【図１２】
2012095909.tif 000014
【手続補正書】
【提出日】平成25年6月28日(2013.6.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項７
【補正方法】変更
【補正の内容】
【請求項７】
Ｎビット（Ｎは２以上の整数）の領域を有する第１の記憶部に対して、入力されるＮビットの第１のデータ列をビット単位に格納し、
前記第１の記憶部の各領域に対応付けられたＮビットの領域を有する第２の記憶部に対して、前記第１の記憶部へ前記第１のデータ列が格納された際に、当該第１のデータ列以前に入力された第２のデータ列について、当該第１のデータ列の各ビットに対応する領域へ格納し、
前記第１の記憶部に格納された前記第１のデータ列と、前記第２の記憶部に格納された前記第２のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の前処理データ列として生成し、
前記生成された第１の前処理データ列に対して可逆圧縮を行う
処理をコンピュータに実行させるデータ可逆圧縮プログラム。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１０
【補正方法】変更
【補正の内容】
【請求項１０】
Ｎビット（Ｎは２以上の整数）の領域を有する第１の記憶部に対して、Ｎビットの第１のデータ列をビット単位に格納し、
前記第１のデータ列の後続のデータ列に対して所定の可逆圧縮が行われた第２のデータ列を入力し、
前記第２のデータ列に対して可逆伸張を行った第１の復元データ列を生成し、
前記第１の記憶部の各領域に対応付けられたＮビットの領域を有する第２の記憶部に対して、前記第１の復元データ列をビット単位に格納し、
前記第２の記憶部に格納された前記第１の復元データ列と、前記第１の記憶部に格納された前記第１のデータ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第１の後処理データ列として出力し、
前記第１の記憶部に対して、前記出力された第１の後処理データ列を格納し、
前記第２のデータ列の後続のデータ列に対して前記所定の可逆圧縮が行われた第３のデータ列を入力し、
前記第３のデータ列に対して可逆伸張を行った第２の復元データ列を前記第２の記憶部へ出力し、
前記第２の記憶部に格納された前記第２の復元データ列と、前記第１の記憶部に格納された前記第１の後処理データ列とについて、対応するビットごとに排他的論理和を算出し、当該算出したＮ個の排他的論理和の値をＮビットの第２の後処理データ列として出力する
処理をコンピュータに実行させるデータ可逆伸張プログラム。
【国際調査報告】
2012095909.tif 000015
2012095909.tif 000016