Cマガジン圧縮記事後日談

これはCマガジン1998年10月号52-62ページの拙稿「データ圧縮アルゴリズム」のサポート情報です。もし何かありましたら何なりと奥村までご一報下さい。

なお，元記事を読んでいただかないと誤解を招くところもあるようなので，新たに データ圧縮と特許 というページを書きつつあります。そちらの方からお読み下さい。

[2001-03-09] リンクを修正しました (Thanks: 富士通様)。 内容が古くなってしまっていますが，なかなか書き直す時間がありません。すみません。

[訂正]

特許番号第2713369号に対応するのは， スタック社の特開平7-111460（1995/04/25）「データ圧縮装置及び方法」 ではなく，特開平03- 68219[H 3. 3.25]だとのことです。

スタック社の圧縮関連の日本国内出願は3件あり， 今回問題になっているのは 1/3 の特許番号第2713369号です。 特開平7-111460（3/3）はこの登録特許からの分割出願になっており， まだ未登録ですので権利化されていません。

特許番号第2713369号は既に登録になっていますので権利化されてはいますが， 小山輝晃氏により異議申立がなされていますので確定ではありません。 その申立内容によっては今後権利消滅と言うこともありうるようです。

まず，たいへんお恥かしいことですが， 畏友 三木和彦氏のお名前を間違えて書いてしまいました。 慎んでお詫び致します。

次に，富士通の問題については，間違えたことも書いてしまいました。 この問題についてここでもう少し整理して書きます。

この記事にも書きましたように，富士通デバイス株式会社の 解説 には，LHAやZipの使うLZ77の基本特許はStac社が保有し， 日本でも特許が成立した（1997年10月31日登録，特許番号第2713369号） と書かれています。 この特許を私は1993年8月10日出願（出願番号特願平05-198670）の 「マッチングストリング探索およびハフマン符合化を用いたデータ圧縮装置および方法」（「符合化」というのは原文の間違いで，正しくは符号化ですね） と間違って書いてしまいましたが， スタック社の開平03- 68219[H 3. 3.25]だとのことです。 これは米国特許 5,003,307 ``Data compression apparatus with shift register search means'' と同じく 5,016,009 ``Data compression apparatus and method'' を合わせて日本で申請したもののようです。 特に 5,016,009 はスタック社がマイクロソフト社との係争で根拠としたもので， ハッシュを使った LZ77 です。

ちなみに，特開平6-224778も 「マッチングストリング探索およびハフマン符合化を用いたデータ圧縮装置および方法」 となっており，スタック社のおかかえ翻訳家のワープロは誤変換が得意なようです。

富士通がもっと具体的に LHA の特許問題に触れているのは， 縮丸 -特許／著作権 というページで，ここには

データ圧縮ソフトの国内分野ではフリーソフトウェアのＬＨＡが有名ですが、ＬＨＡは特許／著作権問題が有り、富士通では原則として、ＬＨＡをユーザシステムに組み込む事は禁止しています。

いろいろな情報を総合すれば，富士通が問題にしているのは，木を使った古い LHA のほうではなく，私たちがより安全と考えた gzip と同様なハッシュを使った新しい LHA のアルゴリズムのようで， これは国内・海外を問わずリスクがあるとしているようです。 古い LHA のアルゴリズムについては， Xerox 社の特許（木を使った LZ77）に抵触する可能性があり， 海外ではリスクがあるが， 国内では特許申請されていないので， 国内での使用はリスクが小さいということです。 ハッシュを使った新しい LHA のほうは， Stac社の特許が国内でも成立しているので， 国内外を問わず，リスクがあるということのようです。 これは LHA だけの問題ではなく， Zip や gzip や zlib，それに PNG や HDF の圧縮についても同じことです。 Sun でも Java 言語のサポートする圧縮形式として Zip 形式を使っていますし， Microsoft も CAB ファイルフォーマットの一つとして MSZIP と称して Zip 形式を使っています。 これらがすべて Stac 特許に抵触するとしたらたいへんなことなので， ちょっと富士通の言っておられることが信じられないというわけです。

