はじめに

目的

ＬＺＷの圧縮理論

問題となる特許

辞書テーブルを利用しないＬＺＷ圧縮法（１）

辞書テーブルを利用しないＬＺＷ圧縮法（２）

もう一つのＬＺＷデコード理論

最後に

お願い

免責事項

　しかし、ＬＺＷ圧縮についてはどうなのだろうか？
　確かにライセンスフリーでＬＺＷ展開を行うことは可能なのかも知れないが、圧縮と展開は対になる物、片方だけが出来ても完全とは言えまい。前回の考察の中でも圧縮について「おそらく可能だろう」という結論に達してはいるが、本当にそれは正しいのだろうか？

　もし、ユニシスの特許に触れることなくＬＺＷ圧縮が可能であるとなれば、ＧＩＦを利用するための壁は完全に消失する。もはやユニシスに高いライセンス料金を支払う必要性は無いのだ。好きな時に、好きな様に、好きなだけ、ＧＩＦを利用すれば良い。それこそが本来ＧＩＦが目指していた道であり、そして誰もがそう望んでいた世界であろう。
　今でこそＧＩＦはアンチユニシス派のプロパンガンダ的運動により、まるで諸悪の根元のような扱いを受けているが、もう少し冷静に物事を見つめ直しても良い時期に来ているのではないだろうか？

◇本当に悪いのはＧＩＦなのか？
◇ＧＩＦを使わないという選択肢が最善の策なのか？
◇なぜユニシスは我々にライセンス料を要求しているのか？
◇我々は一体どうするべきなのか？

　人の意見ではない、自分なりの答えを見つけ出して欲しい。

　着目すべきはテーブルに格納しておくべき「頻繁に現れるデータ列」の選択手法、これこそがＬＺＷ法の肝であり、ＬＺＷがＬＺＷたる所以である。

　ここではＬＺＷ圧縮における辞書テーブルの動きを簡単に紹介しよう。
　まずＬＺＷ圧縮では、圧縮したいデータ列からｎ文字のデータ列を取り出し、それがテーブルに存在するかどうかの確認を行う。ちなみにｎ＝１の場合は必ずテーブルに存在するので、実際にはｎ＝２から始めるのが常である。

図１．辞書テーブルとのマッチング

　さて、ここでテーブル内に存在したからと言ってあわてて出力してはいけない。さらにもう１文字増やして（ｎ＋１）文字で確認してみよう。今度はテーブル内に見つからなかった。
　そう、この時点で初めて出力は確定される。ここでは「ｎ文字ならテーブルにあるが、（ｎ＋１）文字にするとテーブル内には存在しない」という状況である。この時は、「ｎ文字のデータ列」が格納されているテーブル番号を圧縮後の符号化コードとして出力する。

　そしてここで終わらないのがＬＺＷの特徴である。先ほど見つからなかった「（ｎ＋１）文字のデータ列」を新たにテーブルに書き加えるのである。こうして今回は圧縮できなかったデータ列も、もう一度出現した際にはちゃんと圧縮することができる。

図２．見つからなかったデータ列を辞書テーブルに追加

　言うなれば、一度犯した過ちは二度と繰り返さない「自己反省型」圧縮法である。

　この様に、ＬＺＷ圧縮では辞書テーブルを巧みに利用して、繰り返されるデータ列を次々とコンパクトに圧縮していく。説明だけ聞いていると「ふ〜ん、そうなんだ〜。」程度にしか思わないかもしれないが、実際にこれを考え出すというのは凄いことだと思う。
　データの反復性と、動的辞書拡張による圧縮効率の変動なんかを統計的に調査して得られた結果なのか、はたまた単なる思いつきなのか・・・。
　今でこそアンチＬＺＷとも取られかねない活動を行ってはいるが、ＬＺＷの考案者達には素直に敬意を表したいと思う。どんなに当たり前なことであっても、必ず初めの一歩というものは存在するのだから。

　だが、万が一と言うこともあり得るので一応その内容を見てみることにしよう。簡単に紹介すると以下のようになる。

　と言っても、いわゆる極普通のＬＺＷ圧縮法なので特に言うべきこともあまりない。では、「連想メモリを使用する」とは一体何なのかというと、辞書テーブルにプレフィクス・コード・フィールドと呼ばれる第三の領域が含まれるというだけの事である。この領域には”そのエントリに格納されているデータ列”から最後の一文字を削除したデータ列が格納されているエントリのテーブル番号が入っている。
　それで何が嬉しいのかというと、圧縮したいデータ列と辞書の内容とを比較する際に、比較しやすくなると言うメリットがある。ただ、それだけ・・・。
　後は、前章で紹介したとおりの圧縮方法を難解な言葉で長々と書き連ねているだけである。

