Memorandum

12月31日

●大晦日

今年も残りわずかとなりました。M.Hiroi's Home Page を開設してから４年半になりますが、おかげさまでカウンタも 150,000 を突破いたしました。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様にお礼申しあげます。来年もこのページでプログラミングの楽しさを少しでもお伝えできればいいなと思っています。来年もよろしくお願い申しあげます。

それでは、きたるべき年も皆様にとってよいお年でありますように。

12月24日

●150,000 Hit!

本日、カウンタが 150,000 を突破しました。多くの方にアクセスしていただき、とても嬉しく思います。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。

新ジオシティーズに移行して、もうすぐ三ヶ月になります。その間に URL 転送サービスや容量が 50 MB に増えるなど、ジオシティーズのサービスは良くなっているのですが、M.Hiroi's Home Page のアクセス数は減少傾向にあります。去年の 11 月はアクセス数が多く一日平均 126 Hit ありましたが、今年は 102 Hit になりました。まあ、去年に比べると更新回数が少ないので、アクセス数が減少するのは当然ですが、もうひとつ Google のランクも影響しているようです。

M.Hiroi's Home Page は二つの URL (旧 URL http://www.geocities.co.jp/SiliconValley-Oakland/1680/, 新 URL http://www.geocities.jp/m_hiroi/) のどちらでもアクセスすることができます。どちらも同じページなのですが、Google は別のページとして判断しているようです。現在、M.Hiroi's Home Page へのリンクに新 URL が使われているページもありますし、旧 URL が使われているページもあります。Google は新旧 URL を別のページとして扱っているため、今までのランクが二分されてしまい、M.Hiroi's Home Page のランクが低くなったと思われます。

新旧二つの URL でアクセスできるのは便利ですが、Google のランクに影響するとは思ってもいませんでした。今のところ、旧 URL を廃止して新 URL に統一するつもりはありませんが、よろしければ新 URL でリンクしていただけると助かります。

それでは、これからもがんばりますので、よろしくお願い申しあげます。

12月2日

●LZMA （その２）

11 月 5 日 の続きです。LZMA は LZ77 符号に変更を加えた符号化方式です。LZ77 符号は「辞書に基づく符号化方式」のひとつで、「辞書（スライド窓）」の大きさによって圧縮率が大きく変化します。LZ77 符号 (LZSS 符号) は拙作のＣ言語講座 第 22 回 で詳しく説明しています。興味のある方はお読みくださいませ。

LZMA の場合、スライド窓の大きさはデフォルトで 8 M byte に設定されています。この大きさには M.Hiroi も驚きました。LHA の場合、圧縮形式によってスライド窓の大きさが変わり、lh5 = 8 K byte, lh6 = 32 K byte, lh7 = 64 K byte になります。M.Hiroi は標準的な lh5 形式を使っています。

LZMA はオプション -d でスライド窓の大きさを変更することができます。そこで、スライド窓の大きさを変えて試してみました。Canterbury Corpus で配布されているテストデータ The Canterbury Corpus, それを tar でまとめたファイル Canterbury と The Large Corpusを圧縮してみましょう。ご参考までに、LHA (lh5) の結果も示します。

LZMA の場合、スライド窓を大きくするとテキストファイルの圧縮率が高くなります。LHA (lh5) と同じ 8 K byte に設定すると圧縮率は悪くなりますが、それでも LHA より高い圧縮利を叩き出しています。また、kennedy.xls, ptt5, sum などのバイナリファイルは、スライド窓の大きさにかかわらず高い圧縮率を達成しています。

LZ77 符号の場合、スライド窓を大きくすると圧縮率は確かに向上します。そうはいっても、簡単に圧縮率が向上するわけではありません、スライド窓の大きさはもろ刃の剣で、大きくしすぎると圧縮率を低下させる要因にもなるのです。ここまでスライド窓を大きくしても高い圧縮率を叩き出す LZMA には本当に驚きました。LZMA はとても優れた圧縮方式だと思います。

11月28日

●ホームページ容量増量

Yahoo! ジオシティーズのホームページ容量が 50 MB に増量されました。現在、M.Hiroi's Home Page のコンテンツは全部で約 11 MB あり、旧ジオシティーズ (容量 12 MB) では容量が残り僅かになっていました。新ジオシティーズ (容量 15 MB) へ移行して一息ついたのですが、今回の大幅な増量により、当分の間は容量を気にしなくてもよさそうです。

ということで、Perl/Tk memo に 神経衰弱ゲーム と アナログ時計 を追加しました。拙作のページ Tcl/Tk お気楽 GUI プログラミング応用編 のプログラムを Perl/Tk で書き直しただけですが、Perl/Tk に興味のある方は読んでみてください。

11月18日

●『Coffee Cups Complex』 for X680x0 バージョンアップ！

TAU さん の X680x0 用ゲーム『Coffee Cups Complex』がバージョンアップ (Ver 0.10) されました。Ver 0.10 では新しい stage が追加され、手数のカウント方式を切り替えることができます。パズルが好きな X680x0 ユーザーはぜひ遊んでみてください。

●記号の二分探索

11 月 13 日 の続きです。大地さんのプログラムに EOF を表す記号 (256) を追加し、適応型レンジコーダ のプログラムを二分探索に改造してみました。次のリストを見てください。

リスト：二分探索で記号を探す

