1990年

#1792/1982　計算機と算法
★タイトル (SCIENCE )  90/ 1/29   5:55  ( 73)
デバッグお願い＞新スライド辞書圧縮／奥村
★内容
　やっと乗ってきました。最初からスライド辞書部を書き直してみました。考えや
すくするために能率を犠牲にしてインサートノードからｇｏｔｏを追い出したり処
理をサブルーチン化したりしましたのでその分遅くなっていますが、ｐｅｒｃｏｌ
ａｔｉｎｇ　ｕｐｄａｔｅは吉崎版よりずっと簡単になったので、実質的には若干
速くなったのではないかと思います。吉崎さんが指摘されたような同じ文字にとき
どき別の文字が入っている病理的なファイルでも試してみましたが良好なようです。
バグがないかチェックしてくださいませんか。
……略……

#1973/2051　計算機と算法
★タイトル (SCIENCE )  90/ 4/ 3  17:16  (162)
画像圧縮＞これまでのまとめ／奥村
★内容
　まず目的ですが、ＣＡＩ教材やゲームソフトの画面を十分高速に画面に表示する
ことです。簡単にベクトルデータとして表せるものはなるべくそのようにし、スキ
ャナから取り込んだ画像をおもに対象とします（写真、イラストなど）。考えます。
圧縮比が良くてもあまり復号の遅いものは駄目です。圧縮時間はかかってもかまい
ません（といっても限度がありますが）。とりあえずＰＣ−９８０１用を考えます。
　産物は、なるべくＡＮＳＩ規格に従ったＣ、またはＴｕｒｂｏ　Ｐａｓｃａｌの
ソースコードの形とし、誰でも自分の目的に合うように改変して自分のプログラム
に組み込めるようにしたいのです。
　ＰＣ−９８０１では、グラフィックプレーンは古いＶＭ２（私の使っているもの）
までは３枚、それ以後は４枚あり、それぞれ８色、１６色の表示が可能です。
　各プレーンのグラフィックＲＡＭの１バイトは横に並んだ８ドットを表します。
最初の１バイトは左上の８ドット、次の１バイトはその右の８ドット、……という
具合になっています。８０バイトで６４０ドット、つまり横の線１本分になります。
横の線は４００本ありますから、１プレーンは３２０００バイトになります。
　画像の情報をどのような形で見ていくかですが、点ごとに色コードを見ていく方
法と、色プレーンごとにあたかも単色のように考えて処理するかの、２通りが考え
られます。ここではプレーンの数を気にしなくてもいい後者の方法を考えることに
します。
　また、点ごとに見ていくか、１バイト分（横８個の点）をまとめて扱うかの、２
通りの方法があります。ここでは、なるべく高速に処理したいので、１バイト分を
まとめて扱うことにします。ただし、ビットごとの処理を十分高速にできるならば、
点ごとに見ていく方が圧縮比が良くなるかもしれません。このあたりはこれからの
課題です。
　バイトごとの処理の場合は、次のバイトは画面上では８ドット離れた領域を表し
ますが、８０バイト目は画面上ではすぐ下の領域を表します。したがって、圧縮の
ためには、ビデオＲＡＭ上のバイトの順序を無視して、上下に見ていった方が圧縮
比が良くなると思われます。たとえば左上隅から始めて下へ下へと行き、左下隅ま
で行ったら右に１つ進み、また上に上がるというふうにジグザグに見ていくのがよ
いのではないかと思います。
　このようなバイトの並びをどうしたら圧縮できるかですが、画像の特質として、
第１段階の圧縮としては連長圧縮が向いているようです。つまり、同じバイトがい
くつ連続して続くかを調べ、それを数で表すのです。
　連長圧縮の原理を簡単に説明するために、画像でなくふつうのテキストを考えま
しょう。たとえばＡＡＡＡＢＢＣというテキストを４Ａ２Ｂ１Ｃ（またはＡ４Ｂ２
Ｃ１）と表すのが連長圧縮です。ただしこれではＡＢＡＢは１Ａ１Ｂ１Ａ１Ｂとな
ってかえって長くなってしまいます。１個の場合は「１」を省略すればいいではな
いかと思われるかもしれませんが、数の１と文字コードの１は区別できないので、
そう簡単ではないのです。ただし余分に１ビットを使って数と文字を区別するとい
う手もあります。しかし１ビットという半端なものを混在させるとせっかくバイト
ごとになっている文字情報がバイトの境界をまたぐことになってしまいます。また、
性質の違う情報（文字・数）が混在すると、結果をさらに圧縮しようというときに、
圧縮しにくくなります。これを防ぐため、文字か数かを表すビットは別領域に置く
のが望ましいと考えられます。
　もっと簡単に数（連長）と文字とを区別する方法があります。エスケープ文字を
使う方法です。
　まずテキストを一通り調べて、なるべくあまり使われていない文字を１つ選び、
それをエスケープ文字と名づけます。たとえば￥という文字が少ないなら、￥をエ
スケープ文字とします。そして、数（連長）を表すには￥３とか￥５のように前に
エスケープ文字を冠します。エスケープ文字自体は￥０のように表します。この方
法ではＡＡＡＡＢＢＣは￥４ＡＢＢＣと表します（ＢＢは￥２Ｂとするとかえって
長くなるのでＢＢのままにします）。４連以上しか縮まないので、連の長さは３を
引いた値にすることができます（０は￥０に使いますからのけておきます）。この
方法では長さ２５８の連まで３バイトで表せます。また、たとえば￥２５５のとき
は次の２バイトで連長を表すようにすれば、たとえば全く使われていないプレーン
でも５バイトで表せます。実際には、どの文字をエスケープ文字にしたかを出力し
なければならないので、各プレーンあたり最小６バイト必要です。
　この方法は、比較的長い連が多い場合に効力を発揮しますが、３バイト以下の連
ばかりの場合は全く縮みません（しかし元より大きくはなりません）。
　また、タイルパターンのように、交互に別の文字が出てくる場合（テキストの例
でいえばＡＢＡＢＡＢのようなパターン）も、縮みません。
　ＡＢＡＢＡＢを縮めるためには次のような工夫も可能です。
　各バイトの文字コードを　ａ，ｂ，ｃ，……　とします。連長圧縮をかける前処
理として、これを　ａ，（ａ　ｘｏｒ　ｂ），（ｂ　ｘｏｒ　ｃ），……　のよう
に直します。これだと、ａ＝ｂ＝ｃの場合には　ａ，０，０，……　となり、交互
に　ａ，ｂ，ａ，ｂ，……　と並ぶ場合には　ａ，（ａ　ｘｏｒ　ｂ），
（ａ　ｘｏｒ　ｂ），……　となり、いずれにしても、最初の１文字を除いて同じ
値になってしまいます。元に戻すには、ａ　ｘｏｒ　（ａ　ｘｏｒ　ｂ）　＝　ｂ
を使えばよいのです
　しかし、この方法にも欠点はあります。それは、連長が１つ短くなってしまうこ
とです。このため、比較的短い連が多い場合には、圧縮比が悪くなります。それに、
ＡＢＣＡＢＣＡＢＣというパターンはうまくいきません。むしろ、このような同じ
パターンの連続は、圧縮を２段階にして、２段目の圧縮で処理するのが良いかもし
れません（後述）。
　３バイト以下の短い連が多い場合には、上述の方法では縮まないので、別の方法
を考えなければなりません。
　一つの方法は、連長を表すためのビット数を可変にすることです。
　たとえば
　　１　……　０　　　　（１ビット）
　　２　……　１０　　　（２ビット）
　　３　……　１１０　　（３ビット）
　　４　……　１１１０　（４ビット）
というような数の表し方ができます。この場合にも、せっかくバイトの境界が揃っ
ているデータを崩したくないので、連長は別領域に格納するのがよいでしょう。た
とえばＡＡＡＡＢＢＣなら
　　連長情報　１１１０１００
　　文字情報　ＡＢＣ
となります。
　なお、この方法は、文字の変わり目をビット１で表す方法とじつは同値です。こ
の後者の方法では
　　連長情報　１０００１０１
　　文字情報　ＡＢＣ
となりますが、意味は同じことです。
　連長を表すビット数を可変にする方法はいろいろあります。たとえば
　　１　……　０　　　　（１ビット）
　　２　……　１０　　　（２ビット）
　　３　……　１１０　　（３ビット）
　　４　……　１１１００　（５ビット）
　　５　……　１１１０１　（５ビット）
　　６　……　１１１１０　（５ビット）
　　７　……　１１１１１００　（７ビット）
　　８　……　１１１１１０１　（７ビット）
　　９　……　１１１１１１０　（７ビット）
　１０　……　１１１１１１１００　（９ビット）
とすれば、４を表すときはさきほどより１ビット長くなりますが、他の場合はすべ
て、さきほどと同じか、より短くなります。連長４が比較的多い場合にはこの方法
は向きませんが、そうでない場合にはこの方が短くなります。
　その他にも、可変長符号は無数に考えられます。
　どのような可変長符号が最適かは、その画像の連長の分布によります。最初に連
長の分布を調べて、その分布にとって最適な（最もよく縮まる）符号を作るアルゴ
リズムを何十年も前にハフマンという人が考えました。彼のアルゴリズムで作った
符号をハフマン符号といいます。しかしここではハフマン符号化まで考えないこと
にします。
　さて、これで第１段階の圧縮ができました。連長部分と文字（画素）部分とは別
に格納してあるとします。連長部分は、もしハフマン符号を用いたならそれ以上は
縮まないでしょうし、そうでなくても、うまく考えた可変長符号なら、ほぼ最適に
なっているでしょうから、これ以上縮めることは考えないことにします。
　文字（画素）情報の部分は、もっと縮むはずです。
　まず、文字の分布のことを考えましょう。２５６通りの文字のうち、頻繁に使わ
れるものもあれば、そうでないものもあるでしょう。これらをどれも８ビットで表
すのはもったいないことです。頻繁に現れるものほど少ないビット数で表す方が縮
まります。そこで、ここでも最適な可変長符号を見つけるハフマンの方法が使えそ
うです。しかし、本稿ではそこまで考えないことにします。
　ハフマン法のように分布に基づく方法以外によく使われる圧縮法としては、ＵＮ
ＩＸのｃｏｍｐｒｅｓｓコマンドで使われるＬＺＷ法（ＡＲＣやＰＫＡＲＣもこれ
にならっています）、ＬＡｒｃのＬＺＳＳ法があります（ＬＨａｒｃはＬＺＳＳ法
と動的ハフマン法を組み合わせています）。このうち、ここではＬＺＳＳ法を解説
しましょう。
　たとえばＡＢＣＡＢＣＡＢＣというテキストがあったとします。このとき、最初
の３文字はそのまま出力します。次の６文字は、左に３つ戻ったところから始まる
６文字と全く同じですので、（３つ戻る、６文字）という情報を書き出すだけで十
分です。つまり、ＡＢＣ（３，６）と符号化できます。この（位置、長さ）のペア
は、たとえば位置を８個前まで、長さを３２文字までに制限すれば、８ビットで表
せます（長さ０や１はありえないので、実際には長さ３４文字まで表せます）。８
個前とか３２文字とかいう数はでたらめに言っただけで、実験してみて最適の組み
合わせを選ぶべきです。ただ、テキスト圧縮と違って、画像の場合には同じパター
ンが出てくるのはタイリングパターンのような場合が多いと考えられますので、あ
まり遠くまで調べなくてもよいという感じがします。長さは長いほどいいのですが、
あわせて８ビットにした方が処理が速くなると思います。
　この方法では、各バイト文字そのものであるか（位置、長さ）ペアであるかを区
別するためにさらに１ビット必要です。この１ビットも別領域にしまっておくのが
よいでしょう。性質の違うデータは別にするのが、あとでＬＨａｒｃでさらに圧縮
するためにも、良いことだと思います。
　ちなみに、ＬＨａｒｃでは位置は約４千個前まで、長さは６０文字まで調べてい
るので、能率を上げるため、２分木というデータ構造を使っています（第２版では
さらに進んだデータ構造を取り入れます）。しかし８バイト前まで調べるだけなら
通常の文字列サーチでも十分でしょう。
　圧縮法は、これ以外にもいろいろ考えられ、また、圧縮ファイルのフォーマット
も、いろいろ工夫できると思います。ちなみに、画像ファイルの標準としては
    TIFF (tagged image file format)
