情報圧縮と特許  
2002年2月2日
 Leshade Entis
 

■ 初めに

 これまで、GIF の LZW を初めとする情報圧縮に関する特許が、様々なところで取り上げられ論議を呼んできましたが、しかし、具体的な内容に踏み込んだものは少なかったように思います。
 例えば、LZW の特許にしても、LZW のどの部分に特許権が認められているのか、と言う部分は殆ど触れられていなかったと思います。
 しかし、これでは無意味な特許不安が広がるばかりで、今後の圧縮技術の普及に大きな影を落としかねません。実際、特許に抵触するかもしれないと言う理由だけで公開を停止したソフトウェアは多数存在します。
 そこで、私がこれまで研究してきた圧縮技術と、調査した特許に関して、一部例を挙げながら、法律的な側面、技術的な側面の両面から、情報圧縮の特許について考えてみたいと思います。
 
■ 特許とは?
 それでは特許とは具体的にどのような性質のものでしょうか?
 特許とは、知的財産権制度の中で、発明に対する権利を保護するためのもので、特許法によってその権利が定められています。同様に、よく取りざたされる著作権も同じく知的財産権の一つで、著作物に対する権利を保護するためのもので、著作権法と言うものがあります。
 しかしながら、混同されがちですが、特許権と著作権とではずいぶんと権利の性格が異なります。
 それは、発明と著作物の違いであるとも言えます。
 発明とはアイディアであり、技術的思想であり、特許権はそういったものの中でも、高度で産業の発展に寄与するものにのみ認められます。
 一方、著作物とは、思想や感情を創作的に表現したもので、著作権はそういったもの全てに認められます。
 
■ 特許の目的
 では、なぜ特許権と言うものが法律で保護されるようになったのでしょうか?
 それは、特許法の第一条に目的として以下の様に書かれています。
この法律は、発明の保護及び利用を図ることにより、発明を奨励し、もつて産業の発達に寄与することを目的とする。
 この中で最も注目するのは、「発明の保護及び利用」と言う部分です。
 特許法では、特許として認められた発明は、その権利が保護されると同時に、その技術が一般に公開されます。
 従来、重要な技術は一部の技術者のみが握り、外には漏らさないのが普通でした。技術が公然と知られれば、模倣され、しかるべき利益を享受出来なくなります。
 そうなっては多大の努力をつぎ込んで新しい発明をしたとしても、全く報いられません。
 しかしながら、技術が隠蔽されたままでは、科学技術、及び産業の発展の速度は遅くなってしまうでしょう。
 ですから、発明者の権利を保護し、一方でその技術を公開すると言うことは大変に重要なことなのです。
 
■ 特許の要件
 では、どのような発明が特許として認められるのでしょうか?
 それは、特許権法の第二条で以下の様に簡潔に定義されています。
「発明」とは、自然法則を利用した技術的思想の創作のうち高度のものをいう。
 具体的に見ていきますと、「自然法則を利用した」とありますから、人為的取り決め、及び計算方法などは、自然法則を利用していませんから特許としては認められません。
 また、「技術的思想の創作」とありますから、自然法則そのものも特許としては認められません。
 つまり、文字 A は、0100001 と言う 2 進数によって表現すると言うようなエンコーディングそのものや、a を入力して b = k * a によって b を得る計算方法そのものや、k * a を k = k1 * k2 として、k1 * k2 * a とするような数学的な式の変形は特許としては認められません。
 更に、特許権法第二十九条で、特許として認められるための必要条件が挙げられています。それは以下のようなものです。
(1) 「特許出願前に日本国内又は外国において公然知られた発明」ではないこと。
(2) 「特許出願前に日本国内又は外国において公然実施をされた発明」ではないこと。
(3) 「特許出願前に日本国内又は外国において、頒布された刊行物に記載された発明又は電気通信回線を通じて公衆に利用可能となつた発明」ではないこと。
 これは、既に多くの人に知られているか、実際に使われている発明に関しては、特許権は認められないと言う意味です。
 
