JP2012253696A

JP2012253696A - 数値データの圧縮システム及び方法

Info

Publication number: JP2012253696A
Application number: JP2011126795A
Authority: JP
Inventors: Mamoru Ohara; 衛大原; Takashi Yamaguchi; 隆志山口
Original assignee: Tokyo Metropolitan Industrial Technology Research Instititute (TIRI)
Current assignee: Tokyo Metropolitan Industrial Technology Research Instititute (TIRI)
Priority date: 2011-06-06
Filing date: 2011-06-06
Publication date: 2012-12-20
Anticipated expiration: 2031-06-06
Also published as: JP5762151B2

Abstract

【課題】ＦＰＣ方式の技術的課題を解消し、浮動小数点形式の数値データの圧縮率を向上させる。
【解決手段】入力データのビット列及び予測データのビット列のそれぞれの差分による差分ビット列を所定の数の単位の組でメモリにバッファリングするバッファ部と、バッファリングされた差分ビット列のそれぞれから、符号部及び指数部に対応するビット列部分を含む所定のビット数からなる上位ビット列を、所定のビット数からなる１又はそれ以上のブロックに分割し、また分割されたブロックを、上位から下位の順に組ごとに組み替えて連結することにより、先行ビット列としてバッファリングする再構築部と、バッファリングされた先行ビット列ついて、先頭ブロックからの値が零となるブロックの連続数に基づき先行ビット列を圧縮して圧縮先行ビット列を形成する先行列圧縮部とを含む圧縮システム。
【選択図】図７

Description

本発明は、主にコンピュータによる科学技術計算や表計算のソフトウェアで一般的に採用されている浮動小数点形式の数値データの処理に関し、連続して入力される数値入力データを効率的に圧縮及び伸長するためのシステム、方法及びその装置に関するものである。

浮動小数点形式の数値データを圧縮する方式として、従来技術には、当該データを「Ａ×Ｚ + Ｒ（Ａ及びＲは実数、Ｚは整数）」の形で表現し、整数部分Ｚをエントロピィ符号化といった公知の圧縮技術を用いてデータ圧縮するものが存在する（特許文献１〜４）。また、これ以外にも、当該整数部分Ｚを辞書方式で圧縮する方式（例えば、ＬＺ形式のデータ圧縮）も存在する（非特許文献１）。

また、これらの先行技術とは別に、ＩＥＥＥ７５４において規定されている６４ビットの倍精度浮動小数点方式について、ＦＰＣという方式を用いて６４ビットの浮動小数点形式の数値を有するデータ・ストリームを圧縮するシステムが存在している（非特許文献２）。

図１に、先行技術である当該ＦＰＣのアルゴリズムの概要を示す。なお、図１は非特許文献２に記載のＦｉｇ．１（ＦＰＣｃｏｍｐｒｅｓｓｉｏｎａｌｇｏｒｉｔｈｍｏｖｅｒｖｉｅｗ）をそのまま引用したものである。ＦＰＣは、ＩＥＥＥ７５４倍精度浮動小数点形式の数値データの線形入力シーケンス（ｕｎｃｏｍｐｒｅｓｓｅｄ１Ｄｂｌｏｃｋｏｆｄｏｕｂｌｅｓ）における各６４ビット・データ値（「ｄｏｕｂｌｅ_ｂ」）に対して、（ｉ）２つの予測器「ｆｃｍ」及び「ｄｆｃｍ」を用いて各６４ビット・データ値を予測し、（ｉｉ）各予測データ値と入力データ値「ｄｏｕｂｌｅ_ｂ」をそれぞれ比較（「ｃｏｍｐａｒｅ」）し、（ｉｉｉ）比較結果に基づいて「ｄｏｕｂｌｅ_ｂ」により近い方の６４ビット値（「ｃｌｏｓｅｒｖａｌｕｅ」）を「ｓｅｌｅｃｔｏｒ」で選択し、（ｉｖ）入力データ（「ｄｏｕｂｌｅ_ｂ」）のビット列と選択された「ｃｌｏｓｅｒｖａｌｕｅ」のビット列との排他的論理和「ＸＯＲ」を計算する。次いで、（ｖ）その結果に対して、「ｌｅａｄｉｎｇｚｅｒｏｂｙｔｅｃｏｕｎｔｅｒ」において先行０バイト部分をカウントし、（ｖｉ）当該カウント値に基づいて、前記「ｓｅｌｅｃｔｏｒ」からの「ｐｒｅｄｉｃｔｏｒｃｏｄｅ」と共に「ｅｎｃｏｄｅｒ」で圧縮処理を行い、出力（「ｃｏｍｐｒｅｓｓｅｄｂｌｏｃｋ」）するものである。ここで、「ｅｎｃｏｄｅｒ」での先行０バイト部分の圧縮では、先行０バイトの数を３ビットの値にエンコードして、１ビットの「ｐｒｅｄｉｃｔｏｒｃｏｄｅ」と連結して４ビットにコード化する。最終的な出力「ｃｏｍｐｒｅｓｓｅｄｂｌｏｃｋ」は、当該４ビット・コード（ｂｉｔ_ｂ＋ｃｎｔ_ｂ）並びに圧縮されていない残余部（「ｒｅｓｉｄｕａｌ_ｂ」）で構成される。

特許文献１：特許第４０４９７９１号
特許文献２: 特許第４０４９７９２号
特許文献３: 特許第４０４９７９３号
特許文献４: 再表２００４／０９８０６６号