　ま、所詮大したことは無い特許なのだが、通常のＧＩＦ展開ルーチンでは辞書テーブルの構造が上記のように、「プレフィクス・コード・フィールド」＋「最後の一文字」だけを格納しておく、という構成を取っているものが大半だと思われるので、そう言う意味ではやっかいではある。

　では、次の特許を見てみよう。こちらは前回と同じ「データ伸長法および装置ならびにデータ圧縮伸長法および装置」（特許番号：第２６１００８４号）である。このうち、前回は該当しないとした請求項の第１５項、「データ圧縮伸長方法」が今回のターゲットである。

　だが、このクレームはあくまで「データを圧縮して、それを伸長する方法」である為、圧縮しか行わないのであれば問題にはならないのかもしれない。そういった意味では、純粋なＬＺＷ圧縮に関する基本的な特許は、日本国内に於いては存在していないと言うことになる。しかしながら、少しでも疑わしい部分は全てチェックしておいた方が良いのは言うまでもないだろう。

　このクレームでは前半部分に圧縮に関する事が書かれている。以下に、その大まかな内容を箇条書きにしてみた。

◇圧縮したいデータ列と”メモリ”を比較して最も長い一致を見せるエントリを調べる
◇最も長い一致を見せたエントリの番号を圧縮結果として返す
◇最長一致が決定した場合、もう一文字付け足したデータ列を”メモリ”に追加する

　これだけである。
　ちなみに、上で言う”メモリ”が何であるのかというと「データ文字ストリングに関連する符号信号を有するメモリ」の事である。別に辞書テーブルであるとは一言も行っていないのが気になるところではある。
　だが、辞書テーブルであれ連想メモリであれ、「データ文字ストリングに関連する符号信号を有するメモリ」を用意しなければ問題ない事に違いは無い。圧縮したいデータが有って、それに対する圧縮結果がある。要は、それ以外のメモリ領域を持たなければ良いのだ。

　無い物に対して「あれこれこういった操作をすると特許に触れます」などと言われても、最初からそんな物は無いんだから関係ない。つまりは、そう言うことである。

　なお、余談ではあるが日本国内においてユニシスが権利者となっている第三のＬＺＷ関連特許が存在するという話もある。特許番号は２１２３６０２号である。
　しかし、私が調査した限りではこの番号に該当する特許は存在しなかった。念のためユニシスが所持している全特許を調べてみたが、それらしい物は一つも無かった。権利期間が終了してしまったのか、権利範囲を拡大して再申請しているのか、分割申請しているのかは定かではないが、現状において存在していないことは確かである。
　この件については、引き続き調査を行っていきたいと思う。

　さらに余談であるが、ユニシスはＬＺＷの他にも様々な分野の特許を持っているようだ。権利調査の際に分かったのだが、どうもユニシスは金になりそうな技術があると業務に関係する・しないに関わらず、手当たり次第特許を取得しているようにも見える。全体的な数で見れば全然大したことは無く、特定の分野を特許で固めるという事も殆どやらない（やれない）ようだが、少ないながらも質がある程度高い事と、その使い方が実に巧妙であるという点は非常に厄介である。
　どうせなら、本業のシステムソリューション販売で役に立ちそうなビジネスモデル特許でも書いて、世界を震撼させた方が余程儲かるのでは？とも思うのだが、余計なお世話だろうか？
　それとも、したくてもそれが出来ないとか？
　まさかねぇ・・・。

　その真意がどうであるにせよ、こういった疑惑の念を世間に抱かせてしまったという事実だけは、決して拭い去ることは出来ない真実（リアル）である。この事が、今後彼らの企業活動に悪影響を及ぼさないことを切に願う・・・。

　今回も方針としては辞書テーブルを利用しないで行う方法を採りたいと思う。この方が何かと安全であるし、ユニシス側からいちゃもんが来た場合にでも「全然違うじゃん」と堂々と胸を張って答えることが出来る。

　ではＬＺＷ圧縮には他にどういう方法があるのだろうか？

　答えは前回の展開法を見れば何となく想像は付くだろう。そう、例のテーブル内の任意のエントリを返す関数を使用するのだ。

　例えば、今ｎ文字のデータ列を圧縮しようとしているとする。その為には、このｎ文字のデータ列がテーブル内に存在するかどうかの確認を行わなくてはならない。しかし、辞書テーブルは持っていない。

　どうするか？

　幸いなことに、その時点までに圧縮を行った出力結果がある。これを旨く利用すれば辞書テーブルが無くても、ｎ文字のデータ列がテーブル内に存在するかどうかの確認が可能なのだ。