というのがあるそうですが、詳しいことは知りません。
　画像ローダを作られるなら、ヘッダの構造をよく練ることが大切です。違うフォ
ーマットのファイルを読んでしまったときに、間違いであることをできるだけ確実
にチェックできるようにしなければなりません。そのためには、最初の数バイトに
は何らかの署名を入れておきます。ＬＨａｒｃの場合は -lh0- とか -lh1-
というような圧縮方法を表す文字列を最初の５バイトとしています。これはＬＡｒ
ｃ以来の伝統で、元を辿ればかの有名な Software Tools in Pascal の本にあるア
ーカイバが -h- というヘッダを使っています。
　圧縮法やヘッダの構造も進化するでしょうから、方法名は必ず入れるべきです。
逆にいえば、方法名さえヘッダに入れておけば、画像ローダを作る方は、とりあえ
ず適当な方法で作ってしまい、あとでゆっくり改良することができます。
　こういう具合に、いろいろ考えてみましたが、もう春休みは明日だけ。他に仕事
もあるので、プログラムを完成させる時間はなさそうです。

#1977/2051　計算機と算法
★タイトル (SCIENCE )  90/ 4/ 4   6:20  ( 18)
画像圧縮＞もう一つ思いつきました／奥村
★内容
　エスケープ文字法よりこの方がいいかもしれません。前回と同様に、画面の横に
並んだ８ビット分を文字１個と考えて、あたかもテキスト圧縮のように説明します。
　たとえば
　　　ＰＱＲＳＴＴＴＴＵＶ
なら、
　　　ＰＱＲＳＴＴＴＴＵＶ
　　　×××××○○○××　←　直前と同じかどうか調べて
　　　　　　　５　　３　２　←　その個数を数える
として、
　　　文字部分　ＰＱＲＳＴＵＶ
　　　連長部分　５、３、２
とします。エスケープ文字法と同様に、長さ３以下の連はこの方法では縮みません。
しかし、エスケープ文字が不要であり、文字部分と連長部分を分けられるので、第
２段階の圧縮をする場合にも好都合です。さらに、連長部分を可変長符号で表す場
合にもこの方が好都合です。

　追伸：ＲＯＭ男さん般若さんどうも。デコーダは上の方法でもし今日中にできれ
ば作ります。そんなに縮まるならどこかバグっているのかもしれません。

このころ，「計算機と算法」ボードの #2050 で，いよいよ SHIMA さん（大島先生）の dviout，dviprt が登場します。

さて，いよいよ私家版圧縮アーカイバ ar の登場です （当時は UNIX に ar という標準コマンドがあることを知りませんでした）。 ヘッダの2000年対応も完璧です。 