非特許文献１：「ISO/IEC MPEG-4 Audio Lossless Coding (ALS) におけるIEEE754浮動小数点信号の可逆圧縮」、原田ら、信学論、Vol. J89-B, No. 2, pp. 204-313, 2006.）

非特許文献２： M. Burtscher and P. Ratanaworabhan, “FPC: A High-Speed Compressor for Double-Presicion Floating-Point Data,” （http://users.ices.utexas.edu/~burtscher/papers/tc09.pdf）

本発明は、上記ＦＰＣと類似の値予測手法により数値データを圧縮する手法を基本にして、連続して入力される浮動小数点形式の数値データ・ストリームに対する圧縮率を向上することを目的とするものである。

表１は、従来技術によるデータ圧縮率の比較を示している。表中、「表計算」は単利年率０．５％の利率計算を100,000年分行ったデータ、「科学技術計算」は後述する図２のfdtdの圧縮後データ、「観測データ」は同obs_tempの圧縮後データのサイズを示したものである。上記表１からも明らかなように、特に表計算及び科学技術計算の技術分野においては、ＦＰＣ（非特許文献２）と比べ、ＺＩＰに代表される辞書方式の圧縮方式では圧縮率が十分なものとはいえない場合も多く、上述したような、浮動小数点形式の数値データを「Ａ×Ｚ + Ｒ（Ａ及びＲは実数、Ｚは整数）」の形で表し、整数部分Ｚに対して辞書方式で圧縮を行う方式（非特許文献１）においても圧縮率が十分なものとはいえない。

更に、上記ＦＰＣにおいては、そもそも倍精度浮動小数点形式の数値データの予測が困難であり、十分な圧縮率が得にくいという問題がある。当該予測困難性については、図２に参照されるグラフから更に説明される。図２のグラフにおいて、縦軸は上記〔非特許文献２〕で開示されるアルゴリズムを用いて種々のデータセットに対して行った予測の予測的中率、横軸は、ＩＥＥＥ７５４による倍精度浮動小数点形式の符号ビットを１ビット目としたときのビット位置を示している。また、「obs_temp」をはじめとする各データセットは、上記〔非特許文献２〕に開示されているとおりのものであり、ここで「fdtd」については、電磁界解析での数値計算において用いられ、本発明者がシミュレーション用に作成したものである。尚、当該「fdtd」の具体的な内容については本発明の対象外である点に留意されたい。

図示のとおり、多くのデータにおいて、１２ビット目以降のビット位置において予測的中率が低下し、的中率「０．５」（即ち、ランダムに予測したのと同じ結果）に近付いていることが分かる。即ち、従来のＦＰＣによる方式では、このような倍精度浮動小数点形式のデータ予測が困難な条件下で圧縮を行うものとなることから、十分な圧縮率を得ることは難しい。更に、上記ＦＰＣにおいては、各々の浮動小数点形式データに対して別個に圧縮処理を実施している点も圧縮率を制限する一因となっている。

そこで、本発明は、上記のような従来のＦＰＣの問題点を解消するために、上記ＦＰＣと類似の値予測手法による数値データ圧縮方式を基本にして、更に、複数の浮動小数点形式の数値データを所与の数の単位で纏めて一組で処理するように構成し、及び数値データのビット列に対し、特に予測的中率の高い上位ビット列部分とそれ以外の下位ビット列部分に分離した上で、当該上位ビット列部分と下位ビット列部分を独立して圧縮処理を実施することにより、より効果的な浮動小数点形式の数値データの圧縮率を実現することを目的とするものである。

本発明のシステムは、連続して入力される複数の入力データを、各入力データに対する予測データに基づいて圧縮するものであり、当該入力データ及び予測データの浮動小数点形式が、所定のビット数を有する符号部、指数部及び仮数部の順で表される２進数のビット列からなるように構成されている。

より具体的には、本発明のシステムは、（ｉ）入力データのビット列及び予測データのビット列のそれぞれの差分（例えば、排他的論理和）による差分ビット列を所定の数の単位の組でメモリにバッファリングするバッファ部、（ｉｉ）当該バッファリングされた差分ビット列のそれぞれから、符号部及び指数部に対応するビット列部分を含む所定のビット数からなる上位ビット列を、所定のビット数からなる１以上のブロックに分割し、また、当該分割されたブロックを、上位から下位の順に組ごとに組み替えて連結することにより、先行ビット列としてバッファリングする再構築部、（ｉｉｉ）当該バッファリングされた先行ビット列ついて、先頭ブロックからの値が零（０）となるブロックの連続数に基づき先行ビット列を圧縮して圧縮先行ビット列を形成する先行列圧縮部、を含むものである。

当該本発明のシステムにより、上述したＦＰＣ方式の技術的課題を解消し、浮動小数点数の予測が困難な状況であっても、圧縮率を向上させることを可能にする。

また、本発明のシステムにおける上記再構築部は、更に、上記連結された先行ビット列に対して、上位のブロックから順に値が非零（０でない）となるブロックを検査し、及び下位のブロックから順に値が零（０）となるブロックを検査し、当該非零ブロック及び当該零ブロックがそれぞれ検出された場合には、これらを入れ替えるように構成される。

当該構成により、例えば、浮動小数点数の絶対値はほぼ等しいものの、符号ビットだけが異なるような振動データが連続して入力された場合にも十分な圧縮率を確保することを可能にする。

更に、本発明のシステムにおける圧縮部は、差分ビット列から上位ビット列を除いた下位ビット列を組ごとに連結して形成される残余ビット列を、所定のビット数からなるブロックの単位で分割するように構成され、当該ブロックの単位で分割された各ブロックのうち、零（０）が所定のバイト数以上含まれるブロックを抽出及び削除することに基づいて、残余ビット列を圧縮する残余列圧縮部を備える。