int search_code0( Frequency *freq, Ushort value )
{
  int i = 0, j = CODE_SIZE - 1;
  Ushort *count_sum = freq->count_sum;
  while( i < j ){
    int k = (i + j) / 2;
    if( count_sum[k + 1] <= value ){
      i = k + 1;
    } else {
      j = k;
    }
  }
  return i;
}

int search_code1( Frequency *freq, Ushort value )
{
  int c = 0, j;
  Ushort *count_sum = freq->count_sum;
  for (j=128; j; j>>=1) c += (count_sum[c + j] <= value) ? j : 0;
  /* EOF code のチェック */
  if( c == 255 && count_sum[c + 1] <= value ) c++;
  return c;
}

int search_code2( Frequency *freq, Ushort value )
{
  int c = 0, j;
  Ushort *count_sum = freq->count_sum;
  for (j=64; j; j>>=2) {
    if (count_sum[c+j] <= value) c += j;
    else continue;
    if (count_sum[c+j] <= value) c += j;
    else continue;
    if (count_sum[c+j] <= value) c += j;
  }
  /* EOF code のチェック */
  if( c == 255 && count_sum[c + 1] <= value ) c++;
  return c;
}

関数 search_code0 がレンジコーダ用の二分探索です。CODE_SIZE は記号の種類を表すマクロで、EOF (256) を含めて 257 になります。関数 search_code1 と search_code2 が大地さんのプログラムを改造したもので、復号した記号が 255 の場合に EOF のチェックを追加しています。このような改造では、せっかくの高速性が台無しになるかもしれません。興味のある方は他の方法を考えてみてください。

それでは実行結果を示します。テストデータは Canterbury Corpus で配布されている The Canterbury Corpus の中から alice29.txt, kennedy.xls, plrabn12.txt, ptt5 の 4 ファイルと The Large Corpus の bible.txt です。プログラムは Borland C++ 5.5.1 for Win32 でコンパイルし、M.Hiroi のオンボロマシン (Windows95, Pentium 166 MHz) で実行しました。時間はファイルの入出力処理を含むプログラム全体の処理時間です。

さすがに二分探索は高速で、どの関数でも十分に速いのですが、その中で search_code2 が一番高速になりました。なるほど、確かに効果がありますね。大地さんに感謝です。記号に EOF (256) を含めずに、大地さんのプログラムをそのまま使うと、もう少し速くなると思われます。興味のある方は試してみてください。

11月13日

●レンジコーダの復号処理について

昨日、Guest Book で大地さんが投稿された「高速化アルゴリズム」ですが、ジオシティーズのゲストブックに問題があり、プログラムリストのほとんどが掲載されていませんでした。さっそく、大地さんからメールで投稿内容をお送りいただきました。大地さん、ありがとうございます。

大地さんの投稿内容は、レンジコーダのデコード部で使用する記号の探索処理についてです。記号の探索処理は、記号数が多くなると線形探索よりも二分探索を使った方が高速です。大地さんはレンジコーダ用の高速な二分探索（バイナリサーチ）を提案されています。大地さんのメールから転載します。

    int c = 0, j;
    for (j=128; j; j>>=1) c += (sum[c+j] <= tmp1) ? j : 0;

    [Hybrid Search]
    int c = 0, j;
    for (j=64; j; j>>=2) {
        if (sum[c+j] <= tmp1) c += j;
        else continue;
        if (sum[c+j] <= tmp1) c += j;
        else continue;
        if (sum[c+j] <= tmp1) c += j;
    }

なるほど、これはとても面白いアイデアだと思います。M.Hiroi も試してみたいと思います。ただし、大地さんのプログラムでは、記号は 256 種類 (0 - 255) までなので、EOF (たとえば 256) を含める場合はプログラムを改造する必要があります。ご注意ください。興味のある方は、ぜひ試してみてください。

11月5日

●LZMA

データ圧縮のお話です。最近、M.Hiroi は LZSS 符号の改良に関心を持っていて、いろいろ調べているうちに 7-ZIP という圧縮ツールに行き着きました。7-ZIP の作者は Igor Pavlov です。7-ZIP はいくつかの圧縮方式をサポートしていて、その中でデフォルトで使用される LZMA という圧縮方式が LZ77 符号をベースにしています。LZMA はアプリケーションに組み込むことも考えられていて、ソースファイルやドキュメントなど必要なものは LZMA SDK からダウンロードすることができます。

LZMA SDK には実行形式ファイル lzma.exe が含まれているので、さっそく試してみることにしました。Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。ご参考までに、LHA, bzip2, bsrc2 ^[1] の結果も示します。bzip2 と bsrc2 はブロックソートを用いた圧縮ツールです。LZMA の設定はデフォルトのままです。

LZMA は LHA を大きく上回る圧縮率を叩き出しています。テキストファイルでは bzip2 の圧縮率には及ばないものの、kennedy.xls, ptt5, sum では bzip2 と bsrc2 を上回る圧縮率になりました。特に kennedy.xls の圧縮率がとても高いので、合計値では bzip2 を上回る圧縮率になりました。

今度は、The Canterbury Corpus (11 ファイル) を tar でまとめたファイル Canterbury と The Large Corpus を圧縮してみました。ブロックソートの圧縮率はバッファサイズによって大きく変化します。bzip2 のバッファサイズは最大の 900 k byte に、bsrc2 のバッファサイズは 4 M byte に設定しました。

