積年の謎が溶けかかりつつあります それは Canonical Huffman Code

自分の尊厳というか、誇りをかけて CないしC++を用いて、DICOM XA viewerを自分が死ぬまでに作成したいのです。何回も何回も挑戦しては、挫折の連続でした。

その挫折の原因は分かっているのです、どうしてもそこで使用されている Huffman Codeの decodingアルゴリズムを理解できないのです。

DICOM XAは要するにパラパラ漫画です。一枚の漫画は、JPEG Losslessで格納されているのです。JPEG Losslessという企画はもう何十年も昔に制定された国際規格であり、その企画書も読みました。そこでは、HUFFTABという領域に、Huffman Codeによる圧縮をdecodeするためのキーが書かれているのです。そこまでは掴みました。

しかし、どんなアルゴリズムの解説書を読んでも、ハフマン圧縮されたデータをデコードするためには、ハフマン木のデータが必要としか書いていません。ところが、このHUFFTABにはそんな木構造のデータは無く、表形式のデータしか無いのです。

その謎が、急に溶け始めました。まず、以前購入して難しくて読めなかった、もう廃刊となっている書籍 オーム社刊行の「映像情報符号化」という本です。

昨日この本を読んでいて、あっと思いました。そこには、ハフマン圧縮を行って実際に画像情報を圧縮するためには、いちいちハフマン木を作成しては効率が悪いので、テーブル参照法を用いると書いてありました。どうやらこれが求める回答のようでした。どうしてこんな大切なこと、他のアルゴリズムの数ある書籍には一言も記載が無いのでしょうか。

そして、本日届いた英語の書籍 “Managing Gigabytes” という本をチラチラ見ていたら、ついに見つけました。そのアルゴリズムを Canonical Huffman Codes と呼ぶらしいのです。あー 時間を相当そうですね、かれこれ4年間無駄にしました。最初にこれを知っていれば・・・

もっとも、JPEG Losslessなんて今時デジカメにも使用しないし、 DICOM XAでしか残っていない過去の遺物なので、それに用いる Canonical Huffman Codesなんてものも、世間から忘れ去られているのでしょうね。