圧縮アルゴリズムとフリーソフトと特許の話

はじめに

なぜ圧縮？

いつの時代も CPU は I/O より速い

圧縮の種類

• 可逆（無歪） lossless
• 非可逆（不可逆）lossy

一番簡単な圧縮

Run-length coding（連長符号化）

あああああいいい → あ₅い₃

ZeoSync事件

[2002-01-07] ZeoSync Corporation が 1/100 に可逆圧縮する技術を発明したと発表

[2002-03-07] 特許公開

任意の n ビットのファイルを n - 1 ビット以下に可逆に圧縮するアルゴリズムは存在しない。

［証明］ n ビットのファイルは 2ⁿ 通り存在するが，n - 1 ビット以下のファイルは

1 + 2 + 2² + 2³ + …… + 2^n-1 = 2ⁿ - 1

もっとちゃんとした圧縮限界はエントロピー

- Σ p_i log₂ p_i

歴史

LZ77の仲間

LZ77

Jacob Ziv and Abraham Lempel, A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, IT-23(3), 337-343, 1977.

LZSS

James A. Storer and Thomas G. Szymanski, Data compression via textual substitution, Journal of the Association for Computing Machinery, 29(4), 928-951, 1982.

LZSSでは「マハリクマハリタ」を次のように符号化する（文字を8ビットと仮定）

フラグ （1ビット）	文字 （8ビット）	戻り距離 （〜12ビット）	長さ （〜4ビット）
0	マ
0	ハ
0	リ
0	ク
1		4	3
0	タ

[1987] 雑誌に頼まれてデータ圧縮の原稿を書くが，廃刊に

[1988-05-01] 原稿用に書いた lzss.c を PC-VAN に流す

[1988-06-??] これに基づき三木氏が LArc

LZARI/LZHUF/LHarc/LHA/Zip/gzip/zlib/PNG

[1988-08-27] LZARI 奥村晴彦 (LZSS+算術符号化)

フラグ （1ビット）	文字 （8ビット）	長さ （8ビット）	戻り距離 （≧12ビット）
0	マ
0	ハ
0	リ
0	ク
1		3	4
0	タ
9ビット ↓ 算術符号化 or ハフマン符号化			↓ 算術符号化 or ハフマン符号化

[1988-11-??] LZHUF 吉崎栄泰 (LZSS+動的Huffman符号化)

→ [1988-12-??] LHarc

[1989-07-02] 奥村「LZSS+ブロックごとのHuffman符号化」提案

[1990-11-??] LH 2.0 (吉崎)

[1991-02-??] LHa (→ LHA) 2.10 (吉崎)

日本発：テレビ，車，次はアーカイバか！

[1988] LHarc

[1991] LHA

[1991] LHA won the October 1991 PC Magazine Editor's Choice award as the best data compression utility.

[1992] オンラインソフトウェア大賞/フリーソフトウェア大賞

FSP'92	LHA
FSP'93	WTERM
FSP'94	JW_CAD
FSP'95	-
FSP'96	AL-Mail
OSP'97	-
OSP'98-99	Becky! Internet Mail
OSP2000	午後のこ〜だ
OSP2001	-

著作権・商標権の争い

[1978] Ziv and Lempel (LZ78)

[1984] Welch paper (LZW)

[1984] compress (Spencer W. Thomas et al)

[1985] ARC (Thom Henderson, SEA)

[1986] PKARC (Phil Katz, PKWARE)

[1988] SEA 勝訴

MS-DOS 6.0圧縮ドライブ

[1985-03-06] GB patent filed (Waterworth, Ferranti PLC GB)

[1986-03-03] US Patent filed

[1987-10-20] granted USP4,701,745

---> Stac

[1993-01] Stac sues Microsoft

[1994-02-23] Microsoft Loses Patent Suit ($120,000,000)

Stac Electronics → Stac Software → Previo (2000-04-25改名)

LZW特許

[1978] Jacob Ziv and Abraham Lempel, Compression of individual sequences via variable-rate coding, IEEE Transactions on Information Theory, IT-24(5): 530-536, 1978.