このように下位ビット列、即ち、浮動小数点形式の数値データにおける仮数部に対しても圧縮処理を行うことで、浮動小数点数の圧縮率を更に向上させることができる。同じ浮動小数点数が連続して入力されるような容易に予測可能データが入力される場合に特に有利である。

図１は、従来技術のＦＰＣ方式の概要を示すブロック図である。図２は、従来技術の倍精度浮動小数点形式の数値データの予測困難性を示すグラフである。図３は、ＩＥＥＥ７５４で標準化されている倍精度浮動小数点データの表示形式を示す図である。図４は、本発明の第１実施形態における圧縮方式の概要を示すブロック図である。図５は、入力データＡ_ｎと予測データＰ_ｎから差分ビット列Ｄ_ｎを生成するイメージ図である。図６は、本発明の第１実施形態の圧縮方式における圧縮器５の詳細を示すブロック図である。図７は、本発明の第１の実施形態の圧縮方式におけるブロック組み替えに基づく再構築部の先行ビット列及び残余ビット列の形成を示すイメージ図である。図８は、先行列圧縮部の圧縮先行ビット列の形成を示すイメージ図である。図９は、本発明の第２の実施形態の圧縮方式のアドレス再構築部におけるブロック入れ替えを示すイメージ図である。図１０は、本発明の第２実施形態におけるアドレス再構築部におけるブロック入れ替え処理に係るより詳細なイメージ図である。図１１は、本発明の第２実施形態におけるアドレス再構築部におけるブロック入れ替え処理を示すフローチャートである。図１２は、本発明の第３実施形態における圧縮システムの改良の概要を示すブロック図である。図１３は、本発明の第３実施形態における２つの予測値に基づく２つの差分値計算を示すイメージ図である。図１４は、本発明の第３実施形態における２つの差分値に基づく比較器出力を示すイメージ図である。図１５は、発明の第３実施形態における先行ビット列の圧縮を示すイメージ図である。図１６は、本発明の第４実施形態における浮動小数点形式の数値データの圧縮方式を示すブロック図である。図１７は、本発明の第４実施形態の残余列圧縮部における残余ビット集合列Ｒの形成を示すイメージ図である。図１８は、本発明の第４実施形態の残余列圧縮部において圧縮される残余ビット集合列Ｒ’を示すイメージ図である。

本発明の実施形態に係る圧縮・伸長システムを図面に基づいて説明する。尚、以下の実施形態は例示に過ぎず、特許請求の範囲に記載の発明がこれに限定されるものではない。

図３は、ＩＥＥＥ７５４で標準化されている倍精度浮動小数点形式の数値データを２進数のビット列で表示する概要図である。ＩＥＥＥ７５４で標準化されている倍精度浮動小数形式のデータは、以下の計算式に基づいて表されるものである。

ここで、「Ｓ」は符号部、「ｅｘｐ」は指数部、及び「ｆｒａｃｔｉｏｎ」は仮数部を示しており、図３のように２進数の表示形式において、上位ビットから順にそれぞれ１ビット、１１ビット、及び５２ビット、合計６４ビットから形成される。

以下、ＩＥＥＥ７５４で標準化されている倍精度浮動小数点形式の数値データに基づいて各実施形態を記載するが、本発明は、特に注記するもののほか、６４ビットの倍精度浮動小数点形式の数値データに限定されるものではなく、ＩＥＥＥ７５４で同様に標準化されている３２ビットの単精度浮動小数点形式の数値データのみならず、この他多倍長精度の浮動小数点形式（例えば、１２８ビット）の数値データにも適用でき、符号部、指数部及び仮数部で上位から下位の順に構成される２進数のビット列で表現される浮動小数点形式の数値データ全般に適用できるものである。

実施形態

第１実施形態
図４は、本発明の圧縮システムの概要を示すブロック図である。入力される複数の浮動小数点形式の数値データに対し、コンピュータの中央処理装置は、レジスタやキャッシュ・メモリを含むメモリ操作を行いながら、各構成要素において次のように動作する。

入力列１は、連続して入力されるＮ個の浮動小数点形式の入力データＡ_ｎ（ｎ＝１，２，・・・，Ｎ）を示している（Ｎは１以上の整数）。入力データＡ_ｎは、差分器４に順次入力されるとともに、遅延器２において１クロック分遅延されて遅延器２から結合される予測器３に入力される。予測器３では、入力データＡ_ｎが差分器４に入力されるタイミングと同期して、既に入力されていた入力データＡ_０〜Ａ_{（ｎ−１）}(但し、Ａ_０は入力列に先行する仮想的なデータ)から予測される浮動小数点形式の予測データＰ_ｎを予測して、予測器３から結合される差分器４に入力する。差分器４では、入力された入力データＡ_ｎ及び予測された予測データＰ_ｎの各ビット列の差分（例えば、排他的論理和）を計算し、差分ビット列Ｄ_ｎとして出力する。

なお、図５に示したとおり、ここでの予測データＰ_ｎは、例えば、非特許文献２に開示される公知技術を適用して、入力データＡ_０〜Ａ_{（ｎ−１）}から予測することができ、また、差分ビット列Ｄ_ｎのビット列表現においては、予測的中率の高い上位ビットほど「０」の出現確率が高いと想定される（図２も参照）。

当該差分器４に結合される圧縮器５において、以下の図６に詳述する本発明の圧縮処理を行い、
を行う（Ｍは任意の自然数である）。

