高速・可逆な実時間データ圧縮アルゴリズムの開発研究

博士論文

資料形態 : テキストデータ プレーンテキスト

コレクション : 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文

核融合科学研究所の制御データ処理装置は、著者達が平成5年から共同研究として進めてきた「ワークステーションを用いたデータ収集・解析・制御システムの研究」の成果として開発されたものである。これは、大規模システムに対応した構成を取り、容易にCHの拡大を計る事が出来るシステムであり、アナログデータを増幅した後、アナログ・デジタル変換器（ADC）でサンプリング及びデジタイズを行い、多チャンネルの時系列データとして計算機に取り込む。これをバイナリーファイルとして保存する、データベース管理ソフトに登録すると同時にネットワークに実時間配送し、WWWブラウザーによってユーザーがデータ取り込むことが出来るシステムであり、今後の大型システムでのデータ処理システムの一つの大きな方向を示す形となった。<br />　さて、このようなシステムを考える場合、データ量が膨大となり、データの保存・転送のコストが無視できない事が予測される。そのために、圧縮によってデータ量が数分の1になれば、データ保存用のハードディスクなどの費用は数分の1になると同時にネットワークの輻榛（混雑）も数分の1に留めることが出来る。この理由によりデータ圧縮の研究を開始した。<br />　データ圧縮の技術は、情報量の損失のない可逆圧縮と、情報量の損失のある非可逆圧縮の2種類があり、後者は近年マルチメディアへの応用のために盛んに研究が行われているが、計測データに利用することは出来ない。更に、処理形態としては、実時間処理とバッチ処理があり、後者は従来から研究が広く行われてきたが、当然ながら実時間でネットワークを介して監視するデータは高速の実時間圧縮が必要になる。以上の要請のために、今回新たに高速・実時間・可逆なデータ圧縮アルゴリズムを開発し、コーディングに成功し、核融合科学研究所のデータに適用した結果を以下に述べる。<br />　データ圧縮の研究は1948年のShannonの情報理論に端を発し、その後、彼の学生であったHuffmanによって符号化による圧縮方法が考案された。現在のすべての符号化による圧縮はHuffmanにその基礎を置く。その後、1976年にRissanen他によって算術符号化が開発されるが、理解することに多大な努力を要することもあり、それほど一般化されなかった。一方、その後パーソナルコンピュータの発達もあり、Zip-LempelによってLX77，LZ78と言われる圧縮ソフトが1977年及び78年に開発され、一般に利用されるようになった。その後、WelchによってLZ78の改良が行われ、LZWと言われるコードが作られた。一方、著者等は、1988年にLZ77をベースに圧縮ソフトの開発を始め、その年に著者はLZARIを発表し、吉崎はLZHUF、LZarcを発表し、広く日本でも利用されるようになった。そして、1989年に著者は現在広く利用されているLHAと言われるソフトのアルゴリズムを発表し、1990年にC言語で書かれた圧縮ツールを発表した。そして、吉崎がLHAとして完成し、広く利用されるようになった。これとほぼ同じアルゴリズムのソフトとしては、フランスのJean-loup Gaillyによるgzipがある。<br />　さて、圧縮アルゴリズムとして上記に書いた要請があるため、以上の今までの圧縮アルゴリズムを検討し、2つの方法を採用することにした。一つはHuffmanの符号化でり、もう一つはデータの時間的変化を直前の数点のデータから予測する方法を組み合わせた方法である。従って、この方法は予測誤差符号化と言うことが出来る。具体的には、直前の数点のデータから次のデータを予測し、それからの誤差の分布を正規分布及びLaplace分布を用いて、予測誤差の分布グラフを作る・実際のデータとの比較を行うと、誤差分布は正規分布とLaplace分布の間位になっている。これは、時折、急激に変化するデータがあり、そのため予測誤差の2乗和の平均分散を推定すると、分布の中央部の度数分布から推定した分散より大きめの値を得るからである。そして、そのようにして得た分布データを長さ制限のある符号に変換する。ここでは8ビットに制限し、符号化を行った。このような、長さ制限のある符号化を行ったのは最初にLarmore and Hirschbergであり、比較的高速でメモリーを余り使わない効率の良い圧縮方法として知られている。しかし、そのような方法でも大変手間のかかる方法であり、実際に利用される符号は一部に限られるので、より単純で高速な方法を考案した。それは、場合分けを8ビットに制限した時には、406通りしかないので、予めその表を作っておき符号化手順を高速に行うことである。このような方法をとっても1シンボル当たり0.047ビットの損しかなく、これは最悪の場合であるため、実際にはほとんど影響は出ないからである。<br />　以上のアルゴリズムをコーディングし、実際の核融合科学研究所の大型ヘリカル装置のデータの圧縮を行った。実際のデータは熱電対で測定した温度、歪ゲージで測定した歪、マイクロ波の出力、磁場、コイル電流及び電圧、プラズマからの輻射などでからなるデータ群である。急激に変化するデータはやはり圧縮比はそれほど大きくなく、16ビットの生データに対して、8-10ビット程度になるが、変化の少ないデータでは２ビット以下に圧縮された。そして、それら全体を通じて、元データ（複数の性質の違ったデータをすべて含む）が8.74MBに対して、通常バッチファイルの圧縮に利用されているAip，LHAが4.8MB程度に圧縮し、今回開発したソフト（NIFSqと言う）は、2.00MBに圧縮することができた。従って、従来のソフトより圧縮比で2倍程度性能が良い。更に、圧縮時間であるが、CPUのクロックが400MHzのPentium-II，のパーソナルコンピュータ（オペレーティングシステムはLinux）ではZip，LHAに比べて3分の1から4分の1以下の時間で行うことが出来た。従って、従来のソフトに比べてかなり高速なったことが分かった。そして、適応型のソフトのために、現状のデータ処理システムではほとんど無制限なCHまで圧縮可能のソフトとなった。<br />　以上より、当初の要請は満足されたと考えるべきである。今後の課題はアルゴリズムの最適化及びユーザーインターフェースを改良した上でMacintoshなども含めた計算機環境での利用を可能にし、C++やJavaに書き直すことなどである。

application/pdf

総研大乙第62号