[1983-06-20] Welch (Sperry Research Center) 特許を出願

[1984] Terry A. Welch, A Technique for High-Performance Data Compression, IEEE Computer, 17(6): 8-19, 1984.

[1984] compress (Spencer W. Thomas et al)

[1985] ARC (Thom Henderson, SEA)

[1985-12-10] 成立 USP4,558,302

[1986] PKARC (Phil Katz, PKWARE)

[1987] CompuServe GIF

[1994-12] Unisys が警告開始

[1999] UnisysがLZW特許で再警告， フリーソフトなどライセンス違反のソフトで作ったGIFを使うサイトは5000ドル払え。 GIFを扱う多数のフリーソフトが消える。 Burn All GIFs などの抗議運動が起こる

[2003-06-20] 切れるはず (日本では1年後)
Unisysは関連特許でLZWの権利を維持し続けるという

代替技術: PNG

著作権と特許権

著作権	特許権
文化庁	特許庁
表現を保護	アイデアを保護
自動発生	出願・審査・登録
創作〜死後50年	登録〜出願後20年
独立に作れば侵害にならない	偶然同じでも侵害になる

• Dr Ross's Compression Crypt

LHA・gzip等と特許

初期のLHAはUSP4,906,991（Fiala and Greene，Xerox，日本特許なし）が心配

Patricia木を圧縮に用いている

その後，LHA，gzip，Zip，zlib，PNG等は同じアルゴリズムになる

ハッシュを圧縮に用いている

Stac USP4,701,745等もハッシュを用いているが，辛く逃げている

万一LHA，gzip，Zip，zlib，PNGを誰か（Previo？）が訴えたら……

標的は？ Microsoft？ Sun？

代替 → bzip2

MP3特許

MP3 = MPEG-1 Audio Layer-3

• [1992] MPEG-1 成立。
• [1998-09] Fraunhofer (と Thomson multimedia (RCA)) が MP3特許で警告， 1エンコーダあたり$2.5〜5.0 (→ mp3licensing.com)
• [1998] 8hz-MP3 (学生2人によるプロジェクト) は Fraunhofer から$25,000/年 払えというメールを受け取り，配布停止 (The Register 記事)
• [2000] 午後のこ〜だ， オンラインソフトウェア大賞 に。
• [2000末] 午後，ソース配布に
• [2002-03-30] 午後，バイナリ配布再開
  現在はインストール時にソースからコンパイルされるようになっている

午後のサイトにある配布側の論点：

• ネットワーク上で配布する限りは無形物のため、法律で解釈されるところの「物」としての扱いにならないので、侵害行為とはならない
• そもそも「業」として配らないのならば侵害行為とはならない

代替技術: Ogg Vorbis

ソフトウェア特許

以前は装置または方法として特許

[1997-02] 審査基準改訂，ソフトウェアの「媒体」も特許

[2000-12] 審査基準改訂，ネット上のプログラムも「物」として特許

[2002-04-17] 特許法改正，「物」にプログラムが含まれること，ネット経由の提供も含まれることが明記された

特許がフリーソフト攻撃の道具になる

LZW，MP3，RSA，……

Microsoft patents shut out open source (Bruce Perens, ZDNet)

特許を取らせないためには

先行技術（prior art）

発表してしまえば特許は取れない（自分でも）

[1999-12-10] インターネット等の情報の先行技術としての取り扱い運用指針

• 先行技術にネット上の情報も含まれる（掲載日がはっきりするなら）
  
• 掲載日を確定する仕組みが必要

会場で「バージョン管理システムを使えば日時は確定できるのではないか」とご指摘を受けました。 ごもっともでした。 検索する立場からはアルゴリズムのドキュメント（ソース中のコメントでもいいのですが）が見やすいところにあれば便利です。

自衛のための特許

A公開 → A特許は不可能になるが，A'特許は可能

A特許を取っておけばA'特許を取られてもクロスライセンスに持ち込める

特許侵害を指摘された場合

手持ちの特許が多ければ相手の特許侵害を見つけクロスライセンス

