3

演習として、ハフマン木を使用していくつかのシンボルをエンコードしようとしていますが、Python の組み込みデータ型の代わりに独自のクラスを使用しています。

ここに私のノードクラスがあります:

class Node(object):
    left = None
    right = None
    weight = None
    data = None
    code = ''
    length = len(code)

    def __init__(self, d, w, c):
        self.data = d
        self.weight = w
        self.code = c

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

    def __repr__(self):
        return "[%s,%s,(%s),(%s)]" %(self.data,self.code,self.left,self.right)

    def __cmp__(self, a):
        return cmp(self.code, a.code)

    def __getitem__(self):
        return self.code

ここにエンコーディング関数があります：

def encode(symbfreq):
    tree = [Node(sym,wt,'') for sym, wt in symbfreq]
    heapify(tree)
    while len(tree)>1:
        lo, hi = sorted([heappop(tree), heappop(tree)])
        lo.code = '0'+lo.code
        hi.code = '1'+hi.code
        n = Node(lo.data+hi.data,lo.weight+hi.weight,lo.code+hi.code)
        n.set_children(lo, hi)
        heappush(tree, n)
    return tree[0]

（dataフィールドには、最終的にset()ノードの子のすべてのアイテムが含まれることに注意してください。エンコードを正しく取得している間、現時点では合計が含まれているだけです）。

ツリーをエンコードするために私が持っていた以前の関数は次のとおりです。

def encode(symbfreq):
    tree = [[wt, [sym, ""]] for sym, wt in symbfreq]
    heapq.heapify(tree)
    while len(tree)>1:
        lo, hi = sorted([heapq.heappop(tree), heapq.heappop(tree)], key=len)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(tree, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return sorted(heapq.heappop(tree)[1:], key=lambda p: (len(p[-1]), p))

しかし、私の新しい手順が間違っていることに気付きました: 最上位のノードに最終的な葉ではなく最長のコードワードを与え、入力シンボルの順列に対して同じツリーを生成しません。つまり、以下は同じツリーを生成しません (新しいエンコーディング関数で実行した場合):

input1 = [(1,0.25),(0,0.25),(0,0.25),(0,0.125),(0,0.125)]
input2 = [(0,0.25),(0,0.25),(0,0.25),(1,0.125),(0,0.125)]

私は、この種のオフバイワン/順序付けバグを回避するのが本当に苦手であることがわかりました.今後、これをどのように整理すればよいでしょうか?

4

2 に答える 2

1

問題はセグメントにあると思われます: -

lo.code = '0'+lo.code
hi.code = '1'+hi.code

ハイとローの両方が中間ノードになる可能性があり、実際のシンボルがある葉でコードを更新する必要があります。ハフマン木の構築時にコードを保持するのではなく、ハフマン木の構築後にトラバースするだけで個々のシンボルのコードを取得する必要があると思います。

エンコード用の私の擬似コードは次のとおりです。

 tree = ConstructHuffman(); // Same as your current but without code field

 def encode(tree,symbol): 
     if tree.data == symbol : 
         return None
     else if tree.left.data.contains(symbol) :
         return '0' + encode(tree.left,symbol)
     else : 
        return '1' + encode(tree.right,symbol)

上記のエンコード方法を使用してすべてのシンボルのコードを計算すると、それらをエンコードに使用できます。

注:比較機能をコードの比較から重量の比較に変更します。

于 2013-11-16T05:17:15.760 に答える