図６は、本発明の圧縮方式における圧縮器５内部の詳細を示すブロック図である。

圧縮器５は、差分器４からの複数の差分ビット列Ｄ_ｎを所定の数（ここではＭ個）の単位の組でメモリにバッファリングするバッファ部５１、バッファリングされた１組の各差分ビット列Ｄ_ｎについて、浮動小数点形式の符号部及び指数部に対応するビット列部分を含む所定のビット数からなる上位ビット列を、所定のビット数からなる１又はそれ以上のブロックに分割、及び当該分割されたブロックを上位から下位の順に組ごとに組み替えて連結を行い、先行ビット列としてバッファリングし、また、当該差分ビット列から上位ビット列を除いた下位ビット列を組ごとに連結して形成されるビット列を残余ビット列としてバッファリングする再構築部５２、及び、当該先行ビット列に対して圧縮処理を行って出力する先行列圧縮部５３を備えている。

更に図６の再構築部５２について説明すると、図７に示すような態様で、各データのビット列を上位から８ビット（１バイト）、４ビット（１／２バイト）、４ビット（１／２バイト）、及びそれ以外の４８ビット（１２バイト）の順にブロック分割し、上位ビット列のブロック（８ビット＋４ビット＋４ビット）および下位ビット列（４８ビット）について、それぞれのブロックを組単位で組み替えて上位ブロックから順番に連結してメモリにバッファリングする、アドレス演算を行うアドレス再構築部５２１、先行ビット列をバッファリングする先行列バッファ５２２、及び残余ビット列をバッファリングする残余列バッファ５２３を備えている。

図２のグラフで示したとおり、本構成は、連続して入力される複数の入力浮動小数点に対してそれぞれ予測される予測データのうち、上位の数バイト部分については比較的高い予測的中率で予測できるという特徴に着目したものであり、所定のＭ個の差分ビット列のうち当該部分をブロック単位でまとめて組み替えた上で圧縮処理することで従来のＦＰＣと比べて圧縮率を向上させるものである。

ここで、図７に示す先行ビット列及び残余ビット列の構成について更に詳細に説明する。なお、ここでは簡単のためにＭ＝４として説明するが、これに限定されるものではなく、Ｍは任意の自然数とすることができる。

差分器４から入力される複数のデータのうち、連続して入力される４個（即ち、Ｍ個）のデータのビット列（Ｄ_ｎ〜Ｄ_{（ｎ＋３）}）がバッファ部５１にバッファリングされる。ここで、各ビット列の上位２バイト（１６ビット）は、符号部（上位１ビット）及びそれに続く指数部（１１ビット）の計１２ビットを含むものである。再構築部５２では、各データのビット列を符号部（１ビット）と指数部（１１ビット）を含む上位１６ビット（２バイト）からなる上位ビット列、及びそれ以外の４８ビット（６バイト）の下位ビット列に分離し、更に当該上位ビット列を８ビット（１バイト）の第１ブロック及び４ビット（１／２バイト）の２つの第２及び第３ブロックに分割する。ここで、２つの第２及び第３ブロックに分割しているのは、第１ブロック及び第２ブロックの合計１２ビットが、符号部（上位１ビット）と指数部（１１ビット）との合計１２ビットに一致するようにするためである。図７では、第１ブロックがブロック〔１〕〜〔４〕、第２ブロックがブロック〔５〕〜〔８〕、そして第３ブロックがブロック〔９〕〜〔１２〕である。なお、下位のブロックは、４８ビット（６バイト）の下位ビット列でそのまま構成される（ブロックＩ〜ＩＶ）。

再構築部では、更に、図７に示すように、上位ビット列及び下位ビット列について、各ブロックを組単位で組み替えて上位ブロックから順に連結し、６４ビットの先行ビット列Ｌ_ｉ及び１９２ビットの残余ビット列Ｒ_ｉとして形成して、メモリ（先行列バッファ５２２及び残余列バッファ５２３）にバッファリングする。即ち、形成される先行ビット列Ｌ_ｉは、第１ブロック（ブロック〔１〕〜〔４〕）、第２ブロック（ブロック〔５〕〜〔８〕）、第３ブロック（ブロック〔９〕〜〔１２〕）の順番で連結したものである。同様に、形成される残余ビット列Ｒ_ｉは、ブロックＩ〜ＩＶの順番で連結したものである。

次いで、当該先行ビット列Ｌ_ｉを先行列圧縮部５３に入力し、図８に示すように圧縮先行ビット列（ζ＋Ｕ_ｉ）を形成する。即ち、形成された６４ビットの先行ビット列Ｌ_ｉについて、１ブロックを１バイト（即ち８ビット）として、先頭ブロックから値が零（０）の連続するブロック部分Ｚ_ｉとそれ以外のブロック部分Ｕ_ｉに分割し、Ｚ_ｉの連続ブロック数（バイト数）ｚをカウントする。当該連続ブロック数ｚに基づいて先行ビット列Ｌ_ｉを圧縮して圧縮先行ビット列を形成する。Ｍ＝４である場合には、例えば、次の表２に表すテーブルを参照することで、８×ｚビットを３ビットに圧縮する。

例えば、先行ビット列Ｌ_ｉ全体が零（０）の場合には、６４ビットの先行ビット列Ｌ_ｉを３ビットにまで最大限圧縮することができる。そしてＭが特に２の階乗（即ち、Ｍ＝２^ｍ）のときは、Ｍ×１６（ビット）の先行ビット列Ｌ_ｉを最大（ｍ＋１）ビットにまで圧縮することができることになる。

