ネタ本を新たに発掘しました。『マイコンとパズルの世界　BASICプログラミング頭の体操』〔小谷 善行, 産報出版, 1981.〕。

プロジェクトの本文や、活動報告についての感想、ご意見、ご質問を、ぜひコメントでお寄せいただければと思います。現在は支援募集期間中であり、本企画の実施期間ではないため、お寄せいただいた感想などについてはリターンとしてではなく、お返事や回答をさせていただきます。

また、私個人についてはこちらをご覧ください。

では本題、前回の続きです。

先の符号ビット表示のみを取り出し、そのまま並べてみます:
符号ビット表示
１１１１１１０　１１１１１１０
１１１１１１１０　１１１１１１１１０
０　１０
０　１０
１１０　１１１０
１１０　１１１０
１１１１０　１１１１１０
１１１１０　１１１１１０
１１１１１１１１１０　１１１１１１１１１１０
１１１１１０　１１１１０
１１１０　１１０
１１１０　１１０
１１１０　１１０
１０　０
１０　０
１０　０

さらに、これを8ビットずつの並びにしてみます:
2進表示
１１１１　１１０１　　　１１１１　１０１１　　　１１１１　１０１１
１１１１　１１００　　　１００１　０１１０　　　１１１０　１１０１
１１０１　１１１０　　　１１１１　１０１１　　　１１０１　１１１１
０１１１　１１１１　　　１１０１　１１１１　　　１１１１　１０１１
１１１０　１１１１　　　０１１１　０１１０　　　１１１０　１１０１
１１０１　１０１０　　　０１００　１００１
(最後に1ビット、1を付け加えています。)

16進表示
ＦＤ　ＦＢ　ＦＢ
ＦＣ　９５　ＥＤ
ＤＥ　ＦＢ　ＤＦ
７Ｆ　ＤＦ　ＦＢ
ＥＦ　７６　ＥＤ
ＤＡ　４９

この場合、元の32バイトが、17バイトに収まっています。もっとも、これはデータの部分だけですが。

なお、今回は、圧縮の対象のデータを8bit固定長としましたが、可変長でも構わないことに注意してください。

さて、この16進表示だけでは、元に戻せないので、戻すための辞書も作りましょう。前回の投稿分の、「ここで、これらに次のようにbit単位の符号を割り当てたとします」にこのようなデータがありました:
値　　回数　　ビット列
００　２　　　１１１１１１０
０１　１　　　１１１１１１１０
８０　１　　　１１１１１１１１０
０２　５　　　０
４０　５　　　１０
０４　５　　　１１０
２０　５　　　１１１０
０８　３　　　１１１１０
１０　３　　　１１１１１０
１Ｆ　１　　　１１１１１１１１１０
Ｆ８　１　　　１１１１１１１１１１０

ここで「回数」は必要ないので削除します。ついでに「ビット列」と「値」も入れ替えてみましょう:
ビット列　　　　　　　　値　　
１１１１１１０　　　　　００
１１１１１１１０　　　　０１　
１１１１１１１１０　　　８０　
０　　　　　　　　　　　０２
１０　　　　　　　　　　４０
１１０　　　　　　　　　０４
１１１０　　　　　　　　２０
１１１１０　　　　　　　０８
１１１１１０　　　　　　１０
１１１１１１１１１０　　１Ｆ　
１１１１１１１１１１０　Ｆ８　

これを、ビット列の長さで並べ替えます:
ビット列　　　　　　　　値　　
０　　　　　　　　　　　０２
１０　　　　　　　　　　４０
１１０　　　　　　　　　０４
１１１０　　　　　　　　２０
１１１１０　　　　　　　０８
１１１１１０　　　　　　１０
１１１１１１０　　　　　００
１１１１１１１０　　　　０１　
１１１１１１１１０　　　８０　
１１１１１１１１１０　　１Ｆ　
１１１１１１１１１１０　Ｆ８　

続いて「値」もビット列に直しましょう:
ビット列　　　　　　　　値　　　値のビット列　　
０　　　　　　　　　　　０２　　００００　００１０
１０　　　　　　　　　　４０　　０１００　００００
１１０　　　　　　　　　０４　　００００　０１００
１１１０　　　　　　　　２０　　００１０　００００
１１１１０　　　　　　　０８　　００００　１０００
１１１１１０　　　　　　１０　　０００１　００００
１１１１１１０　　　　　００　　００００　００００
１１１１１１１０　　　　０１　　００００　０００１
１１１１１１１１０　　　８０　　１０００　００００
１１１１１１１１１０　　１Ｆ　　０００１　１１１１
１１１１１１１１１１０　Ｆ８　　１１１１　１０００

さて、次にこの「ビット列」と「値のビット列」をくっつけます。この場合、「可変長 + 8ビット」という形式に決まっており、かつ「可変長」つまり「ビット列」の部分は “０” で終っていることに注意しましょう:
全体のビット列
０　００００　００１０
１０　０１００　００００
１１０　００００　０１００
１１１０　００１０　００００
１１１１０　００００　１０００
１１１１１０　０００１　００００
１１１１１１０　　００００　００００
１１１１１１１０　００００　０００１
１１１１１１１１０　１０００　００００
１１１１１１１１１０　０００１　１１１１
１１１１１１１１１１０　１１１１　１０００

では、これを8ビットずつにくっつけたり分割したりします:
全体のビット列 2進表示
００００　０００１　　０１００　１０００　　０００１　１０００
０００１　００１１　　１０００　１０００　　００１１　１１００
０００１　０００１　　１１１１　００００　　１０００　０１１１
１１１０　００００　　００００　１１１１　　１１１０　００００
０００１　１１１１　　１１１１　０１００　　００００　０１１１
１１１１　１１００　　００１１　１１１１　　１１１１　１１１１
１０１１　１１１０　　００１１　１１１１
(最後に１を6こ付け加えました。)

これにより辞書の部分は20バイトとなります。

では、これからもとの「辞書」を再現できるかやってみましょう。
まず、1ビットめは「０」ですから、符号は「０」のみで、以下の8ビットは元の値です。その8ビットは「００００　００１０」とわかります。その次のビット列は「１０」で、それに続く8ビットは「０１００　００００」だとわかります。さらにその次のビット列は「１１０」で、それに続く8ビットは「００００　０１００」だとわかります。以下略。

このようにすると、先のデータに対して辞書を加えて、17バイト + 20バイト = 37バイトとなりました。前回の投稿の「最後に8ビットごとの “□” と “■” の並びをそのままバイトに置き換えるとします」の箇所では32バイトでしたので、嬉しい結果ではありませんが、もとのバイト数が少なかったからというところでしょう。辞書は必要ですが、ここではデータ本体が32バイトに対して17バイトになったことでよしとしましょう。

これらの例は、すこしばかり不自然な面もありますが、データ表現やデータ圧縮の入口のネタには使えるのではないかと思います。もうすこし工夫が必要ですが。文字、それもアルファベットのようなシンプルなものではなく、絵や漢字にすると、面白さとしては違ってくるかと思います。

興味を持たれましたら、ぜひご支援や、コメントを頂ければと思います。