在python中将ShannonFano代码作为maxheap

Question

我有一个用于Huffman编码的最小堆代码，您可以在这里看到：http://rosettacode.org/wiki/Huffman_coding#Python

我试图做一个最大堆香农法诺代码，类似于最小堆。在

这里有一个代码：

from collections import defaultdict, Counter
import heapq, math

def _heappop_max(heap):
"""Maxheap version of a heappop."""
lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
if heap:
    returnitem = heap[0]
    heap[0] = lastelt
    heapq._siftup_max(heap, 0)
    return returnitem
return lastelt

def _heappush_max(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

def sf_encode(symb2freq):
heap = [[wt, [sym, ""]] for sym, wt in symb2freq.items()]
heapq._heapify_max(heap)
while len(heap) > 1:
    lo = _heappop_max(heap)
    hi = _heappop_max(heap)
    for pair in lo[1:]:
        pair[1] = '0' + pair[1]
    for pair in hi[1:]:
        pair[1] = '1' + pair[1]
    _heappush_max(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
print heap
return sorted(_heappop_max(heap)[1:], key=lambda p: (len(p[1]), p))

但我有这样的输出：

^{pr2}$

我用heapq实现Shannon-Fano编码是对的吗？此字符串中的问题：

_heappush_max(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

我不知道怎么解决它。在

期望输出类似于哈夫曼编码

Symbol  Weight  Huffman Code
    2875    01
a   744 1001
e   1129    1110
h   606 0000
i   610 0001
n   617 0010
o   668 1000
t   842 1100
d   358 10100
l   326 00110

添加：

好吧，我尝试过不使用heapq的方法来实现这一点，但是有不可阻挡的递归：

def sf_encode(iA, iB, maxP):
global tupleList, total_sf
global mid
maxP = maxP/float(2)
sumP = 0    
for i in range(iA, iB):
    tup = tupleList[i]
    if sumP < maxP or i == iA: # top group
        sumP += tup[1]/float(total_sf)
        tupleList[i] = (tup[0], tup[1], tup[2] + '0')
        mid = i           
    else: # bottom group
        tupleList[i] = (tup[0], tup[1], tup[2] + '1')
print tupleList
if mid - 1 > iA:
    sf_encode(iA, mid - 1, maxP)
if iB - mid > 0:
    sf_encode(mid, iB, maxP)
return tupleList

Answer 1

在Shannon-Fano编码中，您需要以下steps：

^{bq}$

所以你需要代码来排序（你的输入看起来已经排序过了，所以你可以跳过它），再加上一个递归函数，它可以选择最佳分区，然后在列表的第一部分和第二部分递归。在

一旦列表被排序，元素的顺序就不会改变，所以不需要使用heapq来进行这种编码。在