ハフマン符号化

講義で課題が出たので、Pythonの勉強もかねてプログラム化に挑戦。

ずばりな記事があったので、これのソース読むとこから始めたんだけど、
おおまかには理解できたが、heapqモジュールのheapify()で躓く。

#coding: UTF-8

from itertools import groupby
from heapq import *

#ノードの情報を扱うクラス
class Node(object):
    item = None     #格納している値
    weight = 0      #子ノードを足し合わせた重み
    right = None    #右側のノード
    left = None     #左側のノード

    def __init__(self, i, w):
        self.item = i
        self.weight = w

    def setChildren(self, ln, rn):
        self.left = ln
        self.right = rn

    #ノードの状態を表示
    #def __repr__(self):
    #    return "%s - %s -- %s _ %s" % (self.item, self.weight, self.left, self.right)

    #heapqモジュールを使うため
    def __cmp__(self, a):
        return cmp(self.weight, a.weight)


def huffman(input):
    itemqueue =  [Node(a,len(list(b))) for a,b in groupby(sorted(input))]   #inputをソートしたものを重み付け
    print(type(itemqueue))
    heapify(itemqueue)  #ヒープ化

    #
    while len(itemqueue) > 1:       #残り1つになるまで
        l = heappop(itemqueue)
        r = heappop(itemqueue)
        n = Node(None, r.weight+1)  #右側の符号を1とする
        n.setChildren(l, r)         #右、左の子要素を割り当てる
        heappush(itemqueue, n)      #足し合わせた2つをプッシュする


    codes = {}
    #ノードの値がなければ右側のノードに1,左側のノードに0で符号化する
    #再帰関数を利用し、符号を積み重ねながら枝をたどる
    def codeIt(s, node):
        if node.item:
            if not s:
                codes[node.item] = "0"
            else:
                codes[node.item] = s
        else:
            codeIt(s+"0", node.left)
            codeIt(s+"1", node.right)

    codeIt("", itemqueue[0])
    return codes, "".join(codes[a] for a in input)  #inputの値を""区切りで表示


input = "aababcabcd"
huffman(input)

読みながら自分の言葉で説明付けしたので、文字多いのは割愛。
で、以下実行結果。

$python huffman.py

<class 'list'>
Traceback (most recent call last):
  File "huffman.py", line 62, in <module>
    huffman(input)
  File "huffman.py", line 33, in huffman
    heapify(itemqueue)  #ヒープ化
TypeError: unorderable types: Node() < Node()

怒られる。
itemqueueはリストだから、heapifyでヒープ化できるはずなんだけどできない。
Node() < Node()って何？

...眠いから明日に回す。