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ページ)。

C MAGAZINE  2004年10月号 特別記事 「圧縮ソフト SLC/ELC のアルゴリズム」 (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倍 高速です。(CPU、メモリ、バス幅など実機環境により性能は異なります。)

暗号と情報漏洩対策

当社では、情報漏洩対策の需要が高まってきたことから、従来のデータ圧縮ライブラリ製品と組み合わせて使用できるオプション製品として、暗号ソフトウェアを開発しました。

  • システムやアプリケーションプログラムに組み込み可能
  • 暗号方式 : 米国政府標準 AES(Advanced Encryption Standard)方式を採用
  • 鍵長 および ブロック長 : 128ビット
  • Arcmanager の一部の製品に暗号機能を追加 (2005年11月)
  • パスワード付スクランブル(ある演算処理を行う)圧縮の個別対応可能