なお，富士通も，リスクがあるのは圧縮だけで， 伸長（解凍）には問題がないとしているようです。 圧縮に問題があるかどうかにかかわらず伸長には問題がないということに関しては， Cマガジンにも書いたように，まったくその通りだと思います。

念のためその理由をもう一度書いておくと， LZ77 の伸長アルゴリズムは非常に単純で， 木もハッシュも必要としないからです。 木やハッシュの利用は，圧縮を高速化するだけの目的であり， 遅くてもよければ木やハッシュを使わなくてもまったく同じように圧縮できます。 圧縮されたファイル自体をいくら調べても， 木やハッシュを使ったか使わなかったかの痕跡は原理的に残りません。

なお，念のために書いておきますが， このページは富士通を非難しているわけではまったくありません。 むしろその逆です。 特許についてよく研究している企業が LHA，Zip，gzip，zlib などをどう評価しているのかをご紹介し， ソフトウェア特許の足枷についてご理解いただくことが目的です。 なお，私は特許についてはまったくの素人ですので， いろいろ間違えたことを書いているかもしれません。 皆様のご意見をお待ちしております。

このページはしばしば更新します。

（付）「解凍」ということばについて

LHarc が melting というメッセージを出すので解凍ということばが流行ったという説を聞いて， なるほどと思ったことがあるのですが， 古い BBS のログをいま読み直してみると，LHarc などの日本製アーカイバができる前から， 解凍ということばが普通に用いられていたようです。 私もはるか前から使っていました。 圧縮を専門に勉強している人から見れば，この BBS 用語は奇異に聞こえるようです。 「伸長」という方がいいかもしれません。

さらに考えてみると，解凍は圧縮を解くという意味に限らず， むしろ展開するという意味に近いように思います。

（付）LHA のバージョン

吉崎さん作の LHA の1次配布元は NIFTY FLABO のライブラリです。 現在公開されているいわゆる公式版は 2.13 (91/07/20) ですが， 暫定公開版として 2.55b (92/11/24) も広く流布しています。 '-lh6-' 法（32K 辞書）の解凍に対応したのは 2.50 (92/07/26) からです。

その後の 2.60 (94/06/10) に始まるテスト版から LZ77 符号化を従来の木を使ったものから gzip 類似のハッシュを使ったものに変え，'-lh6-' 法（32K 辞書）の圧縮に対応しました。 2.63 (94/07/07) ではさらに '-lh7-' （64K 辞書）の展開にも対応しました。 この系統のテスト版の最新版は NIFTY FLABO のライブラリ「【フリーソフトウェア】プレリリース評価版」にある

1054  SDI00506 95/05/28    41617     9999  BIN  LHA267.EXE   LHA v3.0 へ向けてのテスト 7

279  SDI00506 95/10/08    50131     3004  BIN  LHA32_00.LZH LHA for Win32 console その0

ソースコードはいろいろあります。 本物の LHA のソースコードの最新版は lha211_s.lzh (91/03/03) のようですが， すべてC言語で書かれた圧縮アルゴリズム実験用ものでは， 最新のものは多分 ar940528.lzh (94/05/28) だと思います（これは私の書いた ar が踏み台になっているようです）。 しかし，公開されておらず，もう NIFTY でも見つかりませんでした。

LHA のアルゴリズムをインプリメントしようと思われる方は， むしろ UNIX 版のソースから始めるのがいいかもしれません。 最新のものは lha-114d.tar.gz で，

LHa for UNIX version 1.14d Jan. 14 1997 by Tsugio Okamoto

その他 LHA 派生ソフトは多数ありますが， ソースが添付されていないものがほとんどであり， はっきりしたことはわかりませんが， -lh6- 対応とうたっているものはハッシュを使ったものだと考えていいと思います。

リンクはご自由にどうぞ。

松阪大学 奥村晴彦 okumura@matsusaka-u.ac.jp

Copyright (c) 1998 Haruhiko Okumura. Last modified: Mon Mar 18 18:33:38 JST 2002