■ 特許権制度
 特許権は日本国の法律によって既定された権利ですので、外国においても同様に保護されるとは限りません。
 しかし、主要な国は特許を認めており、微妙な違いはありますが、ほぼ同じような決まりになっています。

(1) 特許権の存続期間
 特許権は未来永劫存続するわけではなく、一定期間経過すると消滅します。
 その権利の存続期間は国によって異なります。日本は、出願日から20年間であるのに対し、アメリカでは特許日から17年間です。
 因みに、少々ややこしい話ですが、例えば日本の場合、申請すれば特許権の存続期間を5年延長することが出来、最大25年間特許権が存続することになります。

(2) 特許権料
 特許権料とは、ライセンス料と言う意味ではありません。
 特許権は特許料を支払わなければ存続されません。例えば、特許権取得後 1 年目は、最低でも 14,100 円を支払わなければなりません。これを支払わなければ、特許権は失効してしまいます。
 因みに特許料は、年を重ねるごとに高額になっていき、仮に25年間特許権を存続させた場合、特許権料の合計額は、少なくとも 1,553,400 円以上になります。

 
■ コンピュータと特許
 特許には先に述べたように、「自然法則を利用した技術的思想の創作」でなくてはなりませんから、コンピュータプログラムは直接的に特許では保護されません。
 しかし、実際にはプログラムに関する多数の特許が存在しています。これは一体どういうことでしょうか?
 先に、文字 A を 01000001 と言う 2 進数によって表現するというエンコーディングは特許として認められないと述べましたが、文字 A を 01000001 と言う 2 進数に変換する「装置」は特許の対象となりえます。もちろんそれが、「高度な技術思想の創作」に基づくものであればの話ですが。
 つまり、例えばこの場合は文字エンコーディングですが、データフォーマット、ある決まった計算などは、特許としては認められませんが、その具体的な実現方法には特許は認められ得ます。
 コンピュータプログラムに限定して言えば、プログラムの実装方法、すなわちアルゴリズムには特許が認められ得るのです。
 
■ 情報圧縮に関する特許
 インターネットの時代になって特に情報圧縮に関する特許の問題が顕在化してきました。
 最も注目を集めているのが LZW に関する UNISYS 社が所有している特許権でしょう。
 GIF と言う、インターネットの世界では標準とも言うべき画像フォーマットに LZW と言う圧縮手法が用いられるため、ブラウザ等の特許ライセンスが問題となっています。
 また、LZW と並んで問題になっているのが、算術符号と言う圧縮手法です。
 ただ、いずれの問題にしても、具体的にどの部分が特許請求されており、どのようにすればその問題を回避できるのか、と言う議論を聞いたことがありません。
 ただ、「特許が取得されているから使わない方がいい」と言う議論ばかりです。
 しかし、それは明らかに無知から発しています。
 と言うのも、実際に現在有効な特許を調べてみればすぐにわかりますが、特許について全く問題とされていない(少なくとも私はそのような議論をあまり聞いたことが無い)ハフマン符号でさえ、これに関する特許はかなりの数取得されています。
 では、ハフマン符号も特許が取得されているから、ライセンス料を支払わないと使えないのでしょうか? いいえ、必ずしもそうとは限りません。
 特許とは先に述べました通り、プログラムの実装方法に対して認められており、フォーマットそのものは特許権の対象とはなりません。実際、特許として認められているのものは、方法に言及するもののみです。
 そして、ハフマン符号も含めて、算術符号の特許も、その大半が高速化の為の方法なのです。
 