LZMA の圧縮率はとても高く、もはや LHA とは比較になりませんね。bible.txt 以外のファイルでは bzip2 を上回る高い圧縮率になりました。LZ77 符号をベースにした圧縮ツールで、ブロックソートに匹敵する高い圧縮率を叩き出すとは、本当に驚きました。そのかわり、圧縮処理には時間がかかるようです。興味のある方は、いろいろなファイルで試してみてください。

10月30日

●地震お見舞いのお礼

このたびの新潟県中越地震では、皆さまよりお見舞いをいただき、誠にありがとうございました。とても大きな揺れで生きた心地がしなかったのですが、幸いにもわが家ではたいした被害もなくすみましたので、ご安心くださいませ。今回の地震は余震活動が活発で、いつまた大きな余震がくるか不安だったのですが、ようやくおちついて後始末もできるようになりました。

余震活動は収まりつつありますが、いまだに多くの方々が避難生活を余儀なくされています。各地の被災者の皆さまに心からお見舞いを申しあげます。

●変形版・ライツアウト 4 行 5 列盤の最長手数

10 月 19 日 の続きです。変形版・ライツアウト 4 行 5 列盤の最長手数を幅優先探索で求めてみました。

1手のパターン数 20
2手のパターン数 190
3手のパターン数 1140
4手のパターン数 4845
5手のパターン数 14751
6手のパターン数 30500
7手のパターン数 39625
8手のパターン数 30000
9手のパターン数 10000
合計 131072 個

最長手数は 9 手になりました。局面の総数はライトがすべて消えている完成形も含めて全部で 131072 通りになりました。局面の総数は 5 行 5 列盤とたまたま同じになりましたが、最長手数は 1 手長くなりました。

10月19日

●URL 転送サービス

Yahoo! ジオシティーズが旧ジオシティーズから新ジオシティーズへの「URL 転送サービス」を始めました。詳しくは Yahoo! ジオシティーズのヘルプ 旧ジオシティーズから新ジオシティーズへURL転送したい をお読みください。

