#6397/6404 計算機と算法
★タイトル (SCIENCE ) 92/ 2/ 8 3:25 ( 39)
データ圧縮: PKZIPの特許／奥村
★内容
Phillip W. Katz (PKWare, Inc.)
U.S. Patent 5,051,745 (Sep. 24, 1991)
Filed Aug. 21, 1990
を入手しました。残念ながら，クレームが12個あるはずなのに，
クレーム1の途中までのコピーしかありませんでした。でも，
やっていることは十分これでわかります。
われわれのものと同じスライド辞書法です。ただし，木を使う
のではなく，バッファ（スライド辞書）の内容がたとえば
VANPCNEC02
なら，（例えば敷居長が3文字の場合）
1:VAN 2:ANP 3:NPC 4:PCN ...
のように区切ります。番号は各文字列のポインタです。
次に，これらの文字列（VAN, ANP, ...）をハッシュ関数で変換
します。そして，このハッシュ値の順にソートし，ハッシュ値の順に
並んだポインタの列を作ります。
さらに「ハッシュ値」→「ハッシュ値の順に並んだポインタの列の中の位置」
を対応づける表を作ります。同じハッシュ値のポインタが複数あるなら，
その先頭位置を指すようにしておきます。
圧縮したい文字列は，最初の3文字のハッシュ値を求め，同じハッシュ値の
ポインタが並んでいるところの先頭位置を表で見つけ，そこから一つ一つ
実際に文字列比較をして，最長一致列を探します。そのポインタ値と長さ
を圧縮したい文字列の代わりに送ることにより圧縮します（この事情は
われわれの場合と同じです）。
技術的には，上述のデータ構造の更新をどのようにするかが問題に
なりますが，以前別経路から仕入れた情報によると，スライド辞書を
大きめ（2倍？）にとっておき，それが元の半分？になると
再構成するというような無駄のある方法だったと思います。
特許の文章は最大限に一般性を持たせて書いてあるので読みにくく，
細部の技術的なことが書いてないので今まで圧縮にかかわったことの
ない人には何のことかわからないかもしれません。なるべくやさしく
解説したつもりですが詳細はＣマガ昨年１月号の圧縮特集をご覧下さい。
ＲＯＭ男さんどうもありがとうございました。
1992年2月8日（#6408），「ぺぱあみんと★すたあ」さん （XVD20299，美濃吉彦さん） が初登場されました。 CP/M 上の PMarc を作られたかたです。 何でも PMarc は木の代わりにハッシュを使ったアルゴリズムを使っているそうです。 ただし2バイトハッシュですが。 また，各ハッシュ値ごとにリストの長さを覚えておき， 消すときはデクリメントするだけというアイデアだそうです。
#6411/6416 計算機と算法 ★タイトル (SCIENCE ) 92/ 2/ 9 6:13 ( 32) ぺぱあみんとさん，sempaさん，など／奥村 ★内容 ぺぱあみんと★さん，どうもありがとうございます。PMarcに ついては評判は伺っておりましたが具体的なことはよく存じません。 ソースは公表されているのでしょうか？ できれば詳しいアルゴリズム をお教えいただけないでしょうか。もし PKZIP と同じものがそれ 以前にも使われていたと証明できるなら，特許に対して異議申し立て ができるんでしょうか＞ＲＯＭ男さん。 そこまでしなくてもアルゴリズムには興味があります。 ぜひ LHA のアルゴリズム改良にご協力下さい。 ……略……
#6518/6538 計算機と算法 ★タイトル (SCIENCE ) 92/ 2/15 17:39 ( 56) 圧縮＞ＰＫ法の一変形／奥村 ★内容 今日は学校のマラソン大会だったので圧縮について また考えました（意味が通じない？）。 例えば abracadabra という文字列を圧縮するのに， 0 abracadabra 1 bracadabra 2 racadabra 3 acadabra 4 cadabra 5 adabra 6 dabra 7 abra 8 bra 9 ra という文字列をまず最初の２文字でソートし，辞書を作ります。 0 abracadabra <- ab 7 abra 3 acadabra <- ac 5 adabra <- ad 1 bracadabra <- br 8 bra 4 cadabra <- ca 6 dabra <- da 2 racadabra <- ra 9 ra この際に分布数えソートを使えば非常に高速です。カウンタの配列の インデックスは２バイトですから要素が65536個，ちょっとMS-DOSでは 苦しいのですがこれは何とかするとします。そうすれば，ワンパスで ソートでき，おまけとして「辞書のbrで始まる部分はどこからか」 という表（上の図の右側の対応）も自動的にできてしまいます。 それに，安定な整列法ですので，自分自身が現れるまで探すだけですみます。 たとえばまず0番の abra... を辞書から探しますが，その際まずabで 始まる辞書の部分を表で引き，ポインタの0番が出てくるまで探します。 この場合はすぐに0が出てきてしまいますので，そういう文字列は ありません。したがって，最初の1文字 a だけ送ります。 次の b, r, a, c, a, d までも同様です。次の7番の abra は，ab で 始まるところから探すと，自分自身（7番）が現れる前に0番があります ので，「0番と4文字一致」という情報を送り出せばいいわけです。 十分素直なテキストなら，この方法で非常に高速に最近接の最長一致文字列 が見つかりますが，問題は例えばスペースだらけのテキストで， スペース・スペースで始まる文字列がたくさんある場合です。 この場合は昔の LHarc のように遅くなってしまいます。 これをどうするか，どなたか知恵をお貸し下さい。 非常に簡単ですので，どなたかテストしてみてくださいませんか。 これだけでは，ぺぱあみんとさんのお力を借りないとＰＫ特許に抵触 しますか？ ハッシュはしてないというのは無理でしょうか。 ちなみに，今 LHA の UNIX 版が作られつつありますが，どなたかが 以前おっしゃっていたように，UNIX ではむしろ tar との分業を 図るほうがいいかもしれないとも思っています。つまり，今の compress 互換の高圧縮プログラムを作るという方向です。 この点についてもご意見をお聞かせ下さい。
1992年の3月に私は神奈川県立高校を辞職し， 4月から松阪大学で働き始めました。 この準備のため大わらわで， せっかくのぺぱあみんと★さんのメッセージや， 4月2日にアップロードしてくださった slide.c と readme.doc にも詳しくコメントできませんでした。 それ以外にも，やり残したことがたくさんありました。 このころは妻が癌の末期で（1993年死去）， 他のことを考える余裕もなかったという事情もありますが， いろいろ不義理をして皆様にご迷惑をおかけしたと思います。
#7718/8184 計算機と算法 ★タイトル (SCIENCE ) 92/ 5/27 6: 6 ( 49) いろいろ／奥村 ★内容 ……略…… ROM男さんが新しいデータ圧縮論文を送ってくださいました: P. E. Bender and J. K. Wolf. New Asymptotic Bounds and Improvements on the Lempel-Ziv Data Compression Algorithm. IEEE IT 37(3):721--729. 1991. これは，たとえばマハリクマハリタと来て次にまたマハリクと来た 場合，このマハリクの最近接最長一致を探すと，まず４文字前のマ ハリが候補にあがりますが，さらに探すと８文字前のマハリタの方 が長いことがわかります。両者の長さの差は１です。そこで，＜８ ・１＞というペアを送るのです（８は８文字前，１は長さの差）。 以前の方法では，＜８・４＞を送っていました（４は長さ自体）。 復号時には，＜８・１＞を受け取ると８文字前のマハリク……の最 近接最長一致をバッファ内で前向きに探します。マハリがそれだと わかると，これは３文字ですから，長さの差１をこれに加えて，４ 文字が実際の長さだとわかりますので，８文字前から４文字コピー して，マハリクマハリタマハリクと復号できるわけです。この方法 で圧縮比は相対値で１割くらい改善されるとのことです。ただし， 復号時にも最長一致探索が必要ですので，解凍が遅くなります。 ……略……
5月29日には，吉崎さんが LHA の辞書サイズを 32K にする実験をしておられます。これだと当時負けていた ARJ や PKZIP より圧縮率が良くなります。
吉崎さんが LHA でフリーソフトウェア大賞を受賞されます。
#7754/8184 計算機と算法 ★タイトル (SCIENCE ) 92/ 5/30 5:46 ( 35) いろいろ／奥村 ★内容 ……略…… ＲＯＭ男さん， ＡＢＣＤＦＧＨＪＫ．．．ＡＢＣＤＦＧＨＩＪ．．．ＡＢＣＤＥＦＧＨＩ 第２候補 第１候補 圧縮される文字列 ということでしょうか。それなら，最近接最長一致は第１候補の方 で，第２候補は用いられないはずですが。もし ＡＢＣＤＥＧＨＪＫ．．．ＡＢＣＤＦＧＨＩＪ．．．ＡＢＣＤＥＦＧＨＩ 第２候補 第１候補 圧縮される文字列 なら第１候補は捨てられて第２候補が選ばれます。一致長は５です が，第１候補の一致長が４なので，一致長の差１が送られます。で もＲＯＭ男さん流の方法もまた別の方法として良いかもしれません がまだ細部をよく理解していません。もっと詳しくお願いします。 圧縮についてはぺぱあみんとさんのアイデアも取り入れてなんとか しようと思っているのですが，なかなか時間がとれません。今のと ころ休日もゴールデンウィークも皆勤でがんばっているんですが， 仕事の待ち行列はなかなか短くなりません。 ……略…… 吉崎さん，第一回フリーソフトウエア大賞受賞，おめでとうござい ます。 ……略……
7月15日には吉崎さんが LHA の辞書を拡大するために djgpp に移植中と書いておられます。 7月26日には DJ 版 LHA をアップロードしておられます。 圧縮法は -lh6- で，64K バイトまでに対応しています。
#8636/8921 計算機と算法 ★タイトル (SCIENCE ) 92/ 8/ 4 5:25 ( 21) いろいろ／奥村 ★内容 ……略…… インターフェースの8月号がデータ圧縮特集です。まだ最初のとこ ろしか見ていませんが，いかにも大学の人らしいしっかりした記述 です。スライド辞書法とか動的辞書法とかは私の命名とあり，恐縮 しました（本当は Storer の命名）。
#8644/8945 計算機と算法 ★タイトル (SCIENCE ) 92/ 8/ 6 6:50 ( 13) tin, WEB, bit, 瞹昧／奥村 ★内容 ……略…… ＲＯＭ男さん，ＷＥＢというのはどんなファイルも１６分の１にす る方法を発明した会社ですね。まだ政治を良くする発明の方がまし だと思って，最近はＩＢＭＰＲＯにも行っていません。圧縮といえ ば，８月号のｂｉｔに７ｂｉｔｓにもアーカイバの話が少し書いて あり，ＬＺＨとＬＺＷは同じもので，ＬＨＡの圧縮が良いのはＵＮ ＩＸのｃｏｍｐｒｅｓｓと同じアルゴリズムだからだとか，わけの わからないことを書いてありました。 ……略……
このころは EastWind さんも加えて William H. Press 他の『Numerical Recipes in C 日本語版』 を訳していました。 次のは，よた話です。
#9721/9800 計算機と算法
★タイトル (SCIENCE ) 92/10/24 16:43 ( 96)
やったぁ！！／奥村
★内容
やっと翻訳が終わった！！！ （ＥａｓｔＷｉｎｄさんはまだかな）。
いま dviprtl で出力しているところです。
ということでまた覗いて見ました。
５Ｇさん，その通りですね，ファイルは単なるビット列ではなく，
EOF というものもあるので（実際にはディレクトリにファイル長と
して入っているのでしょうが），例えば 4 ビットのファイルの集
合（16 通り）を持ってきて，これを平均の意味で圧縮してみろと
言われたら，圧縮が可能なんですね。元のファイルの長さの合計が
4 × 16 = 64 ビットであるのに対し，
0 + 1 + 1 + 2 + 2 + 2 + 2 + 3 + ... + 3 + 4 = 38
ビットに縮まってしまうのですね。一般に n ビットのファイルの
集合をこの方法で圧縮すると，
圧縮前の合計： n × 2^n ビット
圧縮後の合計： (n - 2) 2^n + n + 2 ビット
では 4 ビット以下のファイルの集合に対して圧縮を挑まれたとし
ます。圧縮すべきファイルは
(0, 1, 1, 2, 2, 2, 2, 3, ..., 3, 4, ..., 4)
の 31 通りです。これに対して，圧縮後のファイルも，当然 0 ビ
ットのものも入れなければ負ける。1 ビットのものも 2 個入れな
ければ負ける，……と考えると，結局，集合としては上と同じでな
ければなりませんので，圧縮比は 100% です。この時点では 0 ビ
ットのファイルを 4 ビットのファイルに対応させても何ら問題は
ありませんが，相手が何ビットで挑んでくるかわからなければ，答
える側も，
(0, 1, 1, 2, 2, 2, 2, 3, ..., 3, 4, ..., 4)
に恒等的に（あっ，これがいけないんだ，同じビット数同士を対応
させると読み替えて下さい）写さなければならない。
つまり，ベクトルを平行にすれば一番得をする。これを Cauchy の
不等式といいます（大嘘ですってば，本気にしないで下さい ^^;）。
それにしても，書いていて嫌になるほどあたりまえの話でした。す
みません。
SHIMA さんのは，
L(n) = ceil(log_2(n+1))
と置くとき，自然数から自然数への単射 f が，どんな N について
も
Σ L(f(n)) ≦ Σ L(n)
L(n)≦N L(n)≦N
を満たすなら，その f はどんな n についても L(f(n)) = L(n) で
なければならないというものですね。ビット列は下位から出力して，
最上位の 1 以降は切頭する（EOF にする）なら，整数がファイル
と対応するのでしょうか。
……略……
リンクはご自由にどうぞ。
松阪大学 奥村晴彦 okumura@matsusaka-u.ac.jp
Last modified: Sun Dec 27 14:46:20 1998