ハフマン符号

初めに言っておくと、今回は失敗の記録だ。

前々回おまけで扱ったfoldTreeとunfoldTree。

「理屈としては」フィボナッチ数列の計算、なんつーのは確かに面白い。

ただし、だ。

果たして「実用に耐える機能なのか?」と言う疑いがどうにも拭えない。

実際、典型的な「使用例」も挙げてみたが、イマイチピンと来なかったんじゃないか。

俺も、だ(笑)。

unfoldTreeとfoldTree(Python版)
unfoldTreeとfoldTree(Racket版)

例を見ても「数値だらけ」だ。

例えばunfoldTree。seedを与えると計算式に従いつつ二分木を生成する。

ただ、いつぞやも見たが、数値だけの木、なんぞ作ったトコで面白くも何ともないんだ。

そして実用性は全くない。

むしろ僕らが興味があるのは、例えば河北彩花と言う文字列をseedとして与えた時に、FANZA AV女優ランキングな二分木を作れる技術なんだ。しかし、河北彩花から石川澪を「計算して作り出」せるのか。当然、そこに「汎用的な計算法」は存在しない。

僕らが「計算で」作れるなら作ってみてぇ二分木。
しかし、各人の「名前のデータ」からお互いの名前を「規則的に」生成する事は不可能なんで、単なる画餅となる。

となると、HaskellのData.Treeモジュールが何の為に存在するんだか、サッパリ分からなくなる。

一つの利用法として考えられるのは、一旦二分木を数値で作っておいて、その数値に、例えばAV女優の名前を関連させていく、ことだ。

FANZA AV女優ランキングの「順位」をキーにしたいなら、これはこれでいいだろう。一方、「名前」で検索、なんか考えるとこの方法は役に立たない。

つまり、どう考えても、unfoldTreeは数値を与えて木を生成するくらいにしか役に立たないんだ。こんな「機能限定」の関数なんざクソだ、って言い切っていいだろう。

また、foldもunfoldも前回見た通り、非常に強力な関数だ、って事は分かったと思う。一方、foldTreeとunfoldTreeには全然汎用性がない。「数学的な構造をfold/unfoldと共有しながら」この非力さは何やねん、って言うのが正直な感想だ。

今んトコ、クソ関数コンビだ、って言って良いくらいだ(笑)。「理論」以外何もありゃしねぇ(苦笑)。

実は前回の「圧縮と解凍」の記事で、最初に考えてたのは「foldTreeとunfoldTreeの実用例になりそうなネタが何かないかな?」だったんだ。つまり、シードの与え方によっては自動で自在な木を生成する、と。と言う事はシードが何らかのデータだとしたら「情報を圧縮して持ってないとならない」と。となると、foldTreeは何らかのデータ形式をコンパクトに「纏めな」アカンだろ・・・と考えていって「あ、これって圧縮と解凍だよな」と思いついた、と。

「fold/unfoldと圧縮/解凍の関連性」は言わばその前哨戦のつもりだったんだ。つまり「何らかのデカイデータ構造をfoldTreeとunfoldTreeで圧縮出来たり解凍出来る?」と。

それで二分木みたいな、場合によっては巨大化するデータをfoldTreeやunfoldTreeを使って圧縮・解凍出来る例が何かないのか、とWeb検索してはみたんだ。僕程度が思いつくアイディアなら当然誰かが既にやってんじゃねぇの、と。

ところが何もない。

いや、ちと待てよ、と。だったらやっぱfoldTreeとunfoldTreeは画餅関数、って事になるんじゃないか、と。

検索ワードを変えてみて、「二分木圧縮解凍」で検索してみた。そうしたらハフマン符号、と言うアルゴリズムに辿り着いた。これは圧縮/解凍のエンコード/デコード規則を二分木で作る、と言うアルゴリズムだ。

「これはfoldTreeやunfoldTreeを上手く使えるネタになるか?」

と思って期待したんだが・・・結論から言うと全く出番がなかった。要はやっぱり、foldTreeやunfoldTreeという関数は、極めて限定的な、全くと言っていいほど汎用性が無い関数だ、って事だ。具体的に言うと、やっぱ「数値しか扱えない」。

マジな話、いくら数理的なバックグラウンドが共通してようと、foldと言う名前を冠して欲しくないくらい、使い勝手が全く無い関数だったんだよ。怒り心頭だ(笑)。

あまりに怒髪天を衝いてたんで、俺がなろう作家だったら怒りに任せて、思わず

「数値しか扱えないじゃないか」とfold侯爵家を追放された俺は冒険者になったけど、チートなしでやっぱり数値しか扱えなかったんでお先真っ暗です

と言ったタイトルのラノベを書き始めるトコだったわ(笑・※1)。