■ 算術符号を特許に触れずに実現できるのか?
 実は私は、算術符号がハフマン符号の次に特許に触れずに実現しやすい符号だと考えています。
 逆に最も特許に触れる可能性が高いと考えているのは辞書をベースにする方法です。LZ77 は辞書ベースの最もポピュラーな方法ですが、やはり実装方法によっては特許に触れる可能性があります。
 私がなぜ辞書ベースの圧縮方法が最も特許に触れる可能性が高いと考えるのかは、特許に触れる可能性をどのように捉えるのかと言うことと深く関係しています。
 辞書ベースの圧縮方式は、フォーマットと符号化方法、及び復号方法がきわめて密接な関係にあります。しかも、その実現方法と言うのが、ベースとなっている原理が簡単であるがゆえにかえって特許と非常に結びつきやすいと言う性質があります。
 一方、算術符号はその基本的な原理が数学的なものであり、それ自体が特許とは直接結びつきにくいと言う性質があります。大抵の算術符号に関する特許は、算術符号を実現する上で高速化する方法や、従来の問題を解決するためのものです。
 例えば、原始的ですが実用的な算術符号として、L-R 型算術符号(※1)が知られていますが(Q コーダーの原型になっていると思われます)、これの特許は取得されていません(と見られます ≫理由は後述の CACM 算術符号と同じ)。これはどのような方法か簡単に説明すると、2 値情報源を入力し、劣勢シンボルの生起確率を 2 の負の累乗で近似した上で、演算の有限桁での打ち切りを可能にしている、と言う重大な特徴をもっています。
 この方法が考案された年代を考えると、当時最も実用的な算術符号であったことがうかがえます。と言うのも、コンピュータの世界では、乗除算演算が実用的になったのは比較的最近で、この L-R 型算術符号は、乗除算を一切用いることなくビットシフトと加減算のみによって実現できるからです。
 そして、現在一般的に使われていると思われる算術符号の原型は、後で紹介する特許でも引用されていますが、「I. H. Witten et al., "Arithmetic Coding For Data Compression", Communications of the ACM, vol. 30, No. 6, Jun. 1987, pp. 520-540.」で示された方法でしょう。(仮に CACM 算術符号と呼ぶことにしましょう)
 この方法の特徴は、多値算術符号において、演算の有効桁での打ち切りを可能にしたことです。
 そして、これは少々重要なことですが、この CACM 算術符号は特許取得されていないと言うことです(と見られます)。
 この CACM 算術符号が特許取得されていないと考えられる理由を以下に列挙しました。

(1) 特許の要件を満たしていない
 特許とは先に述べましたとおり、「自然法則を利用した技術的思想の創作」でなければなりませんが、CACM 算術符号は基本的に算術と取り決めのみで構成されています。従って、特許の要件を満たしている可能性は薄いと見られます。

(2) 特許ではなく機関紙(?)で公開されている
 他の算術符号に関する特許の中から参考文献として、CACM 算術符号が特許としてではなく、上記機関紙(?)によって参照されています。(実際に多数そのような特許が存在します)
 特許の中から、過去に取得された特許を参照する場合には、特許を参照しているのに対して、この手法に関しては上記機関紙(?)を参照していることから、特許取得されていないと想像されます。

 そして、CACM 算術符号が特許取得されていないのであれば、大抵の一般的な算術符号は、大抵のハフマン符号がそうであるように、特許には抵触しないということになります。(但し、CACM 算術符号化方式が、別の特許を含んでいる可能性は完全には否定できません)

(※1) G. G. Langdon, Jr., "Compression of Black-White Images With Arithmetic Coding", IEEE Transactions On Communications, vol. COM-29, No. 6, Jun. 1981, pp. 858-867.
 因みに、Langdon 氏の名前は米国特許を調べていれば幾度も見かけることが出来ますが、IBM に所属していると見られます。

 