#2053/3340　計算機と算法
★タイトル (SCIENCE )  90/ 4/23   6: 3  ( 16)
新圧縮アーカイバ／奥村
★内容
　また改良版を作ってみました。
　圧縮アルゴリズムは、符号語を１６ビットに制限するところだけ違います。この
アルゴリズムはＲＯＭ男さんの作られた正しいアルゴリズムではなく、ソースコー
ドをできるだけ小さくするような手抜きアルゴリズムです。手抜きといえば、四捨
五入アルゴリズムも村上さんが考えた正しいアルゴリズムではなく手抜きです。た
だしＬＨａｒｃより少し桁あふれに注意を払っています。
　ヘッダは、今回はＬＨａｒｃとの互換性を一切考慮せず、基本ヘッダはＡＮＳＩ
Ｃの枠内で得られる情報を過不足なく保存するにとどめ、ＯＳ依存情報はすべて拡
張ヘッダに譲りました。プログラム名は混乱を避けるためａｒに変更しました。
　ＡＮＳＩ　Ｃでは最後に修正した日時を得ることができないので、書庫に入れた
日時だけ基本ヘッダに収めます。この日時は、ＡＮＳＩではｌｏｃａｌ（ＤＳＴ情
報なし）、ｌｏｃａｌ（ＤＳＴである）、ｌｏｃａｌ（ＤＳＴでない）、ＵＴＣの
４種類が可能なので、２ビット分のフラグをつけました。ＤＯＳは１９８０年から、
ＵＮＩＸは１９７０年からの日時になっていますが、ＡＮＳＩでは１９００年から
可能になっているので、日時４バイトでは少なく、上記フラグも合わせて５バイト
にしました。これで５９００Ａ．Ｄ．頃まで使えます。

LHARC 改め LH 2.0 がまだ完成していないうちに偽物が現れ， 吉崎さんが激怒されます。 次のメッセージはダウンロードした際に行抜けが生じています。 

#2070/3340　計算機と算法
★タイトル (SCIENCE )  90/ 4/26   6: 3  ( 37)
ＬＨ２．０の偽物出回る／奥村
★内容
　ついにｐｃｓでＬＨ２．０の偽物が出たそうです。
　（念のためにつけ加えれば、ＬＨ２．０は吉崎さんのＬＨａｒｃの後継アーカイ
バで、まだ完成していません。）
　ＬＨａｒｃ１．１３ｃあたりのソースを参考に作ったものらしいということです。
吉崎さんは、もう完全なソースは公開しないとまで申されていますが、他機種への
移植も考えて、少なくともＣ版は公開していただきたいものです。
　バイナリエディットによる単純な偽物を防ぐためには、どこかに自分自身のＣＲ
Ｃを計算する部分をこっそり入れておくという手があると思います。ＰＫＺＩＰも
確かそれに類したことをしていたと思います。もっとも、どんなことしても、その
気さえあれば、外すのは簡単ですが。
　ウィルスについても、そろそろうちの９８とＰＣ／ＡＴコンパチ機も、予防策を
考えなければならないと思っています。もっとも、９８はまだハードディスクが買
えないので、毎回ＲＡＭディスクにＣＯＭＭＡＮＤ．ＣＯＭを転送して使っている
ので、大丈夫のはずですが、ＰＣコンパチ機が心配です。
　ＭＳ−ＤＯＳのジェネリックなウィルス対策ソフトはあるでしょうか。
　自分で作った方が速いかな。その方が耐性ウィルスもいないだろうし。もっとも、

ルのＣＲＣ計算をすることしか考えていませんが。自分で作れば、ＣＲＣ多項式を
自由に選べるので、耐性ウィルスの心配はないはずだと単純に考えていますが、も
っと巧妙なウィルスもあるのでしょうか。
　それから、またＬＨのことですが、吉崎さん、ファイルサイズとＣＲＣを発表し
ていただければ、偽物はすぐ見分けられます。ほんとはＣＲＣを合わせるのはたや
すいことなのですが、一般には難しいと思われているようなので……。３２ビット
のＣＲＣなら試行錯誤で合わせるには２の３２乗回も計算しなければならないので、
試行錯誤以外の手口を知らない人にとっては、難しいのでは？　複数のＣＲＣ多項
式を使えばさらにＣＲＣ合わせが難しくなるでしょう。本当はそれも（こちらの使
う多項式の組さえわかれば）簡単だったりするのですが……。そうだ、さらに難し
くするためには、ビット列を逆に走査して計算したＣＲＣも含めればいいのでは…
…？　これらのＣＲＣ破りの問題を数学的に考えられた方は、ボードではなく、メ
イルで、関係者だけにお知らせください！
　素因数分解を使う暗号ならもっと安全かな。
　ちなみに、ＣＲＣといっても、左送り、右送り、０で初期化するもの、０ｘＦＦ
ＦＦで初期化するもの、後者ではさらに結果を反転するものとしないものなど、い
ろいろあるようです。ＣＣＩＴＴでは０ｘＦＦＦＦで初期化することを推賞してお
り、ＩＳＨはそれに準拠しているようです。こうしないと、ある種の化け（頭にＮ
ＵＬがいくつも付く）に対して無力です。伝送の際にはこのような化けはけっこう
あるようなので。アーカイバの場合は大丈夫だと思います。

#2094/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/ 4  13:39  ( 46)
Adjusting CRC
★内容
  CRC合わせについて, ちょっとだけ書きます. \LaTeX\ の
記法を使います. あまり易しくは書きません.
  データを $d$ とすると, CRC-CCITTのチェックビットは
$dx^{16}$ を $x^{16}+x^{12}+x^5+1$ で割った余りです.
係数の計算はすべて mod 2 で行います. これがいま $r_1$
だったとすると,
  \[ dx^{16} \equiv r_1 \pmod{x^{16}+x^{12}+x^5+1} \]
となります. 最後から $k$ ビット遡ったところからの16ビ
ット $a$ でCRCを $r$ に合わせるには,
  \[ dx^{16}+ax^{k+16} \equiv r \]
とすればよいので,
  \[ ax^{k+16} \equiv r + dx^{16} \equiv r + r_1, \]
つまり
  \[ a \equiv x^{k+16}(r + r_1) \]
となります.
  \[ x^{16}+x^{12}+x^5+1 \equiv 0 \]
ですから
  \[ x(x^{15}+x^{11}+x^4) \equiv 1 \]
となり,
  \[ x^{-1} \equiv x^{15}+x^{11}+x^4 \]
です. この $k+16$ 乗を $r + r_1$ に掛ければ $a$ が
求められます. 工夫すれば$n$乗は $O(n)$ でなく
$O(\log n)$ のオーダで求められますから, ほんとにあ
っという間に合わせられるはずです. 2つ以上のCRCキー
を合わせるには Chinese Remainder Theorem を使います.

  以上は理論で, まだ何もやってみていません.

  吉崎さん, 実験をされたそうですが, ぜひ実験方法と
結果をお知らせください.

  ただし, あまり誰にでもできるCRC合わせのアルゴリズム
が発表されてしまうと, ウィルス作りの人が {\tt chkcom}
のようなプログラムを簡単に破れるようになりますので,
困るかもしれません. {\tt chkcom} などが改良されるまで
は, もしそういうプログラムを作られた方は, 内輪だけに
配った方が安全かもしれません. 私はまだ何も作っていま
せん.

  昔のザベでウィルスについての座談会があって, その中
で, チェックサムは簡単に合わせられてもCRCを合わせる
のはたくさんのバイトを調整しなければならないような間
違ったことを書いてありました.

  P.S. A minus sign is missing in the above article.
If you know where, you've understood the idea.

#2096/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/ 5   5:59  ( 10)
CRC多項式の選び方/奥村
★内容
  どんな基準で選べばいいのでしょうか. 16個のチェックビットの
パターンは65536通り. これをどのように振り分けるかによって選び
方が違ってくると思われます. CCITTのものなどは, 32767ビットまで
のファイルなら, どの1ビットまたはとなり合った2ビットが反転して
も, チェックビットのパターンが異なるように選んであります.
もし65535ビットまでのファイルでどの1ビットが反転してもチェック
ビットのパターンが異なるようにしたいなら, 別の多項式 (たくさん
ある) を使わなければなりません. ウイルスのような酷い誤りを見つ
けるだけならほとんどどんな多項式でもいいと思います (もっとも x
で割り切れては困りますが).

