ブロック化ハフマン符号を実装してみた（JavaScript）

ブロック化ハフマン符号を実装してみた（JavaScript）:

勉強したので習作。計算効率は完全に無視。ハフマン符号がわかっている人向け。

• 参考: ハフマン符号を実装してみた（JavaScript）
  

1. 概念理解

解きたい課題（ハフマン符号と同じ）: N種類の値を取りうる事象があり、それぞれの値の生成確率がわかっている。できるだけ圧縮効率をあげて 0/1で構成されるビット列にエンコード/デコードしたい。

アプローチ: ハフマン符号は、「1事象を 1符号語に割り当てる」という枠組みで最大の圧縮効率。ブロック化ハフマン符号では、「N事象を 1符号語に割り当てる」という枠組みを使って、より圧縮率を高める。

イメージ図:

ABAACBBAC --[ブロック化]--> ABA ACB BAC --[エンコード]--> 010010010111000111000111 
        --[デコード]--> ABA ACB BAC --[ブロック化解除]--> ABAACBBAC 

2. 拡大情報源という概念

A が 90% の確率で生成され、 B が 10% の確率で生成される情報源を考える。二つの事象をブロック化したとすると、以下のような確率分布が得られる:

2次に拡大した情報源.txt

事象    生成確率 
-------------------- 
AA      0.81 
AB      0.09 
BA      0.09 
BB      0.01 

これを 「4種類の事象が上の表の生成確率で与えられる情報源」とみなすことが可能で、そうするとこの新たに作った情報源（拡大情報源）に対してハフマン符号を使ってみようという気になる。

同様に、三つの事象をブロック化すると、以下のような確率分布が得られる:

3次に拡大した情報源.txt

事象    生成確率 
-------------------- 
AAA    0.729 
AAB    0.081 
... 
(中略) 
... 
BBB    0.001 

これを 「8種類の事象が上の表の生成確率で与えられる情報源」とみなすことが可能で、そうするとこの新たに作った情報源（拡大情報源）に対してハフマン符号を使ってみようという気になる。

3. 拡大情報源の確率分布

やるべきことはただ一つ。上記のように、与えられた整数 N に対して、N次の拡大情報源の統計情報を自動的に作ること。

const DATA = [['A', 0.9], ['B', 0.1]]; 
 
function statsOf(stat, num) { 
  const expandOne = (before) => { 
    const result = []; 
    for (const [id, prob] of before) { 
      stat.forEach(([appendID, p]) => result.push([id + appendID, prob * p])); 
    } 
    return result; 
  } 
  // do work 
  let result = stat; 
  for (let i = 0; i < num - 1; i++) { 
    result = expandOne(result); 
  } 
  return result; 
} 
 
console.log(statsOf(DATA, 2)); 
/* 
[ [ 'AA', 0.81 ], 
  [ 'AB', 0.09000000000000001 ], 
  [ 'BA', 0.09000000000000001 ], 
  [ 'BB', 0.010000000000000002 ] ] 
*/ 
 
console.log(statsOf(DATA, 3)); 
/* 
[ [ 'AAA', 0.7290000000000001 ], 
  [ 'AAB', 0.08100000000000002 ], 
  [ 'ABA', 0.08100000000000002 ], 
  [ 'ABB', 0.009000000000000001 ], 
  [ 'BAA', 0.08100000000000002 ], 
  [ 'BAB', 0.009000000000000001 ], 
  [ 'BBA', 0.009000000000000003 ], 
  [ 'BBB', 0.0010000000000000002 ] ] 
*/ 

4. エンコーダ・デコーダの実装

統計情報が得られれば、統計情報→ハフマン木→エンコーダ・デコーダとサクサク作っていける。ハフマン符号を実装してみた（JavaScript） を少しいじるだけ。

// ブロック化ハフマン符号の各種関数の生成関数 
function blockHuffman (stat, n) { 
  const stats = statsOf(stat, n); 
  const tree = treeOf(stats); 
  // encode 
  const _encode = encoder(dictOf(tree)); 
  const encode = xs => { 
    const splitted = xs.reduce((a, x, i) => { 
      if (i % n === 0) { a.push(x) ; return a; } 
      else { a[a.length - 1] += x; return a; } 
    }, []); // [A, A, A, A] -> [AA, AA] 
    return _encode(splitted); 
  }; 
  // decode 
  const _decode = decoder(tree); 
  const decode = bits => _decode(bits).reduce((a, x) => a.concat([...x]), []); 
  return { encode, decode, stats, tree, dict: dictOf(tree) }; 
} 
 