■ RangeCode は特許に触れないのか?
 特許に触れす、算術符号並みの圧縮率で、ハフマン符号並に高速という触れ込みで広がりを見せつつある RangeCode ですが、この手法は本当に特許に触れないのでしょうか?
 私の中の結論では「否」です。
 RangeCode は算術符号の一種ですが、実のところ、私はどういう特徴を持って RangeCode と呼ぶのかを理解できていません。
 私の理解の範疇では、算術符号の中の「領域」の精度の維持方法が、一般的な算術符号とは異なると言うだけで、それ以外はまったく同じように見えます。
 RangeCode は、算術符号のように下限値と上限値を持つのではなく、下限値と幅を持つのが特徴だと言う記述を多数見受けますが、先に紹介した L-R 型算術符号は、そういう意味では RangeCode と言うことになってしまいます。
 そしてこのことだけでは特許に触れるかどうかは関係ないと思われます。
 つまり、ハフマン符号も実装の方法によっては特許に触れるように、RangeCode も算術符号に関する特許に触れる可能性は同様にあるはずです。
 例として、私が日本国内のサイトで発見した、特許に抵触している可能性が極めて高いと思われる RangeCode の実装を紹介したいと思います。
 DO++ 氏が運営するサイト「どぅぷらぷら」(http://member.nifty.ne.jp/DO/index.htm)では、シンボルの頻度表の母数を 2 の累乗にすることによって高速に符号化・復号可能な RangeCode の実装例が紹介されていますが、この手法は、NEC が取得している特許「算術符号化装置」(特願平8-187948)に抵触していると思われます。
 この NEC の特許は、まさしく「シンボルの頻度表の母数を 2 の累乗にすることによって高速に符号化・復号可能な」算術符号を指し示しているからです。
 興味のある方は、原文を一読してみることをお勧めします。
 
■ Entis 式算術符号は特許に触れないのか?
 RangeCode を紹介したついでに、Entis が供給している EMI フォーマットで採用され、ERI のオプションとして一時期供給(その後廃止;ERISA で再び採用の予定)していた算術符号ですが(ここでは仮に Entis 式算術符号とします)、この算術符号が特許に抵触しないかどうかについて一言説明させていただきたいと思います。
 Entis 式算術符号は、L-R 型算術符号の方法をベースに、独自の手法によって多値の符号化を可能にした算術符号化方式です。
 ある意味、この算術符号化方式は、CACM 算術符号に対する改良のような位置付けとしてみることもできます。
 と言うのも、先に紹介した NEC の特許でも解説されていますが、CACM 算術符号にはいくつかの問題点があります。
 深く立ち入ると長くなるので簡潔に説明しますが、1 つに頻度表を更新する際の問題があります。
 実は、NEC の特許では、「シンボルの頻度表の母数を 2 の累乗にする」事によって高速化を図り、そしてもう一つ、毎シンボル事ではなく、ある一定数のシンボルごとに頻度表の更新を行うと言う手法と組み合わせることによって、頻度表の更新の問題も同時に解決していると言う特徴があります(そしてこの 2 つがこの特許における主要な請求項目となっています)。
 Entis 式算術符号では上記のように、プログラム的なテクニックによってではなく、数学的手法によって頻度表の問題を解決しています(因みに Entis 式算術符号では毎シンボルごとに頻度表を書き換えることが出来ます)(※2)。
 そして、この手法は、特許の要件を満たしている可能性が薄いと見られるため、いかなる特許にも抵触しないと考えられます。

(※2)Entis 式算術符号化方式の、ERI フォーマット仕様書からの抜粋です。Microsoft Word で閲覧ください。 ≫ こちら

 
■ 特許に抵触しない情報圧縮方法の考え方
 では特許に抵触しない情報圧縮方法を考案するにはどのようにすればよいのでしょうか?
 先に述べましたとおり、特許は至る分野で取得されており、厳密な意味で特許に触れないことを証明することはほとんど不可能です。ましてや、個人的な研究に至っては。
 しかし、特許に触れない可能性が極めて高い実現方法を考案することは可能です。

(1) 特許の要件を満たすようなアルゴリズムを用いない
 特許取得されているかどうか、いちいち調べるのは大変な手間と労力が掛かります。
 ですから、はじめから特許の要件を満たすアルゴリズムを可能な限り排除することが重要です。(※3)

(2) 特許について調べる
 特許の要件を満たしていると思われる手法については、特許庁のデータベースを使って既に特許取得されているかどうかを調べると言うことは比較的効果的な手法だと思います。
 手間と暇は少々掛かりますが、お金は掛かりません。
 ただし、これでは確実に既存の特許に触れないかどうかを断言するのは難しいでしょう。

(3) 特許として出願してみる
 特許の要件を満たしていると思われる手法について、特に重要なものは、既に特許が取得されているかどうか調べるために、特許として出願してみると言う方法が考えられます。
 出願には多少のお金も必要ですし、書類を自分で用意するとなると、特許に関するちょっとした勉強も必要でしょうし、当然手間も掛かります。
 しかし最も手堅い方法だと思われます。
 私自身、数年前のことになりますが、Entis 式算術符号化方式に関して、米国に特許出願しようとしたことがあります。(結局実行はしませんでしたが)
 特許出願すれば、その手法が既に特許として認められているのか、特許として認められないのか、新たに特許権が認められるかがはっきりします。

(※3)但し、特許の要件の中の、公然と知られた手法かどうかについてはあまりあてになりません。まれに公然と知られた、または実施されている手法について特許が認められることがあるからです。

 
■ 特許の調べ方
 特許を調べる際、疑わしい特許について、その全文を読むのではいくら時間があっても足りません。
 そこで、まずデータベースの検索機能を使って、関連すると思われる特許を広めに検索します。
 次に、特許の名前でまったく関係ないものを外します。
 そうして絞り込まれた特許について、要約(Abstract)と特許請求の範囲(Claims)を読みます。
 要約とは、文字通り特許の概要を短くまとめたもので、ここを読めばまったく関係のない特許を除外できます。
 また特許請求の範囲とは、実際に特許権として請求されている部分です。ここに記された内容の発明が保護される内容となります。
 特許請求の範囲を読んで、怪しいと感じたものに関しては、更に詳細な説明(Description)を読みます。
 詳細な説明とは、実際に特許請求した部分だけではなく、全体の仕組みなどが解説されています。ここまで読んだ時点で、最終的に特許に触れるかどうかを判断します。
 但し、詳細な説明の内容すべてが特許権として保護されるのではなく、特許請求の範囲で示された部分だけですので、基本的には特許請求の範囲だけでも分かります。
 
■ 最後に
 冒頭でも述べましたが、特にインターネットが普及してからソフトウェア特許の問題が頻繁に取りざたされるようになってきました。
 しかし、私には議論の内容は薄いように感じられました。
 また無知から来る不安感からある種の、特許不安とでも言うべきアンチ特許的風潮に安易に流れているようにも感じられました。
 そうした中で、例えば「算術符号は特許が取得されているから使えない」と言った主張に、また、RangeCode についてその逆の疑問を強く抱くようになってきました。
 これは、私のそうした疑問を投げかけたアンチテーゼです。
 
■ 参考 URL
どぅぷらぷら
http://member.nifty.ne.jp/DO/index.htm

日本特許庁
http://www.jpo.go.jp/indexj.htm

日本特許電子図書館
http://www.ipdl.jpo.go.jp/homepg.ipdl

米国特許庁
http://www.uspto.gov/patft/

 

■ 付録 - ブロック符号と非ブロック符号

 情報をコンピュータで表現する場合(蓄積、または伝送する場合)、情報はまずモデル化され、次に符号化されます。
 符号化された段階で初めて 0 または 1 の組み合わせの形で表現されます(概念上)。
 この符号化の方法は大別すると、ブロック符号化と、それ以外の非ブロック符号化に分類することが出来ます。
 ブロック符号化では、ある 1 つの情報(シンボル)をあるビット数で表現します。
 シンボルは、ビットの境界で区切ることが出来るため、この方式を「ブロック符号」と呼びます。大半の符号化方式はこちらに分類されますが、それはコンピュータで処理しやすいからでもあります。
 8 ビットの整数表現(固定長符号)や、シャノン符号、ガンマ符号、ハフマン符号などはすべてこれに属します。
 これらのブロック符号の中で最も一般化されたものがハフマン符号です。
 ガンマ符号は、ある特定の統計情報に基づいたハフマン符号と一致し、8 ビットの整数表現などは、256 種類のシンボルから構成される、均一な統計情報に基づいたハフマン符号とみなすことが出来ます。
 一方、非ブロック符号化とは、シンボルをビット単位で区切ることをせず、結果として複数のシンボルをまとめて 1 つの符号として出力する方式のことです。
 例えば、2 つの情報 A, B を符号化する場合を例に考えてみます。
 A は 0, 1, 2 の 3 通りの場合があり、B は 0, 1, 2, 3, 4 の 5 通りの場合があり、すべての値の出現頻度が均一と仮定します。
 それぞれブロック符号と非ブロック符号では、例えば以下のような符号化が想像されます。

    ブロック符号  : aabbb (aa = A, bbb = B の固定長符号)
    非ブロック符号 : xxxx  (xxxx = A * 5 + B の固定長符号)

 少し具体的な値を入れて符号化してみましょう。
 例えば、A = 2, B = 3 とするとそれぞれ以下のようになります。

    ブロック符号  : 10011
    非ブロック符号 : 1101

 ブロック符号の方は、はじめの 2 ビットが A で、次の 3 ビットが B をあらわしているので、見ればすぐに A 及び B の値がわかりますが、非ブロック符号は境界が無いのでぱっと見ただけでは分かりません。
 ところでこの例の場合、非ブロック符号は、ブロック符号よりも 1 ビット少なく情報を表現できていますが、なぜでしょうか?
 それは、表現方法と「場合の数」の違いにあります。
 ブロック符号のようにビットの境界でシンボルを区切ると、1 つのシンボルに割り当てられる場合の数は必ず 2 の累乗になりますが、この例の場合、A は 3、B は 5 と 2 の累乗ではなく、余りが出来ています。
 一方、非ブロック符号では、場合の数が A * B = 15 通りと、2 の 4 乗である 16 に近い数字になっています。場合の数の余りが 1 なのは偶然ですが、ブロック符号では毎シンボルごとに発生するのに対して、非ブロック符号では、すべてのシンボルを含めて 1 度しか場合の数が余らないので、理論上の情報量(エントロピー)+1ビット以内で(現実的かどうかはさておき理論上では)情報を表現することが出来ます。
 ところで、すべてのシンボルの場合の数が 2 の累乗だった場合、非ブロック符号はブロック符号とまったく同じ符号長になります。
 つまり、非ブロック符号とは、ブロック符号をより一般化したものと考えることも出来ます。
 因みに、非ブロック符号の代表的なものは算術符号で、つまり算術符号は、符号化方式を実用的に最も一般化したものと考えることも出来ます。

 

■ 追記

 この文章は本文中でも述べているとおり、世の一般的な特許論争に対する私の疑問を投げかけたアンチテーゼです。
 私の「疑問」と言うのは、「本当に算術符号は特許に抵触するのか?」と言うことですが、私が投げかけたいアンチテーゼは、プログラムを組む際には、それがいかなるプログラムであろうと、特許に抵触しないことを完全に証明することなど殆ど不可能に近い状況にあるという認識です。つまり、プログラムを書けば、確率に違いはあれど、多少なりとも特許に抵触する可能性が生じるのです。
 このような状況下では、「算術符号は特許がIBMに取得されているから使えないらしい」と言う理由で、算術符号を使わなかったからと言って、特許に触れないとは限らないと言うことです。
 むしろ、正しい認識ではない安心感によって、別の特許に触れる可能性すらあると思います。
 私がこの文章で言いたいのは、「算術符号は特許に触れる」と言うことでも、「算術符号は特許に触れない」と言うことでもない、と言うことなのです。

 因みに、私は算術符号を系統的に学んだわけではないので(教えてくれるところがあるのかどうかも少々謎ですが)、歴史的にどのような経緯で算術符号が改良されてきたのかを殆ど知りません。
 本文中でいささか自信無げな表現になっているのはそのためです。
 私が根拠にしている情報源は、米国、及び日本国の特許、所有している書籍で、それらから参照されている論文などや、具体的な方法をを手がかりに推論しているレベルです。
 因みに、少々調べてみようと思われた方は、まず米国の古い時代の算術符号に関する特許から読むのがいいと思います。時間さえあれば研究には一番の資料になると思います。

 また、本文中の誤りや、詳しい情報をお持ちでしたら是非お寄せください