図８の例の場合、Ｚ_ｉの連続ブロック数ｚは、「２」である。このときの３ビットのζは、表２より、「００１」と表される。即ち、６４ビット（先行ビット列Ｌ_ｉ）のビット列を、３ビット（「００１」；ζ）＋４８ビット（非零ブロック；Ｕ_ｉ）の合計５１ビットに圧縮することができている。

第２実施形態
本発明による第２の実施形態では、第１の実施形態における先行ビット列Ｌ_ｉの圧縮率を向上させるために、アドレス再構築部５２１において、更に、図９〜図１１に示すブロックの入れ替え処理を行う。

第１実施形態に基づく複数の浮動小数点形式の数値データに対するブロックへの分割及び組み替えに関する構成を実施する場合に、絶対値はほぼ等しいものの、符号部のビットのみが異なるような振動データに対する圧縮が不十分なものとなる場合があるという課題を解決することができる。

図９に示すとおり、先行ビット列Ｌ_ｉに対して、上位ブロックから順に非零ブロックがあるか検査し、また、下位ブロックから順に零ブロックがあるか検査し、それぞれブロックが存在し検出された場合には、ブロックの入れ替えを行う。これにより、先頭ブロックから値が零（０）の連続するブロック部分Ｚ_ｉを拡張し、かつ、それ以外のブロック部分Ｕ_ｉを短縮することができる。

伸長されたブロック部分Ｚ’_ｉは、上述した表２の３ビットζに、入れ替えフラグ１ビット、及び入れ替えブロック位置を示すビット列（８ビット）を加えた合計１２ビットのζ’に圧縮することができる。最終的には、先行ビット列Ｌ_ｉは、当該１２ビットのζ’にブロック入れ替え後のＵ’_ｉを連結したブロックに圧縮することができる（Ｍ＝４の場合）。ここでの入れ替え位置を示すビット位置は、２×Ｍビット長のビットマップであり、入れ替えたブロック位置に対応するビットを「１」とするものである。

図１０は、第２実施形態における先行ビット列Ｌ_ｉの別の実施例を示している。当該実施例を図１１のフローチャートと共に説明する。尚、図１０においても、Ｍ＝４とし、また、１ブロックは１バイトで構成し、簡単のために先行ビット列Ｌ_ｉ及びＬ’_ｉは１６進数で表示している。

先行ビット列Ｌ_ｉに対して、上位ブロック（ブロック１）から順に非零ブロックを検査する（Ｓ１００）。ここでは、ブロック２が「８０」であり、非零ブロックとして検出される（Ｓ１１０）。そして、先行ビット列Ｌ_ｉに対して、下位ブロック（ブロック８）から順に零ブロックを検査する（Ｓ１２０）。ここでは、ブロック８が「００」であり、零ブロックとして検出される（Ｓ１３０）。この場合、それぞれの検査ブロック位置の関係が「２＜８」を満たしていることから（Ｓ１４０）、ブロック２「８０」とブロック８「００」とを入れ替えるように操作し（Ｓ１５０）、入れ替えフラグ・ビットを「１」にし（Ｓ１６０）、更に、入れ替えブロック位置ビット列の第２ビットと第８ビットをそれぞれ「１」にする（Ｓ１７０）。この処理の結果、ζ及びＬ_ｉは、図１０に示すζ’及びＬ’_ｉのように更新される。

引き続き、検査を繰り返して、ブロック３から順に非零ブロックを検査していき、ブロック５の「０１」を検出する（Ｓ１００及びＳ１１０）。また、ブロック７から順に零ブロックを検査していき、ブロック６の「００」を検出する（Ｓ１２０及びＳ１３０）。そして、それぞれの検査ブロック位置の関係が「５＜６」であるので（Ｓ１４０）、同様に、これらのブロックを入れ替えるように操作し（Ｓ１５０）、入れ替えフラグ・ビットを「１」にして（Ｓ１６０）、更に入れ替えブロック位置ビット列の第５ビット及び第６ビットをそれぞれ「１」にする（Ｓ１７０）。この処理の結果、ζ’及びＬ’_ｉは図１０に示すζ’’及びＬ’’_ｉのように更新される。

引き続き、検査を繰り返して、非零ブロックとしてブロック６を、零ブロックとしてブロック５を検出するが（Ｓ１００〜Ｓ１３０）、検査ブロック位置の関係が「６＞５」となり（Ｓ１４０）、これはすでに検査済みであることを意味するものであるため、繰り返しの検査処理を抜け、入れ替え処理を完了（ＥＮＤ）する。

このような入れ替え処理により、第１実施形態では、先頭ブロックから値が零（０）の連続するブロック部分Ｚ_ｉのブロック数ｚ＝１であったものが、第２実施形態では、先頭ブロックから値が零（０）の連続するブロック部分Ｚ’_ｉのブロック数ｚ’’＝５とすることができ、圧縮率の向上に成功する。

以上より、本実施形態では第１実施形態に対して圧縮率を更に向上させることができる。なお、上記入れ替え処理の各ステップは、一例を示しているに過ぎずこれに限定されることはない。即ち、ブロック同士を入れ替え、入れ替えフラグ・ビットを更新することができる処理であればどのような態様で実施してもよい。

第３実施形態
本発明による第３の実施形態は、主に、上記第１実施形態における、予測器３及び差分器４を用いて複数の入力された入力データＡ_ｎ及び複数の予測された予測データＰ_ｎの各ビット列の差分（例えば、排他的論理和）から複数の差分ビット列Ｄ_ｎを出力するという構成についての代替の実施の形態を示すものである。

