GTM-MML4VXJ
Skip to main content

English

Japan

圧縮アルゴリズム

可逆と非可逆

一般にデータ圧縮というと画像や音声などに使用される完全に元に戻さなくてもよい非可逆符号化(Lossy)と100%復元する可逆符号化(Lossless)があります。非可逆符号化にはJPEG,MPEGなどがあります。ここでは、後者の可逆符号化(情報保存型ともいう)について述べます。可逆符号化は、辞書型と統計型に大別されます。

辞書型

可逆符号化で最も多く利用されている辞書型(dictionary coding)の起源は、 Abraham Lempel氏とJacob Ziv氏が発表した1977年IEEE情報理論誌の論文"A Universal Algorithm for Sequential Dat Compression"であると言われています。これは通称、Lempel-Ziv符号化のスライド辞書法またはLZ77などと呼ばれています。このLZ77は、以前に符号化した入力データ列を辞書として利用し、入力データ列の中の連続した部分との最長一致を検索し、その一致情報を符号化するというものです。これが、ある範囲でのデータ列の同じ部分を探し圧縮を行う方法として発展しました。

特許問題

圧縮アルゴリズムに関する特許は、米国の会社がそのほとんどを保有しています。辞書型LZ77の実装法の有力特許は、米国のStac社が保有しており、日本でも特許が成立しています。(1997年10月31日登録 特許番号 第2713369号)現在、一般に広く普及しているアーカイバソフトのLHAやZIP系(WinZIP等)などもこのLZ77をベースにしています。

統計型

一方、辞書型とは異なる手法に統計型(statistical coding)があります。データの出現確率を予測し符号化するものです。その原理は、ある文字が出現すると、その文字がどんな文字列の直後(文脈)で、どんな頻度で出現したかの確率を覚えておき、次に同じ文脈でその文字が出現したときに確率を可変長の符号で表わし、出易い事象程、短い符号で表わすようにします。辞書型でいう同じ繰り返しの文字列というのは、統計型では、最初に出現したときに文脈関係を覚えた文字が次々に起こったものとして表わせます。統計型の方法では、繰り返しの短い文字列から長い文字列まで、文脈を覚えることで、精密に符号化することができます。

富士通の圧縮方式

株式会社富士通研究所(以下、富士通研究所と表記する)では、他社特許を回避するために統計型と辞書型を併用した SLC(Super Lossless data Compression)方式を開発しました。さらに復元速度の高速化を目指した辞書型のELC(Embedded Lossless data Compression)方式を開発しました。これらの富士通特許の最新状況は特許庁のサイトで確認できます。富士通研究所の圧縮アルゴリズムSLC/ELC方式の詳細については、プログラミング技術情報誌「C MAGAZINE」の2004年10月号(9月18日発売)「圧縮ソフトSLC/ELCのアルゴリズム(106-110ページ)」に掲載されています。このC MAGAZINEには当社が執筆した「ビジネス向けデータ圧縮の実装例」についても掲載されました(111ページ)。
この圧縮アルゴリズムに関する技術解説記事 (485 KB)

アーカイバ

当社ではLHAやWinZIPに相当するパソコン用のアーカイバとしてArcmanagerという製品を開発し販売しています。圧縮特許面で安心な富士通研究所が開発した圧縮方式を採用しています。データ圧縮ライブラリ製品としては、1995年3月より(当時はMS-DOS版)製品化していますので、実績や品質面でも安心してビジネスに利用できます。

機器への組み込み

マイコン使用機器のフラッシュメモリ節約用途の需要に応えるためには、省メモリ環境で動作することが絶対条件になります。当社では、この要求に応えるため、組み込み用途に適したデータ圧縮ライブラリESLC(Embedded Super Lossless Compression)を開発し2001年4月より販売開始しました。メモリ容量を多く必要とする圧縮のための辞書サイズを選択可能とすることにより省メモリ環境でも動作します。

高速復元と高速起動

一般にデジタル家電製品などでは使用されているフラッシュメモリの読み出し時間がかかることから起動時間の遅さが問題になっています。この対策として、データを圧縮することにより、読み出すデータ量を削減することにより時間を短縮し高速起動を実現する方法があります。そこで、当社では復元時間を高速化したデータ圧縮ライブラリRELC(Rapid Embedded Lossless data Compression)を開発し2004年8月より販売開始しました。辞書型の最長一致検索などに関して工夫を行い圧縮特許面でビジネスに使えるようにしたものです。圧縮率・圧縮速度重視のESLC、復元速度重視のRELCと組み込み向けの製品ラインナップを強化しました。いずれも富士通研究所が開発した圧縮方式を採用していますので、安心して製品に組み込めます。処理速度はフリーソフトZLIBよりも高速です。ESLCは圧縮速度が約2倍、RELCは復元速度が約2倍ZLIBと比較して高速です。ただし、CPU、メモリ、バス幅など実機環境により性能が異なります。

暗号と情報漏洩対策

最近では情報漏洩対策の需要が高まってきたため、従来のデータ圧縮ライブラリ製品と組み合わせて使用できるオプション製品として暗号ソフトウェアを開発しました。システムやアプリケーションプログラムに組み込んで利用できます。暗号方式は、米国政府標準AES(Advanced Encryption Standard)方式を採用しています。鍵長およびブロック長は128ビットです。2005年11月にはArcmanagerの一部の製品に暗号機能を追加しました。個別対応で、パスワード付スクランブル(ある演算処理を行う)圧縮も用意できます。