本日、URL の転送設定を行いましたので、旧 URL (http://www.geocities.co.jp/SiliconValley-Oakland/1680/) のアクセスは新 URL (http://www.geocities.jp/m_hiroi/) へ転送されます。これにともない、トップページにあったジオシティーズのカウンタを復活させました。

実は、ジオシティーズの 助け合い広場 で、このサービスが準備されていることは知っていたのですが、いつのまにか開始されていたのでちょっと驚きました。このような重要なサービスは「ヘルプ」に追加するだけではなく、トップページ とか お知らせ できちんと説明してもらいたいと思います。

まあ、このほかにも 10 月下旬からは容量が 50 MB に増えるなど、ジオシティーズもがんばっているようなので、M.Hiroi's Home Page はこのまま続けていこうと思っています。これからもよろしくお願いいたします。

●変形版・ライツアウトの最長手数

10 月 15 日 の続きです。変形版・ライツアウト 5 行 5 列盤の最長手数を幅優先探索で求めてみました。

1手のパターン数 25
2手のパターン数 300
3手のパターン数 2300
4手のパターン数 11775
5手のパターン数 36571
6手のパターン数 51540
7手のパターン数 26640
8手のパターン数 1920
合計 131072 通り

最長手数は 8 手になりました。局面の総数はライトがすべて消えている完成形も含めて全部で 131072 通りになりました。ライツアウトよりも局面の総数が少なくて最長手数が短いという結果になりました。

ちなみに 4 行 4 列盤の場合、局面の総数は 65536 通りになるので、ライトがどんな点灯パターンでも解くことができます。それでは、盤を 4 行 5 列にするとどうなるのでしょうか。興味のある方は調べてみてください。

10月15日

●変形版・ライツアウト (2) の解答

10 月 10 日 に出題した「変形版・ライツアウト(2)」の解答です。

          [問題]               [解答]

  ■■■■      □□□□      ●●●●
  ■■■■ ─→ □□□□      ●●●●
  ■■■■      □□□□      ●●●●
  ■■■■      □□□□      ●●●●

   START          GOAL     ●：押すボタン  

        図 : 変形版ライツアウト(2)

最短手数は 16 手、つまり全部のボタンを押さないと解くことはできません。これが 4 行 4 列盤での最長手数の局面になります。ちなみに、n 行 n 列盤で全部のボタンを押すと、各ボタンの状態は 2n - 1 回（奇数回）反転することになります。したがって、n が奇数の場合でも、ボタンを全部押すと解くことができます。ただし、前回説明したように、n が奇数の場合は同じ行または列のボタンを n 個押した方が短い手数で解くことができます。

それでは、ここで問題です。5 行 5 列盤の最長手数は何手になるのでしょうか。興味のある方は挑戦してみてください。

10月10日

●変形版「ライツアウト」の解答

10 月 3 日 に出題したパズルの解答です。

            [問題]               [解答の一例]  

  ■■■■■      □□□□□      ・・・・・  
  ■■■■■      □□□□□      ・・・・・  
  ■■■■■ ─→ □□□□□      ●●●●●  
  ■■■■■      □□□□□      ・・・・・  
  ■■■■■      □□□□□      ・・・・・  
                
  ＳＴＡＴＲ       ＧＯＡＬ     ●：押すボタン  

            図 : 変形版ライツアウト

上図に示したように最短手数は 5 手で、同じ行または列のボタン 5 つ押すと、全てのボタンの状態を反転させることができます。

ちなみに、n 行 n 列盤で同じ行または列のボタンを n 個押した場合、押したボタンの状態は n 回反転し、それ以外のボタンは 1 回だけ反転します。押すボタンは同じ行または列にあるので、そのボタンの状態が n 回反転するのは自明ですね。したがって、n が奇数であればボタンの状態が奇数回反転するので、点灯しているボタンを消灯することができます。ほかのボタンは 1 回だけ反転しているので、これで全てのボタンを消灯することができます。

当然ですが、n が偶数の場合はこの方法で解くことはできません。そこで問題です。

          [問題]

  ■■■■      □□□□  
  ■■■■ ─→ □□□□
  ■■■■      □□□□
  ■■■■      □□□□

   START          GOAL

図 : 変形版ライツアウト(2)

それではパズルをお楽しみください。

10月6日

●ジオシティーズの統合

10 月 5 日より、旧ジオシティーズと拡張版ジオシティーズ（新ジオシティーズ）が統合されました。M.Hiroi's Home Page の移行手続きは無事に終了し、今までの URL http://www.geocities.co.jp/SiliconValley-Oakland/1680/ と新しい URL http://www.geocities.jp/m_hiroi/ のどちらからでもアクセスすることができます。

ただし、トラブルが無いわけではありません。トップページにあるジオシティーズのカウンタが正常に表示されないのです。新 URL からアクセスすると、M.Hiroi が設定したカウンタが表示されるのですが、旧 URL からアクセスすると別のカウンタが表示されます。どうやら、新 URL と旧 URL のアクセスを別々にカウントして表示しているみたいです。まあ、そのうちに修正されると思いますが、とりあえず、いま使っている「スゴいカウンター」を表示することにしました。

●追記

カウンタの動作ですが、ジオシティーズの カウンタヘルプ によると、

移行手続き後、旧ジオシティーズと新ジオシティーズのURLを両方とも残した場合、新ジオシティーズのカウンタツールは新ジオシティーズのURLでアクセスされれた方のみカウントされます。

とのことです。ようするに、今の動作が「仕様」だということです。これには M.Hiroi も驚きました。たぶん、旧 URL もずっと使えるのではなく、そのうちに廃止されて新 URL だけになるのでしょう。そうなったら、他の場所へ引っ越ししようかな、と思っています。

10月3日

●変形版「ライツアウト」

パズルのお話です。ライツアウトは「(株)タカラ」から1995年に発売されたパズルゲーム機で、光っているボタンをすべて消すことができればクリアとなります。ライツアウトのルールは拙作のページ ライツアウトの解法 をお読みください。

今回の問題は、ボタンを押したときの反転パターンを変えた「ライツアウト」です。

        [反転パターン]                    [問題]

  □□□□□      □□■□□    ■■■■■      □□□□□  
  □□□□□      □□■□□    ■■■■■      □□□□□
  □□□□□ ─→ ■■■■■    ■■■■■ ─→ □□□□□
  □□□□□      □□■□□    ■■■■■      □□□□□
  □□□□□      □□■□□    ■■■■■      □□□□□
                
   中央のボタンを押した場合     ＳＴＡＴＲ       ＧＯＡＬ

                  図 : 変形版ライツアウト

それではパズルをお楽しみください。

9月25日

●Interface 11 月号

ＣＱ出版社 発行の月刊誌 Interface 11 月号 (9/25発売) で、M.Hiroi は「高性能圧縮ツール bsrc の改良 bsrc2（後編）」を執筆しました。後編は三分割法によるブロックソートの高速化と 0-1-2 coding と混合法による圧縮率の改善について解説しています。圧縮アルゴリズムに興味のある方は読んでみてください。

9月22日

●140,000 Hit!

本日、カウンタが 140,000 を突破しました。多くの方にアクセスしていただき、とても嬉しく思います。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。最近は xyzzy Lisp のアクセス数が一番多く、次が Ｃ言語講座 で、その次が Perl/Tk になりました。

これからもがんばりますので、よろしくお願い申し上げます。

9月20日

●ジオシティーズの統合

10 月 5 日より旧ジオシティーズは拡張版ジオシティーズ（新ジオシティーズ）に統合されることになりました。旧ジオシティーズで公開されているページは「移行手続き」を行うことで簡単に新ジオシティーズへ移すことができ、今までの URL (http://www.geocities.co.jp/SiliconValley-Oakland/1680/) でも新ジオシティーズの URL でもページにアクセスすることができるようです。ただし、移行手続きには Yahoo! JAPAN ID が必要になります。

新ジオシティーズへ移行しても、今までの URL でアクセスできるのは大きなメリットだと思っています。M.Hiroi は Yahoo! JAPAN ID を持っているので、今のところ移行手続きを行って M.Hiroi's Home Page を新ジオシティーズへ移す予定です。なお、現在のゲストブックは旧ジオシティーズのもので 10 月 5 日までしか利用できません。新しいゲストブックは新ジオシティーズに移ってから用意する予定です。

しばらくの間、いろいろご迷惑をおかけするかもしれませんが、あしからずご了承くださいませ。

8月25日

●Interface 10 月号

ＣＱ出版社 発行の月刊誌 Interface 10 月号 (8/25発売) で、M.Hiroi は「高性能圧縮ツール bsrc の改良 bsrc2（前編）」を執筆しました。前編はマルチキークイックソートと二段階ソート法によるブロックソートの高速化について解説しています。圧縮アルゴリズムに興味のある方は読んでみてください。

8月18日

●『Coffee Cups Complex』 for X680x0

TAU さん が X680x0 用の新作ゲーム『Coffee Cups Complex』を発表されました。ゲームの内容は「回転パズル」です。パズルが好きな X680x0 ユーザーはぜひ遊んでみてください。

8月13日

●暑中お見舞いパズルの解答（２）

8 月 1 日 に出題した「数えて裏返すパズル」の解答です。このパズルはすべての石を裏返すことはできません。最後に白石がひとつ残ることになるので、裏返すことができる石の個数は最大で 8 個になります。実際、このパズルでは 8 個の石を裏返すことができます。手順の一例を示します。

• 8 個の石を裏返す手順（一例）

このパズルは 3 番目の石を裏返しにしますが、4 番目の石を裏返しにするとどうなるでしょうか。この場合、6 個の石しか裏返しにすることができません。興味のある方は、ちょっと考えてみてください。

8月1日

●暑中お見舞いパズル

さっそく問題です。

              ○                            ○ 1 <-- 白石を選ぶ 
            ／  ＼                        ／  ＼            
          ○      ○                    ○      ○ 2        
        ／          ＼                ／          ＼        
      ○              ○          1 ○ <-- 選ぶ     ● 3  3 番目の石を
    ／                  ＼        ／                  ＼  裏返しにする  
  ○───○───○───○    ○───●───○───○  
                                2       3
                                       裏返しにする

                    図 : 数えて裏返すパズル

それではパズルをお楽しみください。

●「数えて裏返すパズル」の解答（一例）

             ○                          ○ 1                      3 ●
           ／  ＼                      ／  ＼                      ／  ＼          
         ○      ○                  ○      ○ 2              2 ○      ○
       ／          ＼              ／          ＼              ／          ＼      
     ○              ○          ○              ● 3      1 ○              ●
   ／                  ＼      ／                  ＼      ／                  ＼  
 ○───○───○───○  ○───○───○───○  ○───○───○───○

             ●                          ●                          ●            
           ／  ＼                      ／  ＼                      ／  ＼          
         ○      ○                  ○      ○                  ○      ○ 1      
       ／          ＼              ／          ＼              ／          ＼      
   3 ●              ●          ●              ●          ●              ● 2  
   ／                  ＼      ／                  ＼      ／                  ＼  
 ○───○───○───○  ○───●───○───○  ○───●───○───●
 2       1                           3       2       1                           3

             ● 2                        ●                          ●            
           ／  ＼                      ／  ＼                      ／  ＼          
       1 ○      ● 3              3 ●      ●                  ●      ●        
       ／          ＼              ／          ＼              ／          ＼      
     ●              ●        2 ●              ●          ●              ●    
   ／                  ＼      ／                  ＼      ／                  ＼  
 ○───●───○───●  ○───●───○───●  ○───●───●───●
                             1                           1       2       3

7月10日

●祝！ M.Hiroi's Home Page 開設四周年

M.Hiroi's Home Page を開設してから本日でちょうど 4 年になりました。この 1 年間で 40,000 Hit を越えるアクセスがあり、1 日のアクセス数は平均で 116 Hit になりました。多くの方にアクセスしていただき、とても嬉しく思います。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。

これからもがんばりますので、今後ともよろしくお願い申し上げます。

6月25日

●130,000 Hit!

本日、カウンタが 130,000 を突破しました。多くの方にアクセスしていただき、とても嬉しく思います。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。

最近は Ｃ言語講座 のアクセス数が一番多く、次が xyzzy Lisp で、その次が Prolog になりました。Ｃ言語講座と Prolog は 4 月中旬頃からアクセス数が増加しています。学校の授業が始まって、学生さんのアクセスが多くなっているのかもしれませんね。

これからもがんばりますので、よろしくお願い申し上げます。

6月19日

●勝手にリンク

ソートアルゴリズムについて参考になるページを見つけたので紹介します。

• Tetsuo Shibuya's home page

渋谷哲朗氏の Web サイトです。講義資料 にある「ソートアルゴリズムⅡ (PDF ファイル) 」 では、基数ソート(radix sort)、マージソート、ソートの並列化など、ソートアルゴリズムについて説明されています。マルチキークイックソートや MSD radix sort など、文字列のソートに興味のある方はとても参考になると思います。

最後に、講義資料を公開されている渋谷哲朗氏に感謝いたします。

6月5日

●S-Prolog と節の入力

Prolog のお話です。10 年以上前の話になりますが、M.Hiroi がお世話になった Prolog 処理系に S-Prolog があります。S-Prolog は、佐藤隆さん が作成された MS-DOS 上で動作する Prolog インタプリタです。当時、M.Hiroi はパソコン通信をやっていなかったので、C MAGAZINE の付録ディスクから入手しました。

S-Prolog はソースが公開されているので、M.Hiroi は XGCC (X68000 用 GCC) でコンパイルして、X68000 上で S-Prolog を動かしていました。S-Prolog は他の環境への移植を考慮して作成されているので、X68000 に移植するのは簡単でした。あのころは X68000 上で S-Prolog を動かした方が快適だったのです。そして、S-Prolog は処理系とともに USER'S MANUAL も大変良くできているので、Prolog 初心者の M.Hiroi にはとても参考になりました。作者の佐藤隆さんに感謝いたします。

S-Prolog の場合、起動したあとプロンプト | が表示されて、節（事実や規則など）を入力する状態になります。ここが SWI-Prolog と違うところです。S-Prolog では、質問を入力するときに ?- を付け加える必要があります。簡単な例を示します。

| like( taro, coffee ).
| ?-like( taro, X ).

X = coffee ->;
no

このように、S-Prolog では端末から事実や規則をそのまま入力することができます。SWI-Prolog の場合、プロンプトが ?- なので、質問を入力する状態になっています。もしも、S-Prolog のように端末から事実や規則を入力したい場合は、consult や [ ] などプログラムを読み込む述語に user を指定します。user は標準入出力を指定する特別なファイル名です。

SWI-Prolog の簡単な実行例を示します。入力の終了は ^D (Ctrl + d) です。

?- [user].
|: foo( a, b ).
|: foo( c, d ).
|: （ここで ^D を入力）
% user compiled 14.55 sec, 528 bytes

Yes
?- foo( X, Y ).

X = a
Y = b ;

X = c
Y = d ;

No
?- 

このように、SWI-Prolog でも端末から事実や規則を入力することができます。Prolog のファイル入出力については、Prolog Programming で詳しく説明する予定です。

5月29日

●油分け算の解答

5 月 23 日 に出題したパズル「油分け算」の解答です。実はこのパズル、7 リットルの容器 A と 10 リットルの容器 B をひとつだけ使って、油を容器 B に 8 リットル入れることができます。ここではその手順を示します。

このように、7 リットルの容器 A と 10 リットルの容器 B を使って、油を 8 リットル計ることができます。あとはこの手順を繰り返すことで、10 リットルの容器 4 つに油を 8 リットルずつ入れることができます。もちろん、10 リットルの容器を複数使えば、もっと短い手数で油を分けることができると思います。興味のある方は挑戦してみてください。

5月23日

●油分け算

さっそく問題です。

それではパズルをお楽しみください。

4月6日

●120,000 Hit!

本日、カウンタが 120,000 を突破しました。多くの方にアクセスしていただき、とても嬉しく思います。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。

M.Hiroi's Home Page には 5 つのメインコンテンツがあり、それぞれのトップページに すごい！！カウンター のカウンタをつけています。2 月下旬ごろ、「すごい！！カウンター」が不調で値をリセットしてしまいましたが、最近は大きなトラブルもなく順調に動作しています。

最近のアクセス数は xyzzy Lisp が 1 位で、2 位が Ｃ言語講座、3 位が Perl/Tk memo になりました。今までは、3 月下旬から 4 月上旬にかけてアクセス数はガクッと減少するのですが、今年はトップページのアクセス数が平均で 100 Hit / day を下回ることがなかったので、ちょっと驚いています。

それでは、これからもがんばりますので、今後ともよろしくお願い申し上げます。

3月26日

●X68000 Emulator in Java 公開

M.Kamada さんの STUDIO KAMADA で X68000 Emulator in Java が公開されました。ソースリストも公開されています。いやー、本当にすごいですね。素晴らしいプログラムを公開された M.Kamada さんに深く感謝いたします。X68000 に興味のある方は STUDIO KAMADA へ GO!! です。

●頭の体操

M.Kamada さんの 日記 (3/24) で「頭の体操」が出題されています。このパズルは数字を環状に並べると難しくなりますが、1 から N までの数字を一列に並べて、隣り合う数字の和が平方数になることを条件にすると、もっと簡単になります。参考文献 によると、この条件では N = 15 で解があり、15 未満の場合は解がありません。興味のある方は挑戦してみてください。

3月21日

●勝手にリンク

またまたデータ圧縮のお話です。Guest Book では、大地さんから優れた方法を教えてもらいました。mtf5zle と BWT+OC の圧縮率にはとても驚きましたが、ほかにもブロックソートで高い圧縮率を達成している Web サイトがありましたので紹介します。

white page

yuu (yuta mori) さんの Web サイトです。『ここは、Suffix ArrayやBWTをあれこれする(?)ページです 。』 とのことですが、suffix array やブロックソート関連の最先端のプログラムが公開されている素晴らしいサイトです。

たとえば、ブロックソート後の処理 (2nd step とか 2nd stage と呼ぶ) では MTF が一般的ですが、ほかにもいろいろなアルゴリズムが考案されています。

• IF (Inversion Frequencies)
• AWFC (Advanced Weighted Frequency count)
• DC (Distance Coding)

white page では、2nd step 用のいろいろなプログラムとその実行結果 (Compression ratios, Compression times, Decompression times) が公開されています。M.Hiroi は上記のアルゴリズムを理解していませんが、結果を見ると、とても優れたアルゴリズムのようです。また、yuu さんが開発された mtfc, mtfc2 は、AWFC と同等以上の圧縮率を達成しています。zzip を越える圧縮率にはとても驚きました。

そして、これらのアルゴリズムの力を十分に引き出しているのが、レンジコーダの binary model です。簡単に説明すると、binary model は zzip のように記号を 2 種類に分けて、符号化に「二値算術符号（レンジコーダ）」を用いているところが特徴です。この方法には M.Hiroi の目からウロコが落ちました。

ブロックソートの符号化で、二値のレンジコーダを用いる方法は寡聞にして知りませんでした。white page には binary model の説明がないのでわかりませんが、yuu さんのオリジナルでしょうか。ブロックソート向きの優れたモデルだと思います。

このほかに、二段階ソート法や copy method など suffix array 関連のプログラムが多数公開されています。ブロックソートや suffix array に興味のある方は必見です。最後に、素晴らしいプログラムを公開されている yuu さんに深く感謝いたします。

3月17日

●bsrc の改良

データ圧縮のお話です。大地さんが Guest Book で紹介された改良型 MTF 法 (MTF5) を、拙作のプログラム bsrc ^[1] とその改良版 bsrc2 ^[*1] で試してみました。大地さんに感謝いたします。

bsrc2 の主な改良点 ^[*2] を示します。

1. ブロックソートに「三分割法(rate-2)」を採用
2. ブロックソート前のランレングスを廃止
3. ランレングス (ZLE + RLE) で RLE を行う連長を 3 から 7 に変更
4. 有限文脈モデルの最高次数を order-2 から order-3 に変更
5. 出現頻度表の合計値を基準にしたモデルの選択 (update exclusion を含む)
6. 出現頻度表の最大値を変更 (first code = 0x1000, second code = 0x800)
7. first code でモデルを選択する場合、記号 1 を 0 に変換する

7 について簡単に説明します。Zero Run Length (ZLE) の場合、記号 0 をランレングスで符号化し、連長を記号 0 と 1 で表します。したがって、first code の直前の記号列が (0, 1, 0) の場合、実際の記号は 0 が続いているわけです。そこで、実際の記号列に合わせて 1 を 0 に変換します。つまり、直前の記号列が (0, 0, 0) のモデルを選択するわけです。実際に試してみたところ、少しですが圧縮率が向上しました。

それでは、実行結果を示します。Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみました。プログラムは bsrc に MTF5 を適用したものが bsrc' で、bsrc2 に適用したものが bsrc2' です。ご参考までに bzip2 と zzip ^[2] の結果も示します

MTF5 の効果ですが、bsrc に適用した bsrc' の場合、kennedy.xls と ptt5 以外のファイルで圧縮率が向上しています。MTF5 はテキストファイルとの相性が良いようです。ところが bsrc2' の場合、圧縮率はかえって悪くなってしまいました。今回の改良は MTF5 と相性が悪いようです。MTF5 に合わせた改良が必要だと思われます。

bsrc2 はすべてのファイルで bsrc と bzip2 の圧縮率を上回っています。改良の効果は十分に出ていますね。今回の改良で bzip2 を越えることができたと思っています。しかしながら zzip にはかないません。zzip は kennedy.xls に対して特別な操作を行っているため、圧縮率が極端に良くなっています。これは例外だとしても、他のファイルで圧縮率を比較すると zzip の方が優れています。zzip は凄いですね。幸いにして、zzip はソースが公開されているので、興味のある方は読んでみてください。

3月1日

●旧ジオシティーズ新規登録終了

ジオシティーズの話です。旧ジオシティーズの新規ホームページ登録は 2 月 17 日で終了したそうです。

2003年11月26日の拡張版ジオシティーズの無料公開に伴い、2004年2月17日を持ちまして従来のジオシティーズの新規ホームページ登録を終了させていただきます。

なお、すでに従来のジオシティーズでホームページをお持ちの場合は、今後とも引き続きご利用になれます。

今後、ジオシティーズで新しいホームページを作成する場合は拡張版ジオシティーズになります。たぶん、そのうちに旧ジオシティーズは拡張版ジオシティーズに統合されると思われます。そろそろ引っ越し先を考えないといけないかな、と思っています。

2月24日

●日経ソフトウエア 4 月号

日経BP社発行の月刊誌 日経ソフトウエア 4 月号 (2/24発売) の「特集１ アルゴリズムでプログラミングの実力アップ」で、M.Hiroi は「Part 4 対戦型ゲームの思考ルーチンを作る」を執筆しました。「三目並べ」と「ロミオゲーム」を例題に、ミニマックス法とアルファ－ベータ法を説明しています。また、「Part 3 コンピュータでパズルを解こう」は コンピュータ＆パズル の高橋謙一郎さんが執筆されています。「やっかいな駐車場」というパズルを例題に、バックトラック、反復深化、幅優先探索を説明されています。興味のある方は読んでみてください。

1月26日

●たらいまわし関数

M.Hiroi's Home Page では、処理系の実行速度を比較するために「たらいまわし関数」を使うことがあります。たらいまわし関数には tarai と tak の 2 種類があるのですが、M.Hiroi は関数 tak しか知りませんでした。ぬえ 鵺 NUE の TAK Function に 2 つの関数があります。

関数 tarai は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄氏によって考案されたそうです。そして、関数 tak は関数 tarai のバリエーションで、マッカーシーによって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。今度はオリジナルの関数 tarai を使ってみたいですね。

●Interface 誌のアンケート結果

ＣＱ出版社 発行の月刊誌 Interface 2003 年 12 月号と 2004 年 1 月号で、M.Hiroi は「高性能圧縮ツール bsrc の理論と実装（前編・後編）」を執筆しました。2004 年 2 月号と 3 月号のアンケート結果によると、前編・後編どちらも第 11 位に入りました。21, 25 項目の中の 11 番目ですから、多くの方に関心を持ってもらえたのではないかと思っております。読者の皆様に厚くお礼申しあげます。

1月21日

●「スライドパズル」の最長手数

1 月 1 日 に出題した新春パズル「スライドパズル」の続きです。問題 A と B の最長手数の局面を求めてみました。次の図を見てください。

  ┌─┬─┬─┐  ┌─┬─┬─┐    ┌─┬─┬─┐   
  │６│３│１│  │３│１│１│    │２│00│４│   
  ├─┼─┼─┤  ├─┼─┼─┤    ├─┼─┼─┤   
  │00│５│１│  │６│５│  │ => │１│５│３│
  ├─┼─┼─┤  ├─┼─┼─┤    ├─┼─┼─┤   
  │４│  │２│  │４│00│２│    │１│６│  │   
  └─┴─┴─┘  └─┴─┴─┘    └─┴─┴─┘   
          最長手数の局面                 GOAL        

        図 : 問題 A の最長手数 (31 手) の局面

  ┌─┬─┬─┐  ┌─┬─┬─┐    ┌─┬─┬─┐  
  │６│４│１│  │４│２│１│    │１│５│３│  
  ├─┼─┼─┤  ├─┼─┼─┤    ├─┼─┼─┤  
  │５│00│２│  │６│00│  │ => │２│00│４│  
  ├─┼─┼─┤  ├─┼─┼─┤    ├─┼─┼─┤  
  │３│  │１│  │３│５│１│    │１│６│  │  
  └─┴─┴─┘  └─┴─┴─┘    └─┴─┴─┘  
          最長手数の局面                 GOAL       

        図 : 問題 B の最長手数 (31 手) の局面

どちらの問題も最長手数は 31 手になりました。興味のある方は 31 手で解けるか挑戦してみてください。

1月12日

●新春パズル「スライドパズル」の解答

1 月 1 日 に出題した新春パズル「スライドパズル」の解答です。

• 問題 A の解答（最短手順 16 手）
• 問題 B の解答（最短手順 26 手）

どちらの問題も 2 つある「１」を交換するところがポイントです。興味のある方は「最長手数の局面」を求めてみてください。局面の総数は「８パズル」と同じ 181,440 通りなので、プログラムは幅優先探索で簡単に作ることができます。

1月1日

●新春パズル

平成 16 年や 2004 年にちなんだパズルです。最初はお約束の「小町算」です。

  ┌─┬─┬─┐    ┌─┬─┬─┐    ┌─┬─┬─┐    ┌─┬─┬─┐  
  │２│00│３│    │２│00│４│    │１│４│６│    │１│５│３│  
  ├─┼─┼─┤    ├─┼─┼─┤    ├─┼─┼─┤    ├─┼─┼─┤  
  │１│４│６│ => │１│５│３│    │２│00│３│ => │２│00│４│  
  ├─┼─┼─┤    ├─┼─┼─┤    ├─┼─┼─┤    ├─┼─┼─┤  
  │１│５│  │    │１│６│  │    │１│５│  │    │１│６│  │  
  └─┴─┴─┘    └─┴─┴─┘    └─┴─┴─┘    └─┴─┴─┘  
      START              GOAL             START              GOAL       
               問題Ａ                              問題Ｂ

                            図 : スライドパズル

それでは、こたつでみかんでも食べながらパズルをお楽しみください。

新春パズル「スライドパズル」の解答

●問題Ａ

  (0)
  ２00３
  １４６
  １５□

  (1)     (2)     (3)     (4)     (5)     (6)     (7)     (8)
  ２00３  ２00３  ２00３  □00３  00□３  00４３  00４３  00４３  
  １４６  １４６  □４６  ２４６  ２４６  ２□６  ２１６  ２１６  
  １□５  □１５  １１５  １１５  １１５  １１５  １□５  １５□  

  (9)     (10)    (11)    (12)    (13)    (14)    (15)    (16)
  00４３  00４□  00□４  □00４  ２00４  ２00４  ２00４  ２00４  
  ２１□  ２１３  ２１３  ２１３  □１３  １□３  １５３  １５３  
  １５６  １５６  １５６  １５６  １５６  １５６  １□６  １６□  

●問題Ｂ

  (0)     (1)     (2)     (3)     (4)     (5)     (6)     (7)     (8)
  １４６  １４６  １４６  １４６  １４□  １□４  １３４  １３４  １３４  
  ２00３  ２00３  ２□３  ２３□  ２３６  ２３６  ２□６  □２６  １２６  
  １５□  １□５  １00５  １00５  １00５  １00５  １00５  １00５  □00５  

  (9)     (10)    (11)    (12)    (13)    (14)    (15)    (16)    (17)
  １３４  １３４  １３４  １３□  １□３  １２３  １２３  □２３  ２□３  
  １２６  １２６  １２□  １２４  １２４  １□４  □１４  １１４  １１４  
  00□５  00５□  00５６  00５６  00５６  00５６  00５６  00５６  00５６  

  (18)    (19)    (20)    (21)    (22)    (23)    (24)    (25)    (26)
  ２１３  ２１３  ２１３  ２１３  □１３  １□３  １５３  １５３  １５３  
  １□４  １５４  １５４  □５４  ２５４  ２５４  ２□４  ２00４  ２00４  
  00５６  00□６  □00６  １00６  １00６  １00６  １00６  １□６  １６□