図１２に示すとおり、本実施形態では、２つの予測器３１、３２を用いて２つの異なる方式で２種類の予測値を計算する。差分器４１、４２において、２つの差分値を計算して圧縮器５’に出力する。そして、圧縮器５’が備える比較部５０において所定のルールに基づいて差分値を当該２つの差分値から選択し、どちらの差分値を選択したかを示す選択ビットと共にバッファ部５１’（図示せず）に内部出力する。この結果、圧縮器５’からの圧縮出力Ｃ’_ｉには、Ｍビット（この場合４ビット）の選択ビット列（選択信号）も含まれることになる。

以下、図１２〜図１５を用いて詳細に説明する。

第１実施形態においては、図５に示したとおり、入力データＡ_ｎが比較器４に入力されるタイミングと同期して、入力されていた入力データＡ_０〜Ａ_{（ｎ−１）}から予測される予測データＰ_ｎを予測器３で予測し、差分器４において、入力データＡ_ｎ及び予測データＰ_ｎの各ビット列の差分（例えば、排他的論理和）を計算し、差分ビット列Ｄ_ｎとして出力している。これに対し、本実施形態においては、図１２及び１３に示すとおり、２つの予測器３１、３２を用いて同様に予測データＰ_ｎ及びＱ_ｎをそれぞれ別々に予測し、当該２つの予測器３１、３２にそれぞれ結合される２つの差分器４１、４２を用いて入力データＡ_ｎと予測データＰ_ｎ及びＱ_ｎとの各ビット列の差分（例えば、排他的論理和）をそれぞれ計算して、差分ビット列Ｄ_ｎ及びＥ_ｎとして圧縮器５’にそれぞれ出力する。

圧縮器５’では、まず、比較部５０によって、差分ビット列Ｄ_ｎ及びＥ_ｎの比較・選択を行う。なお、当該比較・選択に際しては、所定のビット数からなるブロックに分割して処理を行うが、ここでのビット数は、１バイト（即ち８ビット）でも１ビットでもよく、任意の数とすることができる。ここでは、バイト単位でブロックを形成することを想定する。

図１４に８個のブロック（ブロック１〜８）からなる、６４ビットの２つの差分ビット列Ｄ_ｎ及びＥ_ｎの具体例を示す。なお、各ブロックの値は簡単のため１６進数で表示している。比較部５０では、各差分ビット列に対し、値が零（０）となる零ブロックの数ｂをカウントし、当該零ブロック数ｂが大きい方の差分ビット列を選択する。図１４の場合は、差分ビット列Ｄ_ｎ及びＥ_ｎの各零ブロック数ｂ_ｄ（＝４）及びｂ_ｅ（＝２）の値より、値が大きい方の差分ビット列Ｄ_ｎを選択出力Ｆ_ｎとして出力する。その際、どちらの差分ビット列を選択したかを示す１ビットの選択信号Ｓ_ｎを、例えばＤ_ｎを選択した場合はＳ_ｎ＝０、Ｅ_ｎを選択した場合はＳ_ｎ＝１として、併せて出力する。

このように、予測器３１、３２での予測精度がより高いものに対する差分ビット列を、比較部で選択するように圧縮器を構成することにより、その後の圧縮処理における圧縮率を向上させることができる。

図１５は、本実施形態の圧縮器５’において、先行列バッファ５２２にバッファリングされた６４ビットの先行ビット列Ｌ_ｉの圧縮に係る構成を図示したものである。尚、ここでもＭ＝４と仮定しており、先行ビット列Ｌ_ｉ自体は第１実施形態において説明したのと同様に構成される。また、当該先行ビット列Ｌ_ｉから構成されるζ及びＵ_ｉについても第１実施形態と同様である（図８参照）。先行ビット列Ｌ_ｉは、このζに、１×４ビット（即ちＭビット）の選択信号Ｓ_ｎ〜Ｓ_{（ｎ＋３）}を加えて圧縮することができる。

本発明は、本実施形態における差分ビット列の選択に係る構成に、更に実施形態２における先行ビット列に対するブロックの入れ替えに係る構成を組み合わせることにより、より一層データの圧縮率を向上させることができる。

なお、上述した差分ビット列Ｄ_ｎ及びＥ_ｎの比較・選択について、差分器４１、４２に結合するように配置された上記比較部５０で比較・選択を実施するのに替えて、差分ビット列Ｄ_ｎ及びＥ_ｎ両方に対してバッファ部及び再構築部での処理並びにバッファリングを実施し、及び、先行列バッファから比較部５０を結合するように比較部５０を配置して、当該比較部５０で先行列バッファに対して同様の比較・選択の処理を行うように構成することも可能である。

以上の実施形態１〜３においては、ＩＥＥＥ７５４に規定される倍精度浮動小数点形式の数値データのビット列に対して、ブロックの分割をバイト単位（即ち、８ビット単位）により実施するものであるが、本発明はこれに限定されるものではなく、ＩＥＥＥ７５４に規定されるように、浮動小数点形式の数値データが符号部、指数部及び仮数部を用いて表現され、かつ、２進数のビット列が上位からこの順序で構成されるものであれば任意のデータに対して実現することができ、また、図７に示した分割するブロックの単位も、先行列を構成する上位ビット列が符号部及び指数部を含むものであればよく、バイト単位に限定されず、任意のビット数でよい。即ち、符号部及び指数部のビット数で分割ブロックを構成してもよく、更には符号部及び指数部のビット数の約数で１ブロックを構成し、複数ブロックで符号部及び指数部を含む上位ビット列としてもよい。

