データ圧縮装置及びデータ復元装置及びデータ処理システム及びコンピュータプログラム及びデータ圧縮方法及びデータ復元方法
【課題】一連の値を効率よく圧縮する。
【解決手段】予測器１０（予測部）は、入力データの先行する値から後続する符号化対象値の予測値を決定する。オフセット量決定部２０（予測残差算出部・予測残差分類部・基準値算出部）は、予測値の予測誤差の分布に基づいて、予測誤差からの距離が最小となるような予測誤差代表値の集合を決定する。基準値生成部３０は、予測値と予測誤差代表値の集合を元に、複数の残差基準値を決定する。最小残差選択部４０（基準値選択部・符号化部）は、複数の残差基準値の中から、符号化対象値に最も近いものを選択して、該誤差基準値と符号化対象値の差を残差（基準残差）として出力するとともに、選択した残差基準値のインデックス（選択基準値符号）を圧縮データに出力する。残差符号化部５０（符号化部）は、残差を符号語（基準残差符号）に変換して圧縮データに出力する。
【解決手段】予測器１０（予測部）は、入力データの先行する値から後続する符号化対象値の予測値を決定する。オフセット量決定部２０（予測残差算出部・予測残差分類部・基準値算出部）は、予測値の予測誤差の分布に基づいて、予測誤差からの距離が最小となるような予測誤差代表値の集合を決定する。基準値生成部３０は、予測値と予測誤差代表値の集合を元に、複数の残差基準値を決定する。最小残差選択部４０（基準値選択部・符号化部）は、複数の残差基準値の中から、符号化対象値に最も近いものを選択して、該誤差基準値と符号化対象値の差を残差（基準残差）として出力するとともに、選択した残差基準値のインデックス（選択基準値符号）を圧縮データに出力する。残差符号化部５０（符号化部）は、残差を符号語（基準残差符号）に変換して圧縮データに出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データを圧縮するデータ圧縮装置に関する。
【背景技術】
【０００２】
近年、センサの小型化や低価格化が進み、散在する装置群や大規模システムに大量のセンサを設置してその状態を連続的に取得・蓄積し、分析や監視に利用したいというニーズが高まっている。多数のセンサから連続的に到来するストリームデータは、そのまま蓄積すると膨大な量になってしまうため、圧縮率の良い圧縮方式が不可欠となる。
高変動な時系列データでは、線形予測を適用しても予測精度に限界があるため、高い圧縮率が得にくい。特許文献１には、複数の線形予測器を使って先行する値から符号化対象値に対する予測値を複数生成し、符号化対象値に最も近いものを選択して、その予測残差を符号化する方式が記載されている。その際、その予測値（予測器）を伸張時に識別するためのインデックスも合わせて符号化する。このように複数の予測値を用意することにより、予測値を１点だけ用いるよりも広範な領域をカバーすることが出来る。このため、インデックス符号を補助情報として保存する必要は生じるものの、予測残差は小さくなると期待出来る。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１１−１０９９９６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
独立の線形予測器が推定した複数の予測値を単純に集めただけでは、ｎ値の集合として誤差の期待値を最小化できない。このため、得られる予測値の集合は冗長なものであり、典型的には予測値が必要以上に集中してしまい、複数点をおいて広範な領域をカバーする効果が得られない。カバーされる領域を広げるため予測点の数を増やすと、予測点を指定するインデックス符号が長くなり、圧縮率が低下する。
この発明は、例えば上記のような課題を解決するためになされたものであり、センサデータ等の数値データ、特に値の変動が激しく予測が困難な時系列データを対象として、圧縮率の高い可逆圧縮方式を得ることを目的とする。
【課題を解決するための手段】
【０００５】
この発明にかかるデータ圧縮装置は、データを処理する処理装置と、予測部と、予測残差算出部と、基準値算出部と、基準値選択部と、基準残差算出部と、符号化部とを有し、
上記予測部は、上記処理装置を用いて、一連の値のうち少なくともいずれかの値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出し、
上記予測残差算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記値と上記予測部が算出した予測値との差を算出することにより、予測残差を算出し、
上記基準値算出部は、上記処理装置を用いて、上記予測残差算出部が算出した予測残差に基づいて、複数の残差基準値を算出し、
上記基準値選択部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記基準値算出部が算出した複数の残差基準値のなかから、上記予測残差算出部が算出した予測残差に最も近い残差基準値を選択し、
上記基準残差算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記予測残差算出部が算出した予測残差と上記基準値選択部が選択した残差基準値との差を算出することにより、基準残差を算出し、
上記符号化部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記値を表わす符号として、上記基準値選択部が上記複数の残差基準値のうちどの残差基準値を選択したかを表わす選択基準値符号と、上記基準残差算出部が算出した基準残差を表わす基準残差符号との組を生成することを特徴とする。
【発明の効果】
【０００６】
この発明にかかるデータ圧縮装置によれば、一連の値を効率よく圧縮することができる。
【図面の簡単な説明】
【０００７】
【図１】実施の形態１におけるデータ圧縮記憶システム８００の全体構成の一例を示すシステム構成図。
【図２】実施の形態１におけるデータ圧縮装置１００やデータ復元装置２００の外観の一例を示す斜視図。
【図３】実施の形態１におけるデータ圧縮装置１００やデータ復元装置２００のハードウェア資源の一例を示す図。
【図４】実施の形態１におけるデータ圧縮装置１００の機能ブロックの構成の一例を示すブロック構成図。
【図５】実施の形態１におけるデータ圧縮装置１００の予測動作及び残差生成動作を説明するための図。
【図６】実施の形態１におけるデータ圧縮処理の流れの一例を示すフローチャート図。
【図７】実際の時系列データと、第一比較例において符号化される残差との関係を表わすグラフ図。
【図８】実際の時系列データと、第二比較例において符号化される残差との関係を表わすグラフ図。
【図９】実際の時系列データと、実施の形態１におけるデータ圧縮装置１００において符号化される残差との関係を表わすグラフ図。
【図１０】実施の形態１におけるデータ復元装置２００の機能ブロックの構成の一例を示すブロック構成図。
【図１１】実施の形態１におけるデータ伸長処理の流れの一例を示すフローチャート図。
【図１２】実施の形態２におけるデータ圧縮装置１００の機能ブロックの構成の一例を示すブロック構成図。
【図１３】実施の形態２におけるデータ圧縮処理の流れの一例を示すフローチャート図。
【図１４】実施の形態２におけるデータ復元装置２００の機能ブロックの構成の一例を示すブロック構成図。
【図１５】実施の形態２におけるデータ伸長処理の流れの一例を示すフローチャート図。
【図１６】実施の形態３におけるオフセット量決定部２０が算出する予測誤差代表値の一例を示す図。
【図１７】実施の形態４におけるデータ圧縮装置１００の機能ブロックの一例を示すブロック構成図。
【図１８】実施の形態４におけるデータ復元装置２００の機能ブロックの構成の一例を示すブロック構成図。
【図１９】実施の形態４におけるデータ圧縮処理Ｓ６１０の流れの一例を示すフローチャート図。
【図２０】実施の形態４におけるデータ復元処理Ｓ６２０の流れの一例を示すフローチャート図。
【発明を実施するための形態】
【０００８】
実施の形態１．
実施の形態１について、図１〜図１１を用いて説明する。
【０００９】
図１は、この実施の形態におけるデータ圧縮記憶システム８００の全体構成の一例を示すシステム構成図である。
データ圧縮記憶システム８００（データ圧縮システム）は、観測したデータを圧縮して記憶しておき、必要に応じて復元して取り出すことができるシステムである。データ圧縮記憶システム８００は、例えば、観測装置８１０と、データ圧縮装置１００と、データ記憶装置８２０と、データ復元装置２００とを有する。
観測装置８１０は、何らかの観測対象を観測して、観測した結果を表わす観測データを生成する。観測装置８１０は、観測対象を定期的もしくは不定期に繰り返し観測し、その都度、観測データを生成する。したがって、観測装置８１０は、時系列的な順序がある一連の観測データを生成する。
観測装置８１０が生成する観測データは、数値データであり、例えば０以上２のｎ乗未満の整数値をｎビットの２進数で表わす。ここで、ｎは、２以上の整数であり、例えば、１６や３２である。
あるいは、観測データは、例えば０以上１未満の２のｎ乗分の１の倍数をｎビットの固定小数点数形式の２進数で表わすものであってもよい。この場合、観測データは、観測した実際の数値を２のｎ乗倍した整数を表わすものとして取り扱うことができるから、０以上２のｎ乗未満の整数値をｎビットの２進数で表わす場合と同様に扱うことができる。
または、観測データは、例えば所定の範囲内の実数値を、ＩＥＥＥ（電気電子学会）７５４形式のような浮動小数点数形式で表わすものであってもよい。浮動小数点数形式は、例えば、符号部・仮数部・指数部からなり、それぞれの部分は、整数値として取り扱うことができるから、この場合、観測データは、３つの整数値の組（あるいは、符号部を仮数部の一部として扱って、２つの整数値の組）として扱うことができる。
更に、観測データは、例えば複素数やベクトルなどのように、複数の整数値や実数値の組を表わすものであってもよい。
【００１０】
データ圧縮装置１００は、観測装置８１０が生成した一連の観測データを圧縮して、圧縮データを生成する。例えば、１つの観測データがｎビットであり、それがｋ個ある場合、一連の観測データ全体のビット数は、ｋ×ｎビットである。データ圧縮装置１００は、これを圧縮して、ｋ×ｎビットよりも少ないビット数で同じ情報を表わす圧縮データを生成する。すなわち、データ圧縮装置１００が一連の観測データを圧縮する圧縮方式は、可逆圧縮であり、データ圧縮装置１００が圧縮した圧縮データから、元の一連の観測データと全く同じデータを復元することができる。
【００１１】
データ記憶装置８２０は、データ圧縮装置１００が生成した圧縮データを蓄積して記憶する。データ記憶装置８２０は、例えば交換可能な記録媒体を用いて、圧縮データを記憶する。データ記憶装置８２０は、観測装置８１０が生成した一連の観測データよりもビット数が少ない圧縮データを記憶するので、観測装置８１０が生成した一連の観測データをそのまま記憶する場合と比べて、記録媒体の記憶容量が小さくて済む。
【００１２】
データ復元装置２００は、データ記憶装置８２０が記憶した圧縮データを伸長して、元の観測データと同じデータを復元する。データ復元装置２００は、復元したデータを出力する。データ記憶装置８２０が記憶した圧縮データは、可逆圧縮方式によって圧縮されているので、元の観測データを完全な形で復元することができる。
【００１３】
図２は、この実施の形態におけるデータ圧縮装置１００やデータ復元装置２００の外観の一例を示す斜視図である。
データ圧縮装置１００及びデータ復元装置２００は、それぞれ、システムユニット９１０、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）やＬＣＤ（液晶）の表示画面を有する表示装置９０１、キーボード９０２（Ｋｅｙ・Ｂｏａｒｄ：Ｋ／Ｂ）、マウス９０３、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、コンパクトディスク装置９０５（ＣＤＤ）、プリンタ装置９０６、スキャナ装置９０７などのハードウェア資源を備え、これらはケーブルや信号線で接続されている。
システムユニット９１０は、コンピュータであり、ファクシミリ機９３２、電話器９３１とケーブルで接続され、また、ローカルエリアネットワーク９４２（ＬＡＮ）、ゲートウェイ９４１を介してインターネット９４０に接続されている。
【００１４】
図３は、この実施の形態におけるデータ圧縮装置１００やデータ復元装置２００のハードウェア資源の一例を示す図である。
データ圧縮装置１００及びデータ復元装置２００は、それぞれ、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、通信装置９１５、表示装置９０１、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５、プリンタ装置９０６、スキャナ装置９０７、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部の一例である。通信装置９１５、キーボード９０２、スキャナ装置９０７、ＦＤＤ９０４などは、入力部、入力装置の一例である。
また、通信装置９１５、表示装置９０１、プリンタ装置９０６などは、出力部、出力装置の一例である。
【００１５】
通信装置９１５は、ファクシミリ機９３２、電話器９３１、ＬＡＮ９４２等に接続されている。通信装置９１５は、ＬＡＮ９４２に限らず、インターネット９４０、ＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）などに接続されていても構わない。インターネット９４０或いはＩＳＤＮ等のＷＡＮに接続されている場合、ゲートウェイ９４１は不用となる。
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。
【００１６】
上記プログラム群９２３には、以下に述べる実施の形態の説明において「〜部」として説明する機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
ファイル群９２４には、以下に述べる実施の形態の説明において、「〜の判定結果」、「〜の計算結果」、「〜の処理結果」として説明する情報やデータや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵの動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
また、以下に述べる実施の形態の説明において説明するフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、ＦＤＤ９０４のフレキシブルディスク、ＣＤＤ９０５のコンパクトディスク、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｋ）等の記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【００１７】
また、以下に述べる実施の形態の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、以下に述べる「〜部」としてコンピュータを機能させるものである。あるいは、以下に述べる「〜部」の手順や方法をコンピュータに実行させるものである。
【００１８】
なお、データ圧縮装置１００とデータ復元装置２００とは、物理的に異なる装置であってもよいし、物理的に一つの装置であってもよい。また、以下に説明するデータ圧縮装置１００やデータ復元装置２００の各ブロックを、物理的に異なる装置によって実現し、複数の装置が全体としてデータ圧縮装置１００やデータ復元装置２００として機能する構成であってもよい。
【００１９】
図４は、この実施の形態におけるデータ圧縮装置１００の機能ブロックの構成の一例を示すブロック構成図である。
データ圧縮装置１００は、観測装置８１０が生成した一連の観測データを、入力データとして入力する。データ圧縮装置１００は、圧縮データとして、ヘッダデータと、残差符号列データと、基準値インデックスデータとを生成する。
データ圧縮装置１００は、予測器１０と、オフセット量決定部２０と、基準値生成部３０と、最小残差選択部４０と、残差符号化部５０と、パラメータ記憶部７０と、ヘッダ生成部８０とを有する。
【００２０】
予測器１０（予測部）は、入力データの先行する値から後続する符号化対象値の予測値を決定する。
オフセット量決定部２０（予測残差算出部・予測残差分類部・基準値算出部）は、予測値の予測誤差の分布に基づいて、予測誤差からの距離が最小となるような予測誤差代表値の集合を決定する。
基準値生成部３０は、予測値と予測誤差代表値の集合を元に、複数の残差基準値を決定する。
最小残差選択部４０（基準値選択部・符号化部）は、複数の残差基準値の中から、符号化対象値に最も近いものを選択して、該誤差基準値と符号化対象値の差を残差（基準残差）として出力するとともに、選択した残差基準値のインデックス（選択基準値符号）を圧縮データに出力する。
残差符号化部５０（符号化部）は、残差を符号語（基準残差符号）に変換して圧縮データに出力する。
パラメータ記憶部７０は、オフセット量決定部２０や基準値生成部３０が用いるパラメータをあらかじめ記憶している。
ヘッダ生成部８０（符号化部）は、パラメータ記憶部７０が記憶したパラメータなどに基づいて、ヘッダデータを生成する。
【００２１】
図５は、この実施の形態におけるデータ圧縮装置１００の予測動作及び残差生成動作を説明するための図である。
データ圧縮装置１００の特徴は、予測符号化における予測方式（残差生成方式）にある。
【００２２】
まず、データ圧縮装置１００における予測処理の概要を説明する。
【００２３】
黒丸（●）の点は、入力データの時系列を示している。予測処理は、時系列に沿って行う。この図は、入力データの先頭の値ｘ１から時刻ｔ−１の値ｘｔ−１までの符号化が完了しており、これから時刻ｔの値ｘｔを符号化しようとしている状態を示している。
バツ印（×）で示す点は、予測器１０による予測点である。この例において、予測器１０は、直前の値ｘｔ−１をそのまま次の時刻の予測値ｐｔとして用いる。ただし、予測器１０は、これに限定するものではなく、他の線形予測器であってもよいし、非線形予測器であってもよい。例えば、予測器１０は、次の時刻の予測値ｐｔとして、直前のｍ個の値ｘｔ−ｍ，…，ｘｔ−１の平均値を算出する構成であってもよい。あるいは、予測器１０は、次の時刻の予測値ｐｔとして、直前の２つの値ｘｔ−２，ｘｔ−１の差を直前の値ｘｔ−１に加えた値を算出する構成であってもよい。または、予測器１０は、直前のｋ個の値ｘｔ−ｋ，…，ｘｔ−１を通る［ｋ−１］次曲線を算出し、次の時刻の予測値ｐｔとして、算出した［ｋ−１］次曲線上の点の座標を算出する構成であってもよい。あるいは、予測器１０は、直前のｍ個の値ｘｔ−ｍ，…，ｘｔ−１を近似する［ｋ−１］次曲線を最小自乗法などにより算出し（ただし、ｍ＞ｋ）、次の時刻の予測値ｐｔとして、算出した［ｋ−１］次曲線上の点の座標を算出する構成であってもよい。また、観測対象の物理モデルがわかっている場合には、予測器１０は、例えばカルマンフィルタなどの予測フィルタを用いて、次の時刻の予測値ｐｔを算出する構成であってもよい。
【００２４】
図中「履歴」で囲った部分における上下の矢印は、時刻ｔ−Ｎ，…，ｔ−１における予測誤差ｅｔ−Ｎ，…，ｅｔ−１を表している。この予測誤差の履歴を図に示すように集めることで、現在符号化対象としている予測値ｐｔに対してどの程度の予測誤差ｅｔが発生するか（予測誤差の分布）を予測することができる。
【００２５】
オフセット量決定部２０は、予測誤差の分布に対し、ｋ−ｍｅａｎｓ法（ケー平均法）によるクラスタリングを適用することにより、分布を代表するｎ個の代表値（セントロイド）｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝を得ることができる。これらの代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝は、ｋ−ｍｅａｎｓ法のアルゴリズムから、各予測誤差から最近傍点への距離を最小にするようなｎ個の値のセットになっている。白抜き正方形（□）は、代表値の例を示す。この例において、代表値の数ｎは、４である。代表値の数ｎは、他の数であってもよいが、２の累乗（２，４，８，１６，…）であれば、符号化の効率が良いので望ましい。
なお、各クラスタの代表値は、各クラスタに属する予測誤差の平均値のほか、例えば、各クラスタに属する予測誤差の中央値、最頻値などであってもよい。
また、クラスタリングの方式は、ｋ−ｍｅａｎｓ法が望ましいが、他の非階層型クラスタリングであってもよいし、ウォード法など階層型クラスタリングであってもよい。なお、分割するクラスタ数をあらかじめ定めておくのではなく、予測誤差の分布に基づいて、クラスタ数を決定する方式であってもよい。
【００２６】
基準値生成部３０は、これら予測誤差の代表値をオフセットとして、時刻ｔの予測値ｐｔに加えることにより、ｎ個の残差基準値を生成する。最小残差選択部４０は、残差基準値の中から、符号化対象とする実測値ｘｔに最も近いものを選ぶ。残差符号化部５０は、選択した残差基準値と実測値との差分を残差として符号化し、圧縮データに保存する。また、残差基準値のインデックスも同時に圧縮データに保存する。図では、上から２番目の残差基準値ｅ￣２が最も実測値に近い。この残差基準値を用いた残差は、予測値そのものによる残差よりも小さくなっている。
【００２７】
このようにして、予測誤差履歴の代表値ｎ点に基づいて残差基準値として置くことにより、残差に対する期待値を小さくすることが出来る。
【００２８】
図６は、この実施の形態におけるデータ圧縮処理の流れの一例を示すフローチャート図である。
【００２９】
ステップＳ０１において、ヘッダ生成部８０は、入力データに基づいて、データサイズ（入力データの時系列の長さ）Ｔを算出する。ヘッダ生成部８０は、算出したデータサイズＴや、履歴の個数Ｎや代表値の数（残差基準値の数）ｎなどパラメータ記憶部７０が記憶したパラメータに基づいて、ヘッダデータを生成する。ヘッダ生成部８０が生成するヘッダデータは、データサイズＴや履歴の個数Ｎや代表値の数ｎなどのパラメータを表わす。ヘッダ生成部８０は、生成したヘッダデータを圧縮データの先頭に保存する。これらは、例えば固定長バイナリ形式で保存する。
ステップＳ１０において、データ圧縮装置１００は、すべての入力データ｛ｘｔ｜ｔ＝１，…，Ｔ｝に対し、処理が完了したかを判定する。処理が完了した場合、データ圧縮装置１００は、データ圧縮処理を終了する。処理が完了していない場合、データ圧縮装置１００は、Ｓ２０へ進む。
ステップＳ２０において、オフセット量決定部２０は、次の時刻の予測値ｐｔに対応するｎ個の予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝を決定する。この代表値は、時刻ｔ−Ｎ，…，ｔ−１におけるＮ個（Ｎ＞ｎ）の予測誤差の履歴｛ｅｔ−Ｎ，…，ｅｔ−１｝を対象にｋ−ｍｅａｎｓ法を適用して、ｎ個のクラスタに分類したときのクラスタ重心として得ることができる。ｋ−ｍｅａｎｓ法では、予測誤差の履歴に対し次の式で表わされる関数ｆの値を準最小化する代表値を得ることができる。
【数１１】
なお、予測誤差ｅｔは、実測値ｘｔと予測値ｐｔとの差として、次の式により与えられる。
【００３０】
ｅｔ＝ｘｔ−ｐｔ
【００３１】
ステップＳ３０において、予測器１０は、入力データの先行する値から後続する符号化対象値ｘｔの予測値ｐｔを決定する。ここでは、最も単純な予測の例として、次の式のように、時刻ｔ−１の値ｘｔ−１を時刻ｔの値の予測値ｐｔとして用いる。
【００３２】
ｐｔ＝ｘｔ−１
【００３３】
ステップＳ４０において、基準値生成部３０は、上記予測値ｐｔと上記予測誤差代表値の集合｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝とを元に、複数の残差基準値を決定する。予測値をｐｔ、ｎ個の予測誤差代表値を｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝とすると、基準値生成部３０は、残差基準値｛ｘ￣ｔ，ｉ｜ｉ＝１，…，ｎ｝を、両者の和として次の式により求める。
【数１２】
【００３４】
ステップＳ５０において、最小残差選択部４０は、残差基準値｛ｘ￣ｔ，ｉ｜ｉ＝１，…，ｎ｝の中から、符号化対象値ｘｔに最も近いものを選択して、選択した残差基準値ｘ￣ｔ，ｉ＊と符号化対象値ｘｔとの差を残差ｒｔとして出力するとともに、選択した残差基準値のインデックスｉ＊を圧縮データに出力する。
【数１３】
なお、インデックスｉ＊は、次の式で表わされる、基準値の種類数ｎを表現可能な最小のビット数ｂで、固定長バイナリ形式により出力する。
【数１４】
なお、代表値の数ｎが２の累乗でない場合、インデックスｉ＊を表わす符号のビット数を少しでも短くするため、例えばＣＢＴ（完全二分木）符号を用いてインデックスｉ＊を符号化する構成としてもよい。
【００３５】
ステップＳ６０において、残差符号化部５０は、前記残差ｒｔを符号語に変換して圧縮データに出力する。
符号化対象値が整数値である場合、残差符号化部５０は、例えば、残差ｒｔの正負符号１ビットと、｜ｒｔ｜の値をガンマ符号やデルタ符号や指数ゴロム符号により符号化した符号とを出力する。例えば、ｒｔ≧０の場合、残差符号化部５０は、１ビットの正負符号「０」と、ｒｔ＋１をデルタ符号で符号化した符号とを出力する。ｒｔ＜０の場合、残差符号化部５０は、１ビットの正負符号「１」と、｜ｒｔ｜をデルタ符号で符号化した符号とを出力する。
あるいは、残差符号化部５０は、ライス符号やゴロム符号など、符号化する値が小さいほど符号長が短くなる性質を有する他の符号化方式を用いる構成であってもよい。ライス符号（ゴロム−ライス符号）における次数ｋやゴロム符号における法ｍなどのパラメータは、あらかじめ定めた値を用いる構成であってもよいし、生成する符号のビット長が最も短くなるよう、残差符号化部５０が決定する構成であってもよい。例えば、残差符号化部５０は、マルチパス構成として、第一パスで全ての残差｛ｐｔ｜ｔ＝１，…，Ｎ｝を得る。第二パスにおいて、残差符号化部５０は、次数ｋを０から元のバイナリビット数まで変化させ、それぞれの次数ｋによる符号化を試行する。残差符号化部５０は、符号化の結果、最も符号長が短くなる次数ｋを選択し、符号化に用いるパラメータに決定する。残差符号化部５０は、決定したパラメータを表わす符号を、圧縮データの一部として出力する。
【００３６】
符号化対象値が浮動小数点数形式によって表わされる実数値である場合、残差符号化部５０は、例えば、上述した残差ｒｔの代わりに、指数部・仮数部について残差を求め、それぞれを整数とみなして上記符号化を行う。
【００３７】
次に、実際の時系列データに適用した例を用いて、この実施の形態におけるデータ圧縮装置１００の効果を説明する。
【００３８】
図７は、実際の時系列データと、第一比較例において符号化される残差との関係を表わすグラフ図である。
横軸は、時刻を表わす。縦軸は、時系列データの値を表わす。折れ線は、各時刻における符号化対象値を結んだ線である。バツ印（×）は、第一比較例における予測器が予測した予測値を示す。矢印は、符号化される残差を示す。
【００３９】
第一比較例における予測器は、この実施の形態における予測器１０と同様、時刻ｔにおける符号化対象値の予測値ｐｔとして、直前の時刻ｔ−１における値ｘｔ−１を用いる。また、第一比較例における残差符号化部は、符号化対象値ｘｔと、予測器が予測した予測値ｐｔとの差（予測誤差）を、そのまま符号化する。
【００４０】
第一比較例では、符号化される残差が大きいので、圧縮効率が低い。線形予測の次数を増やし、データに対し係数を最適に決定するなどしたとしても、このような予測誤差は発生する。特に、変動が大きなデータの場合は、予測誤差が相対的に大きくなる。
【００４１】
図８は、実際の時系列データと、第二比較例において符号化される残差との関係を表わすグラフ図である。
横軸は、時刻を表わす。縦軸は、時系列データの値を表わす。折れ線は、各時刻における符号化対象値を結んだ線である。バツ印（×）は、第二比較例における複数の予測器がそれぞれ予測した予測値を示す。矢印は、符号化される残差を示す。
【００４２】
第二比較例には、予測器が４つある。第一の予測器は、時刻ｔにおける符号化対象値の予測値ｐｔとして、直前の時刻ｔ−１における値ｘｔ−１を用いる。第二の予測器は、時刻ｔにおける符号化対象値の予測値ｐｔとして、２つ前の時刻ｔ−２における値ｘｔ−２を用いる。第三の予測器は、時刻ｔにおける符号化対象値の予測値ｐｔとして、３つ前の時刻ｔ−３における値ｘｔ−３を用いる。第四の予測器は、時刻ｔにおける符号化対象値の予測値ｐｔとして、４つ前の時刻ｔ−４における値ｘｔ−４を用いる。
第二比較例における残差符号化部は、４つの予測器が算出した４つの予測値ｐｔのうち、符号化対象値ｘｔに一番近い予測値ｐｔと、符号化対象値ｘｔとの差を、符号化する。
【００４３】
予測値１点だけを使う第一比較例と比べると、残差が小さくなっていることがわかる。しかし、已然として、大きな残差が残っている。このように独立な予測値を複数持ってきても、典型的にはグラフの左側に見られるように必要以上に予測点が集中してしまい、予測値の変動領域を適切にカバーすることができない。
【００４４】
図９は、実際の時系列データと、この実施の形態におけるデータ圧縮装置１００において符号化される残差との関係を表わすグラフ図である。
横軸は、時刻を表わす。縦軸は、時系列データの値を表わす。折れ線は、各時刻における符号化対象値を結んだ線である。バツ印（×）は、第二比較例における複数の予測器がそれぞれ予測した予測値を示す。各時刻における符号化対象値から放射状に伸びる細線は、予測誤差の履歴を示す。白抜き正方形（□）は、基準値生成部３０が生成した残差基準値を示す。矢印は、残差符号化部５０が符号化する残差を示す。
【００４５】
データ圧縮装置１００は、第二比較例と同様、４つの値のなかから符号化対象値に最も近い値を選んで、符号化する残差を求める。しかし、第二比較例と異なり、その４つの値は、予測誤差の履歴から得られた代表値であるから、値の変動を適切にカバーできる。第二比較例よりも符号化対象値に近い予測点（残差基準値）が存在し、残差が小さくなるので、圧縮効率が高くなる。
【００４６】
図１０は、この実施の形態におけるデータ復元装置２００の機能ブロックの構成の一例を示すブロック構成図である。
データ復元装置２００は、データ圧縮装置１００が生成した残差符号列データと、基準値インデックスデータと、ヘッダデータとを、圧縮データとして入力する。データ復元装置２００は、入力した圧縮データを損失なく伸長して、データ圧縮装置１００が入力した入力データと同じ出力データを復元する。
データ復元装置２００は、予測器１５と、オフセット量決定部２５と、基準値生成部３５と、選択部４５と、残差復号部５５と、値復元部６５と、パラメータ記憶部７５と、ヘッダ取得部８５とを有する。
【００４７】
ヘッダ取得部８５は、圧縮データの先頭から、ヘッダデータを取得する。
パラメータ記憶部７５は、ヘッダ取得部８５が取得したヘッダデータが表わすデータサイズＴや履歴の個数Ｎや代表値の数ｎなどのパラメータを記憶する。
予測器１５（復元予測部）は、データ圧縮装置１００の予測器１０と同じ方式を用いて、値復元部６５が生成した出力データの先行する値から後続する復号対象値の予測値を決定する。
オフセット量決定部２５は、データ圧縮装置１００のオフセット量決定部２０と同じ方式を用いて、予測値の予測誤差の分布に基づいて、予測誤差からの距離が最小となるような予測誤差代表値の集合を決定する。
基準値生成部３５は、予測値と予測誤差代表値の集合を元に、複数の残差基準値を決定する。
選択部４５は、基準値インデックスデータのなかから、復号対象値についてのインデックスを取得する。選択部４５は、複数の残差基準値の中から、取得したインデックスにより示される残差基準値を選択する。
残差復号部５５は、残差符号列データのなかから、復号対象値についての符号語を取得する。残差復号部５５は、取得した符号語を復号して、残差を算出する。
値復元部６５は、選択部４５が選択した残差基準値と、残差復号部５５が算出した残差とを合計して、元の値を復元し、出力データに出力する。
【００４８】
図１１は、この実施の形態におけるデータ伸長処理の流れの一例を示すフローチャート図である。
【００４９】
ステップＳ０１ａにおいて、ヘッダ取得部８５は、圧縮データの先頭からヘッダデータを取得し、データサイズ（入力データの時系列の長さ）Ｔ、履歴の個数Ｎ、および代表値の数（残差基準値の数）ｎなどのパラメータを読み出す。これらは固定長バイナリ形式で保存されているため特段の伸張処理は不要である。パラメータ記憶部７５は、ヘッダ取得部８５が読み出したデータサイズＴ、履歴の個数Ｎ、代表値の数ｎなどのパラメータを記憶する。
【００５０】
ステップ１０ａにおいて、データ復元装置２００は、ループの終了判定処理をする。以降のステップの繰り返し回数がデータサイズＴより少ない場合、データ復元装置２００は、Ｓ２０へ進む。繰り返し回数がデータサイズＴに達した場合、データ復元装置２００は、データ伸長処理を終了する。
【００５１】
ステップＳ２０において、オフセット量決定部２５は、予測誤差のクラスタリング処理を行う。ステップＳ３０において、予測器１５は、伸張済みの値に基づく予測を行う。ステップＳ４０において、基準値生成部３５は、複数の残差基準値を決定する。これらの処理内容は、データ圧縮処理におけるステップＳ２０〜ステップＳ４０と同じなので、説明を省略する。
【００５２】
ステップＳ５０ａにおいて、選択部４５は、基準値インデックスデータ（圧縮データ）から、残差基準値のインデックスｉ＊を読み出す。残差復号部５５は、残差符号列データ（圧縮データ）から、符号化した残差ｒｔを読み出す。インデックスがｌｏｇ２ｎを超えない最小の整数をビット数とする固定長バイナリ形式で保存されている場合、特段の伸張処理は不要である。残差ｒｔは、例えば、前述のように正負符号１ビットと、絶対値を表わすデルタ符号とにより保存されている。デルタ符号は、可変長符号であるが、一意復号可能であり、瞬時復号可能であるから、データを先頭から読んで行くことで符号長を知ることができ、符号語を読み出すことができる。
【００５３】
ステップＳ６０ａにおいて、残差復号部５５は、残差ｒｔを復号する。
【００５４】
ステップＳ７０ａにおいて、値復元部６５は、上記得られた残差ｒｔを、上記インデックスで参照される残差基準値（値はステップＳ４０で得られる）に加えることにより、元の値ｘｔを得る。
【００５５】
以上のようにして、データ復元装置２００は、データ圧縮装置１００が圧縮したデータを損失なく伸張することができる。
【００５６】
以上のように、この実施の形態におけるデータ圧縮装置１００によれば、予測誤差の分布に基づいて残差の基準値を最小化するようなｎ値の集合を設定することができる。このため、インデックスビットの指定が必要なｎ値を用いる方式でありながら、ｎ値間の冗長性を抑え、効果的に予測点（残差基準点）を増やすことが可能であり、その結果として、優れた圧縮率を得ることができる。
【００５７】
なお、この実施の形態におけるデータ圧縮装置１００は、オンライン処理でクラスタリングを行い、予測値オフセットを決める。オフセット量決定部２０は、入力データに対する予測誤差の履歴より、予測誤差代表値の集合を逐次的に決定する。すなわち、符号化処理を１つずつ実行しながら逐次的に予測誤差履歴のクラスタリングを実行する。このように逐次更新される履歴を使うことにより、予測誤差履歴の局所的な分散を反映して残差基準点を置くことができる。このため、特に非定常な入力データに対し、優れた圧縮率を得ることができる。
【００５８】
また、この実施の形態におけるデータ圧縮装置１００は、予測誤差の代表値（オフセット）を得るためにｋ−ｍｅａｎｓクラスタリングを適用する。オフセット量決定部２０は、ｋ−ｍｅａｎｓ法によるクラスタリングを予測誤差の分布に適用して、予測誤差代表値の集合を決定する。これにより、予測誤差に対し分布を仮定せずに代表値を決定することができる。このため、本発明は離散値を取るようなセンサデータに対しても適用可能であり、汎用性の高い方式となっている。
【００５９】
実施の形態２．
実施の形態２について、図１２〜図１５を用いて説明する。
なお、実施の形態１と共通する部分については、同一の符号を付し、説明を省略する。
【００６０】
実施の形態１におけるデータ圧縮装置１００は、履歴に対し逐次的に予測誤差代表値の生成処理（クラスタリング）を実施・更新するのに対し、この実施の形態におけるデータ圧縮装置１００は、バッチ的に全入力データを対象に実行しておき、各時刻の予測点に対し、同じ予測誤差代表値（予測値に対するオフセット）を適用する。
【００６１】
図１２は、この実施の形態におけるデータ圧縮装置１００の機能ブロックの構成の一例を示すブロック構成図である。
データ圧縮装置１００は、実施の形態１で説明したブロックに加えて、更に、値記憶部１１と、予測値記憶部１２と、オフセット量記憶部２１とを有する。
【００６２】
値記憶部１１は、データ圧縮装置１００が入力した入力データ（観測データ）を記憶する。
予測値記憶部１２は、予測器１０が予測した予測値を記憶する。
オフセット量記憶部２１は、オフセット量決定部２０が決定した複数の代表値を記憶する。
【００６３】
図１３は、この実施の形態におけるデータ圧縮処理の流れの一例を示すフローチャート図である。
【００６４】
ステップＳ３０１は、実施の形態１におけるステップＳ３０に対応する。ステップＳ２０１は、実施の形態１におけるステップＳ２０に対応する。実施の形態１におけるステップＳ２０およびステップＳ３０は、ループの中にあり、逐次的に実行するのに対し、ステップＳ３０１およびステップＳ２０１は、ループの外に出ている。なお、実施の形態１で説明したデータ圧縮処理のステップと同じ番号を付けたステップの処理は、実施の形態１と同じなので、説明を省略する。
【００６５】
ステップＳ３０１において、予測器１０は、値記憶部１１が記憶した入力データの全ての値に対し線形予測を適用して、各値に対する予測値を得る。予測値記憶部１２は、予測器１０が予測した予測値を、ＲＡＭ９１４などのメモリに記憶する。
【００６６】
ステップＳ２０１において、オフセット量決定部２０は、値記憶部１１が記憶した入力データの各値を、予測値記憶部１２が記憶した予測値と比較して、全予測誤差データを得る。オフセット量決定部２０は、得られた全予測誤差データを実施の形態１と同様にクラスタリングして、ｎ個の予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝を得る。オフセット量記憶部２１は、オフセット量決定部２０が算出した予測誤差代表値を、ＲＡＭ９１４などのメモリに記憶する。ヘッダ生成部８０（符号化部）は、オフセット量記憶部２１が記憶したｎ個の予測誤差代表値を、圧縮データ（ヘッダデータ）に補助情報（残差基準値符号）として保存する。これらは例えば固定長バイナリ形式で保存する。
【００６７】
ステップＳ１０１において、データ圧縮装置１００は、ループの判定処理をする。データ圧縮装置１００は、入力データに対する全ての値に対し、符号化が完了しているかを判定する。符号化が完了している場合、データ圧縮装置１００は、データ圧縮処理を終了する。符号化が完了していない場合、データ圧縮装置１００は、ステップＳ４０〜ステップＳ６０の処理を実行する。
【００６８】
ステップＳ４０において、基準値生成部３０は、ステップＳ２０１でオフセット量記憶部２１が記憶した予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝を使って、基準値を生成する。
実施の形態１では、予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝の値が逐次変化するが、この実施の形態では、すべての入力データに対して同一の値を用いる。
【００６９】
それ以外の処理は、実施の形態１と同様なので、説明を省略する。
【００７０】
図１４は、この実施の形態におけるデータ復元装置２００の機能ブロックの構成の一例を示すブロック構成図である。
データ復元装置２００は、データ圧縮装置１００が生成した圧縮データから、元の入力データを損失なく伸張する。
データ復元装置２００は、実施の形態１で説明した機能ブロックと同様の機能ブロックを有するが、オフセット量決定部２５を有さない点が、実施の形態１のデータ復元装置２００と異なる。
【００７１】
ヘッダ取得部８５がヘッダデータから取得するパラメータには、データ圧縮装置１００のオフセット量決定部２０が算出したｎ個の予測誤差代表値が含まれる。パラメータ記憶部７５は、ｎ個の予測誤差代表値を含むパラメータを記憶する。
基準値生成部３５は、実施の形態１で説明したオフセット量決定部２５が算出した予測誤差代表値の代わりに、パラメータ記憶部７５が記憶した予測誤差代表値を使って、基準値を生成する。
【００７２】
図１５は、この実施の形態におけるデータ伸長処理の流れの一例を示すフローチャート図である。
なお、実施の形態１で説明したステップと同じ番号を付与したステップの処理は、実施の形態１と同じであるため、説明を省略する。
【００７３】
ステップＳ２０１ａにおいて、ヘッダ取得部８５は、ステップＳ０１ａで得た代表値の数ｎに基づいて、圧縮データより予測誤差代表値ｎ個を読み出す。これらが固定長バイナリ形式で保存されている場合、特段の伸張処理は不要である。
【００７４】
ステップＳ１０１ａにおいて、データ復元装置２００は、ループの終了判定処理をする。ステップＳ３０〜Ｓ７０ａの繰り返し回数が、ステップＳ０１ａで得たデータサイズＴの回数に達した場合、データ復元装置２００は、データ伸長処理を終了する。繰り返し回数がデータサイズＴに達していない場合、データ復元装置２００は、ステップＳ３０〜Ｓ７０ａの処理を実行する。
【００７５】
ステップＳ４０において、基準値生成部３５は、予測器１５が予測した予測値と、パラメータ記憶部７５が記憶したｎ個の予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝それぞれとの和を算出することにより、ｎ個の基準値を生成する。
【００７６】
それ以外のステップの処理は、実施の形態１と同様なので、説明を省略する。
【００７７】
以上のようにして、本発明によるデータ圧縮装置で圧縮したデータを損失無く伸張することができる。
【００７８】
データ圧縮装置１００は、バッチ処理で事前にクラスタリング処理をする。オフセット量決定部２０は、予測誤差代表値の集合を、入力データに対する予測誤差の分布から一括処理により決定し、決定した予測誤差代表値の集合を圧縮後データに保存する。
【００７９】
このように、本実施の形態におけるデータ圧縮装置１００は、入力データ全体における予測誤差の分布に基づいて残差の基準値を最小化するようなｎ値の集合を設定することが出来る。このため、インデックスビットの指定が必要なｎ値を用いる方式でありながら、ｎ値間の冗長性を抑え、効果的に予測点（残差基準点）を増やすことができ、結果として、優れた圧縮率を得ることができる。
【００８０】
特に、定常と見なすことが可能なデータにおいては、このような構成としても、実施の形態１と同様に残差を小さくする効果を得ることができる。
【００８１】
また、実施の形態１では、各入力データごとに予測誤差代表値を算出したのに対し、この実施の形態では、すべての入力データに対して同一の予測誤差代表値を用いるので、予測誤差代表値の算出処理を１回だけ実行すればよい。計算量が少なくて済むので、データ圧縮処理を高速に実行することができる。
【００８２】
実施の形態３．
実施の形態３について、図１６〜図１６を用いて説明する。
なお、実施の形態１及び実施の形態２と共通する部分については、同一の符号を付し、説明を省略する。
【００８３】
この実施の形態では、予測誤差が正規分布に従って分布すると仮定できる場合について説明する。
【００８４】
オフセット量決定部２０は、あらかじめ、予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝を算出するための係数ａｊ（ｊは１以上ｎ／２以下の整数。）を記憶している。
オフセット量決定部２０は、例えば、予測誤差の履歴｛ｅ１，…，ｅｔ−１｝に基づいて、予測誤差の平均値ｍ及び標準偏差σを算出する。なお、予測誤差の平均値ｍが０になると期待できる場合、オフセット量決定部２０は、予測誤差の平均値ｍ＝０を仮定して、予測誤差の平均値ｍを算出せず、標準偏差σだけを算出する構成であってもよい。
オフセット量決定部２０は、算出した予測誤差の平均値ｍ及び標準偏差σに基づいて、予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝を算出する。オフセット量決定部２０は、例えば、次の式を用いて、予測誤差代表値を算出する。
【数１５】
ただし、ｎ’は、ｎ／２より小さくない最小の整数である。ｍは、オフセット量決定部２０が算出する予測誤差の平均値である。σは、オフセット量決定部２０が算出する予測誤差の標準偏差である。
【００８５】
図１６は、この実施の形態におけるオフセット量決定部２０が算出する予測誤差代表値の一例を示す図である。
横軸は、予測誤差を示す。縦軸は、予測誤差の確率分布を示す。
曲線３００は、予測誤差の確率分布関数である。この例は、予測誤差の平均値ｍが０の場合を示す。
斜線で示した領域３０１〜３０４は、予測誤差の確率分布をｎ個に分割した領域である。オフセット量決定部２０は、予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝として、各領域３０１〜３０４の重心を算出する。
予測誤差の確率分布が正規分布にしたがうと仮定できる場合、各領域の重心と平均値ｍとの差が、標準偏差σの何倍にあたるかを、あらかじめ計算しておくことができる。例えばｎ＝４の場合、予測誤差が下から２５％以内である領域３０１の重心は（ｍ−１．２７σ）、予測誤差が平均値より下の２５％以内である領域３０２の重心は（ｍ−０．３２５σ）、予測誤差が平均値より上の２５％以内である領域３０３の重心は（ｍ＋０．３２５σ）、予測誤差が上から２５％以内である領域３０４の重心は（ｎ＋１．２７σ）である。オフセット量決定部２０は、あらかじめａ１＝０．３２５、ａ２＝１．２７を記憶しておく。オフセット量決定部２０は、算出した標準偏差σに基づいて、各領域の重心を算出し、予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝とする。
一般に、予測誤差が上からｂ１％〜ｂ２％の間（０≦ｂ１＜ｂ２≦１００）にある領域の重心ａは、
【数１６】
【００８６】
ただし、ｅｘｐはネイピア数を底とする指数関数である。ｅｒｆ−１は誤差関数ｅｒｆの逆関数である。
【００８７】
このように、正規分布を用いて、例えば、平均０で予測誤差履歴の分散を持つ正規分布の面積をｎ等分する各領域の重心に残差代表値を置き、そのような等分点がσの何倍に当たるかを予め装置に登録しておくことにより、データの分散に合わせて容易に代表値を決定することができる。
【００８８】
なお、予測誤差が従うと仮定する分布は、正規分布に限らず、他の分布であってもよい。
【００８９】
実施の形態４．
実施の形態４について、図１７〜図２０を用いて説明する。
なお、実施の形態１〜実施の形態３と共通する部分については、同一の符号を付し、説明を省略する。
【００９０】
図１７は、この実施の形態におけるデータ圧縮装置１００の機能ブロックの一例を示すブロック構成図である。
データ圧縮装置１００は、データ入力部１１０と、データ記憶部１１５と、予測部１２０と、予測残差算出部１２５と、予測残差記憶部１４０と、基準値算出部１４５と、パラメータ算出部１５０と、基準値選択部１８０と、基準残差算出部１８５と、符号化部１９０と、符号出力部１９５とを有する。
【００９１】
データ入力部１１０は、ＣＰＵ９１１（処理装置）を用いて、観測装置８１０が出力した観測データを入力する。データ入力部１１０が入力する観測データは、一連の観測値を表わす。
データ記憶部１１５は、磁気ディスク装置９２０（記憶装置）を用いて、データ入力部１１０が入力した観測データを記憶する。
【００９２】
予測部１２０は、ＣＰＵ９１１を用いて、データ記憶部１１５が記憶した観測データが表わす一連の観測値のうち最新の観測値について、その観測値の予測値を算出する。予測部１２０は、その観測値よりも前の観測値に基づいて、その観測値を予測する。例えば、予測部１２０は、ある観測値よりも前のすべての観測値を使って、その観測値を予測する。あるいは、予測部１２０は、ある観測値の直前のいくつかの観測値を使って、その観測値を予測する構成であってもよい。なお、一連の観測値のうち最初の観測値については、それよりも前の観測値が存在しないので、予測部１２０は、例えば、所定の値（例えば０）を、その観測値の予測値とする。
予測部１２０は、例えば線形予測や非線形予測、カルマンフィルタやその他フィルタを用いた予測などを用いて、観測値を予測する。予測部１２０は、観測値の順序を所定の方式で入れ替える構成であってもよい。例えば、２ａ番目の観測値と２ａ＋１番目の観測値の順序を入れ替えて、２ａ＋１番目の観測値を２ａ番目の観測値よりも先に予測する構成であってもよい。その場合、予測部１２０は、２ａ番目の観測値を使わず、２ａ−１番目以前の観測値だけを使って、２ａ＋１番目の観測値を予測する。その代わり、予測部１２０は、２ａ番目の観測値の予測に、２ａ＋１番目の観測値を使う。これにより、２ａ番目の観測値の予測精度を高めることができる。
このように、観測値の順序は、実際にその観測値を観測した順序と異なっていてもよい。ここでいう「観測値の順序」とは、観測値を符号化した符号の依存関係のことである。すなわち、ある観測値ｘａを使って別の観測値ｘｂを予測し、その別の観測値ｘｂを使って観測値ｘａを予測するという循環があると、どちらかの観測値がわからなければもう一方の観測値を予測できないから、符号化した符号を復号できない。したがって、このような循環が存在してはならない。このような循環が存在しなければ、復号時には、復号済の観測値を使ってまだ復号していない観測値を予測することができ、すべての観測値を復号できる。観測値の順序が実際の時系列順と異なる場合、復号後に観測値の順序を入れ替えて、実際にその観測値を観測した時系列順に戻せばよい。
【００９３】
予測残差算出部１２５は、ＣＰＵ９１１を用いて、データ記憶部１１５が記憶した観測データが表わす一連の観測値のうち、予測部１２０が予測値を算出した観測値について、その観測値の予測残差（予測誤差）を算出する。予測残差算出部１２５は、その観測値の予測残差として、予測部１２０が算出した予測値をその観測値から差し引いた差を計算する。
【００９４】
なお、観測値が整数値や固定小数点形式で表現された実数値である場合、予測残差算出部１２５は、整数の引き算を使って、予測残差を算出する。
また、観測値が浮動小数点形式で表現された実数値である場合、例えば、予測残差算出部１２５は、指数部の予測残差として、予測値の指数部を観測値の指数部から差し引いた差を、整数の引き算を使って算出する。予測残差算出部１２５は、予測値を変換して、観測値の指数部に予測値の指数部を一致させる。例えば、予測値の指数部が観測値の指数部より小さい場合、予測残差算出部１２５は、指数部の差の分だけ、予測値の仮数部を右にシフトする。この際、アンダーフローするビットは、無視してよい。逆に、予測値の指数部が観測値の指数部より大きい場合、予測残差算出部１２５は、指数部の差の分だけ、予測値の仮数部を左にシフトする。この際、オーバーフローするビットも、無視してよい。予測残差算出部１２５は、仮数部の予測残差として、変換した予測値の仮数部を観測値の仮数部から差し引いた差を、整数の引き算を使って算出する。また、予測残差算出部１２５は、符号部の予測残差として、観測値の符号部と予測値の符号部とが同じか異なるかを算出する。予測残差算出部１２５は、指数部の予測残差と、仮数部の予測残差と、符号部の予測残差との組を、観測値の予測残差とする。なお、観測値の符号があらかじめわかっている場合、予測残差算出部１２５は、符号部の予測残差を算出しない構成であってもよい。
また、観測値が複数の整数値や実数値の組からなるベクトル値である場合、予測残差算出部１２５は、各成分ごとに予測残差を算出し、算出した予測残差の組を、観測値の予測残差とする。
【００９５】
予測残差記憶部１４０は、磁気ディスク装置９２０を用いて、予測残差算出部１２５が算出した予測残差を表わすデータ（以下「予測残差データ」と呼ぶ。）を記憶する。予測残差データは、予測部１２０が予測値を算出した観測値それぞれについての予測残差を表わす。１つの予測残差は、例えば、１つの整数または複数の整数の組によって表わされる。
【００９６】
基準値算出部１４５は、ＣＰＵ９１１を用いて、予測部１２０が予測値を算出した観測値のそれぞれについて、予測残差記憶部１４０が記憶した予想残差データが表わす予測残差のうち、その観測値よりも前の観測値についての予測残差に基づいて、予測残差基準値（予測誤差代表値）を算出する。なお、ここでいう観測値の前後関係は、予測部１２０の場合と同様、必ずしも、実際にその観測値が観測された順序どおりでなくてもよく、予測部１２０が予測値を予測する順序（依存関係）にしたがう。
基準値算出部１４５は、その観測値よりも前の観測値についての予測残差すべてを使って、予測残差基準値を算出する構成でもよいし、その観測値の直前のいくつかの観測値についての予測残差を使って、予測残差基準値を算出する構成でもよい。その場合、基準値算出部１４５が使う予測残差の数は、予測部１２０が予測値の算出に使う観測値の数と異なっていてもよいし、同じであってもよい。
【００９７】
基準値算出部１４５は、予測残差基準値（予測誤差代表値）を少なくとも１つ算出する。基準値算出部１４５は、予測残差基準値の算出に使う予測残差の分布に基づいて、予測残差が比較的密集している領域（以下「予測残差密集領域」と呼ぶ。）を算出する。基準値算出部１４５は、算出した予測残差密集領域に基づいて、予測残差基準値として、その予測残差密集領域を代表する値を算出する。例えば、基準値算出部１４５は、予測残差密集領域の中央値を予測残差基準値とする。あるいは、基準値算出部１４５は、予測残差密集領域内に入る予測残差の平均値を予測残差基準値とする。予測残差密集領域が複数ある場合、基準値算出部１４５は、複数の予測残差密集領域を算出し、原則として、それぞれの予測残差密集領域について、予測残差基準値を算出する。ただし、複数の予測残差密集領域が比較的近い領域にある場合、基準値算出部１４５は、近くに存在する複数の予測残差密集領域を１つの予測残差密集領域とみなす。基準値算出部１４５は、１つとみなした予測残差密集領域について１つの予測残差基準値を算出する。
基準値算出部１４５は、算出する予測残差基準値の数をあらかじめ定めず、予測残差の分布に基づいて、最適な数の予測誤差基準値を算出する。予測残差基準値の数を増やすと、符号化部１９０が符号化する整数（残差）が小さくなる分、符号長が短くなるが、どの予測残差基準値を選択したかを示すインデックスの符号長が長くなるので、全体としての符号長は、必ずしも短くなるとは限らない。そこで、基準値算出部１４５は、符号長の期待値が最小になる数の予測残差基準値を算出する。例えば、予測残差が比較的まばらなところに予測残差基準値を設けても、その予測残差基準値を使う確率が低いので、残差の符号長はあまり短くならない。また、１つの予測残差密集領域内に複数の予測残差基準値を設けても、どちらの予測残差基準値を使っても残差があまり変わらないので、やはり、残差の符号長はあまり短くならない。このため、符号長の期待値が最小になるのは、予測残差基準値の数が、予測残差密集領域の数と等しい場合である。基準値算出部１４５は、予測残差密集領域の数と同じ数の予測残差基準値を算出する。
【００９８】
なお、予測残差が複数の整数の組によって表わされる場合、基準値算出部１４５は、各成分ごとに独立して予測残差基準値を算出する構成であってもよいし、各成分の予測残差基準値を組として扱う構成であってもよい。例えば、予測残差が２つの整数の組（ｘ，ｙ）によって表わされる場合、各成分ごとに独立して予測残差基準値を算出する構成であれば、基準値算出部１４５は、ｘ成分の予測残差基準値として、ａ個の予測残差基準値ｘ１，ｘ２，…，ｘａを算出し、ｙ成分の予測残差基準値として、ｂ個の予測残差基準値ｙ１，ｙ２，…，ｙｂを算出する。各成分の予測残差基準値を組として扱う構成であれば、基準値算出部１４５は、ｃ個の予測残差基準値の組（ｘ１，ｙ１），（ｘ２，ｙ２），…，（ｘｃ，ｙｃ）を算出する。各成分の間に相関がなく独立している場合には、各成分ごとに独立して予測残差基準値を算出する構成のほうが好ましく、各成分の間に強い相関がある場合には、各成分の予測残差基準値を組として扱う構成のほうが好ましい。
【００９９】
パラメータ算出部１５０は、ＣＰＵ９１１を用いて、予測部１２０が予測値を算出した観測値のそれぞれについて、基準値算出部１４５が算出した予測残差基準値と、予測残差記憶部１４０が記憶した予想残差データが表わす予測残差のうち、その観測値よりも前の観測値についての予測残差とに基づいて、符号化に使うパラメータを算出する。パラメータ算出部１５０が算出するパラメータには、どの予測残差基準値を使って残差を算出したかを表わす基準値インデックスを符号化するためのインデックス符号化パラメータと、残差を符号化するための残差符号化パラメータとがある。
【０１００】
例えば、パラメータ算出部１５０は、予測残差の分布に基づいて、基準値算出部１４５が算出した予測残差基準値それぞれを選択する確率を推定する。パラメータ算出部１５０は、推定した確率に基づいて、ハフマン符号などのエントロピー符号において基準値インデックスに対応する符号を算出し、インデックス符号化パラメータとする。
なお、予測残差が複数の整数の組で表わされ、基準値算出部１４５が各成分ごとに独立して予測残差を算出する構成である場合、パラメータ算出部１５０は、各成分ごとに独立して予測残差基準値を選択する確率を推定する構成であってもよいし、各成分の予測残差基準値の組について、その組を選択する確率を推定する構成であってもよい。
【０１０１】
また、パラメータ算出部１５０は、予測残差の分布と、基準値算出部１４５が算出した予測残差基準値の分布とに基づいて、残差を符号化する符号化方式や、符号化に用いるパラメータを選択する。パラメータ算出部１５０は、選択した符号化方式やパラメータを表わす残差符号化パラメータを生成する。例えば、基準値算出部１４５が算出した予測残差基準値のうち、最も小さい予測残差基準値よりも予測残差が小さい場合や、最も大きい予測残差基準値よりも予測残差が大きい場合は、符号化する残差の絶対値が比較的大きくなる可能性があるのに対し、予測残差が２つの予測残差基準値の間にある場合は、符号化する残差の絶対値がその２つの予測残差基準値の差より大きくなることはあり得ない。符号化する残差が大きい可能性がある場合は、例えばガンマ符号やデルタ符号など大きい整数を比較的短い符号に符号化する符号化方式が効率的である。また、符号化する残差の上限がわかっている場合は、例えばＣＢＴ符号など所定の範囲内の整数を符号化する符号化方式が効率的である。また、符号化する残差の出現確率によっても、最も効率がよい符号化方式が異なる。例えば、残差の絶対値が大きくなるにつれて出現確率が下がっていく場合は、デルタ符号などのユニバーサル符号のように絶対値が小さいほど符号長が短く、絶対値が大きいほど符号長が長くなる符号化方式のほうが効率がよい。逆に、残差の絶対値にかかわらず出現確率があまり変わらない場合は、ＣＢＴ符号のように符号長があまり変わらない符号化方式のほうが効率がよい。また、ゴロム符号やライス符号を使う場合、絶対値の小さい残差の出現確率が高いほど、法ｍや次数ｋを小さくするほうが効率がよい。
パラメータ算出部１５０は、予測残差の分布に基づいて、それぞれの予測残差基準値を選択した場合における残差の確率分布を推定する。パラメータ算出部１５０は、推定した確率分布に基づいて、どの符号化方式が最適であるかを判定し、ライス符号のようにパラメータを持つ符号化方式が最適であると判定した場合は、更に、最適なパラメータの値を算出する。
なお、ある予測残差基準値に対して、予測残差のほうが大きい場合と、予測残差のほうが小さい場合とでは、符号化する残差の確率分布が異なる場合がある。このため、パラメータ算出部１５０は、同じ予測残差基準値を選択した場合でも、符号化する残差が正である場合と、符号化する残差が負である場合とで、異なる符号化方式やパラメータを算出する構成であってもよい。
また、予測残差が複数の整数の組によって表わされる場合、パラメータ算出部１５０は、各成分ごとに異なる符号化方式やパラメータを算出する構成であってもよい。また、基準値算出部１４５が各成分ごとに独立して予測誤差基準値を算出する構成である場合、パラメータ算出部１５０は、各成分に対して選択した予測誤差基準値の組に対して、それぞれ異なる符号化方式やパラメータを算出する構成であってもよい。例えば、予測残差が２つの整数の組（ｘ，ｙ）によって表わされ、基準値算出部１４５が各成分についてそれぞれ独立に予測誤差基準値を算出し、ｘ成分についてａ個、ｙ成分についてｂ個の予測誤差基準値を算出した場合、予測誤差基準値の組合せは、ａ×ｂ通りある。パラメータ算出部１５０は、ａ×ｂ通りの組合せそれぞれについて、ｘ成分の符号化方式やパラメータと、ｙ成分の符号化方式やパラメータとの組を選択する。
【０１０２】
基準値選択部１８０は、ＣＰＵ９１１を用いて、予測部１２０が予測値を算出した観測値のそれぞれについて、予測残差算出部１２５が算出した予測残差と、パラメータ算出部１５０が算出した符号化パラメータとに基づいて、基準値算出部１４５が算出した予測残差基準値のなかから、１つの予測残差基準値を選択する。基準値選択部１８０は、残差を符号化したときの符号長が最も短くなる予測残差基準値を選択する。例えば、基準値選択部１８０は、予測残差との差の絶対値が最も小さい予測残差基準値を選択する。ただし、予測残差基準値によって符号化の方式が異なる場合、必ずしも、予測残差との差の絶対値が最も小さい予測残差基準値が、残差を符号化したときの符号長を最も短くするとは限らない。また、選択した予測残差基準値を示す基準値インデックスを符号化した符号長が、選択した予測残差基準値によって異なる場合、基準値選択部１８０は、基準値インデックスを符号化した符号長も合わせた全体の符号長が最も短くなる予測残差基準値を選択する。例えば、基準値選択部１８０は、基準値算出部１４５が算出した予測残差基準値すべて、もしくは、そのなかから抽出したいくつかの候補について、符号長を算出し、算出した符号長が最も短い予測残差基準値を選択する。
【０１０３】
予測残差が複数の整数の組で表わされ、基準値算出部１４５が各成分ごとに独立して予測残差基準値を算出する構成である場合、基準値選択部１８０は、各成分ごとに、基準値算出部１４５が算出した予測残差基準値のなかから、１つの予測残差基準値を選択する。また、基準値算出部１４５が各成分の予測残差基準値を組として扱う構成である場合、基準値選択部１８０は、各成分の予測残差基準値の組のなかから、１つの組を選択する。
【０１０４】
基準残差算出部１８５は、ＣＰＵ９１１を用いて、予測部１２０が予測値を算出した観測値のそれぞれについて、基準残差を算出する。基準残差算出部１８５は、基準残差として、予測残差算出部１２５が算出した予測残差から、基準値選択部１８０が選択した予測残差基準値を差し引いた差を、整数の引き算を使って計算する。
予測残差が複数の整数の組で表わされる場合、基準残差算出部１８５は、各成分ごとに、予測残差基準値を予測残差から差し引いた差を、整数の引き算を使って計算する。
【０１０５】
符号化部１９０は、ＣＰＵ９１１を用いて、予測部１２０が予測値を算出した観測値のそれぞれについて、パラメータ算出部１５０が算出した符号化パラメータに基づいて、基準値選択部１８０が選択した予測残差基準値を示す基準値インデックスを符号化して、選択基準値符号を生成する。また、符号化部１９０は、ＣＰＵ９１１を用いて、パラメータ算出部１５０が算出した符号化パラメータに基づいて、基準残差算出部１８５が算出した基準残差を符号化して、基準残差符号を生成する。
【０１０６】
なお、符号化部１９０は、基準残差が正であるか負であるかを、基準残差符号の一部として符号化する構成であってもよいし、選択基準値符号の一部として符号化する構成であってもよい。
基準残差の正負を選択基準値符号の一部として符号化する構成の場合、符号化部１９０は、例えば、基準残差算出部１８５が算出した基準残差が正であるか負であるかを判定する。なお、基準残差が０である場合は、正に含まれるものとして扱う構成であってもよいし、負に含まれるものとして扱う構成であってもよいし、符号長が短くなるほうに含まれるものとして扱う構成であってもよい。
基準残差が正であると判定した場合、符号化部１９０は、例えば、基準値選択部１８０が選択した基準値インデックスに、基準残差が正であることを示すビットを付加したものを符号化し、選択基準値符号を生成する。基準残差が０の場合を正として扱う場合において、符号化部１９０は、指数ゴロム符号のように０以上の整数を符号化できる符号化方式を使って、基準残差算出部１８５が算出した基準残差を符号化し、基準残差符号を生成する。なお、ガンマ符号のように１以上の整数を符号化できる符号化方式を使う場合、符号化部１９０は、例えば、基準残差算出部１８５が算出した基準残差に１を加えたものを符号化する。
基準残差が負であると判定した場合、符号化部１９０は、例えば、基準値選択部１８０が選択した基準値インデックスに、基準残差が負であることを示すビットを付加したものを符号化し、選択基準値符号を生成する。基準残差が０の場合を正として扱う場合において、符号化部１９０は、基準残差算出部１８５が算出した基準残差に−１を乗じて正負を反転し、ガンマ符号のように１以上の整数を符号化できる符号化方式により符号化する。なお、指数ゴロム符号のように０以上の整数を符号化できる符号化方式を使う場合は、符号化部１９０は、基準残差算出部１８５が算出した基準残差を−１から差し引いた差（あるいは基準残差の１の補数）を符号化する。
基準残差が正の場合と負の場合とで、基準残差の符号化方式が異なる場合、基準残差の正負を選択基準値符号の一部として符号化する方式が好ましい。また、選択基準値符号をハフマン符号などのエントロピー符号を用いて符号化する構成で、基準残差が正の場合の出現確率と負の場合の出現確率とが異なる場合、基準残差の正負を選択基準値符号の一部として符号化することにより、符号長を短くすることができる。
【０１０７】
予測残差が複数の整数の組で表わされ、基準値算出部１４５が各成分ごとに独立して予測残差基準値を算出する構成である場合、符号化部１９０は、各成分ごとに独立して、基準値選択部１８０が選択した予測残差基準値を示す基準値インデックスを符号化する構成であってもよいし、各成分について基準値選択部１８０が選択した予測残差基準値を示す基準値インデックスの組を符号化する構成であってもよい。ハフマン符号などのエントロピー符号を用いて符号化する場合、出現確率の低い基準値インデックスの組があれば、基準値インデックスの組を符号化する構成のほうが、出現確率の高い基準値インデックスの組を符号化した選択基準値符号の符号長が短くなるので好ましい。
なお、基準値インデックスを圧縮符号化せず、固定長バイナリ形式の符号を生成する構成であってもよい。
【０１０８】
また、予測残差が複数の整数の組で表わされる場合、符号化部１９０は、各成分ごとに、基準残差算出部１８５が算出した基準残差を符号化する。符号化部１９０は、すべての成分について生成した符号の組を、基準残差符号とする。
【０１０９】
符号出力部１９５は、ＣＰＵ９１１を用いて、圧縮データを出力する。圧縮データは、データ入力部１１０が入力した観測データが表わす一連の観測値を表わす。圧縮データは、符号化部１９０が生成した選択基準値符号と基準残差符号との組を複数含む。１つの選択基準地符号と基準残差符号との組は、１つの観測値を表わす。
なお、符号出力部１９５は、符号化部１９０が生成した選択基準値符号と基準残差符号との組をそのまま圧縮データとするのではなく、更に、別の圧縮方式を用いて圧縮したものを圧縮データとして出力する構成であってもよい。
【０１１０】
図１８は、この実施の形態におけるデータ復元装置２００の機能ブロックの構成の一例を示すブロック構成図である。
データ復元装置２００は、データ出力部２１０と、値記憶部２１５と、復元予測部２２０と、予測残差算出部２２５と、値復元部２３０と、予測残差記憶部２４０と、復元基準値算出部２４５と、パラメータ算出部２５０と、復元基準値選択部２８０と、復号部２９０と、符号取得部２９５とを有する。
【０１１１】
符号取得部２９５は、ＣＰＵ９１１を用いて、圧縮データを入力して、選択基準値符号と基準残差符号との組を、順に一組ずつ取得する。
【０１１２】
予測残差記憶部２４０は、磁気ディスク装置９２０を用いて、予測残差算出部２２５がそれまでに算出した予測残差を表わす予測残差データを記憶している。
【０１１３】
復元基準値算出部２４５は、ＣＰＵ９１１を用いて、予測残差記憶部２４０が記憶した予測残差データが表わす予測残差に基づいて、予測残差基準値を算出する。復元基準値算出部２４５は、データ圧縮装置１００の基準値算出部１４５と同じ方式で予測残差基準値を算出する。基準値算出部１４５は、ある観測値について、その観測値よりも前の観測値についての予測残差に基づいて予測残差基準値を算出する。データ復元装置２００がその観測値を復元する時点では、その観測値よりも前の観測値についての予測残差を予測残差算出部２２５が既に算出し、予測残差記憶部２４０が記憶している。このため、復元基準値算出部２４５は、基準値算出部１４５とまったく同じようにして予測残差基準値を算出することができる。すなわち、復元基準値算出部２４５は、基準値算出部１４５が算出する予測残差基準値とまったく同じ予測残差基準値を算出する。
【０１１４】
パラメータ算出部２５０は、ＣＰＵ９１１を用いて、予測残差記憶部２４０が記憶した予測残差データが表わす予測残差と、復元基準値算出部２４５が算出した予測残差基準値とに基づいて、符号化パラメータを算出する。パラメータ算出部２５０は、データ圧縮装置１００のパラメータ算出部１５０と同じ方式で符号化パラメータを算出する。復元基準値算出部２４５と同様、パラメータ算出部２５０は、パラメータ算出部２５０とまったく同じようにして符号化パラメータを算出することができる。すなわち、パラメータ算出部２５０は、パラメータ算出部１５０が算出する符号化パラメータとまったく同じ符号化パラメータを算出する。
【０１１５】
復号部２９０は、ＣＰＵ９１１を用いて、パラメータ算出部２５０が算出した符号化パラメータに基づいて、符号取得部２９５が取得した選択基準値符号と基準残差符号とを復号する。例えば、復号部２９０は、まず、パラメータ算出部２５０が算出した符号化パラメータのうちインデックス符号化パラメータに基づいて、選択基準値符号を復号して、基準値インデックスを復元する。次に、復号部２９０は、復元した基準値インデックスと、パラメータ算出部２５０が算出した符号化パラメータのうち残差符号化パラメータとに基づいて、基準残差符号を復号して、基準残差を復元する。
【０１１６】
復元基準値選択部２８０は、ＣＰＵ９１１を用いて、復元基準値算出部２４５が算出した予測残差基準値のなかから、復号部２９０が復元した基準値インデックスが示す予測残差基準値を選択する。これにより、復元基準値選択部２８０は、データ圧縮装置１００の基準値選択部１８０が選択した予測残差基準値と同じ予測残差基準値を選択する。
【０１１７】
予測残差算出部２２５は、ＣＰＵ９１１を用いて、復号部２９０が復元した基準残差と、復元基準値選択部２８０が選択した予測残差基準値とに基づいて、予測残差を算出する。予測残差算出部２２５は、基準残差と予測残差基準値とを合計した和を、整数の足し算を使って計算して、予測残差とする。これにより、予測残差算出部２２５は、データ圧縮装置１００の予測残差算出部１２５が算出した予測残差と同じ予測残差を算出する。予測残差算出部２２５が算出した予測残差は、予測残差記憶部２４０が記憶して、次の観測値を復元するための予測残差基準値などを算出するために使われる。
【０１１８】
値記憶部２１５は、磁気ディスク装置９２０を用いて、値復元部２３０がそれまでに復元した一連の観測値を表わすデータを記憶している。
【０１１９】
復元予測部２２０は、ＣＰＵ９１１を用いて、値記憶部２１５が記憶したデータが表わす一連の観測値に基づいて、復元しようとしている観測値の予測値を算出する。復元予測部２２０は、データ圧縮装置１００の予測部１２０と同じ方式で観測値を予測する。予測部１２０は、ある観測値について、その観測値よりも前の観測値に基づいて予測値を算出する。データ復元装置２００がその観測値を復元する時点では、その観測値よりも前の観測値を値復元部２３０が既に復元し、値記憶部２１５が記憶している。このため、復元予測部２２０は、予測部１２０とまったく同じようにして予測値を算出することができる。すなわち、復元予測部２２０は、予測部１２０が算出する予測値とまったく同じ予測値を算出する。
【０１２０】
値復元部２３０は、ＣＰＵ９１１を用いて、予測残差算出部２２５が算出した予測残差と、復元予測部２２０が算出した予測値とに基づいて、観測値を復元する。値復元部２３０は、予測残差と予測値とを合計した和を計算することにより、観測値の復元値を算出する。
観測値が整数値や固定小数点形式で表現された実数値である場合、値復元部２３０は、整数の足し算を計算することにより、復元値を算出する。
観測値が浮動小数点形式で表現された実数値であり、予測残差算出部２２５が算出する予測残差が、指数部の予測残差を表わす整数と、仮数部の予測残差を表わす整数と、符号部の予測残差を表わす整数との組である場合、値復元部２３０は、例えば、復元予測部２２０が予測した予測値の仮数部を、指数部の予測残差の分だけシフトする。値復元部２３０は、例えば、指数部の予測残差が正であれば予測値の仮数部を左にシフトし、指数部の予測残差が負であれば予測値の仮数部を右にシフトする。このとき、オーバーフローあるいはアンダーフローしたビットは無視してよい。次に、値復元部２３０は、シフトした予測値の仮数部と、予測誤差の仮数部とを合計した和を、整数の足し算を使って計算する。値復元部２３０は、符号部の予測残差が０でない場合、予測値の符号部を反転する。こうして算出した指数部・仮数部・符号部に基づいて、値復元部２３０は、浮動小数点形式で表現された実数値を復元して、観測値の復元値を得る。これにより、観測値が浮動小数点形式で表現されている場合であっても、桁落ちなどが発生せず、元の観測値とまったく同じ復元値を得ることができる。
値復元部２３０が復元した観測値は、値記憶部２１５が記憶して、次の観測値などを予測するために使われる。
【０１２１】
データ出力部２１０は、ＣＰＵ９１１を用いて、値復元部２３０が復元した一連の観測値を表わす復元データを生成し、出力する。
【０１２２】
図１９は、この実施の形態におけるデータ圧縮処理Ｓ６１０の流れの一例を示すフローチャート図である。
データ圧縮処理Ｓ６１０において、データ圧縮装置１００は、一連の観測値を表わす圧縮データを生成する。データ圧縮処理Ｓ６１０は、観測値取得工程Ｓ６１１と、基準値算出工程Ｓ６１２と、パラメータ算出工程Ｓ６１３と、観測値予測工程Ｓ６１４と、予測残差算出工程Ｓ６１５と、基準値選択工程Ｓ６１６と、基準残差算出工程Ｓ６１７と、符号化工程Ｓ６１８とを有する。データ圧縮装置１００は、観測値取得工程Ｓ６１１から処理を開始する。
【０１２３】
観測値取得工程Ｓ６１１において、データ入力部１１０は、ＣＰＵ９１１を用いて、観測値を入力する。データ記憶部１１５は、磁気ディスク装置９２０を用いて、データ入力部１１０が入力した観測値を記憶する。
データ圧縮装置１００は、ＣＰＵ９１１を用いて、データ記憶部１１５が記憶した一連の観測値のなかから、観測値を１つ選択する。すべての観測値が選択済である場合、データ圧縮装置１００は、データ圧縮処理Ｓ６１０を終了する。未選択の観測値がある場合、データ圧縮装置１００は、未選択の観測値のなかから、先頭の観測値を１つ選択し、基準値算出工程Ｓ６１２へ処理を進める。
【０１２４】
基準値算出工程Ｓ６１２において、基準値算出部１４５は、ＣＰＵ９１１を用いて、予測残差記憶部１４０が記憶した予測残差に基づいて、予測残差基準値を算出する。
パラメータ算出工程Ｓ６１３において、パラメータ算出部１５０は、ＣＰＵ９１１を用いて、予測残差記憶部１４０が記憶した予測残差と、基準値算出工程Ｓ６１２で基準値算出部１４５が算出した予測残差基準値とに基づいて、符号化パラメータを算出する。
【０１２５】
観測値予測工程Ｓ６１４において、予測部１２０は、ＣＰＵ９１１を用いて、データ記憶部１１５が記憶した観測データが表わす一連の観測値のうち、観測値取得工程Ｓ６１１で選択した観測値よりも前の観測値に基づいて、観測値取得工程Ｓ６１１で選択した観測値の予測値を算出する。
予測残差算出工程Ｓ６１５において、予測残差算出部１２５は、ＣＰＵ９１１を用いて、観測値取得工程Ｓ６１１で選択した観測値と、観測値予測工程Ｓ６１４で算出した予測値とに基づいて、予測残差を算出する。予測残差記憶部１４０は、磁気ディスク装置９２０を用いて、予測残差算出部１２５が算出した予測残差を記憶する。
【０１２６】
基準値選択工程Ｓ６１６において、基準値選択部１８０は、ＣＰＵ９１１を用いて、パラメータ算出工程Ｓ６１３でパラメータ算出部１５０が算出した符号化パラメータと、予測残差算出工程Ｓ６１５で予測残差算出部１２５が算出した予測残差とに基づいて、基準値算出工程Ｓ６１２で基準値算出部１４５が算出した予測残差基準値のなかから、予測残差基準値を選択する。
基準残差算出工程Ｓ６１７において、基準残差算出部１８５は、ＣＰＵ９１１を用いて、予測残差算出工程Ｓ６１５で予測残差算出部１２５が算出した予測残差と、基準値選択工程Ｓ６１６で基準値選択部１８０が選択した予測残差基準値とに基づいて、基準残差を算出する。
符号化工程Ｓ６１８において、符号化部１９０は、ＣＰＵ９１１を用いて、パラメータ算出工程Ｓ６１３でパラメータ算出部１５０が算出した符号化パラメータに基づいて、基準値選択工程Ｓ６１６で基準値選択部１８０が選択した予測残差基準値を示す基準値インデックスを符号化して、選択基準値符号を生成する。符号化部１９０は、ＣＰＵ９１１を用いて、パラメータ算出工程Ｓ６１３でパラメータ算出部１５０が算出した符号化パラメータと、基準値選択工程Ｓ６１６で基準値選択部１８０が選択した予測残差基準値を示す基準値インデックスとに基づいて、基準残差算出工程Ｓ６１７で基準残差算出部１８５が算出した基準残差を符号化して、基準残差符号を生成する。符号出力部１９５は、ＣＰＵ９１１を用いて、符号化部１９０が生成した選択基準値符号と基準残差符号との組を、観測値取得工程Ｓ６１１で選択した観測値を表わす符号として出力する。
データ圧縮装置１００は、ＣＰＵ９１１を用いて、観測値取得工程Ｓ６１１に処理を戻し、次の観測値を選択する。
【０１２７】
図２０は、この実施の形態におけるデータ復元処理Ｓ６２０の流れの一例を示すフローチャート図である。
データ復元処理Ｓ６２０において、データ復元装置２００は、データ圧縮装置１００が生成した圧縮データから、元の一連の観測値を復元する。データ復元処理Ｓ６２０は、符号取得工程Ｓ６２１と、基準値算出工程Ｓ６２２と、パラメータ算出工程Ｓ６２３と、復号工程Ｓ６２４と、基準値選択工程Ｓ６２５と、予測残差算出工程Ｓ６２６と、観測値予測工程Ｓ６２７と、観測値復元工程Ｓ６２８とを有する。データ復元装置２００は、符号取得工程Ｓ６２１から処理を開始する。
【０１２８】
符号取得工程Ｓ６２１において、符号取得部２９５は、ＣＰＵ９１１を用いて、圧縮データから、１つの観測値を表わす選択基準値符号と基準残差符号との組を取得する。圧縮データに含まれる選択基準値符号と基準残差符号との組がすべて取得済である場合、符号取得部２９５は、ＣＰＵ９１１を用いて、データ復元処理Ｓ６２０を終了する。未取得の組がある場合、符号取得部２９５は、ＣＰＵ９１１を用いて、未取得の組のなかから、先頭の組を１つ取得する。
【０１２９】
基準値算出工程Ｓ６２２において、復元基準値算出部２４５は、ＣＰＵ９１１を用いて、予測残差記憶部２４０が記憶した予測残差に基づいて、予測残差基準値を算出する。
パラメータ算出工程Ｓ６２３において、パラメータ算出部２５０は、ＣＰＵ９１１を用いて、予測残差記憶部２４０が記憶した予測残差と、基準値算出工程Ｓ６２２で復元基準値算出部２４５が算出した予測残差基準値とに基づいて、符号化パラメータを算出する。
【０１３０】
復号工程Ｓ６２４において、復号部２９０は、ＣＰＵ９１１を用いて、パラメータ算出工程Ｓ６２３でパラメータ算出部２５０が算出した符号化パラメータに基づいて、符号取得工程Ｓ６２１で符号取得部２９５が取得した選択基準値符号を復号して、基準値インデックスを算出する。復号部２９０は、ＣＰＵ９１１を用いて、パラメータ算出工程Ｓ６２３でパラメータ算出部２５０が算出した符号化パラメータと、算出した基準値インデックスとに基づいて、符号取得工程Ｓ６２１で符号取得部２９５が取得した基準残差符号を復号して、基準残差を算出する。
基準値選択工程Ｓ６２５において、復元基準値選択部２８０は、ＣＰＵ９１１を用いて、基準値算出工程Ｓ６２２で復元基準値算出部２４５が算出した予測残差基準値のなかから、復号工程Ｓ６２４で復号部２９０が算出した基準値インデックスによって示される予測残差基準値を選択する。
予測残差算出工程Ｓ６２６において、予測残差算出部２２５は、ＣＰＵ９１１を用いて、復号部２９０で復号部２９０が算出した基準残差と、基準値選択工程Ｓ６２５で復元基準値選択部２８０が選択した予測残差基準値とに基づいて、予測残差を算出する。予測残差記憶部２４０は、磁気ディスク装置９２０を用いて、予測残差算出部２２５が算出した予測残差を記憶する。
【０１３１】
観測値予測工程Ｓ６２７において、復元予測部２２０は、ＣＰＵ９１１を用いて、値記憶部２１５が記憶した観測値に基づいて、符号取得工程Ｓ６２１で符号取得部２９５が取得した選択基準値符号と基準残差符号との組によって表わされる観測値の予測値を算出する。
観測値復元工程Ｓ６２８において、値復元部２３０は、ＣＰＵ９１１を用いて、予測残差算出工程Ｓ６２６で予測残差算出部２２５が算出した予測残差と、観測値予測工程Ｓ６２７で復元予測部２２０が算出した予測値とに基づいて、符号取得工程Ｓ６２１で符号取得部２９５が取得した選択基準値符号と基準残差符号との組によって表わされる観測値の復元値を算出する。値記憶部２１５は、磁気ディスク装置９２０を用いて、値復元部２３０が復元した観測値を記憶する。データ出力部２１０は、ＣＰＵ９１１を用いて、値復元部２３０が復元した観測値を出力する。
データ復元装置２００は、ＣＰＵ９１１を用いて、符号取得工程Ｓ６２１に戻り、次の選択基準値符号と基準残差符号との組を取得する。
【０１３２】
以上、各実施の形態で説明した具体的な構成は一例であり、例えば、異なる実施の形態で説明した構成を組み合わせたり、重要でない部分の構成を他の構成で置き換えたりした構成であってもよい。
【０１３３】
以上説明したデータ圧縮装置（１００）は、データを処理する処理装置（ＣＰＵ９１１）と、予測部（１２０；予測器１０）と、予測残差算出部（１２５；オフセット量決定部２０）と、基準値算出部（１４５；オフセット量決定部２０）と、基準値選択部（１８０；最小残差選択部４０）と、基準残差算出部（１８５；最小残差選択部４０）と、符号化部（１９０；最小残差選択部４０，残差符号化部５０）とを有する。
上記予測部は、上記処理装置を用いて、一連の値（観測値）のうち少なくともいずれかの値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出する。
上記予測残差算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記値と上記予測部が算出した予測値との差を算出することにより、予測残差（予測誤差）を算出する。
上記基準値算出部は、上記処理装置を用いて、上記予測残差算出部が算出した予測残差に基づいて、複数の残差基準値（予測誤差代表値）を算出する。
上記基準値選択部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記基準値算出部が算出した複数の残差基準値のなかから、上記予測残差算出部が算出した予測残差に最も近い残差基準値を選択する。
上記基準残差算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記予測残差算出部が算出した予測残差と上記基準値選択部が選択した残差基準値との差を算出することにより、基準残差（残差）を算出する。
上記符号化部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記値を表わす符号として、上記基準値選択部が上記複数の残差基準値のうちどの残差基準値を選択したかを表わす選択基準値符号（基準値インデックス）と、上記基準残差算出部が算出した基準残差を表わす基準残差符号との組を生成する。
【０１３４】
これにより、符号化部が符号化する基準残差の絶対値が小さくなるので、デルタ符号などのユニバーサル符号のように符号化する整数の絶対値が小さいほど符号長が短くなる符号化方式で基準残差を符号化することより、圧縮率を高くすることができる。
【０１３５】
上記データ圧縮装置（１００）は、更に、予測残差分類部（オフセット量決定部２０）を有する。
上記予測残差分類部は、上記処理装置（ＣＰＵ９１１）を用いて、上記予測残差算出部（オフセット量決定部２０）が算出した予測残差（予測誤差）を複数のクラスタに分類する。
上記基準値算出部（オフセット量決定部２０）は、上記処理装置を用いて、上記予測残差分類部が分類した複数のクラスタそれぞれについて、上記予測残差分類部が上記クラスタに分類した予測残差の代表値を算出することにより、残差基準値（予測誤差代表値）を算出する。
【０１３６】
これにより、基準値算出部が算出する残差基準値の分布が、予測残差の分布に一致するので、選択基準値符号の冗長性を抑えることができ、圧縮率を高くすることができる。
【０１３７】
上記予測残差分類部（オフセット量決定部２０）は、ケー平均法または非階層型クラスタリングまたは階層型クラスタリングを用いて、上記予測残差算出部（オフセット量決定部２０）が算出した予測残差（予測誤差）を複数のクラスタに分類する。
【０１３８】
これにより、クラスタリングに伴う計算量を少なくすることができるので、処理装置の処理能力などデータ圧縮処理に必要な資源を抑えることができる。
【０１３９】
上記基準値算出部（オフセット量決定部２０）は、上記予測残差分類部（オフセット量決定部２０）が上記クラスタに分類した予測残差の平均値または中央値または最頻値を算出して、上記代表値とする。
【０１４０】
これにより、代表値算出に伴う計算量を少なくすることができるので、処理装置の処理能力などデータ圧縮処理に必要な資源を抑えることができる。
【０１４１】
上記基準値算出部（１４５；オフセット量決定部２０）は、上記処理装置（ＣＰＵ９１１）を用いて、上記一連の値（観測値）のうち上記予測部（１２０；予測器１０）が予測値を算出した値それぞれについて、上記一連の値のうち上記値よりも前の値について上記予測残差算出部（１２５；オフセット量決定部２０）が算出した予測残差（予測誤差）に基づいて、上記複数の残差基準値（予測誤差代表値）を算出する。
【０１４２】
これにより、復元時には、他の情報を必要とせず、既に復元した値だけに基づいて、基準値算出部１４５が算出した残差基準値とまったく同じ残差基準値を算出できるので、損失なく値を復元することが可能となる。
【０１４３】
上記基準値算出部（１４５；オフセット量決定部２０）は、上記処理装置（ＣＰＵ９１１）を用いて、上記一連の値（観測値）のうち上記予測部（１２０；予測器１０）が予測値を算出したすべての値について上記予測残差算出部（１２５；オフセット量決定部２０）が算出した予測残差（予測誤差）に基づいて、上記複数の残差基準値（予測誤差代表値）を算出する。
上記符号化部（１９０；ヘッダ生成部８０）は、上記一連の値を表わす符号として、更に、上記基準値算出部が算出した複数の残差基準値を表わす残差基準値符号を生成する。
【０１４４】
すべての予測残差から残差基準値を算出するので、圧縮率が更に高くなる残差基準値を算出することができる。復号時には、残差基準値符号から復元した残差基準値を使って値を復元するので、まだ復元していない値に基づいて残差基準値が算出されていても、損失なく値を復元することが可能となる。また、復号時に残差基準値を算出する計算が不要となるので、処理装置の処理能力などデータ復元処理に必要な資源を抑えることができる。
【０１４５】
以上説明したデータ復元装置（２００）は、データを処理する処理装置（ＣＰＵ９１１）と、符号取得部（２９５；選択部４５，残差復号部５５）と、復元予測部（２２０；予測器１５）と、復元基準値選択部（２８０；選択部４５）と、値復元部（２３０；６５）とを有する。
上記符号取得部は、上記処理装置を用いて、一連の値（観測値）のうち少なくともいずれかの値を表わす符号として、複数の残差基準値（予測誤差代表値）のなかからどの残差基準値を選択すべきかを表わす選択基準値符号（基準値インデックス）と、基準残差（残差）を表わす基準残差符号との組を取得する。
上記復元予測部は、上記処理装置を用いて、上記符号取得部が選択基準値符号と基準残差符号との組を取得した値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出する。
上記復元基準値選択部は、上記処理装置を用いて、複数の残差基準値のなかから、上記符号取得部が取得した選択基準値符号によって示される残差基準値を選択する。
上記値復元部は、上記処理装置を用いて、上記復元予測部が算出した予測値と、上記基準値選択部が選択した残差基準値と、上記符号取得部が取得した基準残差符号が表わす基準残差との合計を算出することにより、上記値を復元した復元値を算出する。
【０１４６】
これにより、データ圧縮装置１００が圧縮した元の値を損失なく復元することができる。
【０１４７】
以上説明したデータ圧縮装置（１００）及びデータ復元装置（２００）及びデータ処理システム（データ圧縮記憶システム８００）は、コンピュータプログラムをコンピュータが実行することにより実現することができる。
コンピュータをデータ圧縮装置またはデータ復元装置またはデータ処理システムとして機能させるコンピュータプログラムによれば、一連の値を効率よく圧縮して記憶することができる。
【符号の説明】
【０１４８】
１０，１５ 予測器、１１ 値記憶部、１２ 予測値記憶部、２０，２５ オフセット量決定部、２１ オフセット量記憶部、３０，３５ 基準値生成部、４０ 最小残差選択部、４５ 選択部、５０ 残差符号化部、５５ 残差復号部、６５，２３０ 値復元部、７０，７５ パラメータ記憶部、８０ ヘッダ生成部、８５ ヘッダ取得部、１００ データ圧縮装置、１１０ データ入力部、１１５ データ記憶部、１２０ 予測部、１２５，２２５ 予測残差算出部、１４０，２４０ 予測残差記憶部、１４５ 基準値算出部、１５０，２５０ パラメータ算出部、１８０ 基準値選択部、１８５ 基準残差算出部、１９０ 符号化部、１９５ 符号出力部、２００ データ復元装置、２１０ データ出力部、２１５ 値記憶部、２２０ 復元予測部、２４５ 復元基準値算出部、２８０ 復元基準値選択部、２９０ 復号部、２９５ 符号取得部、３０１〜３０４ 領域、８００ データ圧縮記憶システム、８１０ 観測装置、８２０ データ記憶装置、９０１ 表示装置、９０２ キーボード、９０３ マウス、９０４ ＦＤＤ、９０５ ＣＤＤ、９０６ プリンタ装置、９０７ スキャナ装置、９１０ システムユニット、９１１ ＣＰＵ、９１２ バス、９１３ ＲＯＭ、９１４ ＲＡＭ、９１５ 通信装置、９２０ 磁気ディスク装置、９２１ ＯＳ、９２２ ウィンドウシステム、９２３ プログラム群、９２４ ファイル群、９３１ 電話器、９３２ ファクシミリ機、９４０ インターネット、９４１ ゲートウェイ、９４２ ＬＡＮ。
【技術分野】
【０００１】
この発明は、データを圧縮するデータ圧縮装置に関する。
【背景技術】
【０００２】
近年、センサの小型化や低価格化が進み、散在する装置群や大規模システムに大量のセンサを設置してその状態を連続的に取得・蓄積し、分析や監視に利用したいというニーズが高まっている。多数のセンサから連続的に到来するストリームデータは、そのまま蓄積すると膨大な量になってしまうため、圧縮率の良い圧縮方式が不可欠となる。
高変動な時系列データでは、線形予測を適用しても予測精度に限界があるため、高い圧縮率が得にくい。特許文献１には、複数の線形予測器を使って先行する値から符号化対象値に対する予測値を複数生成し、符号化対象値に最も近いものを選択して、その予測残差を符号化する方式が記載されている。その際、その予測値（予測器）を伸張時に識別するためのインデックスも合わせて符号化する。このように複数の予測値を用意することにより、予測値を１点だけ用いるよりも広範な領域をカバーすることが出来る。このため、インデックス符号を補助情報として保存する必要は生じるものの、予測残差は小さくなると期待出来る。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１１−１０９９９６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
独立の線形予測器が推定した複数の予測値を単純に集めただけでは、ｎ値の集合として誤差の期待値を最小化できない。このため、得られる予測値の集合は冗長なものであり、典型的には予測値が必要以上に集中してしまい、複数点をおいて広範な領域をカバーする効果が得られない。カバーされる領域を広げるため予測点の数を増やすと、予測点を指定するインデックス符号が長くなり、圧縮率が低下する。
この発明は、例えば上記のような課題を解決するためになされたものであり、センサデータ等の数値データ、特に値の変動が激しく予測が困難な時系列データを対象として、圧縮率の高い可逆圧縮方式を得ることを目的とする。
【課題を解決するための手段】
【０００５】
この発明にかかるデータ圧縮装置は、データを処理する処理装置と、予測部と、予測残差算出部と、基準値算出部と、基準値選択部と、基準残差算出部と、符号化部とを有し、
上記予測部は、上記処理装置を用いて、一連の値のうち少なくともいずれかの値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出し、
上記予測残差算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記値と上記予測部が算出した予測値との差を算出することにより、予測残差を算出し、
上記基準値算出部は、上記処理装置を用いて、上記予測残差算出部が算出した予測残差に基づいて、複数の残差基準値を算出し、
上記基準値選択部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記基準値算出部が算出した複数の残差基準値のなかから、上記予測残差算出部が算出した予測残差に最も近い残差基準値を選択し、
上記基準残差算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記予測残差算出部が算出した予測残差と上記基準値選択部が選択した残差基準値との差を算出することにより、基準残差を算出し、
上記符号化部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記値を表わす符号として、上記基準値選択部が上記複数の残差基準値のうちどの残差基準値を選択したかを表わす選択基準値符号と、上記基準残差算出部が算出した基準残差を表わす基準残差符号との組を生成することを特徴とする。
【発明の効果】
【０００６】
この発明にかかるデータ圧縮装置によれば、一連の値を効率よく圧縮することができる。
【図面の簡単な説明】
【０００７】
【図１】実施の形態１におけるデータ圧縮記憶システム８００の全体構成の一例を示すシステム構成図。
【図２】実施の形態１におけるデータ圧縮装置１００やデータ復元装置２００の外観の一例を示す斜視図。
【図３】実施の形態１におけるデータ圧縮装置１００やデータ復元装置２００のハードウェア資源の一例を示す図。
【図４】実施の形態１におけるデータ圧縮装置１００の機能ブロックの構成の一例を示すブロック構成図。
【図５】実施の形態１におけるデータ圧縮装置１００の予測動作及び残差生成動作を説明するための図。
【図６】実施の形態１におけるデータ圧縮処理の流れの一例を示すフローチャート図。
【図７】実際の時系列データと、第一比較例において符号化される残差との関係を表わすグラフ図。
【図８】実際の時系列データと、第二比較例において符号化される残差との関係を表わすグラフ図。
【図９】実際の時系列データと、実施の形態１におけるデータ圧縮装置１００において符号化される残差との関係を表わすグラフ図。
【図１０】実施の形態１におけるデータ復元装置２００の機能ブロックの構成の一例を示すブロック構成図。
【図１１】実施の形態１におけるデータ伸長処理の流れの一例を示すフローチャート図。
【図１２】実施の形態２におけるデータ圧縮装置１００の機能ブロックの構成の一例を示すブロック構成図。
【図１３】実施の形態２におけるデータ圧縮処理の流れの一例を示すフローチャート図。
【図１４】実施の形態２におけるデータ復元装置２００の機能ブロックの構成の一例を示すブロック構成図。
【図１５】実施の形態２におけるデータ伸長処理の流れの一例を示すフローチャート図。
【図１６】実施の形態３におけるオフセット量決定部２０が算出する予測誤差代表値の一例を示す図。
【図１７】実施の形態４におけるデータ圧縮装置１００の機能ブロックの一例を示すブロック構成図。
【図１８】実施の形態４におけるデータ復元装置２００の機能ブロックの構成の一例を示すブロック構成図。
【図１９】実施の形態４におけるデータ圧縮処理Ｓ６１０の流れの一例を示すフローチャート図。
【図２０】実施の形態４におけるデータ復元処理Ｓ６２０の流れの一例を示すフローチャート図。
【発明を実施するための形態】
【０００８】
実施の形態１．
実施の形態１について、図１〜図１１を用いて説明する。
【０００９】
図１は、この実施の形態におけるデータ圧縮記憶システム８００の全体構成の一例を示すシステム構成図である。
データ圧縮記憶システム８００（データ圧縮システム）は、観測したデータを圧縮して記憶しておき、必要に応じて復元して取り出すことができるシステムである。データ圧縮記憶システム８００は、例えば、観測装置８１０と、データ圧縮装置１００と、データ記憶装置８２０と、データ復元装置２００とを有する。
観測装置８１０は、何らかの観測対象を観測して、観測した結果を表わす観測データを生成する。観測装置８１０は、観測対象を定期的もしくは不定期に繰り返し観測し、その都度、観測データを生成する。したがって、観測装置８１０は、時系列的な順序がある一連の観測データを生成する。
観測装置８１０が生成する観測データは、数値データであり、例えば０以上２のｎ乗未満の整数値をｎビットの２進数で表わす。ここで、ｎは、２以上の整数であり、例えば、１６や３２である。
あるいは、観測データは、例えば０以上１未満の２のｎ乗分の１の倍数をｎビットの固定小数点数形式の２進数で表わすものであってもよい。この場合、観測データは、観測した実際の数値を２のｎ乗倍した整数を表わすものとして取り扱うことができるから、０以上２のｎ乗未満の整数値をｎビットの２進数で表わす場合と同様に扱うことができる。
または、観測データは、例えば所定の範囲内の実数値を、ＩＥＥＥ（電気電子学会）７５４形式のような浮動小数点数形式で表わすものであってもよい。浮動小数点数形式は、例えば、符号部・仮数部・指数部からなり、それぞれの部分は、整数値として取り扱うことができるから、この場合、観測データは、３つの整数値の組（あるいは、符号部を仮数部の一部として扱って、２つの整数値の組）として扱うことができる。
更に、観測データは、例えば複素数やベクトルなどのように、複数の整数値や実数値の組を表わすものであってもよい。
【００１０】
データ圧縮装置１００は、観測装置８１０が生成した一連の観測データを圧縮して、圧縮データを生成する。例えば、１つの観測データがｎビットであり、それがｋ個ある場合、一連の観測データ全体のビット数は、ｋ×ｎビットである。データ圧縮装置１００は、これを圧縮して、ｋ×ｎビットよりも少ないビット数で同じ情報を表わす圧縮データを生成する。すなわち、データ圧縮装置１００が一連の観測データを圧縮する圧縮方式は、可逆圧縮であり、データ圧縮装置１００が圧縮した圧縮データから、元の一連の観測データと全く同じデータを復元することができる。
【００１１】
データ記憶装置８２０は、データ圧縮装置１００が生成した圧縮データを蓄積して記憶する。データ記憶装置８２０は、例えば交換可能な記録媒体を用いて、圧縮データを記憶する。データ記憶装置８２０は、観測装置８１０が生成した一連の観測データよりもビット数が少ない圧縮データを記憶するので、観測装置８１０が生成した一連の観測データをそのまま記憶する場合と比べて、記録媒体の記憶容量が小さくて済む。
【００１２】
データ復元装置２００は、データ記憶装置８２０が記憶した圧縮データを伸長して、元の観測データと同じデータを復元する。データ復元装置２００は、復元したデータを出力する。データ記憶装置８２０が記憶した圧縮データは、可逆圧縮方式によって圧縮されているので、元の観測データを完全な形で復元することができる。
【００１３】
図２は、この実施の形態におけるデータ圧縮装置１００やデータ復元装置２００の外観の一例を示す斜視図である。
データ圧縮装置１００及びデータ復元装置２００は、それぞれ、システムユニット９１０、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）やＬＣＤ（液晶）の表示画面を有する表示装置９０１、キーボード９０２（Ｋｅｙ・Ｂｏａｒｄ：Ｋ／Ｂ）、マウス９０３、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、コンパクトディスク装置９０５（ＣＤＤ）、プリンタ装置９０６、スキャナ装置９０７などのハードウェア資源を備え、これらはケーブルや信号線で接続されている。
システムユニット９１０は、コンピュータであり、ファクシミリ機９３２、電話器９３１とケーブルで接続され、また、ローカルエリアネットワーク９４２（ＬＡＮ）、ゲートウェイ９４１を介してインターネット９４０に接続されている。
【００１４】
図３は、この実施の形態におけるデータ圧縮装置１００やデータ復元装置２００のハードウェア資源の一例を示す図である。
データ圧縮装置１００及びデータ復元装置２００は、それぞれ、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、通信装置９１５、表示装置９０１、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５、プリンタ装置９０６、スキャナ装置９０７、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部の一例である。通信装置９１５、キーボード９０２、スキャナ装置９０７、ＦＤＤ９０４などは、入力部、入力装置の一例である。
また、通信装置９１５、表示装置９０１、プリンタ装置９０６などは、出力部、出力装置の一例である。
【００１５】
通信装置９１５は、ファクシミリ機９３２、電話器９３１、ＬＡＮ９４２等に接続されている。通信装置９１５は、ＬＡＮ９４２に限らず、インターネット９４０、ＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）などに接続されていても構わない。インターネット９４０或いはＩＳＤＮ等のＷＡＮに接続されている場合、ゲートウェイ９４１は不用となる。
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。
【００１６】
上記プログラム群９２３には、以下に述べる実施の形態の説明において「〜部」として説明する機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
ファイル群９２４には、以下に述べる実施の形態の説明において、「〜の判定結果」、「〜の計算結果」、「〜の処理結果」として説明する情報やデータや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵの動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
また、以下に述べる実施の形態の説明において説明するフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、ＦＤＤ９０４のフレキシブルディスク、ＣＤＤ９０５のコンパクトディスク、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｋ）等の記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【００１７】
また、以下に述べる実施の形態の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、以下に述べる「〜部」としてコンピュータを機能させるものである。あるいは、以下に述べる「〜部」の手順や方法をコンピュータに実行させるものである。
【００１８】
なお、データ圧縮装置１００とデータ復元装置２００とは、物理的に異なる装置であってもよいし、物理的に一つの装置であってもよい。また、以下に説明するデータ圧縮装置１００やデータ復元装置２００の各ブロックを、物理的に異なる装置によって実現し、複数の装置が全体としてデータ圧縮装置１００やデータ復元装置２００として機能する構成であってもよい。
【００１９】
図４は、この実施の形態におけるデータ圧縮装置１００の機能ブロックの構成の一例を示すブロック構成図である。
データ圧縮装置１００は、観測装置８１０が生成した一連の観測データを、入力データとして入力する。データ圧縮装置１００は、圧縮データとして、ヘッダデータと、残差符号列データと、基準値インデックスデータとを生成する。
データ圧縮装置１００は、予測器１０と、オフセット量決定部２０と、基準値生成部３０と、最小残差選択部４０と、残差符号化部５０と、パラメータ記憶部７０と、ヘッダ生成部８０とを有する。
【００２０】
予測器１０（予測部）は、入力データの先行する値から後続する符号化対象値の予測値を決定する。
オフセット量決定部２０（予測残差算出部・予測残差分類部・基準値算出部）は、予測値の予測誤差の分布に基づいて、予測誤差からの距離が最小となるような予測誤差代表値の集合を決定する。
基準値生成部３０は、予測値と予測誤差代表値の集合を元に、複数の残差基準値を決定する。
最小残差選択部４０（基準値選択部・符号化部）は、複数の残差基準値の中から、符号化対象値に最も近いものを選択して、該誤差基準値と符号化対象値の差を残差（基準残差）として出力するとともに、選択した残差基準値のインデックス（選択基準値符号）を圧縮データに出力する。
残差符号化部５０（符号化部）は、残差を符号語（基準残差符号）に変換して圧縮データに出力する。
パラメータ記憶部７０は、オフセット量決定部２０や基準値生成部３０が用いるパラメータをあらかじめ記憶している。
ヘッダ生成部８０（符号化部）は、パラメータ記憶部７０が記憶したパラメータなどに基づいて、ヘッダデータを生成する。
【００２１】
図５は、この実施の形態におけるデータ圧縮装置１００の予測動作及び残差生成動作を説明するための図である。
データ圧縮装置１００の特徴は、予測符号化における予測方式（残差生成方式）にある。
【００２２】
まず、データ圧縮装置１００における予測処理の概要を説明する。
【００２３】
黒丸（●）の点は、入力データの時系列を示している。予測処理は、時系列に沿って行う。この図は、入力データの先頭の値ｘ１から時刻ｔ−１の値ｘｔ−１までの符号化が完了しており、これから時刻ｔの値ｘｔを符号化しようとしている状態を示している。
バツ印（×）で示す点は、予測器１０による予測点である。この例において、予測器１０は、直前の値ｘｔ−１をそのまま次の時刻の予測値ｐｔとして用いる。ただし、予測器１０は、これに限定するものではなく、他の線形予測器であってもよいし、非線形予測器であってもよい。例えば、予測器１０は、次の時刻の予測値ｐｔとして、直前のｍ個の値ｘｔ−ｍ，…，ｘｔ−１の平均値を算出する構成であってもよい。あるいは、予測器１０は、次の時刻の予測値ｐｔとして、直前の２つの値ｘｔ−２，ｘｔ−１の差を直前の値ｘｔ−１に加えた値を算出する構成であってもよい。または、予測器１０は、直前のｋ個の値ｘｔ−ｋ，…，ｘｔ−１を通る［ｋ−１］次曲線を算出し、次の時刻の予測値ｐｔとして、算出した［ｋ−１］次曲線上の点の座標を算出する構成であってもよい。あるいは、予測器１０は、直前のｍ個の値ｘｔ−ｍ，…，ｘｔ−１を近似する［ｋ−１］次曲線を最小自乗法などにより算出し（ただし、ｍ＞ｋ）、次の時刻の予測値ｐｔとして、算出した［ｋ−１］次曲線上の点の座標を算出する構成であってもよい。また、観測対象の物理モデルがわかっている場合には、予測器１０は、例えばカルマンフィルタなどの予測フィルタを用いて、次の時刻の予測値ｐｔを算出する構成であってもよい。
【００２４】
図中「履歴」で囲った部分における上下の矢印は、時刻ｔ−Ｎ，…，ｔ−１における予測誤差ｅｔ−Ｎ，…，ｅｔ−１を表している。この予測誤差の履歴を図に示すように集めることで、現在符号化対象としている予測値ｐｔに対してどの程度の予測誤差ｅｔが発生するか（予測誤差の分布）を予測することができる。
【００２５】
オフセット量決定部２０は、予測誤差の分布に対し、ｋ−ｍｅａｎｓ法（ケー平均法）によるクラスタリングを適用することにより、分布を代表するｎ個の代表値（セントロイド）｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝を得ることができる。これらの代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝は、ｋ−ｍｅａｎｓ法のアルゴリズムから、各予測誤差から最近傍点への距離を最小にするようなｎ個の値のセットになっている。白抜き正方形（□）は、代表値の例を示す。この例において、代表値の数ｎは、４である。代表値の数ｎは、他の数であってもよいが、２の累乗（２，４，８，１６，…）であれば、符号化の効率が良いので望ましい。
なお、各クラスタの代表値は、各クラスタに属する予測誤差の平均値のほか、例えば、各クラスタに属する予測誤差の中央値、最頻値などであってもよい。
また、クラスタリングの方式は、ｋ−ｍｅａｎｓ法が望ましいが、他の非階層型クラスタリングであってもよいし、ウォード法など階層型クラスタリングであってもよい。なお、分割するクラスタ数をあらかじめ定めておくのではなく、予測誤差の分布に基づいて、クラスタ数を決定する方式であってもよい。
【００２６】
基準値生成部３０は、これら予測誤差の代表値をオフセットとして、時刻ｔの予測値ｐｔに加えることにより、ｎ個の残差基準値を生成する。最小残差選択部４０は、残差基準値の中から、符号化対象とする実測値ｘｔに最も近いものを選ぶ。残差符号化部５０は、選択した残差基準値と実測値との差分を残差として符号化し、圧縮データに保存する。また、残差基準値のインデックスも同時に圧縮データに保存する。図では、上から２番目の残差基準値ｅ￣２が最も実測値に近い。この残差基準値を用いた残差は、予測値そのものによる残差よりも小さくなっている。
【００２７】
このようにして、予測誤差履歴の代表値ｎ点に基づいて残差基準値として置くことにより、残差に対する期待値を小さくすることが出来る。
【００２８】
図６は、この実施の形態におけるデータ圧縮処理の流れの一例を示すフローチャート図である。
【００２９】
ステップＳ０１において、ヘッダ生成部８０は、入力データに基づいて、データサイズ（入力データの時系列の長さ）Ｔを算出する。ヘッダ生成部８０は、算出したデータサイズＴや、履歴の個数Ｎや代表値の数（残差基準値の数）ｎなどパラメータ記憶部７０が記憶したパラメータに基づいて、ヘッダデータを生成する。ヘッダ生成部８０が生成するヘッダデータは、データサイズＴや履歴の個数Ｎや代表値の数ｎなどのパラメータを表わす。ヘッダ生成部８０は、生成したヘッダデータを圧縮データの先頭に保存する。これらは、例えば固定長バイナリ形式で保存する。
ステップＳ１０において、データ圧縮装置１００は、すべての入力データ｛ｘｔ｜ｔ＝１，…，Ｔ｝に対し、処理が完了したかを判定する。処理が完了した場合、データ圧縮装置１００は、データ圧縮処理を終了する。処理が完了していない場合、データ圧縮装置１００は、Ｓ２０へ進む。
ステップＳ２０において、オフセット量決定部２０は、次の時刻の予測値ｐｔに対応するｎ個の予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝を決定する。この代表値は、時刻ｔ−Ｎ，…，ｔ−１におけるＮ個（Ｎ＞ｎ）の予測誤差の履歴｛ｅｔ−Ｎ，…，ｅｔ−１｝を対象にｋ−ｍｅａｎｓ法を適用して、ｎ個のクラスタに分類したときのクラスタ重心として得ることができる。ｋ−ｍｅａｎｓ法では、予測誤差の履歴に対し次の式で表わされる関数ｆの値を準最小化する代表値を得ることができる。
【数１１】
なお、予測誤差ｅｔは、実測値ｘｔと予測値ｐｔとの差として、次の式により与えられる。
【００３０】
ｅｔ＝ｘｔ−ｐｔ
【００３１】
ステップＳ３０において、予測器１０は、入力データの先行する値から後続する符号化対象値ｘｔの予測値ｐｔを決定する。ここでは、最も単純な予測の例として、次の式のように、時刻ｔ−１の値ｘｔ−１を時刻ｔの値の予測値ｐｔとして用いる。
【００３２】
ｐｔ＝ｘｔ−１
【００３３】
ステップＳ４０において、基準値生成部３０は、上記予測値ｐｔと上記予測誤差代表値の集合｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝とを元に、複数の残差基準値を決定する。予測値をｐｔ、ｎ個の予測誤差代表値を｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝とすると、基準値生成部３０は、残差基準値｛ｘ￣ｔ，ｉ｜ｉ＝１，…，ｎ｝を、両者の和として次の式により求める。
【数１２】
【００３４】
ステップＳ５０において、最小残差選択部４０は、残差基準値｛ｘ￣ｔ，ｉ｜ｉ＝１，…，ｎ｝の中から、符号化対象値ｘｔに最も近いものを選択して、選択した残差基準値ｘ￣ｔ，ｉ＊と符号化対象値ｘｔとの差を残差ｒｔとして出力するとともに、選択した残差基準値のインデックスｉ＊を圧縮データに出力する。
【数１３】
なお、インデックスｉ＊は、次の式で表わされる、基準値の種類数ｎを表現可能な最小のビット数ｂで、固定長バイナリ形式により出力する。
【数１４】
なお、代表値の数ｎが２の累乗でない場合、インデックスｉ＊を表わす符号のビット数を少しでも短くするため、例えばＣＢＴ（完全二分木）符号を用いてインデックスｉ＊を符号化する構成としてもよい。
【００３５】
ステップＳ６０において、残差符号化部５０は、前記残差ｒｔを符号語に変換して圧縮データに出力する。
符号化対象値が整数値である場合、残差符号化部５０は、例えば、残差ｒｔの正負符号１ビットと、｜ｒｔ｜の値をガンマ符号やデルタ符号や指数ゴロム符号により符号化した符号とを出力する。例えば、ｒｔ≧０の場合、残差符号化部５０は、１ビットの正負符号「０」と、ｒｔ＋１をデルタ符号で符号化した符号とを出力する。ｒｔ＜０の場合、残差符号化部５０は、１ビットの正負符号「１」と、｜ｒｔ｜をデルタ符号で符号化した符号とを出力する。
あるいは、残差符号化部５０は、ライス符号やゴロム符号など、符号化する値が小さいほど符号長が短くなる性質を有する他の符号化方式を用いる構成であってもよい。ライス符号（ゴロム−ライス符号）における次数ｋやゴロム符号における法ｍなどのパラメータは、あらかじめ定めた値を用いる構成であってもよいし、生成する符号のビット長が最も短くなるよう、残差符号化部５０が決定する構成であってもよい。例えば、残差符号化部５０は、マルチパス構成として、第一パスで全ての残差｛ｐｔ｜ｔ＝１，…，Ｎ｝を得る。第二パスにおいて、残差符号化部５０は、次数ｋを０から元のバイナリビット数まで変化させ、それぞれの次数ｋによる符号化を試行する。残差符号化部５０は、符号化の結果、最も符号長が短くなる次数ｋを選択し、符号化に用いるパラメータに決定する。残差符号化部５０は、決定したパラメータを表わす符号を、圧縮データの一部として出力する。
【００３６】
符号化対象値が浮動小数点数形式によって表わされる実数値である場合、残差符号化部５０は、例えば、上述した残差ｒｔの代わりに、指数部・仮数部について残差を求め、それぞれを整数とみなして上記符号化を行う。
【００３７】
次に、実際の時系列データに適用した例を用いて、この実施の形態におけるデータ圧縮装置１００の効果を説明する。
【００３８】
図７は、実際の時系列データと、第一比較例において符号化される残差との関係を表わすグラフ図である。
横軸は、時刻を表わす。縦軸は、時系列データの値を表わす。折れ線は、各時刻における符号化対象値を結んだ線である。バツ印（×）は、第一比較例における予測器が予測した予測値を示す。矢印は、符号化される残差を示す。
【００３９】
第一比較例における予測器は、この実施の形態における予測器１０と同様、時刻ｔにおける符号化対象値の予測値ｐｔとして、直前の時刻ｔ−１における値ｘｔ−１を用いる。また、第一比較例における残差符号化部は、符号化対象値ｘｔと、予測器が予測した予測値ｐｔとの差（予測誤差）を、そのまま符号化する。
【００４０】
第一比較例では、符号化される残差が大きいので、圧縮効率が低い。線形予測の次数を増やし、データに対し係数を最適に決定するなどしたとしても、このような予測誤差は発生する。特に、変動が大きなデータの場合は、予測誤差が相対的に大きくなる。
【００４１】
図８は、実際の時系列データと、第二比較例において符号化される残差との関係を表わすグラフ図である。
横軸は、時刻を表わす。縦軸は、時系列データの値を表わす。折れ線は、各時刻における符号化対象値を結んだ線である。バツ印（×）は、第二比較例における複数の予測器がそれぞれ予測した予測値を示す。矢印は、符号化される残差を示す。
【００４２】
第二比較例には、予測器が４つある。第一の予測器は、時刻ｔにおける符号化対象値の予測値ｐｔとして、直前の時刻ｔ−１における値ｘｔ−１を用いる。第二の予測器は、時刻ｔにおける符号化対象値の予測値ｐｔとして、２つ前の時刻ｔ−２における値ｘｔ−２を用いる。第三の予測器は、時刻ｔにおける符号化対象値の予測値ｐｔとして、３つ前の時刻ｔ−３における値ｘｔ−３を用いる。第四の予測器は、時刻ｔにおける符号化対象値の予測値ｐｔとして、４つ前の時刻ｔ−４における値ｘｔ−４を用いる。
第二比較例における残差符号化部は、４つの予測器が算出した４つの予測値ｐｔのうち、符号化対象値ｘｔに一番近い予測値ｐｔと、符号化対象値ｘｔとの差を、符号化する。
【００４３】
予測値１点だけを使う第一比較例と比べると、残差が小さくなっていることがわかる。しかし、已然として、大きな残差が残っている。このように独立な予測値を複数持ってきても、典型的にはグラフの左側に見られるように必要以上に予測点が集中してしまい、予測値の変動領域を適切にカバーすることができない。
【００４４】
図９は、実際の時系列データと、この実施の形態におけるデータ圧縮装置１００において符号化される残差との関係を表わすグラフ図である。
横軸は、時刻を表わす。縦軸は、時系列データの値を表わす。折れ線は、各時刻における符号化対象値を結んだ線である。バツ印（×）は、第二比較例における複数の予測器がそれぞれ予測した予測値を示す。各時刻における符号化対象値から放射状に伸びる細線は、予測誤差の履歴を示す。白抜き正方形（□）は、基準値生成部３０が生成した残差基準値を示す。矢印は、残差符号化部５０が符号化する残差を示す。
【００４５】
データ圧縮装置１００は、第二比較例と同様、４つの値のなかから符号化対象値に最も近い値を選んで、符号化する残差を求める。しかし、第二比較例と異なり、その４つの値は、予測誤差の履歴から得られた代表値であるから、値の変動を適切にカバーできる。第二比較例よりも符号化対象値に近い予測点（残差基準値）が存在し、残差が小さくなるので、圧縮効率が高くなる。
【００４６】
図１０は、この実施の形態におけるデータ復元装置２００の機能ブロックの構成の一例を示すブロック構成図である。
データ復元装置２００は、データ圧縮装置１００が生成した残差符号列データと、基準値インデックスデータと、ヘッダデータとを、圧縮データとして入力する。データ復元装置２００は、入力した圧縮データを損失なく伸長して、データ圧縮装置１００が入力した入力データと同じ出力データを復元する。
データ復元装置２００は、予測器１５と、オフセット量決定部２５と、基準値生成部３５と、選択部４５と、残差復号部５５と、値復元部６５と、パラメータ記憶部７５と、ヘッダ取得部８５とを有する。
【００４７】
ヘッダ取得部８５は、圧縮データの先頭から、ヘッダデータを取得する。
パラメータ記憶部７５は、ヘッダ取得部８５が取得したヘッダデータが表わすデータサイズＴや履歴の個数Ｎや代表値の数ｎなどのパラメータを記憶する。
予測器１５（復元予測部）は、データ圧縮装置１００の予測器１０と同じ方式を用いて、値復元部６５が生成した出力データの先行する値から後続する復号対象値の予測値を決定する。
オフセット量決定部２５は、データ圧縮装置１００のオフセット量決定部２０と同じ方式を用いて、予測値の予測誤差の分布に基づいて、予測誤差からの距離が最小となるような予測誤差代表値の集合を決定する。
基準値生成部３５は、予測値と予測誤差代表値の集合を元に、複数の残差基準値を決定する。
選択部４５は、基準値インデックスデータのなかから、復号対象値についてのインデックスを取得する。選択部４５は、複数の残差基準値の中から、取得したインデックスにより示される残差基準値を選択する。
残差復号部５５は、残差符号列データのなかから、復号対象値についての符号語を取得する。残差復号部５５は、取得した符号語を復号して、残差を算出する。
値復元部６５は、選択部４５が選択した残差基準値と、残差復号部５５が算出した残差とを合計して、元の値を復元し、出力データに出力する。
【００４８】
図１１は、この実施の形態におけるデータ伸長処理の流れの一例を示すフローチャート図である。
【００４９】
ステップＳ０１ａにおいて、ヘッダ取得部８５は、圧縮データの先頭からヘッダデータを取得し、データサイズ（入力データの時系列の長さ）Ｔ、履歴の個数Ｎ、および代表値の数（残差基準値の数）ｎなどのパラメータを読み出す。これらは固定長バイナリ形式で保存されているため特段の伸張処理は不要である。パラメータ記憶部７５は、ヘッダ取得部８５が読み出したデータサイズＴ、履歴の個数Ｎ、代表値の数ｎなどのパラメータを記憶する。
【００５０】
ステップ１０ａにおいて、データ復元装置２００は、ループの終了判定処理をする。以降のステップの繰り返し回数がデータサイズＴより少ない場合、データ復元装置２００は、Ｓ２０へ進む。繰り返し回数がデータサイズＴに達した場合、データ復元装置２００は、データ伸長処理を終了する。
【００５１】
ステップＳ２０において、オフセット量決定部２５は、予測誤差のクラスタリング処理を行う。ステップＳ３０において、予測器１５は、伸張済みの値に基づく予測を行う。ステップＳ４０において、基準値生成部３５は、複数の残差基準値を決定する。これらの処理内容は、データ圧縮処理におけるステップＳ２０〜ステップＳ４０と同じなので、説明を省略する。
【００５２】
ステップＳ５０ａにおいて、選択部４５は、基準値インデックスデータ（圧縮データ）から、残差基準値のインデックスｉ＊を読み出す。残差復号部５５は、残差符号列データ（圧縮データ）から、符号化した残差ｒｔを読み出す。インデックスがｌｏｇ２ｎを超えない最小の整数をビット数とする固定長バイナリ形式で保存されている場合、特段の伸張処理は不要である。残差ｒｔは、例えば、前述のように正負符号１ビットと、絶対値を表わすデルタ符号とにより保存されている。デルタ符号は、可変長符号であるが、一意復号可能であり、瞬時復号可能であるから、データを先頭から読んで行くことで符号長を知ることができ、符号語を読み出すことができる。
【００５３】
ステップＳ６０ａにおいて、残差復号部５５は、残差ｒｔを復号する。
【００５４】
ステップＳ７０ａにおいて、値復元部６５は、上記得られた残差ｒｔを、上記インデックスで参照される残差基準値（値はステップＳ４０で得られる）に加えることにより、元の値ｘｔを得る。
【００５５】
以上のようにして、データ復元装置２００は、データ圧縮装置１００が圧縮したデータを損失なく伸張することができる。
【００５６】
以上のように、この実施の形態におけるデータ圧縮装置１００によれば、予測誤差の分布に基づいて残差の基準値を最小化するようなｎ値の集合を設定することができる。このため、インデックスビットの指定が必要なｎ値を用いる方式でありながら、ｎ値間の冗長性を抑え、効果的に予測点（残差基準点）を増やすことが可能であり、その結果として、優れた圧縮率を得ることができる。
【００５７】
なお、この実施の形態におけるデータ圧縮装置１００は、オンライン処理でクラスタリングを行い、予測値オフセットを決める。オフセット量決定部２０は、入力データに対する予測誤差の履歴より、予測誤差代表値の集合を逐次的に決定する。すなわち、符号化処理を１つずつ実行しながら逐次的に予測誤差履歴のクラスタリングを実行する。このように逐次更新される履歴を使うことにより、予測誤差履歴の局所的な分散を反映して残差基準点を置くことができる。このため、特に非定常な入力データに対し、優れた圧縮率を得ることができる。
【００５８】
また、この実施の形態におけるデータ圧縮装置１００は、予測誤差の代表値（オフセット）を得るためにｋ−ｍｅａｎｓクラスタリングを適用する。オフセット量決定部２０は、ｋ−ｍｅａｎｓ法によるクラスタリングを予測誤差の分布に適用して、予測誤差代表値の集合を決定する。これにより、予測誤差に対し分布を仮定せずに代表値を決定することができる。このため、本発明は離散値を取るようなセンサデータに対しても適用可能であり、汎用性の高い方式となっている。
【００５９】
実施の形態２．
実施の形態２について、図１２〜図１５を用いて説明する。
なお、実施の形態１と共通する部分については、同一の符号を付し、説明を省略する。
【００６０】
実施の形態１におけるデータ圧縮装置１００は、履歴に対し逐次的に予測誤差代表値の生成処理（クラスタリング）を実施・更新するのに対し、この実施の形態におけるデータ圧縮装置１００は、バッチ的に全入力データを対象に実行しておき、各時刻の予測点に対し、同じ予測誤差代表値（予測値に対するオフセット）を適用する。
【００６１】
図１２は、この実施の形態におけるデータ圧縮装置１００の機能ブロックの構成の一例を示すブロック構成図である。
データ圧縮装置１００は、実施の形態１で説明したブロックに加えて、更に、値記憶部１１と、予測値記憶部１２と、オフセット量記憶部２１とを有する。
【００６２】
値記憶部１１は、データ圧縮装置１００が入力した入力データ（観測データ）を記憶する。
予測値記憶部１２は、予測器１０が予測した予測値を記憶する。
オフセット量記憶部２１は、オフセット量決定部２０が決定した複数の代表値を記憶する。
【００６３】
図１３は、この実施の形態におけるデータ圧縮処理の流れの一例を示すフローチャート図である。
【００６４】
ステップＳ３０１は、実施の形態１におけるステップＳ３０に対応する。ステップＳ２０１は、実施の形態１におけるステップＳ２０に対応する。実施の形態１におけるステップＳ２０およびステップＳ３０は、ループの中にあり、逐次的に実行するのに対し、ステップＳ３０１およびステップＳ２０１は、ループの外に出ている。なお、実施の形態１で説明したデータ圧縮処理のステップと同じ番号を付けたステップの処理は、実施の形態１と同じなので、説明を省略する。
【００６５】
ステップＳ３０１において、予測器１０は、値記憶部１１が記憶した入力データの全ての値に対し線形予測を適用して、各値に対する予測値を得る。予測値記憶部１２は、予測器１０が予測した予測値を、ＲＡＭ９１４などのメモリに記憶する。
【００６６】
ステップＳ２０１において、オフセット量決定部２０は、値記憶部１１が記憶した入力データの各値を、予測値記憶部１２が記憶した予測値と比較して、全予測誤差データを得る。オフセット量決定部２０は、得られた全予測誤差データを実施の形態１と同様にクラスタリングして、ｎ個の予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝を得る。オフセット量記憶部２１は、オフセット量決定部２０が算出した予測誤差代表値を、ＲＡＭ９１４などのメモリに記憶する。ヘッダ生成部８０（符号化部）は、オフセット量記憶部２１が記憶したｎ個の予測誤差代表値を、圧縮データ（ヘッダデータ）に補助情報（残差基準値符号）として保存する。これらは例えば固定長バイナリ形式で保存する。
【００６７】
ステップＳ１０１において、データ圧縮装置１００は、ループの判定処理をする。データ圧縮装置１００は、入力データに対する全ての値に対し、符号化が完了しているかを判定する。符号化が完了している場合、データ圧縮装置１００は、データ圧縮処理を終了する。符号化が完了していない場合、データ圧縮装置１００は、ステップＳ４０〜ステップＳ６０の処理を実行する。
【００６８】
ステップＳ４０において、基準値生成部３０は、ステップＳ２０１でオフセット量記憶部２１が記憶した予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝を使って、基準値を生成する。
実施の形態１では、予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝の値が逐次変化するが、この実施の形態では、すべての入力データに対して同一の値を用いる。
【００６９】
それ以外の処理は、実施の形態１と同様なので、説明を省略する。
【００７０】
図１４は、この実施の形態におけるデータ復元装置２００の機能ブロックの構成の一例を示すブロック構成図である。
データ復元装置２００は、データ圧縮装置１００が生成した圧縮データから、元の入力データを損失なく伸張する。
データ復元装置２００は、実施の形態１で説明した機能ブロックと同様の機能ブロックを有するが、オフセット量決定部２５を有さない点が、実施の形態１のデータ復元装置２００と異なる。
【００７１】
ヘッダ取得部８５がヘッダデータから取得するパラメータには、データ圧縮装置１００のオフセット量決定部２０が算出したｎ個の予測誤差代表値が含まれる。パラメータ記憶部７５は、ｎ個の予測誤差代表値を含むパラメータを記憶する。
基準値生成部３５は、実施の形態１で説明したオフセット量決定部２５が算出した予測誤差代表値の代わりに、パラメータ記憶部７５が記憶した予測誤差代表値を使って、基準値を生成する。
【００７２】
図１５は、この実施の形態におけるデータ伸長処理の流れの一例を示すフローチャート図である。
なお、実施の形態１で説明したステップと同じ番号を付与したステップの処理は、実施の形態１と同じであるため、説明を省略する。
【００７３】
ステップＳ２０１ａにおいて、ヘッダ取得部８５は、ステップＳ０１ａで得た代表値の数ｎに基づいて、圧縮データより予測誤差代表値ｎ個を読み出す。これらが固定長バイナリ形式で保存されている場合、特段の伸張処理は不要である。
【００７４】
ステップＳ１０１ａにおいて、データ復元装置２００は、ループの終了判定処理をする。ステップＳ３０〜Ｓ７０ａの繰り返し回数が、ステップＳ０１ａで得たデータサイズＴの回数に達した場合、データ復元装置２００は、データ伸長処理を終了する。繰り返し回数がデータサイズＴに達していない場合、データ復元装置２００は、ステップＳ３０〜Ｓ７０ａの処理を実行する。
【００７５】
ステップＳ４０において、基準値生成部３５は、予測器１５が予測した予測値と、パラメータ記憶部７５が記憶したｎ個の予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝それぞれとの和を算出することにより、ｎ個の基準値を生成する。
【００７６】
それ以外のステップの処理は、実施の形態１と同様なので、説明を省略する。
【００７７】
以上のようにして、本発明によるデータ圧縮装置で圧縮したデータを損失無く伸張することができる。
【００７８】
データ圧縮装置１００は、バッチ処理で事前にクラスタリング処理をする。オフセット量決定部２０は、予測誤差代表値の集合を、入力データに対する予測誤差の分布から一括処理により決定し、決定した予測誤差代表値の集合を圧縮後データに保存する。
【００７９】
このように、本実施の形態におけるデータ圧縮装置１００は、入力データ全体における予測誤差の分布に基づいて残差の基準値を最小化するようなｎ値の集合を設定することが出来る。このため、インデックスビットの指定が必要なｎ値を用いる方式でありながら、ｎ値間の冗長性を抑え、効果的に予測点（残差基準点）を増やすことができ、結果として、優れた圧縮率を得ることができる。
【００８０】
特に、定常と見なすことが可能なデータにおいては、このような構成としても、実施の形態１と同様に残差を小さくする効果を得ることができる。
【００８１】
また、実施の形態１では、各入力データごとに予測誤差代表値を算出したのに対し、この実施の形態では、すべての入力データに対して同一の予測誤差代表値を用いるので、予測誤差代表値の算出処理を１回だけ実行すればよい。計算量が少なくて済むので、データ圧縮処理を高速に実行することができる。
【００８２】
実施の形態３．
実施の形態３について、図１６〜図１６を用いて説明する。
なお、実施の形態１及び実施の形態２と共通する部分については、同一の符号を付し、説明を省略する。
【００８３】
この実施の形態では、予測誤差が正規分布に従って分布すると仮定できる場合について説明する。
【００８４】
オフセット量決定部２０は、あらかじめ、予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝を算出するための係数ａｊ（ｊは１以上ｎ／２以下の整数。）を記憶している。
オフセット量決定部２０は、例えば、予測誤差の履歴｛ｅ１，…，ｅｔ−１｝に基づいて、予測誤差の平均値ｍ及び標準偏差σを算出する。なお、予測誤差の平均値ｍが０になると期待できる場合、オフセット量決定部２０は、予測誤差の平均値ｍ＝０を仮定して、予測誤差の平均値ｍを算出せず、標準偏差σだけを算出する構成であってもよい。
オフセット量決定部２０は、算出した予測誤差の平均値ｍ及び標準偏差σに基づいて、予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝を算出する。オフセット量決定部２０は、例えば、次の式を用いて、予測誤差代表値を算出する。
【数１５】
ただし、ｎ’は、ｎ／２より小さくない最小の整数である。ｍは、オフセット量決定部２０が算出する予測誤差の平均値である。σは、オフセット量決定部２０が算出する予測誤差の標準偏差である。
【００８５】
図１６は、この実施の形態におけるオフセット量決定部２０が算出する予測誤差代表値の一例を示す図である。
横軸は、予測誤差を示す。縦軸は、予測誤差の確率分布を示す。
曲線３００は、予測誤差の確率分布関数である。この例は、予測誤差の平均値ｍが０の場合を示す。
斜線で示した領域３０１〜３０４は、予測誤差の確率分布をｎ個に分割した領域である。オフセット量決定部２０は、予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝として、各領域３０１〜３０４の重心を算出する。
予測誤差の確率分布が正規分布にしたがうと仮定できる場合、各領域の重心と平均値ｍとの差が、標準偏差σの何倍にあたるかを、あらかじめ計算しておくことができる。例えばｎ＝４の場合、予測誤差が下から２５％以内である領域３０１の重心は（ｍ−１．２７σ）、予測誤差が平均値より下の２５％以内である領域３０２の重心は（ｍ−０．３２５σ）、予測誤差が平均値より上の２５％以内である領域３０３の重心は（ｍ＋０．３２５σ）、予測誤差が上から２５％以内である領域３０４の重心は（ｎ＋１．２７σ）である。オフセット量決定部２０は、あらかじめａ１＝０．３２５、ａ２＝１．２７を記憶しておく。オフセット量決定部２０は、算出した標準偏差σに基づいて、各領域の重心を算出し、予測誤差代表値｛ｅ￣ｉ｜ｉ＝１，…，ｎ｝とする。
一般に、予測誤差が上からｂ１％〜ｂ２％の間（０≦ｂ１＜ｂ２≦１００）にある領域の重心ａは、
【数１６】
【００８６】
ただし、ｅｘｐはネイピア数を底とする指数関数である。ｅｒｆ−１は誤差関数ｅｒｆの逆関数である。
【００８７】
このように、正規分布を用いて、例えば、平均０で予測誤差履歴の分散を持つ正規分布の面積をｎ等分する各領域の重心に残差代表値を置き、そのような等分点がσの何倍に当たるかを予め装置に登録しておくことにより、データの分散に合わせて容易に代表値を決定することができる。
【００８８】
なお、予測誤差が従うと仮定する分布は、正規分布に限らず、他の分布であってもよい。
【００８９】
実施の形態４．
実施の形態４について、図１７〜図２０を用いて説明する。
なお、実施の形態１〜実施の形態３と共通する部分については、同一の符号を付し、説明を省略する。
【００９０】
図１７は、この実施の形態におけるデータ圧縮装置１００の機能ブロックの一例を示すブロック構成図である。
データ圧縮装置１００は、データ入力部１１０と、データ記憶部１１５と、予測部１２０と、予測残差算出部１２５と、予測残差記憶部１４０と、基準値算出部１４５と、パラメータ算出部１５０と、基準値選択部１８０と、基準残差算出部１８５と、符号化部１９０と、符号出力部１９５とを有する。
【００９１】
データ入力部１１０は、ＣＰＵ９１１（処理装置）を用いて、観測装置８１０が出力した観測データを入力する。データ入力部１１０が入力する観測データは、一連の観測値を表わす。
データ記憶部１１５は、磁気ディスク装置９２０（記憶装置）を用いて、データ入力部１１０が入力した観測データを記憶する。
【００９２】
予測部１２０は、ＣＰＵ９１１を用いて、データ記憶部１１５が記憶した観測データが表わす一連の観測値のうち最新の観測値について、その観測値の予測値を算出する。予測部１２０は、その観測値よりも前の観測値に基づいて、その観測値を予測する。例えば、予測部１２０は、ある観測値よりも前のすべての観測値を使って、その観測値を予測する。あるいは、予測部１２０は、ある観測値の直前のいくつかの観測値を使って、その観測値を予測する構成であってもよい。なお、一連の観測値のうち最初の観測値については、それよりも前の観測値が存在しないので、予測部１２０は、例えば、所定の値（例えば０）を、その観測値の予測値とする。
予測部１２０は、例えば線形予測や非線形予測、カルマンフィルタやその他フィルタを用いた予測などを用いて、観測値を予測する。予測部１２０は、観測値の順序を所定の方式で入れ替える構成であってもよい。例えば、２ａ番目の観測値と２ａ＋１番目の観測値の順序を入れ替えて、２ａ＋１番目の観測値を２ａ番目の観測値よりも先に予測する構成であってもよい。その場合、予測部１２０は、２ａ番目の観測値を使わず、２ａ−１番目以前の観測値だけを使って、２ａ＋１番目の観測値を予測する。その代わり、予測部１２０は、２ａ番目の観測値の予測に、２ａ＋１番目の観測値を使う。これにより、２ａ番目の観測値の予測精度を高めることができる。
このように、観測値の順序は、実際にその観測値を観測した順序と異なっていてもよい。ここでいう「観測値の順序」とは、観測値を符号化した符号の依存関係のことである。すなわち、ある観測値ｘａを使って別の観測値ｘｂを予測し、その別の観測値ｘｂを使って観測値ｘａを予測するという循環があると、どちらかの観測値がわからなければもう一方の観測値を予測できないから、符号化した符号を復号できない。したがって、このような循環が存在してはならない。このような循環が存在しなければ、復号時には、復号済の観測値を使ってまだ復号していない観測値を予測することができ、すべての観測値を復号できる。観測値の順序が実際の時系列順と異なる場合、復号後に観測値の順序を入れ替えて、実際にその観測値を観測した時系列順に戻せばよい。
【００９３】
予測残差算出部１２５は、ＣＰＵ９１１を用いて、データ記憶部１１５が記憶した観測データが表わす一連の観測値のうち、予測部１２０が予測値を算出した観測値について、その観測値の予測残差（予測誤差）を算出する。予測残差算出部１２５は、その観測値の予測残差として、予測部１２０が算出した予測値をその観測値から差し引いた差を計算する。
【００９４】
なお、観測値が整数値や固定小数点形式で表現された実数値である場合、予測残差算出部１２５は、整数の引き算を使って、予測残差を算出する。
また、観測値が浮動小数点形式で表現された実数値である場合、例えば、予測残差算出部１２５は、指数部の予測残差として、予測値の指数部を観測値の指数部から差し引いた差を、整数の引き算を使って算出する。予測残差算出部１２５は、予測値を変換して、観測値の指数部に予測値の指数部を一致させる。例えば、予測値の指数部が観測値の指数部より小さい場合、予測残差算出部１２５は、指数部の差の分だけ、予測値の仮数部を右にシフトする。この際、アンダーフローするビットは、無視してよい。逆に、予測値の指数部が観測値の指数部より大きい場合、予測残差算出部１２５は、指数部の差の分だけ、予測値の仮数部を左にシフトする。この際、オーバーフローするビットも、無視してよい。予測残差算出部１２５は、仮数部の予測残差として、変換した予測値の仮数部を観測値の仮数部から差し引いた差を、整数の引き算を使って算出する。また、予測残差算出部１２５は、符号部の予測残差として、観測値の符号部と予測値の符号部とが同じか異なるかを算出する。予測残差算出部１２５は、指数部の予測残差と、仮数部の予測残差と、符号部の予測残差との組を、観測値の予測残差とする。なお、観測値の符号があらかじめわかっている場合、予測残差算出部１２５は、符号部の予測残差を算出しない構成であってもよい。
また、観測値が複数の整数値や実数値の組からなるベクトル値である場合、予測残差算出部１２５は、各成分ごとに予測残差を算出し、算出した予測残差の組を、観測値の予測残差とする。
【００９５】
予測残差記憶部１４０は、磁気ディスク装置９２０を用いて、予測残差算出部１２５が算出した予測残差を表わすデータ（以下「予測残差データ」と呼ぶ。）を記憶する。予測残差データは、予測部１２０が予測値を算出した観測値それぞれについての予測残差を表わす。１つの予測残差は、例えば、１つの整数または複数の整数の組によって表わされる。
【００９６】
基準値算出部１４５は、ＣＰＵ９１１を用いて、予測部１２０が予測値を算出した観測値のそれぞれについて、予測残差記憶部１４０が記憶した予想残差データが表わす予測残差のうち、その観測値よりも前の観測値についての予測残差に基づいて、予測残差基準値（予測誤差代表値）を算出する。なお、ここでいう観測値の前後関係は、予測部１２０の場合と同様、必ずしも、実際にその観測値が観測された順序どおりでなくてもよく、予測部１２０が予測値を予測する順序（依存関係）にしたがう。
基準値算出部１４５は、その観測値よりも前の観測値についての予測残差すべてを使って、予測残差基準値を算出する構成でもよいし、その観測値の直前のいくつかの観測値についての予測残差を使って、予測残差基準値を算出する構成でもよい。その場合、基準値算出部１４５が使う予測残差の数は、予測部１２０が予測値の算出に使う観測値の数と異なっていてもよいし、同じであってもよい。
【００９７】
基準値算出部１４５は、予測残差基準値（予測誤差代表値）を少なくとも１つ算出する。基準値算出部１４５は、予測残差基準値の算出に使う予測残差の分布に基づいて、予測残差が比較的密集している領域（以下「予測残差密集領域」と呼ぶ。）を算出する。基準値算出部１４５は、算出した予測残差密集領域に基づいて、予測残差基準値として、その予測残差密集領域を代表する値を算出する。例えば、基準値算出部１４５は、予測残差密集領域の中央値を予測残差基準値とする。あるいは、基準値算出部１４５は、予測残差密集領域内に入る予測残差の平均値を予測残差基準値とする。予測残差密集領域が複数ある場合、基準値算出部１４５は、複数の予測残差密集領域を算出し、原則として、それぞれの予測残差密集領域について、予測残差基準値を算出する。ただし、複数の予測残差密集領域が比較的近い領域にある場合、基準値算出部１４５は、近くに存在する複数の予測残差密集領域を１つの予測残差密集領域とみなす。基準値算出部１４５は、１つとみなした予測残差密集領域について１つの予測残差基準値を算出する。
基準値算出部１４５は、算出する予測残差基準値の数をあらかじめ定めず、予測残差の分布に基づいて、最適な数の予測誤差基準値を算出する。予測残差基準値の数を増やすと、符号化部１９０が符号化する整数（残差）が小さくなる分、符号長が短くなるが、どの予測残差基準値を選択したかを示すインデックスの符号長が長くなるので、全体としての符号長は、必ずしも短くなるとは限らない。そこで、基準値算出部１４５は、符号長の期待値が最小になる数の予測残差基準値を算出する。例えば、予測残差が比較的まばらなところに予測残差基準値を設けても、その予測残差基準値を使う確率が低いので、残差の符号長はあまり短くならない。また、１つの予測残差密集領域内に複数の予測残差基準値を設けても、どちらの予測残差基準値を使っても残差があまり変わらないので、やはり、残差の符号長はあまり短くならない。このため、符号長の期待値が最小になるのは、予測残差基準値の数が、予測残差密集領域の数と等しい場合である。基準値算出部１４５は、予測残差密集領域の数と同じ数の予測残差基準値を算出する。
【００９８】
なお、予測残差が複数の整数の組によって表わされる場合、基準値算出部１４５は、各成分ごとに独立して予測残差基準値を算出する構成であってもよいし、各成分の予測残差基準値を組として扱う構成であってもよい。例えば、予測残差が２つの整数の組（ｘ，ｙ）によって表わされる場合、各成分ごとに独立して予測残差基準値を算出する構成であれば、基準値算出部１４５は、ｘ成分の予測残差基準値として、ａ個の予測残差基準値ｘ１，ｘ２，…，ｘａを算出し、ｙ成分の予測残差基準値として、ｂ個の予測残差基準値ｙ１，ｙ２，…，ｙｂを算出する。各成分の予測残差基準値を組として扱う構成であれば、基準値算出部１４５は、ｃ個の予測残差基準値の組（ｘ１，ｙ１），（ｘ２，ｙ２），…，（ｘｃ，ｙｃ）を算出する。各成分の間に相関がなく独立している場合には、各成分ごとに独立して予測残差基準値を算出する構成のほうが好ましく、各成分の間に強い相関がある場合には、各成分の予測残差基準値を組として扱う構成のほうが好ましい。
【００９９】
パラメータ算出部１５０は、ＣＰＵ９１１を用いて、予測部１２０が予測値を算出した観測値のそれぞれについて、基準値算出部１４５が算出した予測残差基準値と、予測残差記憶部１４０が記憶した予想残差データが表わす予測残差のうち、その観測値よりも前の観測値についての予測残差とに基づいて、符号化に使うパラメータを算出する。パラメータ算出部１５０が算出するパラメータには、どの予測残差基準値を使って残差を算出したかを表わす基準値インデックスを符号化するためのインデックス符号化パラメータと、残差を符号化するための残差符号化パラメータとがある。
【０１００】
例えば、パラメータ算出部１５０は、予測残差の分布に基づいて、基準値算出部１４５が算出した予測残差基準値それぞれを選択する確率を推定する。パラメータ算出部１５０は、推定した確率に基づいて、ハフマン符号などのエントロピー符号において基準値インデックスに対応する符号を算出し、インデックス符号化パラメータとする。
なお、予測残差が複数の整数の組で表わされ、基準値算出部１４５が各成分ごとに独立して予測残差を算出する構成である場合、パラメータ算出部１５０は、各成分ごとに独立して予測残差基準値を選択する確率を推定する構成であってもよいし、各成分の予測残差基準値の組について、その組を選択する確率を推定する構成であってもよい。
【０１０１】
また、パラメータ算出部１５０は、予測残差の分布と、基準値算出部１４５が算出した予測残差基準値の分布とに基づいて、残差を符号化する符号化方式や、符号化に用いるパラメータを選択する。パラメータ算出部１５０は、選択した符号化方式やパラメータを表わす残差符号化パラメータを生成する。例えば、基準値算出部１４５が算出した予測残差基準値のうち、最も小さい予測残差基準値よりも予測残差が小さい場合や、最も大きい予測残差基準値よりも予測残差が大きい場合は、符号化する残差の絶対値が比較的大きくなる可能性があるのに対し、予測残差が２つの予測残差基準値の間にある場合は、符号化する残差の絶対値がその２つの予測残差基準値の差より大きくなることはあり得ない。符号化する残差が大きい可能性がある場合は、例えばガンマ符号やデルタ符号など大きい整数を比較的短い符号に符号化する符号化方式が効率的である。また、符号化する残差の上限がわかっている場合は、例えばＣＢＴ符号など所定の範囲内の整数を符号化する符号化方式が効率的である。また、符号化する残差の出現確率によっても、最も効率がよい符号化方式が異なる。例えば、残差の絶対値が大きくなるにつれて出現確率が下がっていく場合は、デルタ符号などのユニバーサル符号のように絶対値が小さいほど符号長が短く、絶対値が大きいほど符号長が長くなる符号化方式のほうが効率がよい。逆に、残差の絶対値にかかわらず出現確率があまり変わらない場合は、ＣＢＴ符号のように符号長があまり変わらない符号化方式のほうが効率がよい。また、ゴロム符号やライス符号を使う場合、絶対値の小さい残差の出現確率が高いほど、法ｍや次数ｋを小さくするほうが効率がよい。
パラメータ算出部１５０は、予測残差の分布に基づいて、それぞれの予測残差基準値を選択した場合における残差の確率分布を推定する。パラメータ算出部１５０は、推定した確率分布に基づいて、どの符号化方式が最適であるかを判定し、ライス符号のようにパラメータを持つ符号化方式が最適であると判定した場合は、更に、最適なパラメータの値を算出する。
なお、ある予測残差基準値に対して、予測残差のほうが大きい場合と、予測残差のほうが小さい場合とでは、符号化する残差の確率分布が異なる場合がある。このため、パラメータ算出部１５０は、同じ予測残差基準値を選択した場合でも、符号化する残差が正である場合と、符号化する残差が負である場合とで、異なる符号化方式やパラメータを算出する構成であってもよい。
また、予測残差が複数の整数の組によって表わされる場合、パラメータ算出部１５０は、各成分ごとに異なる符号化方式やパラメータを算出する構成であってもよい。また、基準値算出部１４５が各成分ごとに独立して予測誤差基準値を算出する構成である場合、パラメータ算出部１５０は、各成分に対して選択した予測誤差基準値の組に対して、それぞれ異なる符号化方式やパラメータを算出する構成であってもよい。例えば、予測残差が２つの整数の組（ｘ，ｙ）によって表わされ、基準値算出部１４５が各成分についてそれぞれ独立に予測誤差基準値を算出し、ｘ成分についてａ個、ｙ成分についてｂ個の予測誤差基準値を算出した場合、予測誤差基準値の組合せは、ａ×ｂ通りある。パラメータ算出部１５０は、ａ×ｂ通りの組合せそれぞれについて、ｘ成分の符号化方式やパラメータと、ｙ成分の符号化方式やパラメータとの組を選択する。
【０１０２】
基準値選択部１８０は、ＣＰＵ９１１を用いて、予測部１２０が予測値を算出した観測値のそれぞれについて、予測残差算出部１２５が算出した予測残差と、パラメータ算出部１５０が算出した符号化パラメータとに基づいて、基準値算出部１４５が算出した予測残差基準値のなかから、１つの予測残差基準値を選択する。基準値選択部１８０は、残差を符号化したときの符号長が最も短くなる予測残差基準値を選択する。例えば、基準値選択部１８０は、予測残差との差の絶対値が最も小さい予測残差基準値を選択する。ただし、予測残差基準値によって符号化の方式が異なる場合、必ずしも、予測残差との差の絶対値が最も小さい予測残差基準値が、残差を符号化したときの符号長を最も短くするとは限らない。また、選択した予測残差基準値を示す基準値インデックスを符号化した符号長が、選択した予測残差基準値によって異なる場合、基準値選択部１８０は、基準値インデックスを符号化した符号長も合わせた全体の符号長が最も短くなる予測残差基準値を選択する。例えば、基準値選択部１８０は、基準値算出部１４５が算出した予測残差基準値すべて、もしくは、そのなかから抽出したいくつかの候補について、符号長を算出し、算出した符号長が最も短い予測残差基準値を選択する。
【０１０３】
予測残差が複数の整数の組で表わされ、基準値算出部１４５が各成分ごとに独立して予測残差基準値を算出する構成である場合、基準値選択部１８０は、各成分ごとに、基準値算出部１４５が算出した予測残差基準値のなかから、１つの予測残差基準値を選択する。また、基準値算出部１４５が各成分の予測残差基準値を組として扱う構成である場合、基準値選択部１８０は、各成分の予測残差基準値の組のなかから、１つの組を選択する。
【０１０４】
基準残差算出部１８５は、ＣＰＵ９１１を用いて、予測部１２０が予測値を算出した観測値のそれぞれについて、基準残差を算出する。基準残差算出部１８５は、基準残差として、予測残差算出部１２５が算出した予測残差から、基準値選択部１８０が選択した予測残差基準値を差し引いた差を、整数の引き算を使って計算する。
予測残差が複数の整数の組で表わされる場合、基準残差算出部１８５は、各成分ごとに、予測残差基準値を予測残差から差し引いた差を、整数の引き算を使って計算する。
【０１０５】
符号化部１９０は、ＣＰＵ９１１を用いて、予測部１２０が予測値を算出した観測値のそれぞれについて、パラメータ算出部１５０が算出した符号化パラメータに基づいて、基準値選択部１８０が選択した予測残差基準値を示す基準値インデックスを符号化して、選択基準値符号を生成する。また、符号化部１９０は、ＣＰＵ９１１を用いて、パラメータ算出部１５０が算出した符号化パラメータに基づいて、基準残差算出部１８５が算出した基準残差を符号化して、基準残差符号を生成する。
【０１０６】
なお、符号化部１９０は、基準残差が正であるか負であるかを、基準残差符号の一部として符号化する構成であってもよいし、選択基準値符号の一部として符号化する構成であってもよい。
基準残差の正負を選択基準値符号の一部として符号化する構成の場合、符号化部１９０は、例えば、基準残差算出部１８５が算出した基準残差が正であるか負であるかを判定する。なお、基準残差が０である場合は、正に含まれるものとして扱う構成であってもよいし、負に含まれるものとして扱う構成であってもよいし、符号長が短くなるほうに含まれるものとして扱う構成であってもよい。
基準残差が正であると判定した場合、符号化部１９０は、例えば、基準値選択部１８０が選択した基準値インデックスに、基準残差が正であることを示すビットを付加したものを符号化し、選択基準値符号を生成する。基準残差が０の場合を正として扱う場合において、符号化部１９０は、指数ゴロム符号のように０以上の整数を符号化できる符号化方式を使って、基準残差算出部１８５が算出した基準残差を符号化し、基準残差符号を生成する。なお、ガンマ符号のように１以上の整数を符号化できる符号化方式を使う場合、符号化部１９０は、例えば、基準残差算出部１８５が算出した基準残差に１を加えたものを符号化する。
基準残差が負であると判定した場合、符号化部１９０は、例えば、基準値選択部１８０が選択した基準値インデックスに、基準残差が負であることを示すビットを付加したものを符号化し、選択基準値符号を生成する。基準残差が０の場合を正として扱う場合において、符号化部１９０は、基準残差算出部１８５が算出した基準残差に−１を乗じて正負を反転し、ガンマ符号のように１以上の整数を符号化できる符号化方式により符号化する。なお、指数ゴロム符号のように０以上の整数を符号化できる符号化方式を使う場合は、符号化部１９０は、基準残差算出部１８５が算出した基準残差を−１から差し引いた差（あるいは基準残差の１の補数）を符号化する。
基準残差が正の場合と負の場合とで、基準残差の符号化方式が異なる場合、基準残差の正負を選択基準値符号の一部として符号化する方式が好ましい。また、選択基準値符号をハフマン符号などのエントロピー符号を用いて符号化する構成で、基準残差が正の場合の出現確率と負の場合の出現確率とが異なる場合、基準残差の正負を選択基準値符号の一部として符号化することにより、符号長を短くすることができる。
【０１０７】
予測残差が複数の整数の組で表わされ、基準値算出部１４５が各成分ごとに独立して予測残差基準値を算出する構成である場合、符号化部１９０は、各成分ごとに独立して、基準値選択部１８０が選択した予測残差基準値を示す基準値インデックスを符号化する構成であってもよいし、各成分について基準値選択部１８０が選択した予測残差基準値を示す基準値インデックスの組を符号化する構成であってもよい。ハフマン符号などのエントロピー符号を用いて符号化する場合、出現確率の低い基準値インデックスの組があれば、基準値インデックスの組を符号化する構成のほうが、出現確率の高い基準値インデックスの組を符号化した選択基準値符号の符号長が短くなるので好ましい。
なお、基準値インデックスを圧縮符号化せず、固定長バイナリ形式の符号を生成する構成であってもよい。
【０１０８】
また、予測残差が複数の整数の組で表わされる場合、符号化部１９０は、各成分ごとに、基準残差算出部１８５が算出した基準残差を符号化する。符号化部１９０は、すべての成分について生成した符号の組を、基準残差符号とする。
【０１０９】
符号出力部１９５は、ＣＰＵ９１１を用いて、圧縮データを出力する。圧縮データは、データ入力部１１０が入力した観測データが表わす一連の観測値を表わす。圧縮データは、符号化部１９０が生成した選択基準値符号と基準残差符号との組を複数含む。１つの選択基準地符号と基準残差符号との組は、１つの観測値を表わす。
なお、符号出力部１９５は、符号化部１９０が生成した選択基準値符号と基準残差符号との組をそのまま圧縮データとするのではなく、更に、別の圧縮方式を用いて圧縮したものを圧縮データとして出力する構成であってもよい。
【０１１０】
図１８は、この実施の形態におけるデータ復元装置２００の機能ブロックの構成の一例を示すブロック構成図である。
データ復元装置２００は、データ出力部２１０と、値記憶部２１５と、復元予測部２２０と、予測残差算出部２２５と、値復元部２３０と、予測残差記憶部２４０と、復元基準値算出部２４５と、パラメータ算出部２５０と、復元基準値選択部２８０と、復号部２９０と、符号取得部２９５とを有する。
【０１１１】
符号取得部２９５は、ＣＰＵ９１１を用いて、圧縮データを入力して、選択基準値符号と基準残差符号との組を、順に一組ずつ取得する。
【０１１２】
予測残差記憶部２４０は、磁気ディスク装置９２０を用いて、予測残差算出部２２５がそれまでに算出した予測残差を表わす予測残差データを記憶している。
【０１１３】
復元基準値算出部２４５は、ＣＰＵ９１１を用いて、予測残差記憶部２４０が記憶した予測残差データが表わす予測残差に基づいて、予測残差基準値を算出する。復元基準値算出部２４５は、データ圧縮装置１００の基準値算出部１４５と同じ方式で予測残差基準値を算出する。基準値算出部１４５は、ある観測値について、その観測値よりも前の観測値についての予測残差に基づいて予測残差基準値を算出する。データ復元装置２００がその観測値を復元する時点では、その観測値よりも前の観測値についての予測残差を予測残差算出部２２５が既に算出し、予測残差記憶部２４０が記憶している。このため、復元基準値算出部２４５は、基準値算出部１４５とまったく同じようにして予測残差基準値を算出することができる。すなわち、復元基準値算出部２４５は、基準値算出部１４５が算出する予測残差基準値とまったく同じ予測残差基準値を算出する。
【０１１４】
パラメータ算出部２５０は、ＣＰＵ９１１を用いて、予測残差記憶部２４０が記憶した予測残差データが表わす予測残差と、復元基準値算出部２４５が算出した予測残差基準値とに基づいて、符号化パラメータを算出する。パラメータ算出部２５０は、データ圧縮装置１００のパラメータ算出部１５０と同じ方式で符号化パラメータを算出する。復元基準値算出部２４５と同様、パラメータ算出部２５０は、パラメータ算出部２５０とまったく同じようにして符号化パラメータを算出することができる。すなわち、パラメータ算出部２５０は、パラメータ算出部１５０が算出する符号化パラメータとまったく同じ符号化パラメータを算出する。
【０１１５】
復号部２９０は、ＣＰＵ９１１を用いて、パラメータ算出部２５０が算出した符号化パラメータに基づいて、符号取得部２９５が取得した選択基準値符号と基準残差符号とを復号する。例えば、復号部２９０は、まず、パラメータ算出部２５０が算出した符号化パラメータのうちインデックス符号化パラメータに基づいて、選択基準値符号を復号して、基準値インデックスを復元する。次に、復号部２９０は、復元した基準値インデックスと、パラメータ算出部２５０が算出した符号化パラメータのうち残差符号化パラメータとに基づいて、基準残差符号を復号して、基準残差を復元する。
【０１１６】
復元基準値選択部２８０は、ＣＰＵ９１１を用いて、復元基準値算出部２４５が算出した予測残差基準値のなかから、復号部２９０が復元した基準値インデックスが示す予測残差基準値を選択する。これにより、復元基準値選択部２８０は、データ圧縮装置１００の基準値選択部１８０が選択した予測残差基準値と同じ予測残差基準値を選択する。
【０１１７】
予測残差算出部２２５は、ＣＰＵ９１１を用いて、復号部２９０が復元した基準残差と、復元基準値選択部２８０が選択した予測残差基準値とに基づいて、予測残差を算出する。予測残差算出部２２５は、基準残差と予測残差基準値とを合計した和を、整数の足し算を使って計算して、予測残差とする。これにより、予測残差算出部２２５は、データ圧縮装置１００の予測残差算出部１２５が算出した予測残差と同じ予測残差を算出する。予測残差算出部２２５が算出した予測残差は、予測残差記憶部２４０が記憶して、次の観測値を復元するための予測残差基準値などを算出するために使われる。
【０１１８】
値記憶部２１５は、磁気ディスク装置９２０を用いて、値復元部２３０がそれまでに復元した一連の観測値を表わすデータを記憶している。
【０１１９】
復元予測部２２０は、ＣＰＵ９１１を用いて、値記憶部２１５が記憶したデータが表わす一連の観測値に基づいて、復元しようとしている観測値の予測値を算出する。復元予測部２２０は、データ圧縮装置１００の予測部１２０と同じ方式で観測値を予測する。予測部１２０は、ある観測値について、その観測値よりも前の観測値に基づいて予測値を算出する。データ復元装置２００がその観測値を復元する時点では、その観測値よりも前の観測値を値復元部２３０が既に復元し、値記憶部２１５が記憶している。このため、復元予測部２２０は、予測部１２０とまったく同じようにして予測値を算出することができる。すなわち、復元予測部２２０は、予測部１２０が算出する予測値とまったく同じ予測値を算出する。
【０１２０】
値復元部２３０は、ＣＰＵ９１１を用いて、予測残差算出部２２５が算出した予測残差と、復元予測部２２０が算出した予測値とに基づいて、観測値を復元する。値復元部２３０は、予測残差と予測値とを合計した和を計算することにより、観測値の復元値を算出する。
観測値が整数値や固定小数点形式で表現された実数値である場合、値復元部２３０は、整数の足し算を計算することにより、復元値を算出する。
観測値が浮動小数点形式で表現された実数値であり、予測残差算出部２２５が算出する予測残差が、指数部の予測残差を表わす整数と、仮数部の予測残差を表わす整数と、符号部の予測残差を表わす整数との組である場合、値復元部２３０は、例えば、復元予測部２２０が予測した予測値の仮数部を、指数部の予測残差の分だけシフトする。値復元部２３０は、例えば、指数部の予測残差が正であれば予測値の仮数部を左にシフトし、指数部の予測残差が負であれば予測値の仮数部を右にシフトする。このとき、オーバーフローあるいはアンダーフローしたビットは無視してよい。次に、値復元部２３０は、シフトした予測値の仮数部と、予測誤差の仮数部とを合計した和を、整数の足し算を使って計算する。値復元部２３０は、符号部の予測残差が０でない場合、予測値の符号部を反転する。こうして算出した指数部・仮数部・符号部に基づいて、値復元部２３０は、浮動小数点形式で表現された実数値を復元して、観測値の復元値を得る。これにより、観測値が浮動小数点形式で表現されている場合であっても、桁落ちなどが発生せず、元の観測値とまったく同じ復元値を得ることができる。
値復元部２３０が復元した観測値は、値記憶部２１５が記憶して、次の観測値などを予測するために使われる。
【０１２１】
データ出力部２１０は、ＣＰＵ９１１を用いて、値復元部２３０が復元した一連の観測値を表わす復元データを生成し、出力する。
【０１２２】
図１９は、この実施の形態におけるデータ圧縮処理Ｓ６１０の流れの一例を示すフローチャート図である。
データ圧縮処理Ｓ６１０において、データ圧縮装置１００は、一連の観測値を表わす圧縮データを生成する。データ圧縮処理Ｓ６１０は、観測値取得工程Ｓ６１１と、基準値算出工程Ｓ６１２と、パラメータ算出工程Ｓ６１３と、観測値予測工程Ｓ６１４と、予測残差算出工程Ｓ６１５と、基準値選択工程Ｓ６１６と、基準残差算出工程Ｓ６１７と、符号化工程Ｓ６１８とを有する。データ圧縮装置１００は、観測値取得工程Ｓ６１１から処理を開始する。
【０１２３】
観測値取得工程Ｓ６１１において、データ入力部１１０は、ＣＰＵ９１１を用いて、観測値を入力する。データ記憶部１１５は、磁気ディスク装置９２０を用いて、データ入力部１１０が入力した観測値を記憶する。
データ圧縮装置１００は、ＣＰＵ９１１を用いて、データ記憶部１１５が記憶した一連の観測値のなかから、観測値を１つ選択する。すべての観測値が選択済である場合、データ圧縮装置１００は、データ圧縮処理Ｓ６１０を終了する。未選択の観測値がある場合、データ圧縮装置１００は、未選択の観測値のなかから、先頭の観測値を１つ選択し、基準値算出工程Ｓ６１２へ処理を進める。
【０１２４】
基準値算出工程Ｓ６１２において、基準値算出部１４５は、ＣＰＵ９１１を用いて、予測残差記憶部１４０が記憶した予測残差に基づいて、予測残差基準値を算出する。
パラメータ算出工程Ｓ６１３において、パラメータ算出部１５０は、ＣＰＵ９１１を用いて、予測残差記憶部１４０が記憶した予測残差と、基準値算出工程Ｓ６１２で基準値算出部１４５が算出した予測残差基準値とに基づいて、符号化パラメータを算出する。
【０１２５】
観測値予測工程Ｓ６１４において、予測部１２０は、ＣＰＵ９１１を用いて、データ記憶部１１５が記憶した観測データが表わす一連の観測値のうち、観測値取得工程Ｓ６１１で選択した観測値よりも前の観測値に基づいて、観測値取得工程Ｓ６１１で選択した観測値の予測値を算出する。
予測残差算出工程Ｓ６１５において、予測残差算出部１２５は、ＣＰＵ９１１を用いて、観測値取得工程Ｓ６１１で選択した観測値と、観測値予測工程Ｓ６１４で算出した予測値とに基づいて、予測残差を算出する。予測残差記憶部１４０は、磁気ディスク装置９２０を用いて、予測残差算出部１２５が算出した予測残差を記憶する。
【０１２６】
基準値選択工程Ｓ６１６において、基準値選択部１８０は、ＣＰＵ９１１を用いて、パラメータ算出工程Ｓ６１３でパラメータ算出部１５０が算出した符号化パラメータと、予測残差算出工程Ｓ６１５で予測残差算出部１２５が算出した予測残差とに基づいて、基準値算出工程Ｓ６１２で基準値算出部１４５が算出した予測残差基準値のなかから、予測残差基準値を選択する。
基準残差算出工程Ｓ６１７において、基準残差算出部１８５は、ＣＰＵ９１１を用いて、予測残差算出工程Ｓ６１５で予測残差算出部１２５が算出した予測残差と、基準値選択工程Ｓ６１６で基準値選択部１８０が選択した予測残差基準値とに基づいて、基準残差を算出する。
符号化工程Ｓ６１８において、符号化部１９０は、ＣＰＵ９１１を用いて、パラメータ算出工程Ｓ６１３でパラメータ算出部１５０が算出した符号化パラメータに基づいて、基準値選択工程Ｓ６１６で基準値選択部１８０が選択した予測残差基準値を示す基準値インデックスを符号化して、選択基準値符号を生成する。符号化部１９０は、ＣＰＵ９１１を用いて、パラメータ算出工程Ｓ６１３でパラメータ算出部１５０が算出した符号化パラメータと、基準値選択工程Ｓ６１６で基準値選択部１８０が選択した予測残差基準値を示す基準値インデックスとに基づいて、基準残差算出工程Ｓ６１７で基準残差算出部１８５が算出した基準残差を符号化して、基準残差符号を生成する。符号出力部１９５は、ＣＰＵ９１１を用いて、符号化部１９０が生成した選択基準値符号と基準残差符号との組を、観測値取得工程Ｓ６１１で選択した観測値を表わす符号として出力する。
データ圧縮装置１００は、ＣＰＵ９１１を用いて、観測値取得工程Ｓ６１１に処理を戻し、次の観測値を選択する。
【０１２７】
図２０は、この実施の形態におけるデータ復元処理Ｓ６２０の流れの一例を示すフローチャート図である。
データ復元処理Ｓ６２０において、データ復元装置２００は、データ圧縮装置１００が生成した圧縮データから、元の一連の観測値を復元する。データ復元処理Ｓ６２０は、符号取得工程Ｓ６２１と、基準値算出工程Ｓ６２２と、パラメータ算出工程Ｓ６２３と、復号工程Ｓ６２４と、基準値選択工程Ｓ６２５と、予測残差算出工程Ｓ６２６と、観測値予測工程Ｓ６２７と、観測値復元工程Ｓ６２８とを有する。データ復元装置２００は、符号取得工程Ｓ６２１から処理を開始する。
【０１２８】
符号取得工程Ｓ６２１において、符号取得部２９５は、ＣＰＵ９１１を用いて、圧縮データから、１つの観測値を表わす選択基準値符号と基準残差符号との組を取得する。圧縮データに含まれる選択基準値符号と基準残差符号との組がすべて取得済である場合、符号取得部２９５は、ＣＰＵ９１１を用いて、データ復元処理Ｓ６２０を終了する。未取得の組がある場合、符号取得部２９５は、ＣＰＵ９１１を用いて、未取得の組のなかから、先頭の組を１つ取得する。
【０１２９】
基準値算出工程Ｓ６２２において、復元基準値算出部２４５は、ＣＰＵ９１１を用いて、予測残差記憶部２４０が記憶した予測残差に基づいて、予測残差基準値を算出する。
パラメータ算出工程Ｓ６２３において、パラメータ算出部２５０は、ＣＰＵ９１１を用いて、予測残差記憶部２４０が記憶した予測残差と、基準値算出工程Ｓ６２２で復元基準値算出部２４５が算出した予測残差基準値とに基づいて、符号化パラメータを算出する。
【０１３０】
復号工程Ｓ６２４において、復号部２９０は、ＣＰＵ９１１を用いて、パラメータ算出工程Ｓ６２３でパラメータ算出部２５０が算出した符号化パラメータに基づいて、符号取得工程Ｓ６２１で符号取得部２９５が取得した選択基準値符号を復号して、基準値インデックスを算出する。復号部２９０は、ＣＰＵ９１１を用いて、パラメータ算出工程Ｓ６２３でパラメータ算出部２５０が算出した符号化パラメータと、算出した基準値インデックスとに基づいて、符号取得工程Ｓ６２１で符号取得部２９５が取得した基準残差符号を復号して、基準残差を算出する。
基準値選択工程Ｓ６２５において、復元基準値選択部２８０は、ＣＰＵ９１１を用いて、基準値算出工程Ｓ６２２で復元基準値算出部２４５が算出した予測残差基準値のなかから、復号工程Ｓ６２４で復号部２９０が算出した基準値インデックスによって示される予測残差基準値を選択する。
予測残差算出工程Ｓ６２６において、予測残差算出部２２５は、ＣＰＵ９１１を用いて、復号部２９０で復号部２９０が算出した基準残差と、基準値選択工程Ｓ６２５で復元基準値選択部２８０が選択した予測残差基準値とに基づいて、予測残差を算出する。予測残差記憶部２４０は、磁気ディスク装置９２０を用いて、予測残差算出部２２５が算出した予測残差を記憶する。
【０１３１】
観測値予測工程Ｓ６２７において、復元予測部２２０は、ＣＰＵ９１１を用いて、値記憶部２１５が記憶した観測値に基づいて、符号取得工程Ｓ６２１で符号取得部２９５が取得した選択基準値符号と基準残差符号との組によって表わされる観測値の予測値を算出する。
観測値復元工程Ｓ６２８において、値復元部２３０は、ＣＰＵ９１１を用いて、予測残差算出工程Ｓ６２６で予測残差算出部２２５が算出した予測残差と、観測値予測工程Ｓ６２７で復元予測部２２０が算出した予測値とに基づいて、符号取得工程Ｓ６２１で符号取得部２９５が取得した選択基準値符号と基準残差符号との組によって表わされる観測値の復元値を算出する。値記憶部２１５は、磁気ディスク装置９２０を用いて、値復元部２３０が復元した観測値を記憶する。データ出力部２１０は、ＣＰＵ９１１を用いて、値復元部２３０が復元した観測値を出力する。
データ復元装置２００は、ＣＰＵ９１１を用いて、符号取得工程Ｓ６２１に戻り、次の選択基準値符号と基準残差符号との組を取得する。
【０１３２】
以上、各実施の形態で説明した具体的な構成は一例であり、例えば、異なる実施の形態で説明した構成を組み合わせたり、重要でない部分の構成を他の構成で置き換えたりした構成であってもよい。
【０１３３】
以上説明したデータ圧縮装置（１００）は、データを処理する処理装置（ＣＰＵ９１１）と、予測部（１２０；予測器１０）と、予測残差算出部（１２５；オフセット量決定部２０）と、基準値算出部（１４５；オフセット量決定部２０）と、基準値選択部（１８０；最小残差選択部４０）と、基準残差算出部（１８５；最小残差選択部４０）と、符号化部（１９０；最小残差選択部４０，残差符号化部５０）とを有する。
上記予測部は、上記処理装置を用いて、一連の値（観測値）のうち少なくともいずれかの値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出する。
上記予測残差算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記値と上記予測部が算出した予測値との差を算出することにより、予測残差（予測誤差）を算出する。
上記基準値算出部は、上記処理装置を用いて、上記予測残差算出部が算出した予測残差に基づいて、複数の残差基準値（予測誤差代表値）を算出する。
上記基準値選択部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記基準値算出部が算出した複数の残差基準値のなかから、上記予測残差算出部が算出した予測残差に最も近い残差基準値を選択する。
上記基準残差算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記予測残差算出部が算出した予測残差と上記基準値選択部が選択した残差基準値との差を算出することにより、基準残差（残差）を算出する。
上記符号化部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記値を表わす符号として、上記基準値選択部が上記複数の残差基準値のうちどの残差基準値を選択したかを表わす選択基準値符号（基準値インデックス）と、上記基準残差算出部が算出した基準残差を表わす基準残差符号との組を生成する。
【０１３４】
これにより、符号化部が符号化する基準残差の絶対値が小さくなるので、デルタ符号などのユニバーサル符号のように符号化する整数の絶対値が小さいほど符号長が短くなる符号化方式で基準残差を符号化することより、圧縮率を高くすることができる。
【０１３５】
上記データ圧縮装置（１００）は、更に、予測残差分類部（オフセット量決定部２０）を有する。
上記予測残差分類部は、上記処理装置（ＣＰＵ９１１）を用いて、上記予測残差算出部（オフセット量決定部２０）が算出した予測残差（予測誤差）を複数のクラスタに分類する。
上記基準値算出部（オフセット量決定部２０）は、上記処理装置を用いて、上記予測残差分類部が分類した複数のクラスタそれぞれについて、上記予測残差分類部が上記クラスタに分類した予測残差の代表値を算出することにより、残差基準値（予測誤差代表値）を算出する。
【０１３６】
これにより、基準値算出部が算出する残差基準値の分布が、予測残差の分布に一致するので、選択基準値符号の冗長性を抑えることができ、圧縮率を高くすることができる。
【０１３７】
上記予測残差分類部（オフセット量決定部２０）は、ケー平均法または非階層型クラスタリングまたは階層型クラスタリングを用いて、上記予測残差算出部（オフセット量決定部２０）が算出した予測残差（予測誤差）を複数のクラスタに分類する。
【０１３８】
これにより、クラスタリングに伴う計算量を少なくすることができるので、処理装置の処理能力などデータ圧縮処理に必要な資源を抑えることができる。
【０１３９】
上記基準値算出部（オフセット量決定部２０）は、上記予測残差分類部（オフセット量決定部２０）が上記クラスタに分類した予測残差の平均値または中央値または最頻値を算出して、上記代表値とする。
【０１４０】
これにより、代表値算出に伴う計算量を少なくすることができるので、処理装置の処理能力などデータ圧縮処理に必要な資源を抑えることができる。
【０１４１】
上記基準値算出部（１４５；オフセット量決定部２０）は、上記処理装置（ＣＰＵ９１１）を用いて、上記一連の値（観測値）のうち上記予測部（１２０；予測器１０）が予測値を算出した値それぞれについて、上記一連の値のうち上記値よりも前の値について上記予測残差算出部（１２５；オフセット量決定部２０）が算出した予測残差（予測誤差）に基づいて、上記複数の残差基準値（予測誤差代表値）を算出する。
【０１４２】
これにより、復元時には、他の情報を必要とせず、既に復元した値だけに基づいて、基準値算出部１４５が算出した残差基準値とまったく同じ残差基準値を算出できるので、損失なく値を復元することが可能となる。
【０１４３】
上記基準値算出部（１４５；オフセット量決定部２０）は、上記処理装置（ＣＰＵ９１１）を用いて、上記一連の値（観測値）のうち上記予測部（１２０；予測器１０）が予測値を算出したすべての値について上記予測残差算出部（１２５；オフセット量決定部２０）が算出した予測残差（予測誤差）に基づいて、上記複数の残差基準値（予測誤差代表値）を算出する。
上記符号化部（１９０；ヘッダ生成部８０）は、上記一連の値を表わす符号として、更に、上記基準値算出部が算出した複数の残差基準値を表わす残差基準値符号を生成する。
【０１４４】
すべての予測残差から残差基準値を算出するので、圧縮率が更に高くなる残差基準値を算出することができる。復号時には、残差基準値符号から復元した残差基準値を使って値を復元するので、まだ復元していない値に基づいて残差基準値が算出されていても、損失なく値を復元することが可能となる。また、復号時に残差基準値を算出する計算が不要となるので、処理装置の処理能力などデータ復元処理に必要な資源を抑えることができる。
【０１４５】
以上説明したデータ復元装置（２００）は、データを処理する処理装置（ＣＰＵ９１１）と、符号取得部（２９５；選択部４５，残差復号部５５）と、復元予測部（２２０；予測器１５）と、復元基準値選択部（２８０；選択部４５）と、値復元部（２３０；６５）とを有する。
上記符号取得部は、上記処理装置を用いて、一連の値（観測値）のうち少なくともいずれかの値を表わす符号として、複数の残差基準値（予測誤差代表値）のなかからどの残差基準値を選択すべきかを表わす選択基準値符号（基準値インデックス）と、基準残差（残差）を表わす基準残差符号との組を取得する。
上記復元予測部は、上記処理装置を用いて、上記符号取得部が選択基準値符号と基準残差符号との組を取得した値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出する。
上記復元基準値選択部は、上記処理装置を用いて、複数の残差基準値のなかから、上記符号取得部が取得した選択基準値符号によって示される残差基準値を選択する。
上記値復元部は、上記処理装置を用いて、上記復元予測部が算出した予測値と、上記基準値選択部が選択した残差基準値と、上記符号取得部が取得した基準残差符号が表わす基準残差との合計を算出することにより、上記値を復元した復元値を算出する。
【０１４６】
これにより、データ圧縮装置１００が圧縮した元の値を損失なく復元することができる。
【０１４７】
以上説明したデータ圧縮装置（１００）及びデータ復元装置（２００）及びデータ処理システム（データ圧縮記憶システム８００）は、コンピュータプログラムをコンピュータが実行することにより実現することができる。
コンピュータをデータ圧縮装置またはデータ復元装置またはデータ処理システムとして機能させるコンピュータプログラムによれば、一連の値を効率よく圧縮して記憶することができる。
【符号の説明】
【０１４８】
１０，１５ 予測器、１１ 値記憶部、１２ 予測値記憶部、２０，２５ オフセット量決定部、２１ オフセット量記憶部、３０，３５ 基準値生成部、４０ 最小残差選択部、４５ 選択部、５０ 残差符号化部、５５ 残差復号部、６５，２３０ 値復元部、７０，７５ パラメータ記憶部、８０ ヘッダ生成部、８５ ヘッダ取得部、１００ データ圧縮装置、１１０ データ入力部、１１５ データ記憶部、１２０ 予測部、１２５，２２５ 予測残差算出部、１４０，２４０ 予測残差記憶部、１４５ 基準値算出部、１５０，２５０ パラメータ算出部、１８０ 基準値選択部、１８５ 基準残差算出部、１９０ 符号化部、１９５ 符号出力部、２００ データ復元装置、２１０ データ出力部、２１５ 値記憶部、２２０ 復元予測部、２４５ 復元基準値算出部、２８０ 復元基準値選択部、２９０ 復号部、２９５ 符号取得部、３０１〜３０４ 領域、８００ データ圧縮記憶システム、８１０ 観測装置、８２０ データ記憶装置、９０１ 表示装置、９０２ キーボード、９０３ マウス、９０４ ＦＤＤ、９０５ ＣＤＤ、９０６ プリンタ装置、９０７ スキャナ装置、９１０ システムユニット、９１１ ＣＰＵ、９１２ バス、９１３ ＲＯＭ、９１４ ＲＡＭ、９１５ 通信装置、９２０ 磁気ディスク装置、９２１ ＯＳ、９２２ ウィンドウシステム、９２３ プログラム群、９２４ ファイル群、９３１ 電話器、９３２ ファクシミリ機、９４０ インターネット、９４１ ゲートウェイ、９４２ ＬＡＮ。
【特許請求の範囲】
【請求項１】
データを処理する処理装置と、予測部と、予測残差算出部と、基準値算出部と、基準値選択部と、基準残差算出部と、符号化部とを有し、
上記予測部は、上記処理装置を用いて、一連の値のうち少なくともいずれかの値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出し、
上記予測残差算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記値と上記予測部が算出した予測値との差を算出することにより、予測残差を算出し、
上記基準値算出部は、上記処理装置を用いて、上記予測残差算出部が算出した予測残差に基づいて、複数の残差基準値を算出し、
上記基準値選択部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記基準値算出部が算出した複数の残差基準値のなかから、上記予測残差算出部が算出した予測残差に最も近い残差基準値を選択し、
上記基準残差算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記予測残差算出部が算出した予測残差と上記基準値選択部が選択した残差基準値との差を算出することにより、基準残差を算出し、
上記符号化部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記値を表わす符号として、上記基準値選択部が上記複数の残差基準値のうちどの残差基準値を選択したかを表わす選択基準値符号と、上記基準残差算出部が算出した基準残差を表わす基準残差符号との組を生成することを特徴とするデータ圧縮装置。
【請求項２】
上記データ圧縮装置は、更に、予測残差分類部を有し、
上記予測残差分類部は、上記処理装置を用いて、上記予測残差算出部が算出した予測残差を複数のクラスタに分類し、
上記基準値算出部は、上記処理装置を用いて、上記予測残差分類部が分類した複数のクラスタそれぞれについて、上記予測残差分類部が上記クラスタに分類した予測残差の代表値を算出することにより、残差基準値を算出することを特徴とする請求項１に記載のデータ圧縮装置。
【請求項３】
上記予測残差分類部は、ケー平均法または非階層型クラスタリングまたは階層型クラスタリングを用いて、上記予測残差算出部が算出した予測残差を複数のクラスタに分類することを特徴とする請求項２に記載のデータ圧縮装置。
【請求項４】
上記基準値算出部は、上記予測残差分類部が上記クラスタに分類した予測残差の平均値または中央値または最頻値を算出して、上記代表値とすることを特徴とする請求項２または請求項３に記載のデータ圧縮装置。
【請求項５】
上記基準値算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記一連の値のうち上記値よりも前の値について上記予測残差算出部が算出した予測残差に基づいて、上記複数の残差基準値を算出することを特徴とする請求項１乃至請求項４のいずれかに記載のデータ圧縮装置。
【請求項６】
上記基準値算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出したすべての値について上記予測残差算出部が算出した予測残差に基づいて、上記複数の残差基準値を算出し、
上記符号化部は、上記一連の値を表わす符号として、更に、上記基準値算出部が算出した複数の残差基準値を表わす残差基準値符号を生成することを特徴とする請求項１乃至請求項４のいずれかに記載のデータ圧縮装置。
【請求項７】
データを処理する処理装置と、符号取得部と、復元予測部と、復元基準値選択部と、値復元部とを有し、
上記符号取得部は、上記処理装置を用いて、一連の値のうち少なくともいずれかの値を表わす符号として、複数の残差基準値のなかからどの残差基準値を選択すべきかを表わす選択基準値符号と、基準残差を表わす基準残差符号との組を取得し、
上記復元予測部は、上記処理装置を用いて、上記符号取得部が選択基準値符号と基準残差符号との組を取得した値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出し、
上記復元基準値選択部は、上記処理装置を用いて、複数の残差基準値のなかから、上記符号取得部が取得した選択基準値符号によって示される残差基準値を選択し、
上記値復元部は、上記処理装置を用いて、上記復元予測部が算出した予測値と、上記復元基準値選択部が選択した残差基準値と、上記符号取得部が取得した基準残差符号が表わす基準残差との合計を算出することにより、上記値を復元した復元値を算出することを特徴とするデータ復元装置。
【請求項８】
請求項１乃至請求項６のいずれかに記載のデータ圧縮装置と、請求項７に記載のデータ復元装置とを有することを特徴とするデータ処理システム。
【請求項９】
データを処理する処理装置を有するコンピュータが実行することにより、上記コンピュータが請求項１乃至請求項６のいずれかに記載のデータ圧縮装置または請求項７に記載のデータ復元装置または請求項８に記載のデータ処理システムとして機能することを特徴とするコンピュータプログラム。
【請求項１０】
データを処理する処理装置を有するデータ圧縮装置が、一連の値を表わす圧縮データを生成するデータ圧縮方法において、
上記処理装置が、一連の値のうち少なくともいずれかの値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出し、
上記処理装置が、上記一連の値のうち上記予測値を算出した値それぞれについて、上記値と上記予測値との差を算出することにより、予測残差を算出し、
上記処理装置が、上記予測残差に基づいて、複数の残差基準値を算出し、
上記処理装置が、上記一連の値のうち上記予測値を算出した値それぞれについて、上記複数の残差基準値のなかから、上記予測残差に最も近い残差基準値を選択し、
上記処理装置が、上記一連の値のうち上記予測値を算出した値それぞれについて、上記予測残差と上記残差基準値との差を算出することにより、基準残差を算出し、
上記処理装置が、上記一連の値のうち上記予測値を算出した値それぞれについて、上記値を表わす符号として、上記複数の残差基準値のうちどの残差基準値を選択したかを表わす選択基準値符号と、上記基準残差を表わす基準残差符号との組を生成することを特徴とするデータ圧縮方法。
【請求項１１】
データを処理する処理装置を有するデータ復元装置が、一連の値を表わす圧縮データから、上記一連の値を復元するデータ復元方法において、
上記処理装置が、一連の値のうち少なくともいずれかの値を表わす符号として、複数の残差基準値のなかからどの残差基準値を選択すべきかを表わす選択基準値符号と、基準残差を表わす基準残差符号との組を取得し、
上記処理装置が、上記選択基準値符号と基準残差符号との組を取得した値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出し、
上記処理装置が、複数の残差基準値のなかから、上記選択基準値符号によって示される残差基準値を選択し、
上記処理装置が、上記復元予測部が算出した予測値と、上記基準値選択部が選択した残差基準値と、上記符号取得部が取得した基準残差符号が表わす基準残差との合計を算出することにより、上記値を復元した復元値を算出することを特徴とするデータ復元方法。
【請求項１】
データを処理する処理装置と、予測部と、予測残差算出部と、基準値算出部と、基準値選択部と、基準残差算出部と、符号化部とを有し、
上記予測部は、上記処理装置を用いて、一連の値のうち少なくともいずれかの値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出し、
上記予測残差算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記値と上記予測部が算出した予測値との差を算出することにより、予測残差を算出し、
上記基準値算出部は、上記処理装置を用いて、上記予測残差算出部が算出した予測残差に基づいて、複数の残差基準値を算出し、
上記基準値選択部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記基準値算出部が算出した複数の残差基準値のなかから、上記予測残差算出部が算出した予測残差に最も近い残差基準値を選択し、
上記基準残差算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記予測残差算出部が算出した予測残差と上記基準値選択部が選択した残差基準値との差を算出することにより、基準残差を算出し、
上記符号化部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記値を表わす符号として、上記基準値選択部が上記複数の残差基準値のうちどの残差基準値を選択したかを表わす選択基準値符号と、上記基準残差算出部が算出した基準残差を表わす基準残差符号との組を生成することを特徴とするデータ圧縮装置。
【請求項２】
上記データ圧縮装置は、更に、予測残差分類部を有し、
上記予測残差分類部は、上記処理装置を用いて、上記予測残差算出部が算出した予測残差を複数のクラスタに分類し、
上記基準値算出部は、上記処理装置を用いて、上記予測残差分類部が分類した複数のクラスタそれぞれについて、上記予測残差分類部が上記クラスタに分類した予測残差の代表値を算出することにより、残差基準値を算出することを特徴とする請求項１に記載のデータ圧縮装置。
【請求項３】
上記予測残差分類部は、ケー平均法または非階層型クラスタリングまたは階層型クラスタリングを用いて、上記予測残差算出部が算出した予測残差を複数のクラスタに分類することを特徴とする請求項２に記載のデータ圧縮装置。
【請求項４】
上記基準値算出部は、上記予測残差分類部が上記クラスタに分類した予測残差の平均値または中央値または最頻値を算出して、上記代表値とすることを特徴とする請求項２または請求項３に記載のデータ圧縮装置。
【請求項５】
上記基準値算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出した値それぞれについて、上記一連の値のうち上記値よりも前の値について上記予測残差算出部が算出した予測残差に基づいて、上記複数の残差基準値を算出することを特徴とする請求項１乃至請求項４のいずれかに記載のデータ圧縮装置。
【請求項６】
上記基準値算出部は、上記処理装置を用いて、上記一連の値のうち上記予測部が予測値を算出したすべての値について上記予測残差算出部が算出した予測残差に基づいて、上記複数の残差基準値を算出し、
上記符号化部は、上記一連の値を表わす符号として、更に、上記基準値算出部が算出した複数の残差基準値を表わす残差基準値符号を生成することを特徴とする請求項１乃至請求項４のいずれかに記載のデータ圧縮装置。
【請求項７】
データを処理する処理装置と、符号取得部と、復元予測部と、復元基準値選択部と、値復元部とを有し、
上記符号取得部は、上記処理装置を用いて、一連の値のうち少なくともいずれかの値を表わす符号として、複数の残差基準値のなかからどの残差基準値を選択すべきかを表わす選択基準値符号と、基準残差を表わす基準残差符号との組を取得し、
上記復元予測部は、上記処理装置を用いて、上記符号取得部が選択基準値符号と基準残差符号との組を取得した値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出し、
上記復元基準値選択部は、上記処理装置を用いて、複数の残差基準値のなかから、上記符号取得部が取得した選択基準値符号によって示される残差基準値を選択し、
上記値復元部は、上記処理装置を用いて、上記復元予測部が算出した予測値と、上記復元基準値選択部が選択した残差基準値と、上記符号取得部が取得した基準残差符号が表わす基準残差との合計を算出することにより、上記値を復元した復元値を算出することを特徴とするデータ復元装置。
【請求項８】
請求項１乃至請求項６のいずれかに記載のデータ圧縮装置と、請求項７に記載のデータ復元装置とを有することを特徴とするデータ処理システム。
【請求項９】
データを処理する処理装置を有するコンピュータが実行することにより、上記コンピュータが請求項１乃至請求項６のいずれかに記載のデータ圧縮装置または請求項７に記載のデータ復元装置または請求項８に記載のデータ処理システムとして機能することを特徴とするコンピュータプログラム。
【請求項１０】
データを処理する処理装置を有するデータ圧縮装置が、一連の値を表わす圧縮データを生成するデータ圧縮方法において、
上記処理装置が、一連の値のうち少なくともいずれかの値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出し、
上記処理装置が、上記一連の値のうち上記予測値を算出した値それぞれについて、上記値と上記予測値との差を算出することにより、予測残差を算出し、
上記処理装置が、上記予測残差に基づいて、複数の残差基準値を算出し、
上記処理装置が、上記一連の値のうち上記予測値を算出した値それぞれについて、上記複数の残差基準値のなかから、上記予測残差に最も近い残差基準値を選択し、
上記処理装置が、上記一連の値のうち上記予測値を算出した値それぞれについて、上記予測残差と上記残差基準値との差を算出することにより、基準残差を算出し、
上記処理装置が、上記一連の値のうち上記予測値を算出した値それぞれについて、上記値を表わす符号として、上記複数の残差基準値のうちどの残差基準値を選択したかを表わす選択基準値符号と、上記基準残差を表わす基準残差符号との組を生成することを特徴とするデータ圧縮方法。
【請求項１１】
データを処理する処理装置を有するデータ復元装置が、一連の値を表わす圧縮データから、上記一連の値を復元するデータ復元方法において、
上記処理装置が、一連の値のうち少なくともいずれかの値を表わす符号として、複数の残差基準値のなかからどの残差基準値を選択すべきかを表わす選択基準値符号と、基準残差を表わす基準残差符号との組を取得し、
上記処理装置が、上記選択基準値符号と基準残差符号との組を取得した値について、上記一連の値のうち上記値よりも前の値に基づいて上記値を予測することにより、上記値の予測値を算出し、
上記処理装置が、複数の残差基準値のなかから、上記選択基準値符号によって示される残差基準値を選択し、
上記処理装置が、上記復元予測部が算出した予測値と、上記基準値選択部が選択した残差基準値と、上記符号取得部が取得した基準残差符号が表わす基準残差との合計を算出することにより、上記値を復元した復元値を算出することを特徴とするデータ復元方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公開番号】特開２０１２−１１３６５７（Ｐ２０１２−１１３６５７Ａ）
【公開日】平成２４年６月１４日（２０１２．６．１４）
【国際特許分類】
【出願番号】特願２０１０−２６４３２２（Ｐ２０１０−２６４３２２）
【出願日】平成２２年１１月２６日（２０１０．１１．２６）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２４年６月１４日（２０１２．６．１４）
【国際特許分類】
【出願日】平成２２年１１月２６日（２０１０．１１．２６）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]