Блог

Я создаю класс Хаффмана, который может кодировать и декодировать текст, но у меня возникли проблемы с моим методом декодирования. Мой метод кодирования работает нормально, и мой метод декодирования работает для меньших объемов текста. Но когда я пытаюсь декодировать большие объемы текста, я получаю ошибку максимальной глубины рекурсии и не уверен, как это исправить. Класс принимает словарь с символами и их частотами, а затем превращает их в узлы и строит дерево. После построения дерева он помещает символы и их битовый код в другой словарь, который будет использоваться для кодирования и декодирования.

 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

 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)
 

word1 имеет длину 1260. Код Хаффмана использует не менее 1 бита на букву. В результате bitstring1 получается длина не менее 1260 бит. decode повторяется один раз для каждого декодированного бита или, по крайней мере, 1260 раз. Это больше, чем ограничение Python по умолчанию 1000, поэтому вы получаете ошибку.