#2097/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/ 5  11: 2  ( 31)
CRCについてまたまた/奥村
★内容
  CRCは要するにデータのビット列を多項式と見て
ある多項式 (生成多項式) で割った余りをチェックビット
とするものでした. ただし係数の計算は mod 2 で行います.
数学の言葉でいえば, 0 と 1 だけの世界, ガロア体 (Galois
field) GF(2) の世界で係数を計算します. n次の多項式で
割った余りだけを考えるなら, 余りは n - 1 次の多項式です
から, 係数は n 個あり, それがおのおの 0 または 1 の値を
とる世界, GF(2^n) の世界の話になります.
  多項式の世界で素数に当たるもの (より次数の低い多項式
で割り切れないもの) を既約多項式 (irreducible polynomial)
といいます.
  さて, 1, x, x^2, x^3, ..., という列を生成多項式で割った
余りを考えましょう. ずうっと続けていくと, また元の 1 に
戻るはずです. その周期は, 16ビットのCRCなら, たかだか
65535です. 65536ではありえません. なぜならこの周期の中
に0は含まれ得ないからです.
  生成多項式が既約でなければ, 上の周期は65535に満ちません.
しかし, 既約であっても周期が65535になるとは限りません.
周期が65535になる生成多項式を原始多項式 (primitive
polynomial) といいます. 17次の原始多項式を数えたら2048個
ありました.
  ちなみに, 既約多項式の係数を左右逆に並べた多項式 (reciprocal)
はまた既約多項式です. 原始多項式を左右逆にしたものもまた
原始多項式です.
  CCITTやANSIの生成多項式は原始多項式ではありません. これら
はそもそも x + 1 で割り切れるので既約多項式ではありません.
これらは
  1, x, x^2, x^3, ..., x^{32766},
  x + 1, (x + 1)x, (x + 1)x^2, ..., (x + 1)x^{32766}
がすべて異なるCRC値をもつように選ばれているようです. 数えて
みたら, このようなものは1800個ありました.

#2098/3340　計算機と算法    *** ｺﾒﾝﾄ ***
★タイトル (SCIENCE )  90/ 5/ 5  13:37  ( 11)
CRC(続き)/奥村
★内容
  まず訂正. 1箇所16次というのが17次になっていました.
  ではどうしてこういう符号をcyclicというかというと,
じつは本当はCRCはcyclicではないんです. ただし, こう
いう GF(2) の16次の原始多項式を使えば, 65535ビット
をぐるりと巡回置換してもCRC値は代わりません, そうい
う特別な長さの場合だけcyclicなのです.
  なぜかといえば, 65535ビットをたとえば左回りに1ビッ
ト巡回することは, xを掛けて x^{65535} + 1 で割ること
にあたります. ところが, 周期が65535なのですから,
1 と x^{65535} とのCRC値は同じです. ですから
1 + x^{65535} は生成多項式で割り切れるというわけです.

次の書き込みはプログラムが lha 圧縮して ish 化して入っていましたが， ここでは復元しておきました。 タブは4桁にして読んでください。 

#2099/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/ 5  17:34  ( 34)
CRC(また続き)/奥村
★内容
  周期65535 (32767) の生成多項式を列挙するその場かぎ
りのプログラムです:

crctest.c

  いろいろなことをやっていますが, ほんとは d_min をちゃんと
見つけるプログラムを書きたいのですが, まだよくわかりません.
  ウイルス対抗策というだけでなく, ishの誤り訂正率を良くする
ことはできないかという問題意識もあります.
  ishでは内部形式になおしてから縦横斜めにチェックキーをつけ
ていますが, エラーはたぶん元の文字単位で起こるのでしょうから,
元の文字のままで縦・斜めチェックを入れられないか, 各行にCRCを
つけるならついでにそれで誤り訂正も少し (1ビット) くらいなら
できないかなどと考えています.
  CCITTやANSIの生成多項式が x + 1 で割りきれるのは, 32767ビ
ット以下のブロックごとに使うことを想定したためだと思います.
たとえばishが各行にCRCを使ったりXMODEMが128ビットごとにCRCを
使ったりするのは良いのですが, LHarcなどはまったくこの意図に
沿わない形でこれを使っているわけです. むしろ GF(2) の原始多
項式 (周期65535の最大周期列を生成する) を使うべきだったかも
しれません.

#2101/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/ 6  13:41  ( 24)
CRC(またまたまた)/奥村
★内容
  この前の続きです. 尻切れのままで申し訳ありませんでした.

  実際, CCITTやANSIのものではブロック長が32767を超えると d_min
が 2 になってしまいますが, 原始多項式なら65535まで d_min は 3
です. これは, d_min というのはそもそも許される符号語のうちで
1のビットの数の最小数であることから導けます (線形なので, すべ
て0という符号語からの距離だけ考えればいい). 65535ビットのうち
どれか一つだけが1であるような場合は, 最大周期列の定義からして
すべて異なるCRC値になるはずですが, そのような1を二つ重ね合わせ
てCRC値を0にはできないのですから, d_min = 2 ということはありま
せん. 二つ重ね合わせて1にはできるでしょうから d_min = 3 という
わけです. それでも, ブロック長が65535を超えると d_min = 2 にな
ってしまいます. つまり, 1ビットの誤りは見つかるけれども, 2ビッ
ト以上の誤りは帳消しになって見つからないかもしれません. d_min
= 3 なら2ビットの誤りまで確実に見つかります.
  32767ビットというのは4Kバイトで, それ以上のファイルに一つし
かCRCキーを付けないなら, 原始多項式に軍配が上がるはずです (だ
と思います. みんなCCITTやANSIを使っているので少々自信がありま
せんが).
  考えながら書いているので, 文章がおかしいかもしれません. ご
容赦ください.

  吉崎さんと私とでCRC合わせのプログラムを作っていますが, ウィ
ルスの発育を助長するのではないかと思って発表を見合わせています.

UFD さんから上の crctest.c が無限ループにならないかと質問がありました。 

#2103/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/ 8   5:57  ( 14)
UFDさんCRCTESTについて／奥村
★内容
    if (r & 1) r = (r >> 1) ^ poly;
    else       r >>= 1;
は, レジスタ r を左右逆に使っているのでちょっとわかり
にくいかと思いますが, 本来なら >> は << で, 多項式は
左に一つずらすということは x を掛けていることにあたり
ます. それで16ビットからはみだすビットが1なら poly と
xor をとっていますが, これがじつは生成多項式 poly を
法とする剰余計算をしているわけです. ふつうの CRC 計算
ルーチンと同じことです. つまり, x, x^2, x^3, ... と順
に x を掛けていって, poly で割った余りだけ残していく.
それは 0 を除いた 1..65535 を順にとるはずですから, 最
大周期は65535です. いつかは r == 1 に戻ってくるので,
無限ループにはならないのです. 戻ってくるまでの周期を
i で数えています.

UFD さんはすぐに拙作 crctest.c を改良してくださいました。

ＲＯＭ男さんが Brent の論文を FAX で送ってくださいました。 

#2111/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/11   6: 6  ( 54)
圧縮＞重要論文／奥村
★内容
　ＲＯＭ男さんから昨夜ＦＡＸで送っていただいたものです。まだ完全に理解して
いませんが、もしかしたら今やっているものよりこちらの方がいいかもしれません。
検討をお願いします。なお、Ｘ６８Ｋのｉｓｈでは新ｉｓｈフォーマットが復元で
きないようなので、旧ｉｓｈを使って送ります。

brent.txt

