python - 递归霍夫曼解码
问题描述
我正在创建一个可以编码和解码文本的霍夫曼类,但我的解码方法有问题。我的编码方法工作正常,我的解码方法适用于少量文本。但是当我尝试解码大量文本时,我得到一个最大递归深度错误并且不知道如何修复它。该类接收包含字符及其频率的字典,然后将它们转换为节点并构建树。在构建树之后,它将字符及其位码放入另一个字典中以用于编码和解码。
class Node:
def __init__(self,value,data,left=None,right=None):
#Holds frequency
self.value = value
#Holds character
self.data = data
self.left = left
self.right = right
self.code = ""
def __lt__(self, other):
return self.value < other.value
def __le__(self, other):
return self.value <= other.value
def __gt__(self, other):
return self.value > other.value
def __ge__(self, other):
return self.value >= other.value
class MyHuffman():
def __init__(self):
self.chars = {}
self.tree = None
self.decodePosition = 0
def build(self, weights):
huffNodes = []
heapq.heapify(huffNodes)
for x, y in weights.items():
heapq.heappush(huffNodes,Node(y,x))
while len(huffNodes) > 1:
left = heapq.heappop(huffNodes)
right = heapq.heappop(huffNodes)
left.code = 1
right.code = 0
heapq.heappush(huffNodes, Node(left.value+right.value, left.data + right.data, left, right))
self.tree = huffNodes[0]
self.makeLookupTable(self.tree)
def makeLookupTable(self, node, bitCode=""):
codes = bitCode + str(node.code)
if node.left == None and node.right == None:
self.chars[node.data] = codes
else:
self.makeLookupTable(node.left, codes)
self.makeLookupTable(node.right, codes)
return self.chars
def encode(self, word):
bitString = ""
for x in range (0, len(word)):
if word[x] in self.chars:
for y, z in self.chars.items():
if word[x] == y:
bitString = bitString + z
return bitString
def decode(self, bitstring):
for x in bitstring:
if x != "0" and x != "1":
return None
dec = self.recursiveTraverseTree(self.tree,bitstring)
self.decodePosition=0
return dec
def recursiveTraverseTree(self, node, bitString, words=""):
if node.left == None and node.right == None:
words= words + str(node.data)
node = self.tree
if self.decodePosition < len(bitString):
if bitString[self.decodePosition] == "0":
self.decodePosition+=1
return self.recursiveTraverseTree(node.right, bitString, words)
elif bitString[self.decodePosition] == "1":
self.decodePosition+=1
return self.recursiveTraverseTree(node.left, bitString, words)
return words
一些测试在下面运行第一个测试工作正常,但第二个给出 maxRecursion depth 错误
huff = MyHuffman()
freqs = {'z': 50, 'j': 1, "'": 11, 'a': 42, 'd': 3, 'l': 1, 'f': 14, ' ': 31, 'i': 1, 'w': 8, 's': 41, 'r': 2, 'k': 49, 'b': 28, 'q': 28, 'p': 32, 'g': 33, 'v': 51, 'c': 6, 'h': 6, 'm': 5, 'y': 8, 'o': 36, 't': 28, 'u': 23, 'n': 15}
b = huff.build(freqs)
word = "damn son"
bitstring = huff.encode(word)
decrypted = huff.decode(bitstring)
print(f"[{word}] -> [{bitstring}] -> [{decrypted}]")
#Outputs[damn son] -> [1000011001110000101000110010100010110001] -> [damn son]
word1 ="bgzqbbvkqpaawaoasczz nfq szbumq'vzmbvbknsvvqouapcpbzkvbgtbsggcohto p tzhytz kkutanbv ubsbaogasznr tzz pzzsgqfqpsnfugsktpuzztq s vkfzavokoogmvzgpk tagkz zaoz'vaqpqkvbuvqtsbzgf zk kuzasovhauoqwtvvvovko fvbwhzpvpkskouaupspstbvgsbszipqvvuvmuaspzna stvvk gu saaokggnmsvtspkvqvsahvozsawszfpws skgg bqkqu salg fovuknaknpupovafbovqssagpgbfkcuz gf ofgyrokasgc guabqzbtkosqzbzvspzwgnsyfhvoz akgo'htsovzpakabayffpkpkvqrpzzqogsfvvatsvqbaapozavuyovzpbzsz ppuzrqbq'jaq zuqhhpptvkguktcbkazsszsgvocppzptzzhtzgt b mkznz qqk avkmztzsbzkgrovkqsssb pvtvssoutssazasunaavgybffppqgqagbsa gqscwpno'pb qsknzagtu pztqfbmbztmtuzktvza gaovapkvav govpv oazg'qgrpyszvqqzvgvztbavsy pswurtauztkztavv zcqvzs gbt zgzosfvtpk'gyggbokt ktgukzgskfzf ntavpq bzazvtphvcfba knp'zg'vsyqtvuopz tvzks fn'boaakyvskgvgqggqz tknqbbbvskavkgqpskkkvapca rvzpkksvw'p spvhbzfgggzz'fopfsngoujykutkapbvtqzkkaanpogpnozohvqgfwkdpkvgdpouku v zpkkonuzks oznspqz'aszvnt v ytkcptstkftcknfksbkqszqht z wmpafzwf vkofvadvaqagqzpnzavvuzqkau nqobvggzp qv gup fokkbsoaqkoz svu uvzqzzpyfwuq ozszkzspkavsvta tgovt zpyqvpkzpbnvbsakkgvaktkqwukozp zskzr a aobzopg qtmkakk g nz vgagaktwv tptw bfqmsogzhhkpzwaza tokcbta kzzutvzk zvkunqoowako zabvvkqu'zb kp kvakvthgytvsvstpbvngvskgaqnfkokwozbztgszh'pgbopsgdnvzvozzgvsvgpvuzbuvkzat"
bitstring1 = huff.encode(word1)
decrypted1 = huff.decode(bitstring1)
print(f"[{word1}] -> [{bitstring1}] -> [{decrypted1}]")
#Gives maximum recursion depth error
解决方案
这是一个草图(未经测试),它decode
循环重写并保持树搜索递归。
def decode(self, bitstring):
for x in bitstring:
if x != "0" and x != "1":
return None
pos = 0
size = len(bitstring)
dec = ""
while pos < size:
pos, word = self.decode_one(self.tree, bitstring, pos)
dec += word
self.decodePosition = 0
return dec
def decode_one(self, node, bitstring, pos):
"""Return a tuple of the smallest unused position and the word"""
if node.left == None and node.right == None:
return pos, node.data
elif bitstring[pos] == "0":
return self.decode_one(node.right, bitstring, pos + 1)
elif bitstring[pos] == "1":
return self.decode_one(node.left, bitstring, pos + 1)
推荐阅读
- angular - ng构建后如何控制资产路径?
- c++ - 如何将两个独立程序中的数据链接到一个程序中?
- vue.js - Vue:未找到这些 dededecies
- caching - CloudFront 忽略缓存控制:无缓存响应标头
- spring-boot - 为 Cloud Foundry 上的 SpringBoot-Server 启用/禁用 HTTP 压缩
- javascript - 从树中递归删除项目
- python - 如何将列转为标题?- python 熊猫数据框
- jmeter - JMeter HTML 报告仪表板 - 总错误数大于总样本数
- ssl - 如何禁用 Forticlient Fortinet VPN 跟踪日志?
- amazon-web-services - 用于应用程序负载均衡器的 AWS 私有静态 ipv4