いや、書かんけどな(笑)。

深夜アニメ化するかい(笑)?

具体的には、Wikipediaのハフマン符号化のアルゴリズムを見ながらRacketで実装していって、foldTree/unfoldTree使用のチャンスを探す、ってなカンジで作業していったんだが、全く出番がない。むしろ、実装途中では単なるfoldの登場がガンガンあって、図らずも如何にfold/reduceと言う関数が強力なのか、またしても証明するハメになっちまった。

そして、最悪な事に、Racket/Pythonでハフマン符号化のアルゴリズムを実装する事は出来るが結果が面白くない。

ハッキリ言おう。ブログの記事としては大失敗だ(笑)。実装結果がツマラン、と言う事はネタ選びにも失敗してる、ってこった(笑)。

しかし、せっかく実装しちまったんで、紹介だけはしておこうと思う。畜生め(苦笑)。

まずはザーッとWikipediaでハフマン符号の構成と言う部分を見てきて欲しい。

実際、二分木を使うのは、圧縮/解凍規則、要はエンコーディング/デコーディングルールを作成する際、なんだ。つまり、この技術は二分木そのものを圧縮/解凍するものではない。

ぶっちゃけ、最初にハフマン符号を見つけた際に、

「う〜む、これ、何か違うんじゃね?」

と悪い予感はしてたんだ(笑)。ただ、一回実装してみなけりゃ何とも言えんし、zip圧縮にも関わってるアルゴリズムだ、っつーんで興味が先に立っちまったんだよな。

さて、ハフマン符号に於いての圧縮/解凍のエンコーディング/デコーディング規則を生成する二分木をハフマン木と呼ぶらしいが、この構成手順はWikipediaに依ると、次のように書かれている。

「データに出現する文字の出現回数」なんつーのは簡単に求まるだろう。

RacketならSRFI-1のalist-consとalist-deleteを用いた実装をまずは考える。つまり、「連想リスト」対象に、キーを文字、出現回数を値とした「更新」を考えるわけだ。

単純に言うと、例えばデータ"DAEBCBACBBBC"と言う文字列に対して、次のような事をやればいいわけだ(fold利用だ!)。