第４実施形態
上述した実施形態１〜３では、先行ビット列に対して圧縮処理を行う構成であったが、第４の実施形態では、更に、残余ビット列に対しても圧縮処理を行う。

本発明は、上述のとおり浮動小数点形式の数値データの予測困難性に着目したものであり、これを前提とした上で浮動小数点形式の数値データの圧縮率を向上させるものである。

これに対し、同じ値のデータが連続するような一般に容易に予測可能とされるデータに対してこのような圧縮方式を適用した場合には、先行技術文献に記載されるような従来技術を適用した場合と比べて圧縮率が同等若しくはそれ以下になることも想定される。

そこで、本実施形態では、このような容易に予測可能な浮動小数点形式の数値データが入力された場合でも圧縮率を向上させるため、更に、残余ビット列に対して、以下に説明する圧縮方式を適用することにより、圧縮率を向上させる。

図１６は、本実施形態における浮動小数点形式の数値データの圧縮システムを表すブロック図である。図６と比べて、残余列圧縮部５４が追加されている。残余列圧縮部５４は、残余列バッファ５２３にバッファリングされている残余ビット列の入力を受け、圧縮処理を行って圧縮出力をするものである。尚、残余列圧縮部５４以外の各構成要素については、上述の実施形態１〜３に基づいて実現することができる。

以下に、図１７〜図１８を用いて残余列圧縮部５４における残余ビット列Ｒ_ｉに対する圧縮方式について説明する。尚、上述のとおり、残余ビット列Ｒ_ｉはＭ個の４８ビット（即ち、６バイト）のビット列で構成される（図７参照）。

図１７は、残余列圧縮部５４において、残余ビット列Ｒ_ｉについて
をバッファリングしてまとめて連結し、残余ビットの集合列Ｒを形成する構成について記載している。ここでは、残余ビット列Ｒ_ｉにおけるＭ個の６バイト列をｒ_{（ｉ，１）}〜ｒ_{（ｉ，Ｍ）}としている。このようにして形成される残余ビット集合列Ｒは、６×Ｎバイト長のものとなる。残余ビット集合列Ｒに対し、図１８に示すように６バイトの
の中から零（０）が６バイト連続する（即ち、値が０）もの、又は零（０）が５バイト含まれるものを抽出して、この抽出した位置を示す位置列Ｈを形成する。尚、零（０）が５バイト含まれるｒ_{（ｉ，ｊ）}については、当該ｒ_{（ｉ，ｊ）}内の非零（０でない）となるバイトの位置、及びそのビット列を別途記憶する。図１８においては、ｒ_{（ｉ０，１）}及びｒ_{（ｉ１，３）}が、零（０）が６バイト連続するもの又は零（０）が５バイト含まれるものに該当し、これらの位置をＨ_１及びＨ_２として位置列Ｈを生成する。

より具体的には、Ｈ_１＝Ｍ×（ｉ_０−１）＋１、Ｈ_２＝Ｍ×（ｉ_１−１）＋３の値から成る位置列Ｈを形成することになる。ここで、位置列Ｈの各構成要素は、ｎ_ｈバイト長となる。ｎ_ｈは、位置を記憶するために必要な容量であり、６バイトより小さくて済むようにする。

一方、残余ビット集合列Ｒは、当該残余ビット集合列Ｒから、これらｒ_{（ｉ０，１）}及びｒ_{（ｉ１，３）}を削除することで圧縮され、圧縮残余ビット集合列Ｒ’が形成される。

この結果、当初６×Ｎバイト長だった残余ビット集合列Ｒは、（６×Ｎ−２×６）バイト長の圧縮残余ビット集合列Ｒ’に圧縮することができる。圧縮残余ビット集合列Ｒ’及び位置列Ｈを圧縮出力として出力することで圧縮処理は終了する。

本発明は、本実施形態において説明した残余ビット列に対する圧縮処理を、実施形態１〜３で記載した先行ビット列圧縮処理と併せて実施することで、特に、予測が容易な浮動小数点形式の数値データが連続して入力されるような場合に有効なものとなる。

なお、本実施形態における位置列Ｈは、特定のｒ_{（ｉ，ｊ）}の絶対位置を構成要素とするものであり、各構成要素は６バイトより小さい値で構成されるものであるが、特に実装上の観点からは、絶対位置ではなく相対位置として１バイトで各値を表現することができるようにし、当該相対位置、非零バイトｒ_{（ｉ，ｊ）}の位置、非零バイトｒ_{（ｉ，ｊ）}のビットパターンの３バイトを一組として非零バイトｒ_{（ｉ，ｊ）}の出力とするようにすることもできる。更に、相対位置列に同じ値が連続して含まれる場合には、例えば、ランレングス法による圧縮手法を適用することにより、更なる数値データの圧縮が可能となる。

以上、本発明の第１実施形態〜第４実施形態に係る連続して入力される複数の浮動小数点形式の数値データの圧縮方式について説明した。これらの実施形態の説明から分かるとおり、本圧縮方式は可逆式の圧縮方式であり、入力データＡ_ｎ（ｎ＝１，２，・・・，Ｎ）に対する
について、ｉ＝１，２・・・の順に圧縮動作と逆動作を行うことで、圧縮出力Ｃ_ｉを伸長して入力データＡ_ｎ（ｎ＝１，２，・・・，Ｎ）を復元することが可能である。

圧縮結果

表３は、上述した表１に本願発明の一実施形態に基づいて実装し取得したデータを追加したものである。表３のとおり、本願発明の浮動小数点データの圧縮方式は、従来技術のＦＰＣ方式と比較すると、相対的に圧縮率の向上を実現することができている。

産業上の利用分野

