GUST NOTCH? DIARY

圧縮された本 / 真実のみを記述する会 (asin:4873100062)

真面目に読んでみましたよ。
この本、「圧縮」のところに「LZSS」とルビが振ってあります。
こちらで、最初のページのサンプルが見れます。

はい、この本は、LZSSアルゴリズムにより圧縮されたあるテキストの伸長手順を、自然言語でそのまま記述したものなのです。
読み始めればすぐに、これが何かの C++ プログラムであることも分かります。書いてしまいますが、大方の予想どおり、この本の本文を生成するプログラムです。正確には

  • テキストを LZSS 圧縮する機能
  • 圧縮されたテキストを伸長する機能
  • 圧縮されたテキストを伸長する手順を、TeX記法に従った自然言語で出力する機能

があるプログラムになります。
この本は、最初と最後の行以外は、このプログラムの出力をそのまま利用しています。

なので、最初はインタプリタ的に出力が確認できればいいかな、と思って、こんなのを作ってみたんですよ。

ところが、2ページ目の15行目にちょっと怪しい記述がありました。他のところでは半角スペースはちゃんと記号で示されているのに、ここだけただの空白。それでもなんとかそれっぽいコードが続いたのでそのまま続けていたのですが、25行目でまた妙な部分がでてきました。こんどは何かの文字が抜けている。さすがにこれは試行錯誤できるようにしないと正解がわからないかも、ということで、記述内容をデータ化して、それを読み込んで結果を出力できるコードを perl で書いてみました。
その結果分かったのは、15行目の「yen "」となっているところは6文字分、25行目の空の部分は2文字分の文字がないと整合性がとれないということです。
15行目の方は、プログラム中のエスケープ文字である 0x5C(バックスラッシュ/円記号)を TeX で出力するための部分なので、「yen」または「yyen」が含まれる必要があります。
一方25行目の方は、何かの2文字分のパターンを半角空白に置き換えている部分でした。その結果 TeX の出力では何もないように出力されてしまっています。何らかの空白文字か?と思ったのですが、コード中にでてくる他の空白類の文字は既に置換されています。使われていない文字を置き換える必要はないと思うので、どこかコード中に現れるものだと推測したのですが、印字可能文字を含めてしまうとそれが出力に現れてしまいます。
そんなわけで、ここには一体何が入るのか?半日悩んで答えが分かりました。
「全角スペース」でした。
「yen」の後ろにあったのは全角スペースだったのです。半角スペースは記号で可視化されていますが、全角スペースはそのままなのでただの空白に見えていました。そして「全角スペース」を「半角スペース」に置き換えるコードが含まれていたのです。前述のとおり、半角スペースはTeXでは表にでてきませんので何もないように見えていた、ということでした。
結局、この本に書いてあるとおりに書き出していっても、正しい出力は得られません。25行目のところで2バイト分の何かがあることが分からないと、参照元がずれてしまって正しいコードにならないからです。
これは元のコードの方に問題があります。コード中に全角スペースが使用されている必然性はないので、「yen」の後ろは半角スペースにして、全角スペースを半角スペースに置換するコードは削除する、というのが適切なものだと思います。
しかし、元のコードを直しちゃうと本の大半の部分が変わってしまうわけで……。
とりあえず、本に書いてある手順に沿って、この本文を出力できる正しいコードが記述できるようにするためには、25行目のところに「全角スペース」があることが分かるようにしないといけません。しかし、そのプログラムによる出力は「全角スペース」が消えてしまうものになります。また、最初の行の断り書きとして、「引用符内の漢字やカナ(非ASCII)は2文字と数える」ということを示さないと、文字数ではずれてしまいます。
なお、この本のタイトルは「圧縮された本」ですが、元のコードの方が文字数は少ないのでちよっと違和感があります。「LZSSされた本」という意味では正しいです。より正確には「LZSSしている本」でしょう。
ちなみに、正しく出力できたプログラム(lzss.cpp)は

  • g++ lzss.cpp -std=c++11

コンパイルできました。