しかし単に特許を買い集めて訴訟を起こすだけの会社からの脅威は避けられない

フリーソフト作者：特許取得は困難

日本特許だけでも20年維持するには全部自分でやっても約100万円〜

フリーソフト作者：特許調査も困難

次のサイトで検索可能。 しかし素人が漏れなく調べるのは困難

• Japan Patent Office (特許庁)
• US Patent and Trademark Office
• European Patent Office / esp@cenet

Karmarkar特許

アルゴリズム特許として有名

• 1985-04-19 出願
• 1988-05-10 成立 (USP4,744,028)
• 1995 今野浩 （東工大 → 中央大） 『カーマーカー特許とソフトウェア――数学は特許になるか』（中公新書1278，中央公論社，1995）
• 1996 日本特許成立 (2033073)
• 1997 無効審判請求（今野たち）
• 1998-12-15 カーマーカー法特許無効審判審決 「無効とすることはできない」

Knuthと特許

Knuth: アルゴリズムの神様，TeX/METAFONTの作者

• Letter to the Patent Office From Professor Donald Knuth
• Apple's TrueType Patents: FreeType and Patents
• Advogato's Interview: Donald E. Knuth

  ... certainly all the ideas I've ever heard of about TrueType were, I believe, well known in the early '60s.

Knuthも特許を？

• Scaling and Number Base Converting Method and Apparatus (USP3,626,167, Burroughs, filed 1969)
• Methods of Controlling Dot Size in Digital Halftoning with Multi-Cell Threshold Arrays (USP5,305,118, Adobe, filed 1993)

Red Hat と特許

• Embedded Protocol Objects" (2001-08-22 filed)
• Method and Apparatus for Atomic file Look-Up (*) (2001-08-22 filed)
• Method and Apparatus for Handling Communication Requests at a Server Without Context Switching (2001-08-23 filed)
• USP6,110,226 Java development environment using optimizing ahead-of-time compiler (Cygnus Solutions)

Cygnus Support → Cygnus Solutions → Red Hat に買収

LWN: Red Hat and software patents

Statement of Position and Our Promise on Software Patents:

• Red Hat はソフトウェア特許に反対である
• しかし現状では自衛のために特許武装が必要
• フリーソフトに対しては特許権を行使しない（LGPL や BSD は除外？）

BSD，LGPL を入れると誰でも使えてしまう

他の例：

• GPL patent grant for 19 patents (Advogato)
• FSMLabs の RTLinux 特許 (USP5,995,745)

大学でも特許の波

論文書く前に特許取れ

独立行政法人化

TLO (技術移転機関)

遺伝子特許

ヒト遺伝子特許が急増

ヒトゲノム計画 (Human Genome Project): 遺伝情報を公開することによって対抗

[2000-03-14] ClintonとBlairがヒト遺伝子情報を公開するよう科学者に呼び掛け

We applaud the decisions by scientists working on the Human Genome Project to release raw fundamental information about the human DNA sequence and its variants rapidly into the public domain, and we commend other scientists around the world to adopt this policy. (*)

その日のうちに Celera Genomics の株は19％， Incyte Genomics (Incyte Pharmaceuticals) の株は27％落ちた。

たくさんのサイトが遺伝子特許に反対

• Genetics and Patenting (ORNL)
• Genes Patents Detrimental to Care, Training, Research (College of American Pathologists)
• Position Statement on Gene Patents and Accessibility of Gene Testing (American College of Medical Genetics)
• A Primer on Gene Patents (AMSA)

結論

ソフトウェア特許に反対しよう

反対意見が W3C の Patent Policy を変えた

オープンソースつぶしに特許を使う企業に抗議しよう

Unisys， Fraunhofer， ……

特許がある以上，企業は特許武装せざるを得ない

参考リンク

• League for Programming Freedom
• Foundation for a Free Information Infrastructure
• freepatents.org
• Creative Commons
• Software Patents vs. Free Software (Bruce Perens)

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

松阪大学 奥村晴彦 okumura@matsusaka-u.ac.jp
Last modified: Sat Jun 8 18:27:08 JST 2002