Huffman coding

algorithm .groovy

ハフマン符号はデータ圧縮の手法で 『プログラミングコンテストチャレンジブック』 によると貪欲法になるらしい。
出現頻度が高い文字により短い符号を割り当てるので元の文字列より圧縮できる。


エンコードの手順

  1. 文字列から頻度表を作成する
  2. 頻度表からハフマン木を作成する
  3. ハフマン木からコード表を作成する
  4. コード表を使って文字列をエンコードする


デコードの際はコード表がなくてもハフマン木と長さが分かっていれば復号できる。
Java には bit 単位の入出力がないので文字列まま処理した。

// 文字列から頻度表を作成する
def freq(str) {
  str.toList().countBy { it }
}

// 頻度表からハフマン木を作成する
def htree(freq) {
  def cmp = [compare: { a, b -> a.value <=> b.value }] as Comparator
  def pq  = new PriorityQueue(freq.size(), cmp)
  pq.addAll(freq.entrySet())
  while (pq.size() > 1) {
    def a = pq.poll()
    def b = pq.poll()
    pq << new MapEntry([a.key, b.key], a.value + b.value)
  }
  pq.poll().key
}

// ハフマン木からコード表を作成する
def table(htree, prefix="") {
  if (htree in List)
    table(htree[0], prefix+'0') + table(htree[1], prefix+'1')
  else
    [(htree): prefix]
}

// ハフマン木をシリアライズする
def serialize(htree, buffer=new StringBuilder()) {
  if (htree in List) {
    buffer << '1'
    serialize(htree[0], buffer)
    serialize(htree[1], buffer)
  } else {
    buffer << '0'
    buffer << Integer.toBinaryString(htree.bytes[0]).padLeft(8,'0')
  }
}

// ハフマン木をデシリアライズする
def deserialize(bs) {
  if (bs.pollFirst() == '1') {
    return [deserialize(bs), deserialize(bs)]
  } else {
    return readChar(bs) as String
  }
}

def readChar(bs) {
  def c = new StringBuilder(8)
  8.times { c << bs.pollFirst() }
  Integer.parseInt(c.toString(), 2) as char
}

def readInt(bs) {
  def i = new StringBuilder(32)
  32.times { i << bs.pollFirst() }
  Integer.parseInt(i.toString(), 2)
}

def encode(str) {
  def frq = freq(str)       // 頻度表を作成
  def htr = htree(frq)      // ハフマン木を作成
  def tbl = table(htr)      // コード表を作成
  def enc = str.toList().collect { tbl[it] }.join()
  def len = enc.size()
  Integer.toBinaryString(len).padLeft(32,'0') + serialize(htr) + enc + ('0'*(len%8))
}

def decode(enc) {
  def str = new StringBuilder()
  def bs  = enc.toList() as LinkedList
  def len = readInt(bs)     // コード長を読み込む
  def htr = deserialize(bs) // ハフマン木を読み込む
  def cur = htr
  for (int i = 0; i < len; i++) {
    cur = cur[bs.pollFirst() as int]
    if (!(cur in List)) {
      str << cur
      cur = htr
    }
  }
  str as String
}

def str = "this is an example for huffman encoding"
assert str == decode(encode(str))


参考