本発明の圧縮及び伸長システムは、連続して入力される複数の浮動小数点形式の数値入力データを効果的に圧縮してデータを取り扱うことができるため、大規模データを特にＩＥＥＥ７５４に規定される倍精度浮動小数点形式において処理し、メモリに記憶する必要があるようなアプリケーションにおいて、有利なものとなる。

具体的には、（ｉ）表計算ソフトウェアにおいてセルに記憶する大規模データを浮動小数点形式の数値データとして記憶する場合、（ｉｉ）科学技術計算ソフトウェアの計算経過を主記憶内に保存する場合、（ｉｉｉ）フライトレコーダやドライブレコーダにおいて処理される実時間データのログを圧縮して記憶する場合、宇宙観測機から地球への通信といった狭帯域通信路において大規模データの通信を必要とする場合に、本発明によるシステム及び方法は特に有効なものとなる。

Claims

連続して入力される複数の入力データを各前記入力データに対する予測データに基づいて圧縮するシステムであって、
前記入力データ及び前記予測データの浮動小数点形式が、所定のビット数を有する符号部、指数部及び仮数部の順で表される２進数のビット列からなるように構成され、
前記入力データのビット列及び前記予測データのビット列のそれぞれの差分ビット列を所定の数の単位の組でバッファリングするバッファ部と、
前記バッファリングされた差分ビット列のそれぞれから、前記符号部及び前記指数部に対応するビット列部分を含む所定の数のビット数からなる上位ビット列を、所定のビット数からなる１以上のブロックに分割、及び該分割されたブロックを上位から下位の順に前記組ごとに組み替えて連結を行うことにより、先行ビット列としてバッファリングする再構築部と、
前記バッファリングされた先行ビット列ついて、先頭ブロックからの値が零となるブロックの連続数に基づき前記先行ビット列を圧縮して圧縮先行ビット列を形成する先行列圧縮部と、を含むシステム。
請求項１に記載のシステムにおいて、
前記再構築部が、更に、前記連結が行われた先行ビット列に対して、上位のブロックから順に値が非零となるブロックを検査し、及び下位のブロックから順に値が零となるブロックを検査し、当該非零ブロック及び当該零ブロックがそれぞれ検出された場合には、これらを入れ替えるように構成され、
前記先行列圧縮部において形成される前記圧縮先行ビット列が、更に、前記入れ替えたブロックの位置を示すビット列を含む、システム。
請求項１又は２に記載のシステムにおいて、前記予測データが第１の予測データ及び第２の予測データを含み、前記システムは、更に、
前記バッファ部においてバッファリングされる前記差分ビット列が、前記入力データのビット列と前記第１予測データ及び前記第２予測データのビット列とのそれぞれの差分による第１の差分ビット列及び第２の差分ビット列から選択されて、前記バッファ部に出力される比較部を含み、
該選択は、前記第１差分ビット列及び前記第２差分ビット列がそれぞれ備える前記所定のビット数のブロックの数に基づいて行われる、システム。
請求項１から３のいずれか１項に記載のシステムにおいて、前記入力データ及び前記予測データが、ＩＥＥＥ７５４に規定される６４ビットの倍精度浮動小数点形式のデータであり、
前記再構築部で分割されるブロックがバイト単位であり、更に、前記差分ビット列の上位ビット列が、１バイトの第１のブロック、１／２バイトの第２のブロック、及び１／２バイトの第３のブロックの順に分割して形成されることを含む、システム。
請求項１から３のいずれか１項に記載のシステムにおいて、
前記上位ビット列のビット数が、前記符号部及び前記指数部を表すビット数であり、前記再構築部で分割されるブロックが、該ビット数の単位に基づいて構成される、システム。
請求項１から５のいずれか１項に記載のシステムにおいて、
前記再構築部が、更に、前記差分ビット列から前記上位ビット列を除いた下位ビット列を組ごとに連結して形成される残余ビット列を、所定のビット数からなる第４のブロックの単位で分割するように構成され、更に、
該第４のブロックの単位で分割された各ブロックのうち、零が所定のバイト数以上含まれるブロックを抽出及び削除することに基づいて、前記残余ビット列を圧縮する残余列圧縮部を備える、システム。
連続して入力される複数の入力データを各前記入力データに対する予測データに基づいて圧縮する方法であって、
該方法は、コンピュータによって実施され、
前記入力データ及び前記予測データの浮動小数点形式が、所定のビット数を有する符号部、指数部及び仮数部の順で表される２進数のビット列からなるように構成され、
前記入力データのビット列及び前記予測データのビット列のそれぞれの差分ビット列を所定の数の単位の組でメモリにバッファリングするバッファ・ステップと、
前記バッファリングされた差分ビット列のそれぞれから、前記符号部及び前記指数部に対応するビット列部分を含む所定のビット数からなる上位ビット列を、所定のビット数からなる１以上のブロックに分割、及び該分割されたブロックを上位から下位の順に前記組ごとに組み替えて連結を行うことにより、先行ビット列としてバッファリングする再構築ステップと、
前記バッファリングされた先行ビット列について、先頭ブロックからの値が零となるブロックの連続数に基づき前記先行ビット列を圧縮して圧縮先行ビット列を形成する先行列圧縮ステップと、を含み、
前記再構築ステップが、更に、前記連結された先行ビット列に対して、上位のブロックから順に値が非零となるブロックを検査し、及び下位のブロックから順に値が零となるブロックを検査し、当該非零ブロック及び当該零ブロックがそれぞれ検出された場合には、これらを入れ替えるように構成されることを特徴とする、方法。