　その時点までの圧縮結果を例の関数に渡し、「ｘ番目のテーブルの内容が見たい」と命令すれば、即座に？その結果が返ってくる。あとは、関数の出力結果とｎ文字のデータ列とを次々に比較して、同じ物があるかどうかのチェックを行えば良いと云う訳だ。
　同じ物があれば１文字増やしてｎ＋１文字で比較を行い、同じ物が見つからなければ今までに見つかったｎ文字のデータ列を格納していたエントリを符号化コードとして出力する。この辺は通常のＬＺＷ圧縮と何ら変わらない。

　そして、ＬＺＷ特有のいわゆる「自己反省」、つまり見つからなかったデータ列をテーブルに登録する作業は、テーブルが無いので当然行わない。
　あとは、これを繰り返していけば完全な圧縮データが得られる。

　これで一件落着、めでたし、めでたし・・・なのだが、そう浮かれてもいられない。
　実はここで、ひとつ重要なことを忘れている。

　確かにこの方法でＬＺＷ圧縮と同じ事を行うことが出来る。理論的には何も間違ってはいない。ユニシスの特許を回避するという意味でも、かなり有効であると言えるだろう。
　だが、これが実用的かと問われると首を傾げざるを得ないのが現状である。実際に実装してみたことはないので確実なことは言えないが、それでもこの理論に基づくエンコーダーが異常なほど遅いであろう事は容易に想像できる。
　只でさえ遅いあの関数を、膨大な回数呼び出さなくてはならないのだ、遅くなって当然である。おまけに、圧縮が進むにつれ関数に渡すべき圧縮後のデータも大きくなっていく為、関数自体のレスポンスも次第に悪化していくだろう。

　実際、内部では「１組のデータを圧縮するために、それまでの全圧縮データの中からちまちまと展開しつつ該当のデータを探しだす」という実に遠回りな動作を行っているので、仕方ないと言えば仕方ないのかもしれないが。

　実装時の工夫により・・・例えば、明らかに比較しようとしているデータ列と一致しないことが分かっている場合には呼び出しを控えるとか、関数内部の処理過程で比較データ列と違う事が判明した時点ですぐリターンするようにするとか、通常のＬＺＷでも良く行われている気の利いたハッシュ法を取り入れるとか、そういった努力によりある程度までは高速化されるだろうが、それにも限界はあるだろう。

　そこで、次章ではもう一つの可能性について考察してみたいと思う。

　まず最初に圧縮したいと思うデータ（何でも良い）を用意して、じっくりと眺めて欲しい。用意できない方のために、下に例を挙げてみた。よく見て欲しい。

表１．圧縮したいデータ

　何か見えただろうか？何も見えないのであれば、今しばらく集中して見てみよう。・・・ちなみに「数字が見える」とか言うお約束は抜きと言う事でお願いしたい。（笑）
　いくら見ても分からない方にはさっぱり分からないだろうが、ある点に気づいた方も居られるのでは無いだろうか？

　そう、答えは「辞書テーブル」である。

　圧縮前のデータである上の表のデータと、ＬＺＷ圧縮していく際に生成される辞書テーブルとを比べてみると、実は全く同じなのである。ちなみに、誰でも分かるように下に並べて示してみた。今度こそお分かりだろう。辞書テーブルの境界でデータが重なることを除いては、元データと辞書テーブルの内容は全く同一の物と言って良いのだ。

図３．元データと辞書テーブルの同一性

　となると、わざわざ辞書テーブルなんてモノを利用する必要は無くなる。同じ物が最初から用意されているのだから、それを使えば良い。

　問題は、何処がデータ列の切れ目となるかを正確に認識しなくてはならない点だけである。しかし、これも対処法は簡単である。通常のＬＺＷ圧縮で辞書テーブルにデータ列を書き込むのと同じタイミングで、辞書テーブルに書き込む代わりに元データの方に「切れ目を示す印」を付けるのである。（上の図では”<-”）

　この印はテーブルの各エントリが切れ目かどうかを示すフラグとしての役割を果たす物であるから、テーブルと同じ数だけ用意しなければならない。ＧＩＦではエントリが最大でも４０９６個なので、印も４０９６個だけ用意すればよいだろう。さらに、この印はあくまでフラグなので、４０９６ビット（５１２バイト）もあれば十分である。

　実際に元データを仮想辞書テーブルとして利用する際には、「ある印の位置のデータ」から「次の印の位置のデータ」までが一つのエントリとして認識されるので、これから圧縮しようとしているデータ列と仮想辞書テーブル（実はそれまでのデータ列そのものである）が一致するかどうか調べれば良い。

　注意するべき点は、この仮想辞書テーブルの一番最初のデータ列がテーブル番号１番ではないという点である。この仮想辞書テーブルにはデフォルトで初期化される０〜（色数−１）番目のエントリは含まれていないので、仮想辞書テーブルの一番最初のデータ列は、実は「（色数）番目」のエントリなのである。
　もちろん、何度も繰り返している様に、０〜（色数−１）番目のテーブルの内容はテーブル番号のそれと全く同一なので、２文字以上の一致が無く、１文字で出力しなくてはいけない場合は、それをそのまま圧縮後の符号化コードとして出力すれば良い。

