え?C++を体得したんじゃなかったって? 知りませんね、そんなこと。私はC++なんて使わないでJavaScriptでコードを書きます。

ハフマン木を作るアルゴリズム概要

wikiに書いてあるアルゴリズムはこうです。

まず、葉を含むすべての節点のうち、親を持たないものを集める。
その中から、最小の値をもつものと2番目に小さい値をもつものを取り出す。
それらを子供にもつ新しい節点を作る。このとき、新しい節点の値は、両方の子供の値の和とする。

よくわかりませんね。

噛み砕いた概要

上の説明をかみ砕くとこうなります。

「一番出現率の低い文字」と「二番目に出現率が低い文字」を子に持つノードを生成
そのノードを含めて、一つの木になるまで1を繰り返していく

例

例えばある文にiが6回、 eが5回、 tが5回、 sが4回出たとします。その場合、出現率が一番低いのはs、二番目に低いのはt(とe)です。

そしたら、 sとtを子に持つノードAを生成します。そのノードの出現回数は9回となります。

再び出現率を見ます。すると一番低いのはe、二番目はiです。これらを合成して出現回数11回のノードBを作ります。

再度、出現率を見ます。一番低いのはノードA、二番目はノードBとなります。最後にこれらを合成すればハフマン木の完成です。

ハフマン木からハフマン符号を作る

ハフマン木からハフマン符号を求める方法はこうです。

根からたどる
左にすすんだ場合は0、右にすすんだ場合は1を末尾に追加
葉にたどり着いたときの文字列がハフマン符号

先ほどの例では

i	11
e	10
t	01
s	00

となります。

wikiが紛らわしい図を使っている

あまり関係ないのですが、wikiのハフマン符号の図がわかりづらいです。ななめ読みが癖になっている私のような人が読むとwikiは「[0, 10, 110, 1110, ... (n個の1)0]とするのがハフマン符号」という風に見えます。ヒジョーに紛らわしいのでもうちょい適切な例にしてほしいです。

Lorem ipsumをハフマン符号にかける

かの有名なダミーテキストLorem ipsumをハフマン符号にかけてみます。今回は「Lorem ipsum dolor sit amet, consectetur adipiscing elit」まででやってみます。

結果はこんな感じです

{ t: '000',
  i: '001',
  r: '0100',
  m: '0101',
  c: '0110',
  g: '01110',
  p: '01111',
  ' ': '100',
  o: '1010',
  s: '1011',
  u: '11000',
  d: '11001',
  l: '11010',
  a: '11011',
  n: '11100',
  L: '111010',
  ',': '111011',
  e: '1111' }

[文字, 出現回数, ハフマン符号の長さ]を求めてみました。

[ [ ' ', 7, 3 ],
  [ 'i', 6, 3 ],
  [ 't', 5, 3 ],
  [ 'e', 5, 4 ],
  [ 's', 4, 4 ],
  [ 'o', 4, 4 ],
  [ 'm', 3, 4 ],
  [ 'r', 3, 4 ],
  [ 'c', 3, 4 ],
  [ 'd', 2, 5 ],
  [ 'l', 2, 5 ],
  [ 'u', 2, 5 ],
  [ 'a', 2, 5 ],
  [ 'p', 2, 5 ],
  [ 'n', 2, 5 ],
  [ 'g', 1, 5 ],
  [ 'L', 1, 6 ],
  [ ',', 1, 6 ] ]

出現回数が多いものほど短く設定されていることが分かります。

コード

最後に実装を載せておきます。ES2015バリバリ使ったので実行する際はご注意を。

class Node {
    constructor(val) {
        this.value = val;
        this.child = [];
    }
    addLeft(node) {this.child[0] = node}
    addRight(node) {this.child[1] = node}
}

function count(str) {
    // strの中のそれぞれの文字の出現回数をカウントする
    const counter = new Map();
    for (const s of str) counter.set(s, counter.has(s) ? counter.get(s) + 1 : 0);
    return [...counter.entries()];
}
function createHuffmanTree(pairs) {
    // pairs:= [['a', 2], ['b', 2], ...]
    pairs = pairs.map(item => [new Node(item[0]), item[1]]);
    while (pairs.length > 1) {
        let min1 = 0, min2 = 1; // min1は最小要素のインデックス、min2は二番目へのインデックス
        if (pairs[min1][1] > pairs[min2][1]) [min1, min2] = [min2, min1];
        for (let i = 2, _i = pairs.length; i < _i; i++) {
            if (pairs[i][1] < pairs[min1][1]) {
                [min1, min2] = [i, min1];
            } else if (pairs[i][1] < pairs[min2][1]) {
                min2 = i;
            }
        }
        const parent = new Node(null);
        parent.addLeft(pairs[min1][0]);
        parent.addRight(pairs[min2][0]);
        if (min1 > min2) [min1, min2] = [min2, min1]; // 下でpairsからmin1、min2の要素を取り除くときにspliceを使うため、必要なら入れ替え
        pairs.push([parent, pairs[min1][1] + pairs[min2][1]]);
        pairs.splice(min2, 1); pairs.splice(min1, 1);
    }
    return pairs[0][0];
}
function HuffmanCoding(tree, dic = {}, s = '') {
    if (tree.value !== null) dic[tree.value] = s;
    if (tree.child[0]) dic = HuffmanCoding(tree.child[0], dic, s + '0');
    if (tree.child[1]) dic = HuffmanCoding(tree.child[1], dic, s + '1');
    return dic;
}
const test = 'Lorem ipsum dolor sit amet, consectetur adipiscing elit';
const huffmanCode = HuffmanCoding(createHuffmanTree(count(test)));
console.log(huffmanCode);
console.log([...test].map(s => huffmanCode[s]).join(''));
console.log(([...test].map(s => huffmanCode[s]).join('').length / 8) + 'byte');

終わりに

まだハフマン符号がなぜ接頭符号になるのか、圧縮効率がいいのか理解できていないので、もう少し調べてみようと思います。

Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

ハフマン符号をJavaScriptで実装した