(57)【要約】【課題】  時系列データなどの順序が規定されたデータの圧縮を、高圧縮率で実現すること。【解決手段】  順序が規定された順序データを圧縮する順序データ圧縮方法であって、コンピュータが、順序が規定された順序データから連続する複数個の順序データを切り出し、当該複数個の順序データそれぞれについて複数個のデータ要素に分割し、当該データ要素それぞれについて順序データにおけるビット位置が同じデータ要素が連続するように当該データ要素を並べ替えてデータ要素列を作成する圧縮前処理手順と、圧縮前処理手順により作成されたデータ要素列を圧縮するデータ圧縮手順と、データ圧縮手順により圧縮されたデータ要素列を記憶手段に格納するデータ格納手順と、を実行することを特徴とする。【選択図】      図３
2007088962.tif 000002
【特許請求の範囲】
【請求項１】
順序が規定された順序データを圧縮する順序データ圧縮方法であって、
コンピュータが、
順序が規定された前記順序データから連続する複数個の前記順序データを切り出し、当該複数個の前記順序データそれぞれについて複数個のデータ要素に分割し、当該データ要素それぞれについて前記順序データにおけるビット位置が同じデータ要素が連続するように当該データ要素を並べ替えてデータ要素列を作成する圧縮前処理手順と、
前記圧縮前処理手順により作成された前記データ要素列を圧縮するデータ圧縮手順と、
前記データ圧縮手順により圧縮された前記データ要素列を記憶手段に格納するデータ格納手順と、
を実行することを特徴とする順序データ圧縮方法。
【請求項２】
前記データ圧縮手順は、ランレングス符号化により前記データ要素列を圧縮することを特徴とする請求項１に記載の順序データ圧縮方法。
【請求項３】
前記データ格納手順は、前記データ要素列の順序に従って、シーケンシャルファイルに前記データ要素列を格納することを特徴とする請求項１または請求項２に記載の順序データ圧縮方法。
【請求項４】
順序が規定された順序データを解凍する順序データ解凍方法であって、
コンピュータが、
前記順序データにおけるビット位置が同じデータ要素が連続する前記データ要素列について、圧縮された当該データ要素列を記憶手段から読み取るデータ読み取り手順と、
前記データ読み取り手順により読み取られた前記データ要素列を解凍するデータ解凍手順と、
前記データ解凍手順が解凍した、前記順序データを構成する前記データ要素列を前記順序データに統合する解凍後処理手順と、
を実行することを特徴とする順序データ解凍方法。
【請求項５】
前記データ解凍手順は、ランレングス符号化により前記データ要素列を解凍することを特徴とする請求項４に記載の順序データ解凍方法。
【請求項６】
前記データ読み取り手順は、前記データ要素列の順序に従って、前記データ要素列が格納されたシーケンシャルファイルから前記データ要素列を読み取ることを特徴とする請求項４または請求項５に記載の順序データ解凍方法。
【請求項７】
請求項１ないし請求項３のいずれか１項に記載の順序データ圧縮方法、または、請求項４ないし請求項６のいずれか１項に記載の順序データ解凍方法をコンピュータに実行させるための順序データ処理プログラム。
【請求項８】
順序が規定された順序データを圧縮する順序データ圧縮装置であって、
順序が規定された前記順序データから連続する複数個の前記順序データを切り出し、当該複数個の前記順序データそれぞれについて複数個のデータ要素に分割し、当該データ要素それぞれについて前記順序データにおけるビット位置が同じデータ要素が連続するように当該データ要素を並べ替えてデータ要素列を作成する圧縮前処理部と、
前記圧縮前処理部により作成された前記データ要素列を圧縮するデータ圧縮部と、
前記データ圧縮部により圧縮された前記データ要素列を記憶手段に格納するデータ格納部と、
を有することを特徴とする順序データ圧縮装置。
【請求項９】
順序が規定された順序データを解凍する順序データ解凍装置であって、
前記順序データにおけるビット位置が同じデータ要素が連続する前記データ要素列について、圧縮された当該データ要素列を記憶手段から読み取るデータ読み取り部と、
前記データ読み取り部により読み取られた前記データ要素列を解凍するデータ解凍部と、
前記データ解凍部が解凍した、前記順序データを構成する前記データ要素列を前記順序データに統合する解凍後処理部と、
を実行することを特徴とする順序データ解凍装置。
【請求項１０】
請求項８に記載の順序データ圧縮装置、および、請求項９に記載の順序データ解凍装置を備えることを特徴とする順序データ処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、順序データ圧縮方法、順序データ解凍方法、順序データ処理プログラム、順序データ圧縮装置、順序データ解凍装置、および、順序データ処理システムに関する。
【背景技術】
【０００２】
現在インターネット技術とセンサ技術の発展により、通信機能を有するセンサから発生する時系列データを収集する時系列センサデータ情報収集システムが実現しつつある。例えば移動体位置管理システムは走行している大量の車などをセンシングして、車の移動のログを管理する。地震監視システムは大量の散布された地震計からの情報を収集し、地震発生時の揺れ方等を記録する。
【０００３】
センシングされた時系列データは次々と流入するため、そのデータを損失することなくディスクに格納することが求められている。時系列センサデータ情報収集システムでは、あらゆるものにセンサが付加され、センサは長期間にわたり運用されるので、センサから発生する時系列データのデータ量は膨大になる。よって、時系列データを圧縮してからディスクに格納することが望ましい。
【０００４】
従来の可逆圧縮手法としてハフマン符号化（非特許文献１）やブロックソーティング（非特許文献２）が挙げられる。ハフマン符号化は圧縮時には圧縮するデータをその登場頻度に応じてハフマン木を生成し、ハフマン木に応じて符号をデータに割り当てる手法である。解凍時は同様にハフマン木を生成し、圧縮されたデータを解析する。ブロックソーティングは、圧縮時には圧縮するデータをローテーションさせ複数のデータ列を作成した後にソーティングする。ソーティングされたデータ列が圧縮の対象のデータとなる。
【非特許文献１】Huffman,D.A著，“A method for the construction of minimum redundancy codes”，In Proc. I.R.E，1952
【非特許文献２】M.Burrows and D.J. Wheeler著，“A block-sorting lossless data compression algorithm”，ISRC Research Report，1994
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、従来の可逆圧縮手法をそのまま活用するだけでは、時系列データの圧縮率を充分に高めることはできない。例えば、ハフマン符号化ではデータの登場頻度をカウントするが、時系列データは取りうる値の幅が大きい離散値であるので、多種類の値がそれぞれ低頻度で発生するような統計結果となる。その結果、圧縮率は低くなってしまう。
【０００６】
そこで、本発明は、前記した問題を解決し、時系列データなどの順序が規定されたデータの圧縮を、高圧縮率で実現することを主な目的とする。
【課題を解決するための手段】
【０００７】
前記課題を解決するために、本発明は、順序が規定された順序データを圧縮する順序データ圧縮方法であって、コンピュータが、順序が規定された前記順序データから連続する複数個の前記順序データを切り出し、当該複数個の前記順序データそれぞれについて複数個のデータ要素に分割し、当該データ要素それぞれについて前記順序データにおけるビット位置が同じデータ要素が連続するように当該データ要素を並べ替えてデータ要素列を作成する圧縮前処理手順と、前記圧縮前処理手順により作成された前記データ要素列を圧縮するデータ圧縮手順と、前記データ圧縮手順により圧縮された前記データ要素列を記憶手段に格納するデータ格納手順と、を実行することを特徴とする。
【０００８】
これにより、隣り合う値が同じになることが多いデータ要素列を作成することで、高い圧縮率で順序データを圧縮することができる。
【０００９】
本発明は、前記データ圧縮手順が、ランレングス符号化により前記データ要素列を圧縮することを特徴とする。
【００１０】
これにより、隣り合う値が同じになることが多いデータ要素列を圧縮することでランが大きくなり、高い圧縮率で圧縮することができる。
【００１１】
本発明は、前記データ格納手順が、前記データ要素列の順序に従って、シーケンシャルファイルに前記データ要素列を格納することを特徴とする。
【００１２】
これにより、高速なシーケンシャルアクセスができる。
【００１３】
本発明は、順序が規定された順序データを解凍する順序データ解凍方法であって、コンピュータが、前記順序データにおけるビット位置が同じデータ要素が連続する前記データ要素列について、圧縮された当該データ要素列を記憶手段から読み取るデータ読み取り手順と、前記データ読み取り手順により読み取られた前記データ要素列を解凍するデータ解凍手順と、前記データ解凍手順が解凍した、前記順序データを構成する前記データ要素列を前記順序データに統合する解凍後処理手順と、を実行することを特徴とする。
【００１４】
これにより、隣り合う値が同じになることが多いデータ要素列を読み取ることで、高い圧縮率で圧縮された順序データを解凍することができる。
【００１５】
本発明は、前記データ解凍手順が、ランレングス符号化により前記データ要素列を解凍することを特徴とする。
【００１６】
これにより、隣り合う値が同じになることが多いデータ要素列は、ランが大きく圧縮されているので、高い圧縮率で圧縮されたデータを解凍することができる。
【００１７】
本発明は、前記データ読み取り手順が、前記データ要素列の順序に従って、前記データ要素列が格納されたシーケンシャルファイルから前記データ要素列を読み取ることを特徴とする。
【００１８】
これにより、高速なシーケンシャルアクセスができる。
【００１９】
本発明は、前記順序データ圧縮方法、または、前記順序データ解凍方法をコンピュータに実行させるための順序データ処理プログラム。
【００２０】
これにより、隣り合う値が同じになることが多いデータ要素列を作成することで、高い圧縮率で順序データを圧縮することができる。
【００２１】
本発明は、順序が規定された順序データを圧縮する順序データ圧縮装置であって、順序が規定された前記順序データから連続する複数個の前記順序データを切り出し、当該複数個の前記順序データそれぞれについて複数個のデータ要素に分割し、当該データ要素それぞれについて前記順序データにおけるビット位置が同じデータ要素が連続するように当該データ要素を並べ替えてデータ要素列を作成する圧縮前処理部と、前記圧縮前処理部により作成された前記データ要素列を圧縮するデータ圧縮部と、前記データ圧縮部により圧縮された前記データ要素列を記憶手段に格納するデータ格納部と、を有することを特徴とする。
【００２２】
これにより、隣り合う値が同じになることが多いデータ要素列を作成することで、高い圧縮率で順序データを圧縮することができる。
【００２３】
本発明は、順序が規定された順序データを解凍する順序データ解凍装置であって、前記順序データにおけるビット位置が同じデータ要素が連続する前記データ要素列について、圧縮された当該データ要素列を記憶手段から読み取るデータ読み取り部と、前記データ読み取り部により読み取られた前記データ要素列を解凍するデータ解凍部と、前記データ解凍部が解凍した、前記順序データを構成する前記データ要素列を前記順序データに統合する解凍後処理部と、を実行することを特徴とする。
【００２４】
これにより、隣り合う値が同じになることが多いデータ要素列を読み取ることで、高い圧縮率で圧縮された順序データを解凍することができる。
【００２５】
本発明は、前記順序データ圧縮装置、および、前記順序データ解凍装置を備える順序データ処理システムである。
【００２６】
これにより、隣り合う値が同じになることが多いデータ要素列を作成することで、高い圧縮率で順序データを圧縮することができる。
【発明の効果】
【００２７】
本発明により高い圧縮率で順序データを圧縮することができる。またデータ量を小さくすることができるので、ディスクにアクセスするときのＩ／Ｏ（Input／Output）コストも低減でき、また格納するのに必要なディスク容量も小さくすることができる。
【発明を実施するための最良の形態】
【００２８】
以下に、本発明の最良の実施形態を示す。
【００２９】
図１（ａ）は、順序データ処理装置１を示す構成図である。順序データ処理装置１は、演算処理を行う際に用いられる記憶手段としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備えるコンピュータとして構成される。なお、メモリは、ＲＡＭ（Random Access Memory）などにより構成される。演算処理は、ＣＰＵ（Central Processing Unit）によって構成される演算処理装置が、メモリ上のプログラムを実行することで、実現される。以下、順序データの一例として時系列データをもとに説明を行うが、それらの説明は任意の順序データにも適用が可能である。
【００３０】
順序データ処理装置１は、圧縮前処理部１０、データ圧縮部１２、データ格納部１４、データ解凍部１６、および、解凍後処理部１８を含めて構成される。なお、順序データ処理装置１は、図１（ａ）のようなスタンドアロンの構成としてもよいし、図１（ｂ）のようなネットワークシステムの構成としてもよい。図１（ｂ）は、順序データ処理装置１が、圧縮を担当する順序データ圧縮装置２、および、解凍を担当する順序データ解凍装置３に分散され、互いにネットワークで接続され、通信部２０を介して圧縮されたデータが通信される。
【００３１】
圧縮前処理部１０は、次々と流れ込んでくる時系列データのデータ値を分割して並び替える。データ圧縮部１２は、圧縮前処理部１０が並び替えた後の時系列データを圧縮する。データ格納部１４は、例えばメモリやハードディスクなどの記憶手段により構成され、データ圧縮部１２による圧縮後の時系列データを格納する。データ解凍部１６は、データ格納部１４に格納された時系列データを解凍する。解凍後処理部１８は、データ解凍部１６による解凍後の時系列データを並び替えて統合する。
【００３２】
なお、圧縮前処理部１０から解凍後処理部１８に接続される矢印は、この方向にデータ処理に関するパラメータが通知されることを意味する。このパラメータの詳細は、後記する。パラメータの通知方法は、直接通知してもよいし、圧縮されたデータについてその属性として付加することにより、間接的に通知してもよい。さらに、順序データ圧縮装置２、および、順序データ解凍装置３は、あらかじめ設定された同じパラメータ値を互いに活用することにより、順序データ圧縮装置２から順序データ解凍装置３へのパラメータの通知処理を省略することができる。
【００３３】
図２（ａ）は、圧縮前処理部１０を示す構成図である。データ一時保存部３０は、メモリなどの記憶手段により構成され、次々と流れ込んでくる時系列データを保存する。データ分割部３２は、時系列データのデータ値を分割する。データ並び替え部３４は、作業領域としてメモリを利用することにより、分割されたデータ値を並び替える。
【００３４】
図２（ｂ）は、解凍後処理部１８を示す構成図である。データ並び替え部３４は、圧縮前処理部１０のデータ一時保存部３０に保存された時系列データの量を基に分割されたデータ値を並び替える。データ統合部３６は、並び替えられたデータ値を統合する。
【００３５】
図３は、本実施形態における時系列データの可逆圧縮方法における圧縮処理を示すフローチャートである。この圧縮処理は、圧縮アルゴリズムを実施する前に、時系列データを時間軸に沿って分割する前処理により、高い圧縮率を実現することを特徴とする。これにより、格納するデータ量を削減でき、ディスクアクセスの処理を低減できるので処理が速くなるとともに、ディスク媒体のコストも抑えられる。
【００３６】
まず、圧縮前処理部１０のデータ一時保存部３０は、時系列データを連続する順序に沿って分割し、Ｎ時間ごとに時系列データを切り出す（Ｓ１１）。なお、個々の時系列データは、計算機の内部において複数バイトの集合として表現される。以下、データ値の一例として、４バイト長のデータ値が最下位のバイトから順にデータを格納するリトルエンディアン形式を仮定して説明するが、この方式以外にも任意の形式のデータ値を扱ってもよい。なお、４バイト長のうち、４バイト目には、値の＋−を示す符号部、および、値の桁数を示す仮数部が格納されている。
【００３７】
次に、圧縮前処理部１０のデータ分割部３２は、データ一時保存部３０が切り出した各時系列データについて、１つの時系列データをＭ個のデータ列に分割する（Ｓ１２）。例えば、４バイトの時系列データを４つに分割した結果、１バイトのデータが４つ並んだデータ列が生成される。図４（ａ）は、時系列データの計算機内での内部表現を示す説明図である。時系列データのＮ個の値が、それぞれ４つずつ分割され、Ｎ個の行要素およびＭ個（４個）の列要素を有する行列が形成される。
【００３８】
さらに、圧縮前処理部１０のデータ並び替え部３４は、データ分割部３２によりバイト単位に分割されたデータを並び替える（Ｓ１３）。図５は、データの並び替え処理（Ｓ１３）を具体的に説明するフローチャートである。
【００３９】
データ並び替え部３４は、１〜Ｎまで値をとるループ変数ｉ（Ｓ１３１）および１〜Ｍまで値をとるループ変数ｊ（Ｓ１３２）を用いて、図４（ａ）に示す行列に対して、行と列とを入れ替える転置行列演算を行い（Ｓ１３３）、図４（ｂ）に示す行列を生成する。そして、データ並び替え部３４は、Ｓ１３３で生成した行列について、各行を列方向に接続することにより、図４（ｃ）に示す１行の順序列を生成する（Ｓ１３４）。これにより、時系列データを構成する同じ位（同じバイト目）のデータ同士が、隣り合うように並ぶこととなる。
【００４０】
そして、データ圧縮部１２は、データ並び替え部３４が並び替えたデータ（バイト列）に対して圧縮を行う（Ｓ１４）。符号化方式には、例えば、ランレングス符号化を用いる。ランレングス符号化はワンパスで実行できるので高速処理に向いているためである。なお、データ圧縮部１２は、例えば、次の表に示す様々な符号化方式を、単独で活用または複数の符号化方式を併用してもよい。
【表１】
2007088962.tif 000003
【００４１】
なお、Ｓ１１で切り出されたデータを、そのままＳ１４で圧縮すると、隣り合う値は似ていないため、高い圧縮率は、期待できない。しかし、Ｓ１１で切り出されたデータに、前処理（Ｓ１２，Ｓ１３）を行うことにより、隣り合う値が同じになることが多くなるので、高い圧縮率が期待できる。この効果は、特に、センサなどで計測された時系列データにおいてはデータ値が急激に変化せず、ゆるやかに（漸次的に）変化するため、顕著になる。そして、符号部および仮数部は、低頻度で変化するため、隣り合う値が同じになることが多くなる。また、時系列データを構成する各データについて、桁数が大きいデータは、桁数が小さいデータに比べて変化が少ない。
【００４２】
さらに、データ格納部１４は、データ圧縮部１２により圧縮されたデータを格納する（Ｓ１５）。格納は、圧縮されたデータの順序ごとに、データを先頭から順番にアクセスするシーケンシャルファイルの形で行うことが望ましい。これは、高速なシーケンシャルアクセスができるようにするためである。
【００４３】
以上、圧縮処理について、説明した。なお、図１における圧縮前処理部１０から解凍後処理部１８に接続される矢印に関するパラメータは、Ｓ１１における時系列データを切り出すＮ時間、および、Ｓ１２における１つの時系列データの分割数Ｍ個である。これらのパラメータは、それぞれ大きい値にすると、小さい値よりも高い圧縮率が期待できる。一方、リアルタイム処理などで時系列データの入力から圧縮された時系列データを出力するまでの処理時間を短縮化したいときには、パラメータの値を小さくすればよい。よって、処理時間が制限されたときには、制限された処理時間の範囲内で、パラメータの値を大きくした方が、高い圧縮率を実現できる。
【００４４】
図６は、本実施形態における時系列データの可逆圧縮方法における解凍処理を示すフローチャートである。この解凍処理は、図３の圧縮処理と比較すると、処理順序を逆転させたものである。
【００４５】
データ解凍部１６は、データ格納部１４から圧縮された時系列データを読み取り（Ｓ２１）、Ｓ１４の圧縮アルゴリズムに対応する解凍アルゴリズムを実施することにより、解凍を行う（Ｓ２２）。データ並び替え部３４は、Ｓ２２で解凍されたデータをＳ１３と同じ方法で並び替える（Ｓ２３）。データ統合部３６は、Ｍ個のデータ列を１つの時系列データに結合する（Ｓ２４）。解凍後処理部１８は、Ｎ時間ごとにまとめられた時系列データを出力する（Ｓ２５）。
【図面の簡単な説明】
【００４６】
【図１】本発明の一実施形態に関する順序データ処理装置を示す構成図である。
【図２】本発明の一実施形態に関する圧縮前処理部および解凍後処理部を示す構成図である。
【図３】本発明の一実施形態に関する圧縮処理を示すフローチャートである。
【図４】本発明の一実施形態に関する時系列データの計算機内での内部表現を示す説明図である。
【図５】本発明の一実施形態に関する並び替え処理を示すフローチャートである。
【図６】本発明の一実施形態に関する解凍処理を示すフローチャートである。
【符号の説明】
【００４７】
１      順序データ処理装置
２      順序データ圧縮装置
３      順序データ解凍装置
１０    圧縮前処理部
１２    データ圧縮部
１４    データ格納部
１６    データ解凍部
１８    解凍後処理部
【図１】
2007088962.tif 000004
【図２】
2007088962.tif 000005
【図３】
2007088962.tif 000006
【図４】
2007088962.tif 000007
【図５】
2007088962.tif 000008
【図６】
2007088962.tif 000009