const bh2 = blockHuffman(DATA, 2); 
console.log(bh2.dict); // -> { AA: '0', BA: '100', BB: '101', AB: '11' } 
console.log(bh2.encode([...'AAABBABB'])); // -> 011100101  
console.log(bh2.decode(bh2.encode([...'AAABBABB'])).join('')); // -> AAABBABB 

5. 遊んでみる

１事象あたりの平均符号長が、N (=拡大の次数)を大きくしていくとどう変化していくかを見てみる。圧縮の理論限界＝情報源のエントロピー 0.4690 に近づいていくのがわかる。

const avLengths = [1, 2, 3, 4, 5, 6].map(n => { 
  const { stats, dict } = blockHuffman(DATA, n); 
  return stats.reduce((a, x) => a + x[1] * dict[x[0]].length, 0) / n; 
}); 
console.log(avLengths); 
/* 
[ 1, 
  0.6450000000000001, 
  0.5326666666666667, 
  0.49255000000000004, 
  0.480194, 
  0.4701568333333332 ] 
*/ 

6 コード

// 確率分布からハフマン木を構築 
function treeOf (stats) { 
  const arr = stats.map(x => [...x]); 
  while (arr.length !== 1) { 
    arr.sort((a, b) => a[1] < b[1]); // sort by frequency 
    const [a, b] = arr.splice(-2); // pop last 2 nodes 
    arr.push([[a[0], b[0]], a[1] + b[1]]); // push 1 node 
  } 
  return arr[0][0]; 
} 
 
// ハフマン木からエンコード用の辞書を作成 
function dictOf(tree) { 
  const result = {}; 
  const rfn = (obj, ctx) => { 
    if (typeof obj === 'string') { 
      result[obj] = ctx; 
      return; 
    } 
    rfn(obj[0], ctx + '0'); 
    rfn(obj[1], ctx + '1'); 
  }; 
  rfn(tree, ''); 
  return result; 
} 
 
// encode 関数の生成関数。辞書を渡すと encode 関数を返す 
const encoder = dict => ids => ids.map(id => dict[id]).join(''); 
 
// decode 関数の生成関数。ハフマン木を渡すと decode 関数を返す 
const decoder = tree => bits => { 
  let current = tree; 
  // define 1-bit decoder 
  const _decode = bit => { 
    current = bit === '0' ? current[0] : current[1]; 
    if (typeof current === 'string') { // decoded! 
      const result = current; 
      current = tree; 
      return result; 
    } 
    return null; // needs more to be decoded 
  }; 
  // do the work 
  const result = []; 
  for (const bit of bits) { 
    const val = _decode(bit); 
    if (val) { 
      result.push(val); 
    } 
  } 
  return result; 
}; 
 
// num 次に拡大した情報源の確率分布を計算 
function statsOf(stat, num) { 
  const expandOne = (before) => { 
    const result = []; 
    for (const [id, prob] of before) { 
      stat.forEach(([appendID, p]) => result.push([id + appendID, prob * p])); 
    } 
    return result; 
  } 
  // do work 
  let result = stat; 
  for (let i = 0; i < num - 1; i++) { 
    result = expandOne(result); 
  } 
  return result; 
} 
 
// ブロック化ハフマン符号の各種関数の生成関数 
function blockHuffman (stat, n) { 
  const stats = statsOf(stat, n); 
  const tree = treeOf(stats); 
  // encode 
  const _encode = encoder(dictOf(tree)); // internal encode 
  const encode = xs => { 
    const splitted = xs.reduce((a, x, i) => { 
      if (i % n === 0) { a.push(x) ; return a; } 
      else { a[a.length - 1] += x; return a; } 
    }, []); // [A, A, A, A] -> [AA, AA] 
    return _encode(splitted); 
  }; 
  // decode 
  const _decode = decoder(tree); 
  const decode = bits => _decode(bits).reduce((a, x) => a.concat([...x]), []); 
  return { encode, decode, stats, tree, dict: dictOf(tree) }; 
} 
 
// 事象生成ジェネレーター。確率分布に従って事象列を生成 
const observe = num => { 
  const result = []; 
  [...Array(num).keys()].forEach(() => { // num times 
    const rval = Math.random(); 
    const total = DATA.reduce((a, x) => a + x[1], 0); 
    let acc = 0; 
    for (const [id, freq] of DATA) { 
      acc += freq / total; 
      if (acc > rval) { 
        result.push(id); 
        return; 
      } 
    } 
  }); 
  return result; 
}; 
 
 
const DATA = [['A', 0.9], ['B', 0.1]]; 
const avLengths = [1, 2, 3, 4, 5, 6].map(n => { 
  const { stats, dict } = blockHuffman(DATA, n); 
  return stats.reduce((a, x) => a + x[1] * dict[x[0]].length, 0) / n; 
}); 
console.log(avLengths);