　それから、圧縮の本を一つ米国から取り寄せましたので、これもそのうちに紹介
します。ＣＡＣＭの新しい号にも何か圧縮関係で載っています。しかし、時間がな
い。今日は断れない飲み会。
　昨日は某出版社の人が来ていろいろ情報交換をしました。
　ＵＦＤさんのｃｒｃｔｅｓｔは、結局どこが違うのかわかりませんでした。同じ
ような感じですが。１がｓになっていましたが。
　１６元方程式で任意の１６ビットで合わせられるわけですね。なるほど。しかし
まあ実際には連続した１６ビットで十分でしょうが。

#2113/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/12   5:58  ( 26)
圧縮＞Ｂｒｅｎｔの算法など／奥村
★内容
　説明不足でしたが、このアルゴリズム、まだよく理解していないのですが、ちょ
っとＬＺＷみたいに見えるけれども、論文に書いてあることによれば、完全な最大
一致列を見つけることができるということです。もしそうなら、圧縮比はわれわれ
の方法と変わりません。
　もう一つ入手した本は、
    Timothy C. Bell, John G. Cleary, and Ian H. Witten,
    Text Compression (Prentice-Hall, 1990)
というものです。この前ここで紹介したＡＣＭ　ＣＳの論文と同じ著者で、内容も
ただあれをふえんしただけのもののようです。ＣＡＣＭに載った算術圧縮のＣ算譜
も収録してありますので、そちらの方を持っておられない方は、買う価値もあろう
かと思います。丸善に注文してもいいでしょうが、私は直接Ｐｒｅｎｔｉｃｅに手
紙を書いて送ってもらいました。代金はマスターカードの番号（とｅｘｐ．ｄａｔ
ｅとｓｉｇｎａｔｕｒｅ）を書いておけばそちらから引き落としてくれます。
　もう一つ、新しいＣＡＣＭの記事は、ハフマンなど接頭符号の復号法をいろいろ
書いてあるようですが、まだ良く読んでいません。

　蛇足：算譜＝プログラム、算法＝アルゴリズム、作譜＝プログラミング。これら
は計算機科学からなるべくカタカナを追放しようという人たちが提案する用語です。
　ＡＣＭ＝米国の計算機関連の学会。ＡＣＭ　ＣＳ＝ＡＣＭ　Ｃｏｍｐｕｔｉｎｇ
Ｓｕｒｖｅｙｓという雑誌。ＣＡＣＭ＝Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏｆ
ｔｈｅ　ＡＣＭという雑誌。

　追伸：ＲＯＭ男さん、．ｄｖｉどうも。まだ解凍してませんが、日本語が入って
いると私のＴｅＸでははじかれてしまうんでしょうね。アルゴリズムをこのような
形で書いてあるのをＴｅＸ化しようとするとけっこう面倒です。ＷＥＢのような
フィルタ（ＷＥＢでなかったかな）をかけると簡単にちゃんとなるのでしょうか。

#2116/3340　計算機と算法    *** ｺﾒﾝﾄ ***
★タイトル (SCIENCE )  90/ 5/12  19:24  (  2)
圧縮＞Ｂｒｅｎｔ／奥村
★内容
　吉崎さんに、あれでは最大一致文字列は見つからないのではないかと言われ、
考え込んでいるところです。

#2117/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/12  20:39  ( 34)
圧縮＞Ｂｒｅｎｔもう一度／奥村
★内容
もう一度, 問題の部分. 前回は無理に訳してしまったので,
ニュアンスがわからなくなってしまったかもしれません.
こんどは原文のまま書きます:

  if match then
    begin
    represent the matching entry in H by (k, m);
    { Save the best match found so far }
    k' ← k;  m' ← m;
    replace the representation of the matching entry in H by (j+1, m);
    if k + m ≦ n then
      enter s_k ... s_{k+m} in H (overwriting any matching entry);
    m ← m + 1
    end
  else
    enter s_{j+1} ... s_{k+m} in H

ここに載せてあるものは, まだ sliding dictionary になる前の,
バッファが無限に大きい場合の算法で, sliding dictionary にする
詳細は, 論文には書いてありません.

問題なのは, ある文字列が見つかったなら, enter s_k ... s_{k+m},
つまり, 一つ長いものを新たに登録する (もし同じものがあれば上書き
する, overwriting any matching entry) ようなのです. そして, 一致
長 m を増やして繰り返しています. ここのところに秘密があるのでは
ないでしょうか.

といっても, おおまかなことしか書いてないので, まだ算譜にできな
いでいます.

ちなみに, この論文では, WeinerやMcCreightの算法 (trieを
使ったもの) も文献を引用していますが, 同じ O(n) でもちょ
っと複雑であまり用いられていないのではないかと書いてあり
ました.

#2122/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/13  19:19  ( 31)
圧縮>Brentデモプログラム/奥村
★内容
  論文の算法をそのまま算譜にしてみました. したがって,
スライド辞書にはなっていません. また, ハッシュ表の衝突
は無視しました. たとえば brent aaaabaaacaaba とすると
a(0,3)b(3,3)c(6,4) と表示するだけのものです. コマンド
ラインの3番目に -d とするとデバッグ情報を出力します.

brent.c

#2130/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/15   2:28  ( 15)
ＲＯＭ男さんそのとおりでした／奥村
★内容
  私のはものすごく無駄をしていたようです.
\begin{verbatim}
    abcdefg0abcdef1abcde2abcd3abc4ab5abcdefg