　以上の点にだけ注意していれば、問題なく疑似ＬＺＷ展開のプログラムが書けるだろう。

　では、第一の方法で問題となっていたスピードに関する問題はどうであろうか？
　この仮想辞書テーブルを利用する方法では、目的とする辞書テーブルのエントリを直にそのまま読み込むことが出来る為、かなり高速に動作すると思われる。
　通常のＬＺＷ法でも、実際には各エントリに該当するデータ列がそのまま格納されているわけではない。リスト構造のように、順番に辿っていって初めて該当するデータ列が得られる（この手法こそが特許番号：３０１６８６８号である）のだ。それを考慮すると、今回の方法は通常のＬＺＷ法よりも高速になる場合も十分あり得るだろう。

　この様に速度面でも非常に有効であり、ユニシスの特許にも抵触しない。まさに完璧である。この方法さえあれば、他には何も要らないのではないか？先ほどの第一の方法は一体何だったのか？そう思われるかもしれない。

　しかし、ここでわざわざ２つの方法を紹介したのには訳がある。と言うのは、実は私自身この第二の方法でユニシスの特許を回避できるのかどうか不安に感じているのだ。いや、不安に思っていると言う点に関しては、どちらにも不安はあるのだが、第二の方法の方がより危険性が高いのではないかと考えている。
　確かに特許の請求項からは外れた全く新しい方法には違いないのだが、フラグを立てることによって元データ自身を仮想的な辞書テーブルと見なす行為が通常の辞書テーブル利用と同じと判断された時点で、この第二の方法はアウトである。何せ、その他の部分に関しては通常のＬＺＷ法と何ら変わりは無いのだから。

　その辺りの危険性を考慮した上で速度を取りたいというのであれば、こちらの方法を使用するのも良いかもしれないが、出来れば第一の方法を使用した方が無難なのは間違いないだろう。

　もっとも、元データ自身はプログラマが自分で作り出す物ではなく、ハナから存在している物である。その元データの中に重複するデータがあるかどうかを調べているだけ（フラグを立てて調べ易くしてはいるが）なのだから、問題ないとは思うが・・・。
　根本的に、後で検索するためのデータとして別メモリ空間に格納しておくか、それをやらないか、という大きな差異があるという事だけは覚えておいて欲しい。

　ちなみに第一の方法が何故安全なのかと言うと、第一の方法では圧縮する元のデータと圧縮後のデータを格納する領域以外に一切メモリを必要としない点、出力データの書き込み時以外では何のアクションも発生しない点、が挙げられる。何と言っても、「辞書テーブルらしき」ものすら存在せず、入力に対して何のアクションも起こさず、ダイレクトに出力が返ってくるのだ。これほど安全な方法も他にあるまい。

　さらに言えば、展開と異なり圧縮作業はそれほど高速である必要は無いという事実も挙げられる。秒間６０コマのＧＩＦ画像を生成したところで、喜ぶ人間もそうは居まい。結局の所、多少の速度低下は目を瞑っても安全な方法を採用した方が良いのではないかと思うが、どうだろうか？

　どういう事かと言うと、展開作業によって生成された展開後のデータそのものが、仮想辞書テーブルとして利用できてしまうのである。

　アルゴリズムとしては、展開データを書き込む際に一緒にフラグも立てておくだけである。符号化コード”ｘ”が指定されたならば、フラグ位置を参考に過去の展開データの中からｘ番目に該当するデータ列を引っ張ってきて、そのまま最後尾の位置にコピーすれば良い。

　実に簡単、かつ「比較的」高速である。

　ただし、第二の圧縮理論と同様の危険性を孕んでいる為注意されたい。

　なお、今回の圧縮理論に関してはサンプルソースを提示していない。これはひとえに筆者である私の怠慢以外の何物でもないのだが、仮にサンプルがあったとて、それを自前のソフトに組み込めるだけの技量があれば、一から自分で書く事も決して難しい事では無いと思う。

　さらに今回は実際にＧＩＦエンコードを行う際の注意点も特に挙げていないが、これは前回と大体同じと思って構わない。実際、エンコード処理自体よりもこちらの可変ビット長入出力処理の方が難易度が高いと思われるので、やはり通常のＧＩＦエンコードプログラムが書ける位の技量が無いと実装は困難かもしれない。

　とは言え、これでユニシス特許を回避できるＬＺＷデコード／エンコード理論が一応の完成を見た訳で、これによりＧＩＦフォーマットのサポートを諦めざるを得なかったフリーソフト等でＧＩＦサポートが復活する様な事にでもなれば幸いである。