1989年2月，紆余曲折を経て， やっとわれわれのグループの総決算ともいえるデータ圧縮特集が， The BASIC の3月号に掲載されました。
1989年4月からは，距離的にもやや仕事がきつい高校に移ったので， あまり圧縮については考えられなくなってしまいました。 その代わり，ときどき CompuServe などを覗き，あちらの人と話し合うのが楽しくなってきました。
#1091/1977 計算機と算法 ★タイトル (SCIENCE ) 89/ 5/10 1:27 ( 20) ＣｏｍｐｕＳｅｒｖｅだより ★内容 昨日ＣｏｍｐｕＳｅｒｖｅのＩＢＭＰＲＯのＬＨＡＲＣ関連のボードに初めて行 ってみました。今朝見たらもうたくさんの返事がくっついていたので驚きました。 ＳＥＡからはやはりＡＲＣという名前はつけてほしくない旨のコメントがかつて あったようですが、その後あまり問題になっていないところを見るとたいしたこと もないのかな。 Ｐｈｉｌ ＫａｔｚはＬＺとＳｈａｎｎｏｎ−Ｆａｎｏ法をくっつけようとして いるとのことです。うまくいくのかな。 ＳｙｓＯｐ Ｃｏｎｒａｄ Ｋａｇｅｙａｍａ氏の質問。なぜスイッチはケース センシティブなのか。提案。例えばＭＹＦＩＬＥ．ＥＸＥなる自己解凍ファイルが あれば、ＭＹＦＩＬＥ ／ｄのようにするとその中身のディレクトリだけ見れるよ うにしてはどうか。ただしサイスがあまり増えるようならいらない。また、ＭＹＦ ＩＬＥ ＦＩＬＥ．１のように特定のファイルを指定して自己解凍できないか。こ れによってどのくらい自己解凍ファイルのサイズが増えるか。 Ｇｒａｎｔ Ｅｌｌｓｗｏｒｔｈ氏から。ＬＺＨＵＦの頻度テーブルの変更法は もっとうまくできるのではないかという気がする。 その他、５｢ろいろなメッセージがありましたが、まだ具体的なアルキSリズムにつ いての話には残念ながらなっていません。 追伸：おっとこれは何日も前に書いたものだった。もうポストしたものかな。 いずれにせよ昨日とかあるのはやや前の話です。
ここで一つアイデアが浮かびました。 データ圧縮の考え方を使ったバイナリ差分です。
#1099/1982 計算機と算法
★タイトル (SCIENCE ) 89/ 5/14 19:42 ( 36)
もう一つのデータ圧縮／奥村
★内容
以下に書くことは、確かどこかで読んだことのある内容だと思うのですが、ソー
スが思い出せません。オリジナルなアイデアではありません。とりあえず手もとに
ある本などを参考にして、その議論を復元してみます。
データ圧縮というと、与えられたテキストなり画像なりを圧縮することだけを考
えがちですが、われわれにとって有用なもう一つの圧縮があります。
われわれはプログラムを作るとき第１版、第２版、……と改良を重ねていくわけ
ですが、それらの間にはほぼ共通の部分もたくさんあるはずです。そこで、第２版
を発表したときは、第１版との違いの部分だけをうまく提示することができれば、
第１版をもっているものにとっては、かなり小さい「修正箇所」だけのファイルを
もらうだけで第２版が復元できるはずです。
といっても、パッチを当てるというわけではなく、ある部分に新しいコードが挿
入されてその後の部分は後ろにずれるという類のことにも対応できなければなりま
せん。
こういったことは、絶対ジャンプ命令の多い実行ファイルではあまりうまくいか
ないかもしれませんが、ソースプログラムなどではたいへん効力を発揮するのでは
ないかと思います。
ＵＮＩＸのｄｉｆｆは（といっても私はＵＮＩＸ使ったことないのですが）、こ
ういう考えの一つの実現と見ることができるでしょう。ｄｉｆｆはＭｃＩｌｒｏｙ
の作ったプログラムで、テキストファイルにしか適用できません。そのアルゴリズ
ムは例えば
J. W. Hunt and T. G. Szymanski, A fast algorithm for computing
longest common subsequences, CACM (May 1977)
にあるそうです（読んでない）。ｄｉｆｆ自体のアルゴリズムは
M. D. McIlroy and J. W. Hunt, An algorithm for differential file
comparison, Bell Labs Computing Science Technical Report 41 (1976)
にあるそうです。
データ圧縮の文脈ではｉｎｃｒｅｍｅｎｔａｌ ｃｏｄｉｎｇの一種と考えられ
ます。これについては、例えば
M. Visvalingam, Indexing with coded deltas: a data compaction
technique, Software Practice and Experience 6, 397-403 (1976)
に言及されているそうです。
どうも「そうです」が多くてすみません。どなたか研究してみてくださいません
か。われわれがＢＢＳで交換するプログラムは、完成品が１つあるだけというので
はなく、皆の意見を聞いては少しずつ手を加えて改良していくというタイプが多い
ように思いますので、この種の「圧縮」はけっこう役に立つのではないかと思いま
す。どうでしょうか。
#1115/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 6/ 3 6: 2 ( 16) 圧縮＜ＣｏｍｐｕＳｅｒｖｅ／奥村 ★内容 ＰＫＺＩＰ１．０はあと１〜２週間ほどでベータ版になるとか。今月中には完成 するらしい。新アルゴリズムは３つのバリエーションがあり、ファイルの性質によ って使い分けるとのこと。欠点はＰＫＺＩＰ、ＰＫＵＮＺＩＰ、ＺＩＰ２ＥＸＥと ３つに分かれていて使いにくく、自己解凍ファイルは１５４８０バイトも増える。 このことからアルゴリズムはＬＨＡＲＣと違うことがわかる。 ＰＫシリーズの作者Ｐｈｉｌ Ｋａｔｚはミルウォーキーあたりに住む２６才の 青年。ＣｏｍｐｕＳｅｒｖｅにはほとんど現れない。ＣｏｍｐｕＳｅｒｖｅではＺ ｅｎｉｔｈ Ｆｏｒｕｍにときどき現れる程度。そこのＳｙｓｏｐはＪｏｓｅｐｈ （Ｊｏｅ） Ｋａｔｚというノースキャロライナに住む英語の教授だがＰｈｉｌの 親類ではないらしい。ＰＫは自前のＢＢＳを持つが、回線が少ないので、主にＥＸ ＥＣ−ＰＣというローカルＢＢＳで圧縮関係の話をしているらしい。そこでの話の 内容がご隠居先生がポストしてくださったｅｘｅｃ．ｐｋというファイルらしいの ですが、残念ながら私には回線不良（？）のため読めない。それに何かアルゴリズ ムについて書いてあるならどなたか教えてください。 まちがえた、ｅｘｅｃ．ｐｋはＮＩＦＴＹだった。ＰＣ−ＶＡＮでもどこかにあ るんでしょうか。
私の頭の中には，LZHUF の Huffman 部分を dynamic Huffman ではなく古典的な2パス Huffman にして高速化するアイデアが出はじめました。
#1150/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 6/14 6:14 ( 43) ＬＺＨＵＦの高速化のアイデアなど／奥村 ★内容 ＣｏｍｐｕＳｅｒｖｅではＬＨａｒｃが良いかＰＫＺＩＰが良いかというような 議論が続いていました。アルゴリズムについては全然といってよいほど話題が出ま せん。日本のＢＢＳはかつて米国でＣＰ／Ｍはなやかなりし頃のように趣味でプロ グラムを作る人でにぎわっているが、米国のＢＢＳではＭＳ−ＤＯＳの時代になっ てから既存のプログラムを利用する方法に関心が移ってしまったということです。 ＬＨａｒｃを高速にするには、ひとつにはある程度大きいファイルについては適 応型をやめて２パスでハフマン（または算術または後続文字集合）圧縮するのが良 いかもしれません。こうすると特に解凍はうまくすると表を引くだけでできるので 非常に速くなるでしょう。もう一つはスライディング辞書部分をまったく書き換え てしまって２分木でなくｔｒｉｅのようなものにするという方法が考えられます。 あと、一致位置については、表をもっていると自己解凍ファイルが大きくなるので、 次のように単純化することを考えたんですが、ＬＨａｒｃでは一致位置が９ビット から始まるのに対してこれは８ビットから始まるので、中程度の距離ではかえって ビット数が多くなってしまい、ファイルの性質にもよりますが、圧縮比はやや落ち る傾向にあります。ＩＳＨとＬＨａｒｃで解凍してください。 ＲＯＭ男さん、私は最初、理論的には２５５ビットまで行くかと思ったのですが、 吉崎さんに言ったら、頻度がある程度おおきくなると全部を２で割るので根の頻度 に上限があり、そのため計算してみると二十何ビットまで（ちょっと忘れた）にし かならないというふうなことでした。いずれにしても当初１６ビットまでと考えた のは違っていたのでｌｏｎｇに変えることにしたということで、新しいＬＺＨＵＦ では３２ビット整数を使っています。 みるくさんどうも。ＮＩＦＴＹでも同時に同じこと書いたら、吉崎さんがメール でソースを送ってくださいました。このｃｏｍｐｒｅｓｓ．ｃは * Revision 4.0 85/07/30 12:50:00 joe というもの（１６ビット版）です。ＰＫＺＩＰのソースという話は知りません。ま だベータテスト結果くらいしか出てないのでは？ ＭＡＳＳＡＮさんお久しぶりです。ぜひまた手伝ってください。Ｈｕ−Ｔｕｃｋｅｒ というのはよく知らないので調べておきます。
次のログには抜けがあるようです。
#1159/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 6/17 6:15 ( 38) 簡略化２次ハフマン圧縮／奥村 ★内容 １文字圧縮部分のアルゴリズムだけです。 原理はいたって簡単です。各文字の直後に最も頻繁に現れる１６個の文字を表 に登録します。表にない文字が来ると「００」に続いてその文字自体を送り、表 の右端に登録します。表があふれたら右側から捨てていきます。表にある文字は、 表の左にある文字ほど短いビット数で送り、そのすぐ左側の文字と交換します。 こうするうちに、頻繁に現れる文字ほど表の左に集まります。 復元部分はまだ書いていませんが、６ビットずつ読んで表を引けばよいでしょ う。どなたか作ってみてください。 ふつうの適応型ハフマンより速く圧縮比も良いのですが、Ｓｔｏｒｅｒの本に あるダイナミックディクショナリ法の方が圧縮比は良いようです。 Ｐｈｉｌ Ｋａｔｚのいっている「後続文字集合（ｆｏｌｌｏｗｅｒ ｓｅｔ ）」の方法よりこちらの方がきっと良いでしょう。 ただし、２文字の相関は、スライディング辞書アルゴリズムがすでに考慮して くれているので、それと組み合わせても単純なハフマンより圧縮比が良くなるこ とはないようです。 むしろスライディング辞書アルゴリズムを高速化して通常の２パスハフマンを 使うことの方が期待できます。この場合も、ハフマンコードの復元には表を使い ます。コードのほとんどは１２ビット以下ですから、４Ｋバイトの表を作れば、 については、例えば表からリストをつないで探索します。あるいはｌｚｓｓでや ったように、根が４Ｋ個ある２分木で探索すればさらに速くなるでしょう。
#1210/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 6/25 16:28 ( 49) ＰＫＺＩＰのアルゴリズム／奥村 ★内容 大久保先生がポストしてくださったｕｎｚｉｐを読んで推測してみました。 ＰＫＺＩＰでは３つの方法がサポートされているようです。 ・ｓｔｏｒｅ 単に各文字をコピーするだけ ・ｓｈｒｉｎｋ ダイナミック辞書（ＬＺＷの改良版） ・ｒｅｄｕｃｅ スライディンク辞書＋後続文字集合（ＬＺＨＵＦの変形） このうち特に問題となっているｒｅｄｕｃｅアルゴリズムについて記します。 アルゴリズムは、前段がスライディング辞書エンコーダ、後段に後続文字集合 によるエンコーダがあります。 スライディング辞書エンコーダは、バッファにそれまで読んだ４０９６バイト の文字を保管しておき、新しく読んだ文字列との最長一致の位置と長さ（≧３） を送るか、一致が３文字に満たないなら１文字を出力します。 ２パスのため、この段の出力はすべて１バイト単位にしてあります。そのため、 余分の１ビットで文字そのものを送るか《位置・長さ》ペアを送るかの区別をす るということができないので、エスケープシーケンスを用いています。エスケー プ文字はアスキーコード１４４の文字です。ただし、本当に１４４という文字を 送りたいときは１４４に続けて０を送ります。１４４のすぐ後が０以外なら《位 置・長さ》ペアを意味します。 以下はパラメータｆ＝１，２，３，４によってビットの扱いが異なります。こ のパラメータの値はヘッダに入っています。 １４４の次の２ないし３バイトが《位置・長さ》ペアを表します。 まず、１４４のすぐ次のバイトは、下位（８−ｆ）ビットが（一致長さ−３） を表し、上位ｆビットが一致位置のオフセットの上位バイトの値を表します。 通常は、その次に送るバイトが一致位置のオフセットの下位バイトです。ただし、 オフセット０が１つ前、オフセット１が２つ前、……のような数え方をします。 ここで、もし１４４のすぐ次のバイトの下位（８−ｆ）ビットがすべて立って いれば、そのすぐ次にもう１バイト送り、実際の（一致長さ−３）は、最初のバ イトの下位（８−ｆ）バイトの値＋次のバイトの値となります。そして３バイト 目が一致位置のオフセットの下位バイトとなります。 上述の前段エンコーダの出力は、さらに２パスで圧縮されます。その方法は、 １パス目ですべてを走査し、各文字の次に最も頻繁に現れるｎ文字の表を作りま す。ただし０≦ｎ＜６４で、ｎの値は各文字ごとに異なっていてもかまいません。 とにかくオプティマルな値を決めます。 こうしてできた後続文字集合の表をまず送ります。表は最大（６＋８×６３） ×２５６ビットの大きさで、２５６種類の文字のおのおのについて次の情報を持 っています。 ・後続文字集合の大きさｎ（０≦ｎ＜６４）……６ビット ・後続文字集合のｎ個の要素……８ｎビット それに続けて、２パス目で次のような符号化を行います。 まず、１つ前の文字をｃとします（ｃ＝０に初期化します）。 文字を読むごとに、それがｃの後続文字集合に属しているかどうか調べ、属し ているかいないかの区別を１ビットで送ります（例外としてｃの後続文字集合の 大きさが０のときはこのビットは不要です）。 次に、その文字が表のｋ番目に登録されていたならば（０≦ｋ＜ｎ）、ｋの値 を最小ビット数で出力します。つまり、例えばｎ＝１６なら、ｋを４ビットで出 力します。もし後続文字集合に属していなければ、８ビットで文字をそのまま出 力します。 こんなところでしょうか。間違っていたら教えてください。 Ｓｈａｍさん転送しておきます。
#1215/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 6/25 18:39 ( 44) ハフマン法の解説／奥村 ★内容 話の流れに関係ないが、古典的ハフマン法のわかりやすい解説を考えています。 以下は試案。 ハフマン法というのは各文字を一定のビット数の符号語に対応させるのですが、 その際、例えば１０１０という符号語があれば、これをプリフィックス（頭）とし て持つ符号語（例えば１０１０１）は存在できません。逆に、１０１０１があれば １０１０も存在できません。これをプリフィックスコードの仮定ということにしま す。この仮定がなければ符号語の切れ目が１パスで判断できなくなります。 さて、簡単のため、符号化すべき文字がＡＢＣ……Ｚの２６文字であり、 Ａの頻度≧Ｂの頻度≧……≧Ｚの頻度 だとしましょう。これらに符号語を割り当てるわけですが、 Ａの符号語の長さ≦Ｂの符号語の長さ≦……≦Ｚの符号語の長さ でなければ最適な割り当てといえないことは自明でしょう（長さとはビット数です）。 ここで、Ｙの符号語とＺの符号語は同じ長さでなければなりません。なぜならば、 もしそうでなかったとすると、例えば Ｙ：１０１００１ Ｚ：１１００１１１ のようになるわけですが、もし １１００１１１ という符号語がもしあるなら、それの最後の１を取った １１００１１ という符号語はあってはなりません（プリフィックスコードの仮定）。しかし、こ ういう符号語が他にないなら、これをＺの符号語としてしまえば、圧縮されたファ イルの長さが減るはずですから、最適にコードを選んだという仮定と矛盾します。 したがって、Ｙの符号語とＺの符号語とは同じ長さです。（さらに短い１１００１ という符号語もないからもう１ビット取ってしまえ……おっとこれでは「……≦Ｚ の符号語の長さ」の仮定に反する！） さて、再びプリフィックスコードの仮定から、 １１００１ という符号語は存在しえません。したがって、 １１００１０ という符号語は存在しえます。よって、符号語の割り当てをやりくりすれば、 Ｙ：１１００１０ とすることが可能です。こうすると、ＹとＺは最後の１ビットだけで区別されるこ とになります。そこで、今後は １１００１ という符号語を（Ｙ，Ｚ）の組を表すものと考え、１１００１が現れたら次の１ビ ットで両者の区別をすると考えることにします。組α＝（Ｙ，Ｚ）は１つの文字の ように考えるわけです。そして、αの頻度はＸの頻度とＹの頻度の和です。 こうすれば、アルファベットはＡ，Ｂ，……，Ｘ，αの２５文字に減り、このア ルファベットに対してさきほどと同様な議論をすれば、次第に文字の種類が減り、 最後には１個になってしまいます。この最後の１個に長さ０の符号語を割り当てれ ば、全部の符号語が再帰的に決ってしまいます（頻度が等しいものの並べ方につい ての不定性はあります）。これがハフマンコードです（最後の詰めが甘いか）。
#1216/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 6/25 18:40 ( 7) ＰＫＺＩＰのアルゴリズム補足／奥村 ★内容 日本グループの作品がバッファを最初スペース（２０Ｈ）で初期化するのに対し て、ＰＫＺＩＰはＮＵＬ（０）で初期化しているようです。 後続文字集合の大きさｎについて０≦ｎ＜６４としましたが、実際は０、２、４、 ８、１６、３２のいずれかだろうと思われます。とすれば個数を表す部分のビット 数は６ビットでなく３ビットですみそうですが。 感想：意外と粗雑なアルゴリズムでびっくりしました。もしかしたら現在の版は もっと工夫しているのかも。
NIFTY では前にわたしが考えたバイナリ差分ソフトが開発されつつあります。; 最初の頃は LDARC と言っていたのですが，後に LDIFF になりました。
#1251/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 6/29 1:20 ( 27) ＮＩＦＴＹよりＬＤＡＲＣ構想／奥村 ★内容 ……前略…… 以下奥村のコメント。 一致長さはうんと長いものが期待できますので、仮に１６バイトなり２５６バイ トなりの一致があったならば、ひょっとしたらもっと長く一致しているんではなか ろうかと勘ぐって、その位置からさらに後も一致をチェックしてみて、あれあれや っぱりもっと一致するということなら、一致長さをうんと長く出すようにすれば如 何。長さのエンコードはＦｉａｌａたちの論文の解説で紹介したｕｎａｒｙ ｃｏ ｄｅを用いれば、短い一致から長い一致まで、可変長でエンコードできます。おお そうだ、この「最大限一致したらもっと長く一致していないか試してみる」という アイデアはＬＺＨＵＦにも応用できそうだ。こうすればＦの値をあまり大きくしな いでも、ほんのときたま現れる非常に長い一致を活かすことができるのでは。
#1258/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/ 1 15:35 ( 19) 新ＺＩＰ、ＰＫ対ＳＥＡ／奥村 ★内容 ６月１８日、Ｐｈｉｌ ＫａｔｚとＳＥＡのＴｈｏｍ Ｈｅｎｄｅｒｓｏｎとを 招いて行われたＧＥｎｉｅのオンライン座談会の様子。大久保先生からいただだい たファイルによります。大久保先生どうもありがとうございます。 最初は２人とも平和に話していたのだが、次第に白熱し、とうとうＰＫはＴｈｏ ｍに「貴殿は嘘つきか。私がこれこれしかじかのことを認める証言をしたなどと書 いて貴殿が出した手紙類は何だ」などと言い放つやいなや退散してしまった。この 態度にはＰＫの支持者までもがあきれてしまった。 以下はＰｈｉｌ Ｋａｔｚの発言の抜粋。 新しいＰＫＺＩＰはＳｈａｎｎｏｎ−Ｆａｎｏ法を２重あるいは３重に使ってい る。ＬＺＨＵＦの問題点は適応型Ｈｕｆｆｍａｎ法が非常に遅いことにある。Ｓｈ ａｎｎｏｎ−Ｆａｎｏ法についてはほとんど（１冊の）教科書だけから学んだ。Ｐ ＫＺＩＰの暗号化の方法は排他的論理和ではなくもっと安全なものである。．ＺＩ Ｐファイルフォーマットはパブリックドメインである。ＳＥＡのＡＲＣは署名が１ バイトしかないがＰＫＺＩＰは４バイトもある。アーカイブファイルの最初の１バ イトが化ければＡＲＣフォーマットでは読めなくなる。独立なサードパーティに、 ファイル化けに対する抵抗力を試してもらいたい。 また、南アフリカ産のＺＥＢＲＡという圧縮ソフトがあって、ＬＨＡＲＣより圧 縮比が良い、ただしＣで書かれていることによるオーバヘッドがある、という話題 も出ました。
#1260/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/ 2 15: 0 ( 30) いろいろ／奥村 ★内容 ＣｏｍｐｕＳｅｒｖｅで最近の日本でのことを書いたところ返事が２通あり。 クリスチャンセン氏からの返事： ＬＨＡＲＣもいいが遅すぎる。もう少し速くならないか。ところで、ディスクを ＦＡＴを含めて圧縮する「ｃｏｐｙｄｉｓｋ」というのはできないか。 エルズワース氏からの返事： ２パスにすれば解凍はずっと速くなろうが、表を付けねばならない。シャノン・ ファノが（ハフマンのように）最適でないということは疑問である。ＺＩＰのα版 がその証拠。算術圧縮はなんとか速くならぬものか。（ＬＤＡＲＣのような）差分 圧縮は非常に興味がある。ＰＡＫにもそのような機能がある（エルズワース氏は私 の言ったことをバージョン管理機能と間違えているらしい）。 話は変わりますが、ダイナミックハフマンについて。スライディング辞書圧縮が だんだん速くなるにつれて、一致長の上限はもう少し増やしたいところ。しかし、 これでは一致長の大きいところで統計が少なすぎてハフマンで縮まりにくくなる。 したがって、一致長が大きいところでは幾つかをまとめて頻度を求めた方がよいと 思います。最も簡単には、例えば１６バイト以上の一致は同じ符号にして、続く数 ビットで一致長を表せばいいでしょう。やってみましたが、微々たる違いでした。 お恥ずかしいことですが、ＲＯＭ男さんに指摘されるまで、私はＭＳ−ＤＯＳの ファイル比較ユーティリティＦＣのアスキーモードでの動作を知りませんでした。 要するにＵＮＩＸのｄｉｆｆそのものでした。この出力と旧ファイルとを読み込ん で新ファイルを復元するｎｅｗというＰＤＳもあるとのことです。 しかし、残念ながらＦＣは行単位で働き、バイナリモードでは単なるパッチをあ てた部分を見つけるくらいにしか使えないようです。バイナリファイルについても 新旧バージョンの違いを見つけてその情報をなるべく少ないビット数で出力するよ うなものがあればよいのですが。 ＮＩＦＴＹでもあれから何も新情報は入りません。
いよいよ今の LHA のアルゴリズムが私の頭の中ではっきり形をとりはじめます。 しかしコーディングする暇がありません。
#1261/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/ 2 17:49 ( 27) 擬似２パスハフマン圧縮／奥村 ★内容 ２パスは速い、しかしフロッピーディスク使用の場合はＩ／Ｏが遅い。 この問題を解決するために、内部に例えば３２Ｋないし６４Ｋバイトのバッファ を設けることを考えました。 まず、圧縮の１パス目は、スライディング辞書圧縮します。最長一致は２５６バ イトくらいにしておきます。こうすれば、１文字送出か一致発見かで１ビット、続 いて文字自体か一致長を８ビットにできます。一致長に続いて１２ビットで一致位 置を表します。これらは、中間ファイルに出力する代わりに、内部バッファに入れ て行きます。同時に、１文字（２５６種類）＋一致長（２５６種類）＝５１２種類 の「文字」について、頻度を数えていきます。 内部バッファがいっぱいになったなら、２パス目に移ります。５１２種類の「文 字」は古典的なハフマン圧縮をします。表は、この前ポストしたＣのソースの流儀 で出力します。あの方式では、実際に使われた「文字」だけについてハフマン木を 出力するので、小さいファイルではそれなりに小さい表になります。また、一致位 置はＬＺＨＵＦ方式の可変長コードで出力します。 中規模のファイルなら、これだけで終わってしまいます。 大きいファイルについては、上記のことを繰り返します。その際、ハフマン木は 内部バッファ一杯分ごとに新しく作ってもよいし、最初の数十Ｋバイト分（これは １パス後の大きさ。圧縮前の大きさにして１００Ｋバイトにもなるかもしれない） での頻度分布がその後も続くと仮定して、以前のハフマン木を流用してもかまいま せん。後者の方法なら、木は１回の送出ですみます。 復元は、最初に木があるので、１パスでできます。これは大変高速です。 細かい改良点として、「文字」は５１２種類では多すぎるので、例えば１６バイ ト以上の一致は一括して１つの「文字」で表し、“一致文字数−１６−ＴＨＲＥＳ ＨＯＬＤ”を次の７ビット（例えば）で送ってもよいと思います。この方が、最初 に送る木の大きさが減ります。 こういうもののプロトタイプを作ろうとずっと考えているのですが、なかなか手 がまわりません。どなたかやってみませんか。
#1269/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/ 3 19:26 ( 21) ＣｏｍｐｕＳｅｒｖｅより／奥村 ★内容 差分圧縮を誤解した向きもあったので再度いろいろ説明したところ次の返事あり。 アーブ・ホフより： ディスクまるごと圧縮ならＦＡＳＴＢＡＣＫというのがあるよ。 グラント・エルズワースより： ２パスにすれば圧縮比も良くなるだろう。差分圧縮は、ちゃんと管理された事後 保全の一環として行うのでなければかえって混乱をもたらすのでは？ アーブ・ホフより： 米国ではＳＥＡがＡＲＣという名前を登録商標にしてしまった。ＡＲＣを含む名 前をつけると法的に問題になる可能性があるし、それに．ＡＲＣという拡張子をも たない圧縮ファイルを作るプログラムがＡＲＣを含む名前を持つことは混乱につな がる。われわれが初めてＬＨＡＲＣという名を目にしたときは、．ＡＲＣファイル を作る新しいプログラムかと思った。多くの人がこのように思い込んでしまった。 名前としてはＬＨＡＲＣでなく単にＬＨとするだけで十分であり、この方が一般に 受け入れられやすいであろう。いずれにせよＬＨＡＲＣ１１３Ｃはほとんどの人が ＬＨとリネームしてしまったし、ＣｏｍｐｕＳｅｒｖｅのファイル名は６文字に限 られているのだから、ＬＨ１１３Ｃ．ＥＸＥなら６文字でちょうどいい。いずれに せよ、速度が現在最も重要視されている。ＰＫＺＩＰ１．０はＬＨＡＲＣの２倍の 速さだが、それでもＰＫＰＡＫの半分の速さしかない。
NIFTY ではバイナリ差分プログラムがやっと完成します。
#1274/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/ 5 5:52 ( 7) ＬＤＡＲＣをポストしました／奥村 ★内容 以下はＮＩＦＴＹからダウンロードしたＬＤＡＲＣです。回線が悪いのか自作ソ フトが悪いのか、あいかわらず１０ブロックに１回はチェックサムエラーが起きる という感じで心配でしたが、比較的小さいファイルのため、なんとか読むことがで きました。ＮＩＦＴＹでちゃんとＸＭＯＤＥＭで読めたのはこれが初めてかな。 ＬＺＨＵＦ４．ＣとＬＺＨＵＦ５．Ｃの差分ファイルを作ってみましたが、たっ たの３０４バイト。すばらしいものです。これでバージョンアップのたびに長いフ ァイルをアップロード／ダウンロードする手間がはぶけます。三木さんに脱帽！
#1297/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/ 9 6: 7 ( 25) ＣｏｍｐｕＳｅｒｖｅより／奥村 ★内容 以下は前回のアクセス時以降にポストされた全メッセージの要約。 jeff clough: Ａｕｔｏｒｕｎは危険と思う。 Irv Hoff: ＬＨＡＲＣでは改善されている。ＬＨＡＲＣのｓｆｘは１３００弱増える程度だ がＰＫＺＩＰ１．０（８月１日に出る予定）では１５４８０バイトも増え、ａｕｔ ｏｒｕｎはできない。しかしＬＨＡＲＣより２倍ほど速く、圧縮比も１％ほど良い。 ＬＨＡＲＣが今の３〜５倍速くなれば無敵なのだが。 Bob Tolz: ＳＥＡがＡＲＣの商標権を得たとは知らなかった。 Irv Hoff: ＡＲＣ商標権獲得はＳＥＡのヘンダーソン自身が６月１８日のオンライン会議で 明らかにした。 K.OKUBO: 法律家がａｒｃのネーミングについてどう言うか聞いてみたい。日本では商標に 関する訴訟が多い。 Irv Hoff: ポピュラーなプログラムの名は２文字で十分である。スーパーディレクトリＳＤ を見よ。いずれにせよ多数の人がＬＨＡＲＣ．ＥＸＥからＬＨ．ＥＸＥにリネーム しているようだ。ＳＥＡの登録商標ＡＲＣを避ける手でもある。 John Jurewicz: 差分圧縮プログラムはあるか？ K.OKUBO: 三木氏のＬＤＡＲＣというのができた。またしてもＡＲＣが付く。適当に改名さ れたい。三木氏にＬＤではどうかと聞いてみよう。
7月10日には MASSAN さんが LHarc の名前が問題になるのなら LHa はどうかと提案されています。チベット語で神様のことだそうです。
#1312/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/11 5:58 ( 26) ＣｏｍｐｕＳｅｒｖｅより／奥村 ★内容 Grant Ellsworth: ＰＫＺＩＰ１．０はＬＺＨＵＦより圧縮比が良いこともあるが平均すると多少悪 い。良い場合も、一致長のためではない。ＰＫによれば一致長は６４を超えない。 しかし最小一致は３でなく２である。大きなファイルでは適応型ハフマンは２パス ハフマンより悪い。ＰＫＺＩＰ１．０は８Ｋの窓を使うので１０Ｋ以上のファイル ではＬＺＨＵＦより良い。頻度の差が大きいときはハフマンよりシャノン・ファノ が良い。 Steve Burg (PKWARE社): エルズワース氏の言ってくれたことでだいたいよい。ただ、バイナリファイルで は最小一致長は２で辞書は４Ｋである。８Ｋ辞書を使う場合は最小一致長は３であ る。最大一致長は元は各６６、６７であったが、後に１バイト付け加えたため２５ ６だけ増した。これで圧縮は若干良くなった。ＬＨＡＲＣよりずっと圧縮比が良い 場合には主に８Ｋ辞書が効いている。ハフマンとシャノン・ファノの違いはほとん ど見られなかったが、解凍は後者の方がずっと速く、表の格納も効率的にできる。 さらに一種の最適経路（オプティマル・パス）アルゴリズムでリテラル（文字をそ のまま送る）とコピー（一致位置・長さを送る）のどちらを選ぶか決めていること も圧縮に若干効いている。ＰＫＺＩＰの高速化にあたっていつもこの最適経路アル ゴリズムに手を加えており、そのためベータテスト版より圧縮比は若干良くなって いる。［奥村注：どういうアルゴリズムかは全く不明］ John Jurewicz: 大久保教授がもうすぐ三木氏のＬＤＡＲＣをＣｏｍｐｕＳｅｒｖｅにアップロー ドしてくれるとのこと。“−ａｒｃ”命名問題がエスカレートしてＰＫ論争の再現 となり彼ら紳士たちに職業的・個人的支障をもたらさぬよう切に望む。
#1321/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/13 0:29 ( 38) ｄｉｆｆのアルゴリズムと差分圧縮／奥村 ★内容 ＣＡＣＭ（Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ）は日本でい えば情報処理学会にあたる米国のＡＣＭ（Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｃｏｍｐｕｔｉｎｇ Ｍａｃｈｉｎｅｒｙ）が出しているあまり肩のこらない専門 誌です。この最新号（といっても６月号。航空便にしてもらっていないので１〜２ か月遅れで到着する）にｄｉｆｆのアルゴリズムが載っていました。ｄｉｆｆは Ｕｎｉｘのｆｉｌｅ ｄｉｆｆｅｒｅｎｃｅ ｕｔｉｌｉｔｙ（２つのファイルの 比較をする小道具プログラム）です。もっともこの記事はｄｉｆｆのアルゴリズム の解説が主体なのではなくＬｉｔｅｒａｔｅ Ｐｒｏｇｒａｍｍｉｎｇと題して Ｋｎｕｔｈの文芸的プログラミング手法を解説したものでその例題としてｄｉｆｆ のなかのさわりの部分を簡略化したもののソースコードを載せているだけです。そ れに文芸的プログラミングの解説としてもいささかかたよった記事なのであまりお すすめできません。しかし、これでなんとかｄｉｆｆの考え方が解読できました。 目的はもちろん、三木さんがｌｄｉｆｆで実現しようとしている ｄｉｆｆｅｒｅｎｔｉａｌ ｅｎｃｏｄｉｎｇ（差分圧縮）のよりよいアルゴリズ ムを考えるためです（差分は本当はｄｉｆｆｅｒｅｎｃｅで、 ｄｉｆｆｅｒｅｎｔｉａｌとすると微分の意味になってしまうのですが、情報処理 関係では差分の形容詞形としてｄｉｆｆｅｒｅｎｔｉａｌを使うようです）。 前置きが長くなりましたが、この記事による限り、ｄｉｆｆのアルゴリズムは次 のようになっています。 まず、旧ファイル、新ファイルをスキャンして、そのすべての行を（２分木なり ハッシュ表なりを使って）登録します。その際、全く同じ行のダブりを検出できま すが、旧ファイルと新ファイルにおのおの１回だけ現れる行をマークします。あと は、このマークした行を核として前後の行を次々に調べていけば、変わっていない ブロックがマークされることになります。結局、違いのある行だけが残ることにな ります。 このアルゴリズムは、ファイルが行という自然な単位で構成されていることを利 用しているので、このままではバイナリファイルには使えません。バイナリファイ ルに適用するためには、少なくとも一方のファイルについては、すべての場所から 始まる一定長さのバイト列を登録しなければなりません。 そこで、例えば旧ファイルについては０〜Ｎ−１、Ｎ〜２Ｎ−１、……のように Ｎバイトずつに区切って表または木に登録し、次に新ファイルについてはすべての 位置から始まる文字列をこの表または木と照合して、一致が見られたら、さらに逆 方向と順方向に、こんどはＮバイト単位ではなく１バイト単位でたどっていって、 正確にどのバイトからどのバイトまでが一致するかを調べる、ということが考えら れます。 この方法では最悪の場合２Ｎ−２バイトの一致が検出できないことがあります。 しかし、プログラムの改訂作業では、かなり長いブロックがそのまま残りますので、 この方法でも十分有効かもしれません。
このあたりで圧縮で U.S. Patent がとられているというニュースが入ってきます。
#1323/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/14 6: 3 ( 4) それは大変／奥村 ★内容 そんなものにＰＡＴＥＮＴをやるくらい米国ＰＡＴＥＮＴ ＯＦＦＩＣＥも 落ちたのでしょうか。Ｋａｒｍａｒｋａｒ法だとかＦａｓｔ Ｈａｒｔｌｅｙ Ｔｒａｎｓｆｏｒｍだとかも。 われわれもＬＡＲＣ、ＬＨＡＲＣにパテントとりましょうか。
もちろんこの最後の部分は冗談で，パテントを維持するような財源はありません。
そうこうしているうちに，このパテントの MWS 法の PL/I ソースを入手して解読しました。
#1340/1982 計算機と算法
★タイトル (SCIENCE ) 89/ 7/17 18: 3 ( 48)
ＭＷＳ法解説／奥村
★内容
これはＳｔｏｒｅｒの本でいうＩＤ−ＬＲＵ法のことだと思います。
ＩＤとはｉｄｅｎｔｉｔｙ ｈｅｕｒｉｓｔｉｃ、つまり前回の一致文字列と今
回の一致文字列をつないだ文字列を新たに辞書に登録するものです。辞書要素は１
〜４０９６の番号がついています。すべての１文字は最初から辞書の１〜２５６番
の要素として登録されています。ＬＲＵとはｌｅａｓｔ ｒｅｃｅｎｔｌｙ
ｕｓｅｄ、つまり辞書が一杯になったら古いものから消していくことの意です。
例えば次のようなテキストを圧縮するとします。
THE_CAT_AT_THE_CAR_ATE_THE_RAT
すると結果は次のようになります。
Matched 85: T
Matched 73: H
Inserted 257: TH
Matched 70: E
Inserted 258: HE
Matched 96: _
Inserted 259: E_
Matched 68: C
Inserted 260: _C
Matched 66: A
Inserted 261: CA
Matched 85: T
Inserted 262: AT
Matched 96: _
Inserted 263: T_
Matched 262: AT
Inserted 264: _AT
Matched 96: _
Inserted 265: AT_
Matched 257: TH
....
一致した辞書要素の番号を出力します。したがって、圧縮されたファイルは
85 73 70 96 68 66 85 96 262 96 257 ...
のようになります。ちなみに、前回アップしたＳＱＵＥＥＺＥ．ＣはＡＰ−ＬＲＵ
法、すなわちａｌｌ−ｐｒｅｆｉｘ ｈｅｕｒｉｓｔｉｃを使っています。これは
前回の一致がＴＨＥ＿で今回の一致がＣＡＴなら辞書には
ＴＨＥ＿Ｃ ＴＨＥ＿ＣＡ ＴＨＥ＿ＣＡＴ
の３つを登録するというものです。ちなみにＩＤ＿ＬＲＵ法ではＴＨＥ＿ＣＡＴし
か登録しません。
Ｓｔｏｒｅｒによれば、ＡＰ法のほうが速く辞書を膨らませるが、ＩＤ法のほう
が辞書をけちって使うので長いファイルでは有効だということです。
もちろんこのＭＷＳ法のプログラムは概念を説明するためだけのもので、実際に
はｔｒｉｅにハッシュ法を使って高速化するものと思います。
圧縮比を改選するには、辞書の小さいうちは少ないビット数を送るとか、ハフマ
ン法と組み合わせるとか、あるいは辞書のすべての要素を葉としてｓｐｌａｙ木を
作ってそれでさらに圧縮するとか、いろいろ考えられそうです。ただし最初のもの
を除いてこれらのアイデアはあまり有効とは考えられませんが。
三木さんの LDIFF は， 三木さんがなかなかソースを見せてくれないという不満もあり， 自分でコーディングしてみることにしました。
#1349/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/19 6:20 ( 37) 簡略版バイナリ差分ＢＤＩＦＦ／奥村 ★内容 三木さんのＬＤＩＦＦのマネですが、遅いことは天下一品です。たった今完成し たばかりで、バグがある可能性があります。メモリもこんなに使う必要はありませ ん。そのうちちゃんとした版をアップします（期待しないでください）。 ……略……
いくつかのバージョンをアップロードした末，名前を bd にしてしまいました。
#1352/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/19 19:59 ( 47) 差分圧縮ちゃんと直しました／奥村 ★内容 まともに書き直しました。すみません。混乱しないように名前はｂｄとしました。 ところで、どういうわけか前回の急遽取り下げたものは三木さんのｌｄｉｆｆと同 等の圧縮比にしかなりませんが、これならそれよりさらに縮みます。どういうわけ でしょうか。まさか三木さんが偶然私と同じヘマをしているとは思えませんので別 の原因でしょうが。どういうヘマかというと、コピーの後はリテラル、リテラルの 後はコピーと仮定してしまったのです。そんなことちっともないんですが、油断を するととんでもない間違いをしがちです。ただし、リテラルの後はコピーというの はこのプログラムについては正しいので、その部分だけ生かして、つまり最初にア ップしたものと２回目の取り下げ版とを足して２で割ったようなものがこれです。 三木さんのプログラム読まれた方は解説して下さい。昔はこれでもＺ８０の機械 語をハンドアセンブルした世代なのですが今はアセンブラ見ると頭痛くなる。
PKZIP 1.0 は Shannon-Fano 法を使っているようです。
#1374/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/27 6: 0 ( 3) シャノン・ファノが……／奥村 ★内容 木を格納するのに便利だというわけではなさそうです。じつをいうとなぜハフマン でなくシャノン・ファノにしたかは今もって謎です。ご本人（ＰＫ）もあまり違いが よくわかってないんじゃないかと思います。
バイナリ diff のほうもだんだん進んできます。
#1375/1982 計算機と算法
★タイトル (SCIENCE ) 89/ 7/27 17:40 ( 51)
新バイナリｄｉｆｆ／奥村
★内容
【アルゴリズムの概略】
新ファイルの各文字から始まる文字列について、旧ファイル（６４Ｋ未満）と比
較し、５文字以上の一致が見つかったなら、その長さ・位置を出力する。見つから
なかったなら、５文字以上の一致が見つかるまで次々に文字列を比較し、５文字以
上の一致が見つかった時点で、一致しなかった文字の個数と文字列そのものを出力
してから、一致の長さ、位置を出力する。出力はバイト単位で、圧縮はしていない
ため、ＬＨＡＲＣでさらに圧縮できる。評価版のため、速度は考慮していない。実
際には木を使うためずっと速くなる。６４Ｋ未満用。
【アルゴリズムの詳細】
以下のソースコードを見て下さい。
【性能比較】
BD2.EXE (22091 bytes) - BD1.EXE (21661 bytes)
LDIFF: 5810 bytes BD: 4623 bytes
ＥＸＥファイルではＢＤの方がかなり小さくなる。
LHarc の偽物 ICE というのが米国で出回ります。 それと同時に PAK というシェアウェアも出現します。
#1391/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/30 6:33 ( 10) ＣｏｍｐｕＳｅｒｖｅより／奥村 ★内容 ＬＨＡＲＣより「ｆａｓｔｅｒ ａｎｄ ｂｅｔｔｅｒ」をうたい文句にＰＡＫ ２．０が出た。確かに速いが圧縮比はほとんど変わらない。ＳＦＸは８．５Ｋ。こ れは＄１５のシェアウェア。フルスクリーン版ＰＡＫＦは＄３０。圧縮ルーチンの ライブラリのようなものも売り出す。 ＩＣＥというのはＬＨＡＲＣと同サイズで単にバイナリをエディットした悪質な もの。説明書きに「ＬＨＡＲＣから改名しました」などとも。しかしこの名前はな かなかしゃれているとの評判。 追伸：これを書いてここにきたらもうＰＡＫが……。大久保先生どうもありが とうございます。
新 LZ + Huffman は吉崎氏と競争でコーディングします。
#1393/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/30 15: 7 ( 93) 奥村版静的ハフマン＋ＬＺ ★内容 やっとバグが取れたようなのでとりあえず送ります。これから吉崎さんのを勉強 させていただきます。アルゴリズムは、できるだけ大きいバッファをメモリ上に確 保しておき、１パス目はメモリに書き出します。なるべく速くするためにメモリの アクセスがなるべくバイト単位になるようにします。バッファがいっぱいになった らそれをスタティックハフマンで圧縮して出します。表はあまり効率的でなく、使 った文字の種類×１０（ないし１１）ビット程度だと思います（あまりよく考えて いない）。２回目にバッファを使うときからは、以前送りだした表を流用した方が 新たに表を送るより効率的な場合は、以前の表で流用するようにしました。圧縮比 の方は、ダイナミックハフマンの方が良い場合と悪い場合があります。木の大きさ が文字種類にほぼ比例するため、長い一致はまとめて数えています。どちらの方が 良いかは一概にはいえないようです。木の送り方も含めて検討の要があるかもしれ ません。 解凍の速さはやはりスタティックハフマンならではです。まだ木をいちいち下り ながら解凍していますが、表を引くようにすればもっともっと速くなりそうです。
同じアイデアで出発しているのですが， ちょっとしたコーディングで違いが出ています。
#1394/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/30 16: 2 ( 11) 実験結果 ★内容 吉崎版 奥村版１ 奥村版２ 完成品（．ＥＸＥ）の大きさ ２１９２４ １９７２６ １９７２６ パソコン通信ログ３９０２３→２２５９５ ２２５６９ ２２５８３ Ｃソースコード １２８５３→ ４４７２ ４４５８ ４４６４ コマンド．コム ２４１６１→１５３７８ １５３６１ １５３６４ ＦＣ．ＥＸＥ １４５３０→ ９２９２ ９２７４ ９２７８ ＊奥村版１は１６文字以上の一致はまとめて数える方式 ＊奥村版の最大一致長はＦ＝２５６ ＊ＴＣ２．０（ＩＢＭＰＣ版ラージモデル）でコンパイル ＊圧縮後の大きさは表示値でなく実測値（吉崎版では４バイト異なる） 吉崎版の中身をまだよく見ていないので、この差が何に起因するか定かでありません。
#1396/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 7/30 19:24 ( 70) 圧縮の算法 ★内容 吉崎さんの算譜でも勉強しようと思いましたが、やはり別の人の書いた算譜を読 むのは一苦労です。 中座していたアルゴリズム事典の第２版にでもとりかかろうかとも思ったのです が、何日か前の自分は他人であるとのことばもあるように、何日かたてば自分の書 いた算譜を理解するのに苦しむ羽目になるかもしれないので、算法をまとめておく ことにしました。 まず、圧縮すべきファイルはリングバッファに読み込んで、現在の位置より４０ ９６文字前から１文字前で始まる４０９５種類の文字列と比較し、現在の位置で始 まる文字列と最も長く一致する部分を見つけます。３バイト以上の一致が見つから なかったならば、現在位置の文字をｃとして、ＥｎｃｏｄｅＣｈｕｎｋ（ｃ，０） と唱えます。ｐ＋１文字前で始まるｃ＋３バイトと一致するならＥｎｃｏｄｅＣｈ ｕｎｋ（２５６＋ｃ，ｐ）と唱えます（ｃ≧０、ｐ≧０）。すると、Ｅｎｃｏｄｅ Ｃｈｕｎｋ関数が後を引き受けてくれます。 ＥｎｃｏｄｅＣｈｕｎｋ（ｃ，ｐ）という関数は、自分が呼び出された回数とｃ の度数分布を数えると同時に、（ｃ，ｐ）の組を、できるだけ詰めて（しかもでき るだけバイト単位になるようにして）内部のバッファ（６４Ｋほどの大きさ）に貯 め込みます。 バッファがいっぱいになると、度数分布をもとにして、ハフマン木を作ります。 そして、いよいよ本当の出力が始まります。 まず、呼び出された回数（これをブロック長と呼びます）を１６ビットで書き出 します。次に、１ビットで、ハフマン木を送出するか否かを書き出します。このビ ットが「１」なら、次にはハフマン木があります。「０」なら、ありません。ハフ マン木がない場合は、前回に受け取ったハフマン木を継続使用することになります。 ですから、初回はハフマン木があるのが普通ですが、もし全くなければ、こちらで 定めた最も平均的なハフマン木を使うことになるでしょう（この辺はまだ考えてい ません。英語については文字の出現確率の統計がいろんな本に載っています）。 木をどういう形式で出力するかは後で述べます。 さて、木のあとは、バッファの中身の（ｃ，ｐ）ペアの一つ一つについて、ｃの 部分は上に述べた木を使ってハフマン圧縮し、ｐの部分は適当な可変長プリフィッ クスコードで圧縮し、どんどん送り出します。（ｃ，ｐ）ペアの個数はすでに「ブ ロック長」として送りだしてあるので、受け手はブロックの終わりを知ることがで きます。 このようなブロックの連続が圧縮ファイルの中身です。 ブロック長が０になっていたら、そこで圧縮ファイルが終わります。 さて、木の送り出し方ですが、最初に木を構成するときに、左の子が非葉で右の 子が葉となる節があれば、左右を取り替えておきます。すると、任意の節から下を 見ると、左右とも葉、左右とも非葉、左が葉で右が非葉の３通りに分類されます。 この最後の場合が最も多いので、このような節は１ビット「０」で表します。左右 とも葉の節は２ビット「１０」、左右とも非葉の節は２ビット「１１」で表します。 このようにすると、根も含めた非葉はすべて１〜２ビットで表せます。葉そのもの は（ｃ，ｐ）ペアのｃを表すわけですが、このｃの可能な値の数がふつうは５１２ 通り以下ですので、９ビットで送り出せます。根も含めた非葉節の数は葉の数より １個少ないので、木全体は文字の種類×（１０ないし１１）ビットで表せます。た いへん複雑なように聞こえますが、実際は手続きＷｒｉｔｅＴｒｅｅ（）の再帰的 呼出しによりとても小さくきれいな算譜になります。葉を受け取る関数ＲｅａｄＴ ｒｅｅ（）も同様に再帰的な美しい関数です。 ハフマン木の構成法自体はここで述べる余裕がありませんが、ソーティングは使 わず、優先待ち行列（ｐｒｉｏｒｉｔｙ ｑｕｅｕｅ）というものをヒープ（メモ リ領域のことではなくヒープソートのヒープ）で実現したものを使いました。最も 頻度の小さい２つの節を取り出しては新しい節を登録するというハフマン木の構成 法にとてもマッチした算法だと思います。 さて、文字の種類×（１０ないし１１）ビットはまだ大きすぎるでしょうか。英 語のようにスペースからｚまで限られた文字しか使わない場合にはこれでもけっこ う小さくなります。また、ファイルが小さいなら、文字種類はファイルの大きさを 超えられませんので、表自体もファイルに見合って小さくなります。 符号語のビット数の上限をたとえば１６に制限したならば、４ビット×（文字種 類の上限）で表を表すことも可能です。ＰＫはさらに同じビット数の符号が何文字 も続くことが多いのに注目して、４ビットで繰返しの数を表しているようです。し かし、アスキーコード順に並べた場合に符号語のビット数が同じものが連続してい くつも現れるというのもむしろ不思議なことで、繰返しの数はむしろ４ビットに固 定せず可変長コードにするのが自然でしょうか。このあたりはもっと実験が必要で しょう。あまり工夫すると泥臭くなり、自己解凍ファイルの大きさも増えるでしょ うね。 私の算譜はやっとバグがとれたてのもので、速さはもっともっと速くなるものと 思います。 以下はオンライン。ＲＯＭ男さん、どうも。いまちょっと読んだかぎりではあま りピンとこなかったので、オフラインでじっくり考えてみます。よかったらもっと 具体的に教えてください。
CompuServe でも新 LHA への期待が高まっています。
#1400/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 8/ 1 6:26 ( 5) ＣｏｍｐｕＳｅｒｖｅより／奥村 ★内容 たくさんの意見の要約： ＩＣＥはおもしろい名前だが、実際はＬＨＩＣＥとして登録されている。これを 読むとｌｉｃｅつまりシラミに聞こえる。ＬＨＡＲＣは絶対ＬＨＩＣＥと改名しな い方がよい。ＬＨという意見が有力で、ＬＺＨというのもあった。拡張子は混乱を 防ぐため「．ＬＺＨ」のままがよいということ。
8月4日には，符号長を16ビットに制限した Huffman 符号化ルーチンが完成します。
8月5日には，PK に倣って lazy evaluation を実装します。
#1405/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 8/ 5 9: 5 ( 55) 圧縮＞スライド辞書部改良版／奥村 ★内容 ＰＫに倣って１文字先読みにより圧縮比を改善したものです。またまたすごくな りました。時間は（腹時計ですが）変わらないみたいです。残る仕事はいろんなパ ラメータの調整です。例えば清適は不満の文字数Ｎ１が今は２７０になっていたと 思いますがあのへんはいじれますし、最大一致長が今は２５６になっていましたが もっと長くしても時間はあまり変わらないでしょうから長くしてみるとか、ファイ ルによってはリングバッファを８Ｋにしてみるとか、２パスハフマンの１パス目を いれておくバッファを残メモリに応じて大きくするような工夫をするとか、１バッ ファ分終わったら次に必ず木を再計算するかそれとも最初に作った木を繰り返し用 いるかそれとも木を作ってみてからどちらが徳か考えてみるようにするとか、いろ いろ変形が考えられます。これで数キロバイト未満のファイルならダイナミックハ フマン、それ以上（あるいは解凍時間を短縮するスイッチを指定する）なら静的ハ フマンというように使い分け、あとは吉崎さんが最適なアセンブリコードを書いて くださったなら、ＰＫＺＩＰなどには負けません。なお、私のコードはろくにテス トしていないのでバグがいたり無駄な部分がある可能性が大きいのでどなたか読み 直してチェックしてください。米国のユーザも新ＬＨに期待しています。
#1415/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 8/ 7 6:39 ( 3) ついでにＮＩＦでは……／奥村 ★内容 吉崎さんが広範囲のファイル（何百？）にわたってＬＨＡＲＣ，静的ハフマン、 だいなみっくはふまんについて比較してくださいました。やはり表の分だけ静的 ハフマンの方が大きくなる傾向のようです。残念。
われわれの bdiff と同じものを別の人が作っておられたことがわかりました。 これが現在流布している bdiff，bupdate です。
#1417/1982 計算機と算法 ★タイトル (EUF07245) 89/ 8/ 7 19:27 ( 3) ＢＤＩＦＦ＞今ＰＩＧに行ってびっくり／奥村 ★内容 ＰＳＨさんがわれわれと同じ構想のその名もＢＤＩＦＦというのを作られている ではありませんか。同じような発明が同時に複数起こるとはよくあることですが、 おもしろいと思いました。
#1419/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 8/ 8 2:13 ( 14) ＰＫＺＩＰ１．０、ＢＤＩＦＦ／奥村 ★内容 ＰＫＺＩＰ１．０は２０Ｋまでのコメント（テロップ？）が可能で、たとえば ＰＫＺＩＰ −ｚ ｚｉｐｆｉｌｅ ＜ＨＩ．ＴＸＴ とすれば ＨＩ．ＴＸＴ がコメントになるという。また、キーボードの配置を変えるような悪質ＡＮＳＩ コメントはフィルタできるとのこと。 話は変わるがＰＳＨさんのＢＤＩＦＦは８バイトかなんか単位でファイルを比 較し、それが何％か一致していれば同期がとれていると見るというものらしい。 そのためＬＤＩＦＦより速い。出力コードには０が多くＬＨａｒｃにはかかりや すいとのこと。テキストファイルはあまり小さくならないのでバイナリ用にチュ ーンしてあるようだ。ＬＤＩＦＦの方が圧縮比はずっと良いようだ。 なお、ＰＳＨさん自身はＬＤＩＦＦを知っているはずとのこと。だから偶然同 じアイデアが浮かんだということでもないらしい。 ＢＤＩＦＦはＭＩＸのＶ．Ｃ．でバージョンアップをしており、Ｖ．Ｃ．では ＶＺの９８版→Ｊ３１００版の差分をＢＤＩＦＦで発表しているとのこと。 どうやら差分圧縮は２つのスタンダードができてしまったようですね。
#1429/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 8/19 6:15 ( 9) ＰＫＺＩＰのリリース／奥村 ★内容 １．０版は８月２１日から始まる週にはｒｅｇｉｓｔｅｒｅｄ ｕｓｅｒｓに 送り始められるであろうとのこと。これはＰｈｉｌ自身のメッセージ。しかしこの １日前にＰＫ社に電話した人は社員から「９月１日前は無理」と聞いたという話も あり、まだあまりはっきりしない。 ＬＨ（ａｒｃ）とどっちが先に出るか関心の的になっている。 ＮＩＦＴＹでは吉崎さんがいま新ＬＨをアセンブラで書いている途中とのことで す。まだ何も現れません。ＰＫＺＩＰとどちらが早いか。 アルゴリズムの提案はもうありませんか。
#1440/1982 計算機と算法 ★タイトル (SCIENCE ) 89/ 8/26 6:11 ( 17) ＰＫＺＩＰ１．０１出来／奥村 ★内容 Ｃｏｍｐｕｓｅｒｖｅはこのニュースでにぎわっていました。ＯＳ／２版も出た ようです。 ある人は１００ほどあるＬＺＨファイルをＺＩＰに変換したがほとんどのものは かえって大きくなった（数百バイトほど）と言っています。 別の人は４ＭＢほどのＬＺＨをＺＩＰに変換したがＬＺＨよりかなり小さくなり、 特に速さはすばらしいとのこと。 ４９３Ｋの画像ファイルをＺＩＰで圧縮した人によれば、２分３５秒かかって ７８ＫにしかならなかったがＬＨＡＲＣでは１分２０秒で７６Ｋになるとのこと。 ＰＫ社の人によればＰＫＺＩＰはＬＨＡＲＣよりずっと長い最大一致長なのでファ イルによっては非常に時間がかかる。 ＰＫＺＩＰの配布版自体はＰＫＺＩＰで圧縮した場合より小さくなっているが、 これはＰＫＺＩＰ自体は１パスだが別に２パスのオプティマイザを開発しており、 それを使ったとのこと。これで圧縮比が１−３％改善される。ＰＫＺＩＰの次の版 は２パスになるかもしれない。 追伸：もう日本にも上陸しているらしいです。早いですね。さっそくどこかで 見つけてこよう。
新 LHA の実験は遅々として進みません。
この年（1989年）の10月6日には，Stac 社の Whiting 特許（米国特許 5,003,307）が出願されています（特許成立は1991年3月26日）。
リンクはご自由にどうぞ。
松阪大学 奥村晴彦 okumura@matsusaka-u.ac.jp
Last modified: Mon Feb 8 10:06:03 1999