> (foldl (lambda (elt lst)
　　　　(cond ((assv elt lst)
　　　　　　　　=> (lambda (x)
　　　　　　　　　　(alist-cons elt (add1 (cdr x))
　　　　　　　　　　　　　　　(alist-delete elt lst))))
　　　　　　　(else (alist-cons elt 1 lst)))) '() (string->list 　　　　　　　　　　　　　　　　　　　　"DAEBCBACBBBC"))
'((#\C . 3) (#\B . 5) (#\A . 2) (#\E . 1) (#\D . 1)) ;; 返り値

畳み込み対象は'()となり、ここが最終的に連想リストになり、返る。ここがアキュムレータだ。

(assv elt lst)でアキュムレータ内にeltとしてやってきたキーと値のペアが見つかったらその値を+1する、そうじゃなければ「初めて見つかったeltなんで、値を1としてアキュムレータにeltとのペアをalist-consする。

ロジックとしては簡単だろう。むしろ、ここで気をつけるのは、「関数型プログラミングで連想リストを扱う場合」、データの破壊的変更を避ける為、一旦該当データを連想リストから取り除く(alist-delete)せなアカン、って事だ。

さて、手順を確認する。

まず、葉を含むすべての節点のうち、親を持たないものを集める。

もう返り値がリストな以上、「親を持たないもの」は既に勝手に集まってる。

その中から、最小の値を持つものと2番目に小さい値を持つものを取り出す。

これは、リストの中で「値が最小な値」から昇順にソートしろ、って事を指す。

取り敢えずこの後、「文字」より「値」が重要なアルゴリズムに入っていくんで、文字と値の順序を変えたリストを要素にするフツーのリストを生成する。その要素が昇順に並んでいればいい。

ここまでを、まずは一つの関数として纏めてしまおう。

;; 各要素の発生回数を数える
(define (countDatum data)
　(map (match-lambda
　　　　　((cons n c) `(,c ,n)))
　(sort
　　(foldl (lambda (elt lst)
　　　　　(cond ((assv elt lst)
　　　　　　　　=> (lambda (x)
　　　　　　　　　　(alist-cons elt (add1 (cdr x))
　　　　　　　　　　　　　　　(alist-delete elt lst))))
　　　　　　　　(else (alist-cons elt 1 lst))))
　　　　'() (string->list data)) #:key cdr <)))

実行するとこうだ。

> (countDatum "DAEBCBACBBBC")
'((1 #\E) (1 #\D) (2 #\A) (3 #\C) (5 #\B))

Pythonで同様のロジックを書くと次のようになる(from functools import reduceしてるもの、とする)。

# 各要素の発生回数を数える
def countDatum(data):
　def foo(d, elt):
　　try:
　　　d[elt] += 1
　　except KeyError:
　　　d[elt] = 1
　　finally:
　　　return d
　return sorted([[v, k] for k, v in reduce(foo, list(data), {}).items()])

辞書型に対しては「破壊的変更」なんだけど、外枠のreduceの初期値(辞書)は非破壊的に更新されていく。要は関数fooの返り値によって辞書型がすげ替えられていくんだ。

よって、キーが存在する場合、しない場合に応じて辞書のキー(elt)によって辞書の値は破壊的に更新されるが、関数fooは必ず辞書そのものを返さないとならない。そのための例外処理のfinally節だ。ここも必ず実行される。

そしてreduceによって形成された辞書型はitemsメソッドによってビューオブジェクトと言うイテラブルに変換される。あとはリスト内包表記でキーと値の位置を取り替え、昇順に並べ変えればいい。

>>> countDatum("DAEBCBACBBBC")
[[1, 'D'], [1, 'E'], [2, 'A'], [3, 'C'], [5, 'B']]

そして次のプロセスに移る。

それらを子供に持つ新しい節点を作る。このとき、新しい節点の値は、両方の子供の値の和とする。
以上を根節点に到達するまで繰り返すと、木が完成する。

ここで「木を生成」するんだが・・・・・・。ルール自体は簡単だ。ここでunfoldTreeが使えるか?とちょっと期待したんだけど、unfoldTreeには次の重大な欠陥がある。

それは

unfoldTreeは根(ルート)からしか木が生成出来ない。

いきなり頓挫だ(笑)。上のプロセスを見てみれば分かるが、ハフマン木は葉から根に向かって生成された木だ。従って、このケースでは使用不可能なんだ。

葉から根に向かって二分木なんて作れるの?って思うかもしれんけど作れる。どうやって作るのか、っつーとまたもやfold関数で作れちゃうんだ。unfoldTree要らないやん(笑)。

Wikipediaの指示に従ってハフマン木を生成する関数は次のように、foldを使ってすぐ書ける。

;; ハフマン木を生成
(define (generateHuffman lst)
　(foldl (lambda (elt lst)
　　　　(if (null? lst)
　　　　　elt
　　　　`(,(+ (car elt) (car lst)) (,elt ,lst))))
　　　'() lst))

実行結果はこうだ。

> (generateHuffman (countDatum "DAEBCBACBBBC"))
'(12 ((5 #\B) (7 ((3 #\C) (4 ((2 #\A) (2 ((1 #\D) (1 #\E)))))))))

Wikipediaで紹介されているような二分木になってるだろう。

Pythonでもreduceを使えばお茶の子サイサイ、だ。

# ハフマン木を生成
def generateHuffman(lst):
　return reduce(lambda lst, elt: elt if lst == []
　　　　　　　　else [elt[0] + lst[0], [elt, lst]], lst, [])

# 実行
>>> generateHuffman(countDatum("DAEBCBACBBBC"))
[12, [[5, 'B'], [7, [[3, 'C'], [4, [[2, 'A'], [2, [[1, 'E'], [1, 'D']]]]]]]]]

もう、fold/reduce強力過ぎ(笑)。Wikipediaに言われた通り、fold/reduce一本槍、でここまで来れる。

しかし、次のステップがまた問題なんだ。

次に、根から順に左右に0と1の値を割り振っていく（左右のどちらに0と1を与えるかは任意）。すると、それぞれの葉（記号）に対して、一意にビット列が与えられる。この記号とビット列の関係をもとに、もとのデータの記号をビット列に変換していくことで符号化が行われる。

一つ目はまたもやunfoldTree(Haskell版)の機能の限界、もう一つはここでの「ビット演算」がどんな操作なのか、伺う事は出来てもハッキリした事は書いてない、んだよな。

もうちょっと細かく見てみよう。上のプロセスの1つ目のポイントは、要はさっき作り上げたハフマン木がデータとして持ってる「数値」を別の数値で置き換えろ、と言ってるんだ。

そして、その木の「置き換え」の方向性は、今度は根から始めて葉の方向へ辿れ、と言ってる。また、根が0で(この場合は、12を0に置き換える)左に進めば0、右に進めば1と・・・その意味はともかくとして振り分けていく。

この「新しい番号付け」をどうするか。これは、元々のアイディアから言うと、

unfoldTreeがシードに二分木を受け取り、その木を「コピー」出来るか否か

にかかってるんだよ。

つまり、「複製しながら数値を改変」出来れば、この問題は一気に終了へと近づく。

近づく、んだが・・・・・・。

結論から言うとここでもHaskellスタイルのunfoldTreeはクソの役にも立たなかった(笑)。

原因が何か、ってのもハッキリしている。それは

HaskellのunfoldTreeが想定してる木は葉が空リストでないとならない。

ととんでもない仮定になってんだ(笑)。つまり「葉のスタイルまで」指定されてて、雁字搦めなんだ。

もう一回、RacketやPythonが返したハフマン木を見てみよう。

;; Racket
'(12 ((5 #\B) (7 ((3 #\C) (4 ((2 #\A) (2 ((1 #\D) (1 #\E)))))))))
## Python
[12, [[5, 'B'], [7, [[3, 'C'], [4, [[2, 'A'], [2, [[1, 'E'], [1, 'D']]]]]]]]]

見りゃ分かるが、葉が「文字」になっている。しかし、これを「終了サイン」とする事が出来ないんだ。

前々回見たHaskell流のunfoldTreeの定義を思い出そう。

;; Racket
(define (unfoldTree f b)
　(match-let ((`(,a ,bs) (f b)))
　　`(,a ,(map (lambda (b)
　　　　　　　(unfoldTree f b)) bs))))
## Python
def unfoldTree(f, b):
　match f(b):
　　case a, bs:
　　　return [a, [unfoldTree(f, b) for b in bs]]

これらは再帰関数だが、もっと正確に言うと「再帰関数をリストにマッピング」(Pythonではリスト内包表記でリストの各要素に再帰関数を適用)している。

と言う事は変数bsはリストじゃなきゃならない。しかし、葉が文字だと、再帰途中で「リストではない文字が」bsに束縛されてしまう、って事なんだ。

これが、Haskell版unfoldTreeがシードとして葉が空リストである二分木じゃなきゃいけない理由だ。そしてだからこそunfoldTreeは二分木をコピー出来ない。

ダセェ(笑)。

しかし、unfoldTreeを使わない(と言うか使えない)状態だと、二分木を「コピーする」のは結構厄介だ。そう、この「数値挿げ替え」は本質的には二分木のコピーなんだ。

ここでは二分木をリストで実装してるが、実はリストで実装すると二分木は長さが必ず2になる。上のハフマン木の計算結果を見ると、かなり複雑に見えるだろう。しかし「長さは2」なんだ。

しかし長さが2でもリストのリストのリストの・・・となってるから複雑に見えるわけだ。言い換えるとリストが繰り込まれていて、こいつを「処理」してくのが厄介なんだよ。

さて、二分木のコピーに付いて論じる前にもう一つ、Wikipediaに書いてる「忖度アリ」のアルゴリズムの話に話を移そう。

次の写真を見て欲しい。

ハフマン木が、ルート(根)から始まって、左に進むと0、右に進むと1、ってのは良く分かる。

一方、得られた符号が「何故にそうなってんだ」ってのは「予想は出来る」が、かと言って、「どういう演算を採用してる」かはハッキリとは書いてない。

根から順に左右に0と1の値を割り振っていく（左右のどちらに0と1を与えるかは任意）。すると、それぞれの葉（記号）に対して、一意にビット列が与えられる。

これだと「一意にビット列が与えられる」根拠にはならない。文字Bに0が振り分けられるのは分かるが、文字Cが10になる「根拠」は全く書かれてないし、また、そういう「ビット演算」が何なのか、は一般論ではないわけだ。

多分気づく人は気づくだろうが、0か1かの経路だけではなく、1が得られた時、累積的に2^xが適用されていく、ってのがこの計算の根拠なんだ。何故なら、2進数だと、桁が一つ上がる度に2が掛けられていく、からだ。

つまり、Bは 0 + 2^1で2、つまり2進数で10となっている。同様にAは0 + 2^2 + 2^1 = 6、つまり2進数では110、Dは0 + 2^3 + 2^2 + 2^1 = 14で2進数では1110、Eは例外的に1 + 2^3 + 2^2 + 2^1 = 15で2進数では1111、となる。

と言う事は、まずはハフマン木の葉、特に1を指定された経路には1を「足していった」累積結果を持たせて、最終的にそれを利用した「2の累乗の和」を取り、葉の値として与えなアカンわけだ。

;; Racket
;; 符号情報を作成
(define (codeInfo n)
　(apply + (map (lambda (x)
　　　　　　　　(expt 2 x)) (range 1 (add1 n)))))

# Python
# 符号情報を作成
def codeInfo(n):
　return sum([2 ** i for i in range(1, n + 1)])

ところで、「左に進めば0」「右に進めば1」とか言ってたのに何でこんなシチ面倒臭い計算になってんだろ?本当にこれで「圧縮」ってのが上手く行ってるんだろうか?

実際、僕らみたいに「超高級言語に慣れてる」とビットの世界は正直良く分からん。

分からんが、結論から言うと、例えばWikipediaに載ってる例ではDAEBCBACBBBCと言う文字列は1110110111101001101000010に変換される。25ビットの長さの「情報」だ。

んで、ハフマン木が最終的に作り出すエンコーディング/デコーディングルールは、今回は次のようになってる。

ここで、25ビットデータである1110110111101001101000010を先頭から見ていく。

1はデコード表にないんで次の1も合わせて引っこ抜く。でも11もデコード表にない。次の1も引っこ抜けば合わせて111だがこれもデコード表にない。次は0なんで合わせて1110で、これがデコード表のDと一致するんでDにデコードする。

残りは21ビットデータである110111101001101000010。1はない、11はない、110なんでここまででAが確定。残りは18ビットの111101001101000010・・・。

とビット列の先頭から見ていった際に「デコード表で意味が確定する」トコまで読んでデコーディング、ってのが仕組みなわけだ。

だから結果、性質的にはハフマン符号化、ってぇのは「1が単独で存在する事」はない。そして、0が直接文字と解釈されるのは「いきなりあるビット列の先頭が」0になってる時以外はあり得ないわけ。確かにメモリに0と1しか並んでなくて、そのクセそれを「自然と意味を確定させる」には上手い方法だ。

これを作り出す為に先ほどのcodeInfo関数を作ったわけだが、まぁ、超高級言語を使ってる我々としては、ビットの世界はやっぱピンと来ない(笑・※2)。

さて、codeInfo関数を作ったので、「二分木をコピーしながら改変」の問題へと戻ろう。

平たく言うと、この「作業」自体は単に再帰を使えばいい、って事になる。

;; 再帰版
(define (value2code tree)
　(match-let ((`(,x ,xs) tree))
　　(if (char? xs)
　　　`(,(add1 (codeInfo (sub1 x))) ,xs)
　　　(match-let ((`((,m ,left) (,n ,right)) xs))
　　　　(let ((k (codeInfo x)))
　　　　　`(,x ((,k ,left) ,(value2code `(,(add1 x) ,right)))))))))

木を受け取った時にそれを先頭(x)とそれ以外(xs)へと分解する。

取り敢えず終了条件としては「それ以外」が文字だった際に、文字のエンコード/デコードルール(数値)と文字データのペアを使ってそれを返す。

それ以外の場合再帰に入るわけだが、Wikipediaの解説を見る限りハフマン木には特徴がある。それは、左の子は常に葉になってる、って事だ(※3)。

つまり、親と左の子が単純データとして「確定」してる以上、再帰対象は右の子、となる。そして右の子だけを見た場合の根(ルート)は親の数値に1を加算したモノ、となるわけだ(何故なら経路が1だから)。

> (generateHuffman (countDatum "DAEBCBACBBBC"))
'(12 ((5 #\B) (7 ((3 #\C) (4 ((2 #\A) (2 ((1 #\D) (1 #\E)))))))))
> (value2code (cons 0 (cdr (generateHuffman (countDatum "DAEBCBACBBBC")))))
'(0 ((0 #\B) (1 ((2 #\C) (2 ((6 #\A) (3 ((14 #\D) (15 #\E)))))))))

ハフマン木の構造がそのままコピーされ、なおかつ数値が更新されてるのが分かるだろう。

なお、下で(cons 0 (cdr (generateHuffman (countDatum "DAEBCBACBBBC"))))してるのは、ルート(根)の値を0にする為だ。

さて、上の関数value2codeは再帰関数だ。

一方、SchemeやRacketをやってると、「単なる再帰」だと効率が悪そうだな、と思う。

どうしても末尾再帰の方が良くないか?って考えちまうわけだ。末尾再帰最適化を頼りたくなっちまうんだな。

一方、このテの関数は「初見」時に末尾再帰最適化が可能なのか、パッと見分からなくなる。

んで、こういう場合、一旦再帰関数を、川合史朗さんが書いた「なんでも継続」を読みながら「継続受け渡し方式」に書き換えてしまえば、「理論的に」末尾再帰化が可能なのか不可能なのかが判定が出来る。

;; 継続受け渡し方式版
(define (value2code/cps tree cont)
　(match-let ((`(,x ,xs) tree))
　　(if (char? xs)
　　　(cont `(,(add1 (codeInfo (sub1 x))) ,xs))
　　　(match-let ((`((,m ,left) (,n ,right)) xs))
　　　　(let ((k (codeInfo x)))
　　　　　(value2code/cps `(,(add1 x) ,right)
　　　　　　　　　　　　　(lambda (u)
　　　　　　　　　　　　　　(cont `(,x ((,k ,left) ,u))))))))))

value2code/cpsは末尾再帰呼び出しされている。

んで、川合史朗さんがサンプルとして挙げてるleaf-count/cpsと違って末尾再帰呼び出しは1段階のみ、だ。

平たく言うと理論的には、継続受け渡し形式で、1段階で再帰呼び出ししてるパターンはフツーの末尾再帰関数へと書き換える事が出来、末尾再帰最適化が可能だ。

一方、leaf-count/cpsのように、末尾再帰呼び出しが2段階以上だとフツーの末尾再帰関数として記述は出来ない。何故なら末尾再帰関数内で再帰する、って事は内側の「呼び出し」が末尾再帰になってないから、だ。これは継続受け渡し方式では末尾再帰に「見える」が、末尾再帰最適化は保証されない、んだ。

さて、「理論的には」value2codeは末尾再帰化出来る事は分かった。一方、アキュムレータ部分を「木として構築する」のが実は厄介なんだな(苦笑)。

継続受け渡し方式を参考にして次のように書いても思いっきり失敗するだろう(笑)。

;;; ダメな例
(define value2code/tco?
　(case-lambda
　　((tree acc)
　　(match-let ((`(,x ,xs) tree))
　　　(if (char? xs)
　　　　`((,(add1 (codeInfo (sub1 x))) ,xs) ,acc)
　　　　(match-let ((`((,m ,left) (,n ,right)) xs))
　　　　　(let ((k (codeInfo x)))
　　　　　　(value2code/tco? `(,(add1 x) ,right)
　　　　　　　　　　　　　　`(,x ((,k ,left) ,acc))))))))
　　((tree)
　　(value2code/tco? tree '()))))

> (value2code/tco? (cons 0 (cdr (generateHuffman (countDatum "DAEBCBACBBBC")))))
'((15 #\E) (3 ((14 #\D) (2 ((6 #\A) (1 ((2 #\C) (0 ((0 #\B) ())))))))))

実行すると何だかおかしな値が返ってくるだろう(笑)。

そう、フツーに再帰すれば「リストの順序が保持」されるが、末尾再帰で書くと「逆順で返ってくる」ってのは良くある。

フツーのリスト相手じゃそれでもいいんだけど、二分木相手だと大変だ。「繰り込みの順番」が逆なんで、根になって欲しいモノが奥深くの葉になり、奥深いトコにあった筈の葉がルートになってしまう。

これじゃアカンがな。

これの一番簡単な解決法は、ハフマン木の親と左の子と空リストを要素としたリストに一旦してしまってアキュムレータ(acc)に詰め込み、計算終了時に二分木へと再構成する事だ。

;; 末尾再帰版
(define value2code/tco
　(case-lambda
　　((tree acc)
　　(match-let ((`(,x ,xs) tree))
　　　(if (char? xs)
　　　　(foldl (lambda (y x)
　　　　　　　(match-let ((`(,parent (,left '())) y))
　　　　　　　　`(,parent (,left ,x))))
　　　　　　`(,(add1 (codeInfo (sub1 x))) ,xs) acc)
　　　　(match-let ((`((,m ,left) (,n ,right)) xs))
　　　　　(let ((k (codeInfo x)))
　　　　　　(value2code/tco `(,(add1 x) ,right)
　　　　　　　　　　　　　(cons `(,x ((,k ,left) '())) acc)))))))
　　((tree)
　　(value2code/tco tree '()))))

つまり、再帰時点で、ハフマン木から

'((15 #\E) (3 ((14 #\D) ())) (2 ((6 #\A) ())) (1 ((2 #\C) ())) (0 ((0 #\B) ())))

と言うリストを生成する。各要素は先頭を除いて、まるで「右の子が空リストの木」に見える要素となっている。

計算停止時点に於いて、foldを用いてリストの先頭からその空リストへ要素を「はめ込む」様に「畳み込んで」行く。結果、元のようなハフマン木を生成出来る、って寸法だ。

ここでまたしてもfoldの強力さ、が見て取れるだろう。

なお、Pythonはいつも言ってる通り、再帰が苦手なんで、whileでRacketの末尾再帰版をエミュレートする必要がある。

# Python版
def value2code(tree):
　def foo(x, y):
　　match y:
　　　case [parent, [left, []]]:
　　　　return [parent, [left, x]]
　acc = []
　　while True:
　　　match tree:
　　　　case [x, xs]:
　　　　　if isinstance(xs, str):
　　　　　　return reduce(foo, acc, [1 + codeInfo(x - 1), xs])
　　　　　match xs:
　　　　　　case [[m, left], [n, right]]:
　　　　　　　k = codeInfo(x)
　　　　　　　tree, acc = [x + 1, right], [[x, [[k, left], []]]] + acc

如何に3.10以降登場したパターンマッチ構文が強力なのか良く分かる例になってると思う。パターンマッチ構文がなければ(これでも複雑には見えるが)ここまでシンプルに書けない。

しかしながら、再帰も末尾再帰も知らない、言い換えるとPythonしかプログラミング言語の知識がない人には、こういう「ハフマン木をコピーして再構成」と言うコードを書き下すのはなかなか厄介なんじゃないか、って思う。書けてももっと複雑でゴチャゴチャしたコードになるんじゃないか。

言い換えると、実際そんなに使わないでも、「再帰」と言う考え方自体が如何に強力な発想なのか、って事を実感して欲しい。

それを知る、のと知らない、では大きく違うんだ。

再帰を外したトコに「プログラミングの基礎」なんぞは存在しない。

さて、ハフマン木を再構成はしたが、それだけでは役に立たない。

ハフマン符号は以前見たランレングス圧縮とは違い、「どんなデータでも圧縮・解凍出来る」普遍的な変換規則を提供しない。あくまで特定の「与えられた」データに対して、「尤も効率の良い」変換規則を提供する。

つまり、「符号化」の為のルールをデータによって変えて提供する、ってのがハフマン符号化のキモ、なんだ。データAに対してはルールAを提供するが、このルールAはデータBには適用出来ない。あくまで「特定のデータに対して」圧縮・解凍の「ルール」を提供する、ってわけだな。

従って、エンコード規則やデコード規則を記述した「変換テーブル」を生成しないといけない。具体的にはハフマン木の「葉」のデータを拾い集めた「変換テーブル」を作るわけだが。

ここでfoldTreeが使えるか?と思ったがまたしても使えない(苦笑)。理由は同じだ。foldTreeが扱える二分木は葉が空リストじゃなきゃいけないから、だ(笑)。Haskell流定義だとmapで再帰関数をリストに適用するんで、データに葉である文字が出てきた時点で破綻する(笑)。

よってまたしても再帰処理によって葉の情報を集積して返さないとならない。

(define dfs
　(case-lambda
　　((tree acc)
　　(match-let ((`(,a (,b ,bs)) tree))
　　　(match-let ((`(,x ,xs) bs))
　　　　(if (char? xs)
　　　　　(let ((lst (reverse `(,bs ,b ,@acc))))
　　　　　　(values (map (match-lambda (`(,x ,xs) (cons xs x))) lst)
　　　　　　　　　(map (match-lambda (`(,x ,xs) (cons x xs))) lst)))
　　　　　(dfs bs (cons b acc))))))
　　((tree)
　　(dfs tree '()))))

これもWikipediaで解説しているハフマン木では左の子が常に葉だ、と言う性質を利用して、左の子に関しては問答無用でアキュムレータ(acc)に積んでいく。

終了条件は右の子の右の要素がリストじゃなくって文字だった時、だ。その時、アキュムレータを逆順に直し、連想リスト化して多値を返す。多値化してる理由は、「エンコードテーブル」と「デコードテーブル」を同時に返す為、だ。ルール自体は同じでも文字と数値のどっちをキーにするんだ?と言うのは明確化しておいた方がいい。よってテーブルを「同時に返す」方が効率的だろう。

Pythonでは同ロジックを以下のようにして書く。

def dfs(tree):
　acc = []
　while True:
　　match tree:
　　　case [a, [b, bs]]:
　　　　match bs:
　　　　　case [x, xs]:
　　　　　　if isinstance(xs, str):
　　　　　　　lst = lambda: reversed([bs, b, *acc])
　　　　　　　return {xs: x for x, xs in lst()}, dict(lst())
　　　　　　tree, acc = bs, [b] + acc

このブログでは初めて、「エンコードテーブル」を作成する為に辞書内包表記を使う(キーと値の順序を入れ替える為)。また、Pythonは多値が無いが、代わりにタプルとして結果を返す。

Pythonでのピットフォール(落とし穴)はreversed等のイテラブルを返す関数だ。イテラブルは変数に代入されていようが、「一回使われると」消えてしまう性質がある。

よってイテラブルは、引数が無いラムダ式ででも包んでおかないと再利用が出来ない。これをコンピュータサイエンス用語で「サンク(thunk)を作る」と呼ぶ。

さて、最後は圧縮関数を書く。繰り返すが、ハフマン符号化は「特定のデータに対して」もっとも効率の良い圧縮を行うが、普遍的な符号化じゃない。よって圧縮したデータを返しても、「デコード規則」も同時に教えないと、画餅に帰してしまう。

よって「多値を返す」関数として書いた方が合理的、となる。

両者共、各関数をローカル関数として大本の呼び出し関数createValue2Codeに詰め込んでいる。

なお、Python版の注意点は、このケースだとRacket版と同じように、countDatum関数は処理対象として外側のcreateValue2Codeが受けてるdataを参照してる。

これはdataがシーケンス前提、だからだ。Pythonは不思議な言語で、レキシカルスコープは、対象がシーケンスの場合に於いてのみ、マトモに働く。一方、単なる数値なんかを使うと、nonlocal宣言しとかないとローカル関数から外部環境に変数を探しに行かない。言い換えるとマトモにレキシカルスコープが動かない、んだ。

今回は「良い」ケースだが、ハッキリ言っちゃえば極悪仕様だと思ってる(笑)。

;; Racket
> (compress "DAEBCBACBBBC")
'(14 6 15 0 2 0 6 2 0 0 0 2)
'((0 . #\B) (2 . #\C) (6 . #\A) (14 . #\D) (15 . #\E))
# Python
>>> compress("DAEBCBACBBBC")
([15, 6, 14, 0, 2, 0, 6, 2, 0, 0, 0, 2], {0: 'B', 2: 'C', 6: 'A', 14: 'E', 15: 'D'})

これで完成、なわけだが、ちと待てよ、って思うだろう。Racket/Python上だと「文字が特定のルールに従って数値に変換されている」だけであって、「これは圧縮か?」と言われるとちと困る結果になってるだろう。

いや、「圧縮ルールに従ってる」んで、圧縮、ではあるんだけど、Racket/Python上だとどう見ても「単なる変換」だ。しかも解凍関数を書かなくても、ルール(変換テーブル)が提示されてる以上、人力で元データを復元可能だ(笑)。

これ、どういう事かっつーと、先にも書いた通り、元々ハフマン符号化ってのは、データをビット列に変換するってのがキモで、それに拠って単なる文字データのビット列より情報量を削減出来るわけだ。

一方、ここではアルゴリズムに従ってハフマン符号化のプログラムを組んだんだけど、ロジックに注視するため、「ビット列」を導入せんかった。そして「超高級言語である」RacketやPythonだとそこを実装するのが面倒臭い(笑)。あるいは数値情報->ビット列へのコンバータさえあれば「どーにでもなる」範疇の話、なんだよ。

だから言ったろ(笑)。結果が面白くねぇ、って(笑)。今回のブログ記事はネタ選びに失敗してんだって(笑)。

そしてもう一つ問題がある。

先にも書いたけど、ハフマン符号化、と言うのは、データ要素の出現率に基づいて、適切な「数値」をデータ要素へと振り分けていく。データAの「符号化/復号化テーブル」はデータAにしか通用せず、データBには使えない、と言う特徴がある。

一方、「どんな数値を用意するのか」は、実はこのアルゴリズムを使う以上「決まってる」んだ。それは0、2、6、14、・・・と言う数列で、最後の要素には最後の前の要素へと振り分けられた数値 + 1が「必ず」振り分けられる。

つまり、二分木をわざわざ用いなくても、ある意味「振り分ける数値」自体は一意に決まってんだよな。

数学的に書くと、文字数をカウントして降順にソートした長さNのテーブルのn番目の要素に対して、

と言う数値を振り分けろ、って事なんだ。こんなもん、プログラミング言語なら、別に二分木なんぞ経由せんでもすぐ書けるだろう。

;; Racket
(define (codeInfo n)
　(let ((lst (cons 0 (unfold (lambda (x)
　　　　　　　　　　　　　(= x n))
　　　　　　　　　　　　(lambda (x)
　　　　　　　　　　　　　(apply + (map (lambda (y)
　　　　　　　　　　　　　　　　　　　　(expt 2 y)) (range 1 (add1 x)))))
　　　　　　　　　　　　add1
　　　　　　　　　　　　1))))
　　`(,@lst ,(add1 (last lst)))))
# Python
def codeInfo(n):
　lst = [0] + list(unfoldr(lambda x: None if x == n else (sum([2 ** i for i in range(1, 1 + x)]), 1 + x), 1))
　return [*lst, 1 + lst[-1]]

つまり、ハフマン符号による圧縮は次のように書ける事となる。

要は二分木を使ったプログラムは無駄だった、ってこった(笑)。Wikipediaのアルゴリズムに従う限り、そういう結論だ。なんだそれ(苦笑)。

なお、英語ではアルファベットの文字の出現率、なんつーのが割に分かってるんで、よっぽど特殊な並びとか、人工的な羅列じゃない限り、上の「数値ルール」がハッキリしてる以上、どのアルファベットに何を割り当てるのか、ってぇのは比較的一意に決まりやすいんじゃないか。

そういう意味では「文書の圧縮」なら決まりきったテーブルで平均的には「良い」圧縮になるんじゃないか、と予想してる。

予想だけ、だけどな。

まぁ、いずれにせよ、今回の記事は大失敗だ(笑)。

※1: Lisp/Python王国では