今年も残りわずかとなりました。M.Hiroi's Home Page を開設してから五年半になりますが、おかげさまでカウンタも 186,000 を突破いたしました。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様にお礼申しあげます。
それでは、きたるべき年も皆様にとってよいお年でありますように。
個人的な事情で M.Hiroi's Home Page の更新が滞ってしまいました。今までのように更新するのはちょっと難しい状況ですが、M.Hiroi's Home Page は続けていきたいと思っております。これからもよろしくお願いいたします。
M.Hiroi's Home Page を開設してから本日でちょうど 5 年になりました。この 1 年間で 40,000 Hit を越えるアクセスがあり、1 日のアクセス数は平均で 111 Hit になりました。多くの方にアクセスしていただき、とても嬉しく思います。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申しあげます。
これからもがんばりますので、今後ともよろしくお願い申しあげます。
本日、カウンタが 170,000 を突破しました。多くの方にアクセスしていただき、とても嬉しく思います。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。最近は Ｃ言語講座 のアクセス数が一番多く、次が xyzzy Lisp で、その次が Prolog になりました。去年もそうでしたが、4 月中旬頃からＣ言語講座と Prolog のアクセス数が増えています。学校の授業が始まって、学生さんのアクセスが多くなっているのかもしれません。
先月から始めた お気楽 Standard ML of New Jersey 入門 ですが、おかげさまで先日 1000 Hit を越えました。多くの方にアクセスしていただき、本当にありがとうございます。SML/NJ は強く型づけされたプログラミング言語ですが、実際に使ってみると、思っていたよりも柔軟にプログラムを作ることができました。これも ML の特徴である型推論や多相関数といった機能があるからできることなのでしょう。SML/NJ はとても面白いプログラミング言語だと思います。
これからもがんばりますので、よろしくお願い申しあげます。
負でない整数 a と b の最大公約数を求める場合、「ユークリッド (Euclid) の互除法」を使うと簡単です。
負でない整数 a と b (a > b) で、a を b で割った余りを r とする。このとき、a と b の最大公約数は b と r の最大公約数に等しい。
ユークリッドの互除法は簡単に証明できます。a と b の割り算を次の式で表します。
(1) a = q * b + r
ここで、a と b の最大公約数を m とすると、a = m * a', b = m * b' となります。すると、式 (1) は式 (2) で表すことができます。
(2) m * a' = q * m * b' + r
左辺は m で割り切れるので、右辺も m で割り切れる必要があります。q * m * b' は m で割り切れますね。したがって、r も m で割り切れることになります。つまり、r = m * r' になるので、b と r の最大公約数は a と b の最大公約数 m と同じになります。
同様に、b と r の最大公約数を求めます。b を a とし、r を b にして同じ計算をすればいいわけです。この計算を繰り返し行うと、a と b はどんどん小さくなっていき、r = 0 になったときの b が最大公約数になります。次の例を見てください。
a b r --------------- 42 30 12 30 12 6 12 6 0 最大公約数は 6
このように、42 と 30 の最大公約数 6 を簡単に求めることがでいます。プログラムは再帰定義を使って簡単に作ることができます。たとえば、SML/NJ でプログラムを作ると次のようになります。
リスト：最大公約数 fun gcd( a, 0 ) = a | gcd( a, b ) = gcd( b, a mod b )
このプログラムは a < b でも動作します。実行例を示します。
- gcd( 42, 30 ); val it = 6 : int - gcd( 30, 42 ); val it = 6 : int
複数の整数の最大公約数を求める場合、縮約 (reduce) を使うと簡単です。SML/NJ の関数 foldr を使うと次のようになります。
- foldr gcd 0 [63,42,35]; val it = 7 : int
最小公倍数は最大公約数を使って簡単に求めることができます。次の例を見てください。
- fun lcm( a, b ) = a * b div gcd( a, b ); val lcm = fn : int * int -> int - lcm( 5, 7 ); val it = 35 : int - lcm( 14, 35 ); val it = 70 : int - foldr lcm 1 [1,2,3,4,5,6]; val it = 60 : int
整数 a と b の最小公倍数は a * b / gcd(a, b) で求めることができます。複数の整数の最小公倍数も foldr を使って簡単に求めることができます。
先日、Functional Programming を新設しました。先月の Memorandum で簡単に紹介した Standard ML of New Jersey (SML/NJ) の入門講座を書いています。関数型言語は手続き型言語とは違う独特の面白さがあります。Functional Programming では SML/NJ で簡単なプログラムを作りながら関数型プログラミングを楽しんでいきたいと思っております。たいしたことはできませんが、よろしくお付き合いくださいませ。
4 月 6 日 の続きです。今回は 0-1-2 coding で試してみました。テストプログラムの種類を示します。
(A) BlockSort -> MTF-3 -> RLE7 -> 0-1-2 coding (B) BlockSort -> MTF-3 -> 改良版 1 -> 0-1-2 coding (C) BlockSort -> MTF-3 -> 改良版 2 -> 0-1-2 coding
今回のテストでは 2 以上の記号にランレングスを適用しています。0-1-2 coding の場合、この方が圧縮率が高くなります。改良版 1 は Sam さんの方法で、改良版 2 は改良版 1 の開始連長を -1 したものです。なお、記号 0xfe と 0xff の出現頻度はとても少ないので、テストプログラムではランレングスを適用していません。Sam さんの方法とは少し異なることに注意してください。
実行結果は次のようになりました。
ファイル名 サイズ (A) (B) (C) ------------------------------------------------- alice29.txt 152,089 42,047 42,022 42,022 asyoulik.txt 125,179 38,805 38,788 38,788 cp.html 24,603 7,482 7,479 7,479 fields.c 11,150 2,936 2,934 2,934 grammar.lsp 3,721 1,208 1,208 1,208 kennedy.xls 1,029,744 89,515 84,567 82,877 lcet10.txt 426,754 104,540 104,487 104,486 plrabn12.txt 481,861 141,804 141,761 141,761 ptt5 513,216 47,846 47,833 47,832 sum 38,240 12,277 12,274 12,274 xargs.1 4,227 1,670 1,670 1,670 ------------------------------------------------- 合計 2,810,784 490,130 485,023 483,331
予想通り kennedy.xls には大きな効果がありました。ビットモデルと比べると、少しですが圧縮率が向上するファイルがあるので、Sam さんの改良版は 0-1-2 coding と組み合わせた方がよいのかもしれません。興味のある方はいろいろ試してみてください。
データ圧縮のお話です。Sam さんが Guest Book で紹介された ZLE の改良を試してみました。Sam さん、ありがとうござます。拙作のＣ言語講座番外編 ランレングスの改良 では、ZLE (Zero Length Encoding) と RLE (Run Length Encoding) を組み合わせる方法を説明しました。Sam さんの方法は ZLE と RLE を組み合わせる方法の改良版で、「記号ごとにランレングスを開始する連長を変える」というものです。次の表を見てください。
記号 連長 ---------------------- 0 -- (ZLE) 1 10 (RLE10) 2, 3 9 (RLE9) 4 - 7 8 (RLE8) 8 - 15 7 (RLE7) 16 - 31 6 (RLE6) 32 - 63 5 (RLE5) 64 - 127 4 (RLE4) 128 - 255 3 (RLE3)
大きな記号ほどランレングスを開始する連長 (N) を短くします。一般にブロックソートと MTF 法を適用した場合、小さな記号の個数が極めて多くなり、大きな記号の個数はとても少なくなります。したがって、大きな記号で長い連長が出現することはほとんどなく、ランレングスの効果もほとんどありません。
Sam さんの方法は記号ごとに開始連長 N を変えることで、大きな記号でもランレングスによる符号化が行われるように工夫されています。しかしながら、大きな記号ほどランレングスの効果は少なくなるので、あまり効果がないように思われます。ところが、ランレングスを適用することで、大きな記号を小さな記号に変換することができるのです。次の例を見てください。
FF FF FF FF == RLE3 ==> FF FF FF 00
FF が 4 つ連続している場合、RLE3 で符号化しても記号数は同じ 4 になります。記号の個数は同じですが、最後の FF が 00 に変換されていますね。このように、ランレングスには大きな記号を小さな記号に変換する効果があるわけです。まあ、そうはいっても、大きな効果を期待できるというわけではありません。一般的なテキストファイルの場合、効果はほとんどないでしょう。バイナリファイルの場合、効果があるかもしれません。
それでは実際に試してみましょう。テストデータは Canterbury Corpus で配布されている The Canterbury Corpus です。プログラムは Borland C++ 5.5.1 for Win32 でコンパイルし、M.Hiroi のオンボロマシン (Windows95, Pentium 166 MHz) で実行しました。
テストプログラムの種類を示します。
(A) BlockSort -> MTF-3 -> ZLE7 -> ビットモデル (B) BlockSort -> MTF-3 -> 改良版 1 -> ビットモデル (C) BlockSort -> MTF-3 -> 改良版 2 -> ビットモデル
とりあえず、単純な ビットモデル を使います。改良版 1 は Sam さんの方法で、改良版 2 は改良版 1 の開始連長 (N) を -1 したものです。なお、記号 0xfe と 0xff の出現頻度はとても少ないので、テストプログラムではランレングスを適用していません。Sam さんの方法とは少し異なることに注意してください。
実行結果は次のようになりました。
ファイル名 サイズ (A) (B) (C) ------------------------------------------------- alice29.txt 152,089 42,281 42,280 42,280 asyoulik.txt 125,179 38,982 38,979 38,980 cp.html 24,603 7,624 7,624 7,624 fields.c 11,150 3,060 3,060 3,060 grammar.lsp 3,721 1,237 1,237 1,237 kennedy.xls 1,029,744 101,210 96,753 95,344 lcet10.txt 426,754 105,295 105,285 105,290 plrabn12.txt 481,861 142,259 142,248 142,248 ptt5 513,216 48,085 48,087 48,085 sum 38,240 12,615 12,614 12,616 xargs.1 4,227 1,706 1,707 1,706 ------------------------------------------------- 合計 2,810,784 504,354 499,874 498,470
大きな効果があったのは kennedy.xls だけで、他のファイルの圧縮率はほとんど同じでした。Sam さんの方法はユニークで興味深い方法ですが、その効果は一部のファイルに限られているようです。興味のある方はいろいろなデータで試してみてください。
昨日、カウンタが 160,000 を突破しました。多くの方にアクセスしていただき、とても嬉しく思います。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。最近は xyzzy Lisp のアクセス数が一番多く、次が Ｃ言語講座 で、その次が Perl/Tk になりました。
ところで、オーム社から xyzzy の解説書 入門xyzzy が 3 月 28 日に出版されます。xyzzy はとても優れたエディタですが、初心者にはちょっと難しいと思われているようです。わかりやすい入門書があれば xyzzy を使ってみたい、という方もいるでしょう。この本をきっかけに、xyzzy ユーザが増えるといいなと思っています。ちなみに、Google で "入門xyzzy" を検索すると拙作のページ xyzzy Lisp Programming もヒットします。最近、xyzzy Lisp のアクセス数が多いのは、これが原因かもしれませんね。
これからもがんばりますので、よろしくお願い申しあげます。
Tcl/Tk のお話です。ひさしぶりに Tcl/Tk を 8.4.9 にバージョンアップしました。ActiveState の ActiveTcl をダウンロードしましたが、M.Hiroi のオンボロマシン (Windows 95, Pentium 166 MHz) でも動作したのでよかったです。
ActiveTcl は Tcl/Tk の有名な拡張ライブラリが含まれていて大変便利です。また、Tcl/Tk 8.4 から追加されたウィジェット (labelframe, panedwindow, spinbox) もあります。これらのウィジェットを拙作のページ Tcl/Tk お気楽 GUI プログラミング で紹介できればいいな、と思っています。
Tk は Tcl だけではなく、Perl/Tk, Python/Tkinter, Ruby/Tk など他のプログラミング言語でも利用されています。実際、Tcl/Tk の知識は他のプログラミング言語で Tk を扱うときにとても役に立ちます。GUI に興味のある方は、Tcl/Tk でプログラミングしてみるのも悪くはないと思います。
それから、拙作の リンク集 に今井さんのページ もっとTcl/Tk を追加しました。Tcl/Tk の情報が充実していて大変素晴らしいページです。Tcl/Tk 関連ではとても有名なページなので、ご存知の方は多いと思います。また、もっとTcl/Tk の 関連リンク には、拙作のページ Tcl/Tk GUI Programming がリンクされています。今井さんに深く感謝いたします。これからもよろしくお願いいたします。
ＣＱ出版社 発行の月刊誌 Interface 4 月号 (2/25発売) で、M.Hiroi は「PPM によるファイルの圧縮（後編）」を執筆しました。後編は PPM (Prediction by Partial Matching) の符号化アルゴリズムと実装方法について詳しく解説しています。圧縮アルゴリズムに興味のある方は読んでみてください。
データ圧縮のお話です。ブロックソート でファイルを圧縮する場合、MTF 法 と ランレングス でデータを変換し、レンジコーダ で符号化すると高い圧縮率を達成することができます。ここで、情報源モデルを工夫すると圧縮率をさらに向上させることができます。
ブロックソート向きの情報源モデルは、structured model, 0-1-2 coding, binary model, ビットモデル などいくつかありますが、この中で 0-1-2 coding とランレングス (RLE)、特に Zero Length Encoding (ZLE) との相性はあまりよくありません。RLE の場合は、2 以上の記号に対して RLE を適用することで、この問題を回避することができます。
これらの情報源モデルに 混合法 を適用すると、圧縮率が向上する場合があります。RLE -> 0-1-2 coding (混合法) では大きな効果がありましたが、ZLE -> 0-1-2 coding (混合法) はまだ試したことがありません。もしかすると、混合法を適用することで、ZLE -> 0-1-2 coding でも圧縮率が向上するかもしれません。そこで、実際に試してみることにしました。
テストデータは Canterbury Corpus で配布されている The Canterbury Corpus です。プログラムは Borland C++ 5.5.1 for Win32 でコンパイルし、M.Hiroi のオンボロマシン (Windows95, Pentium 166 MHz) で実行しました。
テストプログラムの種類を示します。
(A) BlockSort -> MTF-3 -> 0-1-2 coding (binary model + 混合法) (B) BlockSort -> MTF-3 -> RLE7 (記号 2 以上) -> 0-1-2 coding (binary model + 混合法) (C) BlockSort -> MTF-3 -> ZLE7 -> 0-1-2 coding (binary model + 混合法) (D) BlockSort -> MTF-3 -> ZLE7 -> 0-1-2 coding (binary model + 混合法 + jil さんの改良版)
0-1-2 coding (binary model + 混合法) は、混合法による binary model の改良 のプログラム (rcb012x.c) を使いました。(D) はゲストブックで jil さんから教えてもらった改良方法を使っています。jil さん、ありがとうございます。
結果は次のようになりました。
| ファイル名 | サイズ | (A) | (B) | (C) | (D) |
|---|---|---|---|---|---|
| alice29.txt | 152,089 | 41,710 | 41,710 | 42,046 | 41,974 |
| asyoulik.txt | 125,179 | 38,548 | 38,549 | 38,790 | 38,722 |
| cp.html | 24,603 | 7,439 | 7,439 | 7,571 | 7,560 |
| fields.c | 11,150 | 2,933 | 2,933 | 3,025 | 3,020 |
| grammar.lsp | 3,721 | 1,210 | 1,210 | 1,232 | 1,230 |
| kennedy.xls | 1,029,744 | 83,234 | 80,656 | 82,944 | 82,856 |
| lcet10.txt | 426,754 | 103,720 | 103,719 | 104,579 | 104,408 |
| plrabn12.txt | 481,861 | 140,784 | 140,784 | 141,234 | 141,001 |
| ptt5 | 513,216 | 47,427 | 47,428 | 47,758 | 47,689 |
| sum | 38,240 | 12,119 | 12,115 | 12,342 | 12,330 |
| xargs.1 | 4,227 | 1,675 | 1,672 | 1,698 | 1,696 |
| 合計 | 2,810,784 | 480,799 | 478,215 | 483,219 | 482,486 |
(C) と (D) を見てください。混合法を適用することで、ZLE -> 0-1-2 coding でも高い圧縮率を達成しています。この結果にはちょっと驚きました。(C) と (D) では、(D) の方が少しだけ圧縮率が高くなりました。jil さんの方法は確かに効果がありますね。しかしながら、(A) と (B) の圧縮率にはわずかに及びません。今回の結果を見ると、ZLE よりも専用 RLE の方が 0-1-2 coding に適しているようです。興味のある方はいろいろなデータで試してみてください。
ＣＱ出版社 発行の月刊誌 Interface 3 月号 (1/25発売) で、M.Hiroi は「PPM によるファイルの圧縮（前編）」を執筆しました。前編は「桁上げのないレンジコーダ」と PPM (Prediction by Partial Matching) の基本となる「有限文脈モデル」について解説しています。圧縮アルゴリズムに興味のある方は読んでみてください。