\end{verbatim}
について考えていて, 論文でよくわからなかったところが納得できる
ようになりました. それは
\begin{quotation}
  In practice it is sufficient just to check that $h(K) = h(K')$,
  $\|K\| = \|K'\|$, and that the first few bytes of $K$ and $K'$ agree;
  the probability of a `false match' is small and we can check for it and
  backtrack if necessary before encoding $(j - k', m')$.
\end{quotation}
のところです. 途中の abcde などは長さとハッシュ値が合っていたら文字ごと
チェックは省略してどんどん長いものを探し, 最後にチェックして false match
だったら backtrack するということのようです.

#2133/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/16   6:10  ( 41)
吉崎さんのｂｒｅｎｔ／奥村
★内容
　さすがは吉崎さん、もうできたみたいです。私の ar の slide.c に置
き換えて使ってみてください。Garbage collection はまだしてないので
DICSIZ 分しか読み込みません。hash の計算部分だけをアセンブラにした
ら Trie とほぼ同等になったということです。

slide.c
……略……

#2138/3340　計算機と算法
★タイトル (SCIENCE )  90/ 5/17   5:54  ( 16)
吉崎さんのslide.c/奥村
★内容
  VzエディタをIBM PCに入れて遊んでいまして, まだあまり深く
考えていません. でも, 次の部分はバグではないでしょうか.

    for (i = DICSIZ * 2; i <= MAX_HASH_VAL; i++) next[i] = NIL;
                            ^

  吉崎さんの出された例

    F:\TC>brent abcdef0abcdef1abcdef2bcdef
    abcdef0(6,6)1(6,6)2(19,5)
                        ^^

考えてみましたが, 簡単に修復する方法は思いつきません.
われわれの方法では最近接一致位置を求めることが本質的
ですから, このままでは残念ながら brent は駄目のようです.
やはり trie しか道はないのでしょうか.

このころはもう「計算機と算法」ボードの話題は TeX が多くなっていました。 吉崎さんの LHA（当時は LH と呼ばれていた）は遅々として進まず， やっと1990年7月27日に NIFTY にオールC言語の試作版 LHx が出ます。 翌28日には「計算機と算法」に転載しました。 しかし実は吉崎さんの README には次のように書いてあります。 

　このバージョンは、NIFTY-Serve の flabo のみで公開します。転載はあまり
ましくないのですが、圧縮・復元アルゴリズムの検討や、他のＯＳへの移植のた
めに転載される場合にはかまいません。フリーソフトウェアを普及させるための
転載や、会員へのサービスを目的としての転載はお断りします。また、必ずソー
スを転載して下さい（実行ファイルのみの転載は認めません）。

Huffman 木の長さが16ビットを超えると高速な実装が面倒になるので， 長さを16ビットに制限するための部分を， 吉崎さんとＲＯＭ男さんと私とで競争で書きました。 

#2374/3342　計算機と算法
★タイトル (SCIENCE )  90/ 8/ 9  18:51  ( 44)
新ａｄｊｕｓｔ／奥村
★内容
　吉崎さんのものを最初から書き直していたら、なんとなく納得のいくものができ
ました。吉崎さんやＲＯＭ男さんと考えていることは同じなのでしょうか、なんと
なく自己流にきれいに書けると分かった気になるものです。吉崎さん流にいうと、
ｃｕｍの右から見ていって、１のビットを消していきます。ＲＯＭ男さん流にいう
と、下の長すぎるところの部分木を、上に寄せてていって、空いているところがあ
ればそこに移植します。思い違いがあるかもしれませんのでチェックしてください。
　これを使ったｍａｋｅｔｒｅｅ全体も書いてみました。コード生成部は吉崎さん
のｍａｋｅｔｂｌに習って効率化しました。ところが、他もいろいろいじったので、
どこかで同期がとれなくなってしまって、現在ａｒは動作しない状態です。
……略……

このころになると，手抜きをして一つの書き込みの中で圧縮のことや TeX のことなどをごっちゃに書くことが多くなり， タイトルも手抜きで「いろいろ」というのが多くなりました。 

#2375/3342　計算機と算法
★タイトル (SCIENCE )  90/ 8/ 9  18:54  ( 49)
いろいろ（また手抜きタイトル）／奥村
★内容
　（これは朝書いたものです。）
　吉崎さん、こちらにも出てきていただいてありがとうございます。
＞　　Ｔｒｉ−Ｐ経由だと、アップロード時に改行待ちにしても行が飛ぶこ
＞　とがあるようなので、なかなかこちらに書き込めないでいます。この文
　ＰＣ−ＶＡＮの通常のアクセスポイントは＾Ｍをエコーバックし、少し遅れてホ
ストが＾Ｊをエコーバックするので、＾Ｊを待ってから送ればいいのですが、Ｔｒ
ｉ−Ｐはどうなっているのか不明です。いずれにしてもプロンプト＞はホストが返
すのでしょうから、＞待ちにするしかないようです。行末の文字欠けといい、ＰＣ
−ＶＡＮのホストのファイルシステムの悪さはさんざん文句を言われながら改善さ
れないですね。ＰＣ−ＶＡＮ経験者は迷わず富士通のメインフレームを導入するで
しょう。ただし富士通のエンジニアにはバックアップをとらせないとか……。
　ＳＯＬＩＴＯＮさん、言い遅れましたが、邦訳ありがとうございます。これで私
も……といいたいところですが、訳を読ませていただいたかぎりでは、マウスが必
要のようですね。残念。どこかＩＢＭＰＣ用のマウスを安くで売っているところあ
りませんでしょうか。ＴｕｒｂｏＰａｓｃａｌだそうですからソースを入手できれ
ば９８用にリコンパイルできるでしょうけれども、シェアウェアじゃ無理か。
　ＣｏｍｐｕＳｅｒｖｅでもＩＢＭＰＲＯの圧縮ボードではあまりまともな話はあ
りませんが、メイルでいろいろ貴重な情報を教えていただけることがあります。向
こうではどうもアルゴリズムは簡単に公開せず金にするような感じです。ａｒをい
ろいろ試してくれた人の話では、吉崎さんのｍａｋｅ−ｔｒｅｅはかえって遅くな
ったとか言っています。なにかおかしいことでもしているのでしょうか。ＬＨｘは
長いので送っていませんが、先日のｍａｋｅ＿ｔｒｅｅだけ送ったところａｒと組
み合わせてテストしてくれています。１６ビット修正用はまだ送っていません。と
ころが、あのａｒのバグっている１６ビット修正部分、まず問題はないだろうとさ
ぼっていたところ、ついに２００ｋほどのファイルであのＩｎｔｅｒｎａｌ　ｅｒ
ｒｏｒというメッセージが出たそうです。やはり１６ビットを超す場合もあるんで
すね。
　ＭａｃでＣｏｍｐａｃｔｏｒという新しい圧縮ソフトが出たそうです。私にメイ
ルをくれた人は、その作者に手紙を書いてみたが、アルゴリズムについては教えて
くれないそうです。ａｒとの比較では、多くのファイルでａｒが勝つとのことです。
　私のａｒでは、まず起こらないことには手抜きするという方針で、１６ビットを
超えたものはみな１６ビットに直し、その分１５ビット以下のものを何でも１６ビ
ットにしてしまうことを、プリフィックスコードができるまで繰り返し、あとは知
らんぷりというアルゴリズムです。当然オプティマルなプリフィックスコードはで
きません（吉崎さん流にいうとｃｕｍｕｌａｔｅが０ｘ１００００未満になります）。
それでもちゃんとプリフィックスコードができるので、放っておくことにしました
が、問題はそこから後にあり、もう一度コードを最編成するところ（すぐ上）はオ
プティマルなコードを仮定して作ったものに手を加えなかったので、混乱してしま
うというわけです。今ｈｕｆ．ｃを見直してびっくりしました。
……略……

次の改良版 ar というものが，海外で ar002 として配布されていたものです。 たとえば Mark Nelson の The Data Compression Book (M&T Books, 第2版: 1996, ISBN:1-55851-434-1) の付録ディスクに収録されている ar002.exe という自己解凍ファイルがこれに相当します。 

#2389/3342　計算機と算法
★タイトル (SCIENCE )  90/ 8/15   5:35  ( 55)
圧縮>ar(poor man's LH)改良版/奥村
★内容
　ヘッダをＬＨｘもどき（レベル１）にしてみました。あと、いろいろバグやら能
率の悪いところを直しました。ＡＮＳＩ準拠です。タイムスタンプ表示はあきらめ
ました。圧縮アルゴリズム部分だけを自由にいじっていろいろテストしてみたい方
向きです。圧縮時のワイルドカード展開はしませんので
   for %f in (*.c *.h) do ar a test.ar %f
のようにしてください（％ｆがだめなら％％ｆ）。無断転載無断改変等歓迎。
……略……

このように私の書いたものはいつでも「無断転載無断改変等歓迎」 としていました。今でいうオープンソースの走りですね。 このいわゆる ar002 には一つだけコンパイラ依存のバグがあります。 maketbl.c の24行目の 

    while (i <= 16) weight[i++] = 1U << (16 - i);
は当時の Turbo C で通ってしまったので気付かなかったのですが，ほんとうは 
    while (i <= 16) {
        weight[i] = 1U << (16 - i);  i++;
    }
とすべきでした。これ以外のバグは報告されていません。

同じ1990年8月15日に，吉崎さんから改竄版 LHarc についてのお知らせが入りました。 当時はインターネットがなかったのでオリジナルの配布先がわかりづらく， 電子署名なども一般的でなかったので， 転載を経ているうちに改竄されていることがときどきありました。

1990年9月12日あたりから，CP/M 上の PMarc が話題になっています。 

#2487/3351　計算機と算法
★タイトル (SCIENCE )  90/ 9/14   5:51  ( 19)
ＰＭａｒｃ＆ＴＵＧｂｏａｔ９月号／奥村
★内容
　ＰＭａｒｃのアルゴリズムは、１０Ｋのスライド辞書だそうです。ハフマンの代
わりに、各文字に一番最近現われたものから順に０から２５５までの番号を振り、
番号の小さいものほど短い符号を割り当てるということです。速いのは、アセンブ
ラで十分最適化してあるからのようです。
……略……

#2518/3351　計算機と算法
★タイトル (SCIENCE )  90/ 9/26   5:37  ( 68)
% Length-Limited Huffman Codes / H.Okumura
★内容
\newenvironment{englishonly}{\par\setlength{\baselineskip}{1.2em}}{\par
  \vspace{.3em}}
\begin{document}
\noindent 次のような論文がありました.
\begin{englishonly}
 \begin{quote}
  Lawrence L. Larmore and Daniel S. Hirschberg.
  A Fast Algorithm for Optimal Length-Limited Huffman Codes.
  {\it Journal of the ACM}, 37:\,464--473, 1990.
     % この文献の表し方は van Leunen 流. %
 \end{quote}
 Abstract.
 An $O(nL)$-time algorithm is introduced for constructing
 an optimal Huffman code for a weighted alphabet of size $n$, where
 each code string must have length no greater than $L$.  The algorithm
 uses $O(n)$ space.
\end{englishonly}

まず次の問題を考えます (Coin Collector's problem).
要素の個数 $m$ の集合 $I$ があります.
各要素には幅と重さがあり, 幅は2の整数(負でもよい)乗です.
$I$ の部分集合で幅の和がちょうど与えられた値 $X$ になり,
重さの和が最小になるものを求めるのが問題です.

要素をあらかじめ重さの順に整列しておけば
次の $O(m)$ の算法で解けます.
以下で diadic expansion とは2進展開のことです.

\begin{englishonly}
 \begin{quote}
  \setlength{\parskip}{0em}
  \renewcommand{\.}{\hspace*{1em}}
  \renewcommand{\=}{\leftarrow}
  \obeylines
  $S \= \emptyset$
  for all $d$, $L_d \=%
    \mbox{list of items having width $2^d$, sorted by weight}$
  {\bf while} $X > 0$ {\bf loop}
  \.${\it minwidth} = \mbox{the smallest term in the diadic expansion of $X$}$
  \.{\bf if} $I = \emptyset$ {\bf then return} \lq\lq No solution.''
  \.{\bf else}
  \.\.$d \= \mbox{the minimum such that $L_d$ is not empty}$
  \.\.$r \= 2^d$
  \.\.{\bf if} $r > \it minwidth$ {\bf then return} \lq\lq No solution.''
  \.\.{\bf else if} $r = \it minwidth$ {\bf then}
  \.\.\.Delete the minimum weight item from $L_d$
  \.\.\.\.and insert it into $S$
  \.\.\.$X \= X - \it minwidth$
  \.\.{\bf end if}
  \.\.$P_{d+1} \= {\rm PACKAGE}(L_d)$
  \.\.discard $L_d$
  \.\.$L_{d+1} \= {\rm MERGE}(P_{d+1},L_{d+1})$
  \.{\bf end if}
  {\bf end loop}
  {\bf return} \lq\lq$S$ is the optimal solution.'' %
 \end{quote}
 {\sc The Step PACKAGE}. \ The list $P_{d+1}$ is formed
 from $L_d$ by combining items in consecutive
 pairs, starting from the lightest.  That is, the $k$th item of $P_{d+1}$
 is the package formed by combining items $(2k-1)$ and $2k$ of $L_d$.
 If $L_d$ is of odd length, its heaviest item is simply discarded.
 The MERGE step is just the usual merging of two sorted lists.
\end{englishonly}

Length-limited Huffman の問題は上の問題に帰着できるというわけですが,
時間がないのでここまで.
\end{document}

#2532/3351　計算機と算法
★タイトル (SCIENCE )  90/ 9/29   5:39  ( 35)
差分アルゴリズム／奥村
★内容
MASSANの挙げておられた
\begin{quote}
    Webb Miller.
    {\it A Software Tools Sampler}.
    Prentice-Hall, 1987.
\end{quote}
は確か以前パラパラと目を通して, サイズ $m$, $n$ のファイル
の差分を求めるのに $O(mn)$ の場所が必要であるように思って,
これでは使い物にならないと早合点して追究を止めてしまったの
だと思います. これが私が以前\#2332で {\it wanted\/} リスト
に挙げた論文の一つ
\begin{quote}
    Eugene W. Myers.
    An $O(ND)$ difference algorithm and its variations.
    {\it Algorithmica}, 1:251--266, 1986.
\end{quote}
の解説になっていることは気づきませんでした. ただしMillerの
本によればこのアルゴリズムが初めて現れる文献は
\begin{quote}
    W. Miller and E. W. Myers.
    A file comparison program.
    {\it Software---Practice and Experience}, Nov.\ 1985, 1025--1040.
\end{quote}
だそうです. さらに, {\it diff\/} タイプのスクリプトでなく三木さんの
{\it Ldiff\/} タイプのもの (copy, append) を使うアルゴリズムの文献が
\begin{quote}
    Walter F. Tichy.
    The string-to-string correction problem with block moves.
    {\it ACM Transactions on Computer Systems}, Nov.\ 1984, 309--321.
\end{quote}
にあると書いてあります. これらの文献も {\it wanted\/} リストに加えま
す. とりあえずはMillerの本を少し勉強します (本当は昨日読もうと思った
のですがあわただしくて\ldots. 今日--明日は久里浜高校の文化祭です.
立ち番の間に目を通そうと思います. お暇でしたら文化祭を見に来てくださ
い.

#2536/3351　計算機と算法
★タイトル (SCIENCE )  90/ 9/30   5:44  ( 52)
MASSANの差分器/奥村
★内容
まずどうでもいいことから.
\begin{quote}
ある文字列ｓのｉ番目に始まる長さｊの部分を s[i:j] と表すことにしま
しょう。
\end{quote}
Millerは
\begin{quote}
ある文字列ｓのｉ番目からｊ番目の部分を\ldots
\end{quote}
のつもりで使っているのではないでしょうか ($i = 1$ なら同じこと).
\begin{quote}
ファイルの比較のように，全部メモリに載せて比較するわけに行かない場合
どうしたらいいか。
\end{quote}
これについてはMillerの本112ページの中ほどに
\begin{quote}
  in the paper cited above, Gene Myers shows how the algorithm can be
  modified to run in space proportional to $m + n$.
\end{quote}
とありますので, もう少しスペース効率を良くする方法はあるのでしょ
うね. しかし, $O(m + n)$ でもメモリから溢れるときは,
適当な heuristic を使って初めの部分から捨てていくことになるのでし
ょうか. たしか ldiff はそうしていたと思います. GNU diff はどうや
っているのでしょうか.

ldiff は三木さんが ``さぼっている間に bdiff/bupdate に追い越された
ので何か良いアイデアはないか'' という意味のことを NIFTY に書いてお
られましたが, その後は不明です. まず, diff タイプの insert/delete
script よりもやはり copy/append script の方が小さくなりそうな気が
しますがどうでしょうか. それなら新 LH の trie でファイル1 (サイ
$m$)のすべての長さ256までの文字列の辞書を $O(m)$ の手間で作ってし
まい, それに照合しながらファイル2を符号化していくのが速いのでしょ
うか. それと差分の表現の問題があります. 80x86 の実行ファイルの差分
を表現するにはどんな方法が良いのでしょうか. ちょっと前の方を変えた
だけでアドレスがみんな狂ってしまいます. テキストファイルみたいにう
まくいきません. 80x86 の命令を知った差分器が必要でしょうか.

MASSAN 作 Mdiff を期待しています. 三木さん, 吉崎さんの次のヒーロー
は MASSAN かも?

{\tt myers.c} は楽しませていただきました. アルゴリズムのリアルタイ
ムの図解がいいですね (ただし少し遅くしないと目に止まらない).
{\tt instr()} は
    i = 0;
    while ((c = getchar()) != EOF && c != '\n')
        if (i < MAXLIN && ! isspace(c)) s[i++] = c;
    s[i] = '\0';
のようにしないとリターンキーを打たないで ^Z (UNIX なら ^d) を打つと
無限ループになりそうです.

どうもまだ差分のことについては頭が回り始めないのでトリヴィアルなこと
ばかりですみません.

#2706/3361　計算機と算法
★タイトル (SCIENCE )  90/11/10  19:56  ( 22)
arj014についてなど／奥村
★内容
　ＡＮＳＩ　Ｃで書いてあるとか圧縮比とかから考えてａｒ００１に他のアーカイ
バにあるいろいろな機能を付けたもののようですね。このａｒ００１はずっと前の
もので１６ビットを超える符号語については吉崎さんから指摘されたようにバグっ
ていたりするのですが……。ａｒ００１のソースにはちゃんとＩＤを書いておいた
ので連絡してくれれば新しいのがあることを言えたのですが（Ｉｎｔｅｒｎｅｔか
らＣｏｍｐｕＳｅｒｖｅへはｅｍａｉｌを双方向に送れる）。新しいａｒ００２は
ＣｏｍｐｕＳｅｒｖｅのＩＢＭＰＲＯに入っています。Ｋａｙａさんに頼まれて送
ったもので、ＩＳＨで送ったのですがちゃんとバイナリに直してライブラリに入れ
てくれています。こちらからメイルするのも面倒ですが。
　ａｒｊは、せっかくＡＮＳＩ　Ｃで書いたのですからソースで提供すればいいと
思うのですが、商業指向かな。実行コードだけの提供ならＡＮＳＩ　Ｃで書いたと
いう宣伝文句はあまり意味がありません。むしろＴｕｒｂｏ　Ｃでコンパイルした
と言った方が適切かも（Ｔｕｒｂｏ　Ｃでコンパイルした痕跡があります）。
　ところで、いまＣＩＳ（＝ＣｏｍｐｕＳｅｒｖｅ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓ
ｅｒｖｉｃｅ）に入ってきたのですが、Ｗｏｌｆｒａｍ　Ｒｅｓｅａｒｃｈ（あの
Ｍａｔｈｅｍａｔｉｃａを作ったところ）がＣＩＳに出店を出したということです。
また、この前ａｒ００２を読んだある人が「Ｐａｓｃａｌに直すかアルゴリズムの
詳しい解説をするかしてくれないか」と言ってきたので「いま圧縮の原稿で忙しい。
そちらでもパブリッシュしてくれる雑誌があれば英訳してもいい」と半ば冗談に言
ったのですが、そうしたら「こいつなら絶対大丈夫」と某パソコン雑誌の編集者の
アドレスを送ってきました。吉崎さんどうしますか？　英訳などじつをいうと面倒
で閉口しています。

#2712/3361　計算機と算法
★タイトル (SCIENCE )  90/11/11   8:21  ( 30)
ａｒｊ０１４についてなど／奥村
★内容
　さらに詳しく読むとａｒ００１（００２ではない）の影響がかなり見られるよう
です。ヘッダの説明（ｔｅｃｈｎｏｔｅ．ｄｏｃ）がまた非常に似ています。ファ
イルタイプでバイナリとテキストを分けたのもａｒ００１の発想と同じです。これ
はａｒ００１を作った時点ではぜひ必要なものと思っていました。テキストファイ
ルはＯＳによって構造がかなり違います。ＭＳ−ＤＯＳ（ｃｒｌｆ）とＵＮＩＸ（
ｌｆ）はまあ似ていますが、ＯＳによっては行の長さ＋行で表すものもあるでしょ
うから、バイナリと見なして読み書きすることは問題があります。でも、ａｒ００
２では単純さとＬＨ互換を考えてこれはなくしました。
　ａｒｊ０１４のＭｅｔｈｏｄ１−−３はａｒ（ＬＨ）方式とほぼ同じようです。
スライド辞書のサイズで分けているんでしょうか。Ｍｅｔｈｏｄ４はＦｉａｌａ＆
Ｇｒｅｅｎｅ流のｕｎａｒｙ　ｃｏｄｅのようです。また、木への挿入も手を抜い
て行う方式のようです。速さはこれが一番でしょう。
　ａｒｊ０１４では暗号化は簡単な方法を使っているようです。ＬＨではＦＥＡＬ
を採用するのでしょうか。キーを初期値として自前の乱数を発生し各文字とＸＯＲ
する程度でも、圧縮後に暗号化しヘッダやコメント（無圧縮の部分）は暗号化しな
いならかなり強いとは思います。乱数としては簡単にはキーを８バイトとしハッシ
ュして３２ビットに縮め、３２ビット合同法乱数を使い、上位８ビットとＸＯＲす
れば、ルーチンはＣ言語で数行でできてしまいますし、速いです。
……略……

ようやく LH ができあがります。 

#2767/3361　計算機と算法
★タイトル (SCIENCE )  90/11/20   5:38  (  4)
ＬＨ新版出来／奥村
★内容
　ＮＩＦＴＹではアセンブラ版ＬＨ２．０の評価版が出ました。なるべく転載しな
いようにとか書いてありましたが、吉崎さん、どうしましょうか？
　ダウンロードしたついでにテディ松本さんのＬＥＸＥＭという実行もできる速い
アーカイバもいただいてきました。これもこちらに転載しましょうか？

#2785/3361　計算機と算法
★タイトル (SCIENCE )  90/11/23   4:56  ( 23)
LH 2.0 試作版入荷 (ライブラリ/PDS)/奥村
★内容
　吉崎さんの時間的制約のためＮＩＦＴＹ以外では基本的にノーサポートというこ
とですが、それでもかまわないならということでお許しを得て試作版をいただいて
きました。バグレポートや改良案などありましたらこのボードに書いていただけれ
ば、立ち寄られたときに見てくださると思いますが、質問の回答などは期待しない
でください。マニュアルの補遣を以下に挙げます。なお、試作版のため、ＳＦＸ機
能はありません。
……略……

1990年11月25日，室蘭の大学生だった 岡本継男さん も登場します。 岡本さんはその後 UNIX 版 LHA のメンテをやってくださっています。

次の書き込みの詳細については Efficient decoding of prefix codes をご覧下さい。 

#2967/3361　計算機と算法
★タイトル (SCIENCE )  90/12/30   5:10  ( 22)
速いハフマン符号化,TurboC++,etc／奥村
★内容
最近のComm. ACMに接頭符号の速い復号法というのが載っていた
のですがあまり面白そうでないので読んでいませんでした.
Computing ReviewsにHorspool先生が書いているところによ
れば, これより次の方が速いとのこと.
  Y. Choueka, A. S. Fraenkel, S. T. Klein, and Y. Perl.
  Huffman coding without bit-manipulation.  Report CS86-05,
  Weizman Institute, Rehovot, Israel, 1986.
でも新LHより良い方法があるだろうか...
……略……

#2974/3361　計算機と算法
★タイトル (SCIENCE )  90/12/31   6: 1  (  9)
ＤＤＪデータ圧縮コンテスト、ＤＩＥＴ／奥村
★内容
　１月号のＤＤＪ（米国のコンピュータ雑誌Ｄｒ．　Ｄｏｂｂ’ｓ　Ｊｏｕｒｎａｌ
のことです）によれば、２月号はデータ圧縮プログラミングコンテストだそうです。
米国内では１月早々に発売されるのでしょうから、早く入手されたかたがおられまし
たら内容を教えてください。日本のＣマガに続いて米国でも圧縮ブームなのでしょう
か。ＵｎｉｓｙｓがＵＮＩＸのｃｏｍｐｒｅｓｓの特許をとって云々ということで、
皆独自の圧縮に頼る傾向が出てきたのでしょうか。
　ところで、Ｔｅｄｄｙ　Ｍａｔｓｕｍｏｔｏさんの新しい圧縮ソフトＤＩＥＴをＰ
ＤＳに入れておきましたが、この日本語版のメッセージはいかがでしたでしょうか？
このメッセージだけでヒット間違いなしです。

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

松阪大学 奥村晴彦 okumura@matsusaka-u.ac.jp

Last modified: Mon Dec 28 19:44:50 1998