使用字典解碼霍夫曼代碼

Question

我需要使用包含ASCII和霍夫曼位之間的翻譯文件的文件來解碼用我的程序編碼的霍夫曼編碼。我已經從「碼」，在編程'字典到ASCII像這樣的：

{'01110': '!', '01111': 'B', '10100': 'l', '10110': 'q', '10111': 'y'} 

我創建的函數：

def huffmanDecode (dictionary, text) : 

需要字典和代碼。我試圖尋找在字典中key的文本和同時使用更換方法形式串和子從重新但都沒有消息正確解碼。 例如，如果代碼是：

011111011101110 

它應該是簡單的將其解碼到：

By! 

但我一直無法通過遍歷代碼和搜索匹配做詞典！

如何通過查找文本中的關鍵字並將其替換爲值來使用字典中的鍵及其值解碼代碼？

任何幫助，非常感謝。

Answer 1

不知道你試過了什麼，但是re.sub或replace可能不起作用，因爲它們不一定會從字符串的開頭替換。您必須查看該字符串以什麼代碼開始，然後替換該代碼，然後繼續處理該字符串的其餘部分。

例如，像這樣：

def huffmanDecode (dictionary, text): 
    res = "" 
    while text: 
     for k in dictionary: 
      if text.startswith(k): 
       res += dictionary[k] 
       text = text[len(k):] 
    return res 

或者遞歸：

def huffmanDecode (dictionary, text): 
    if text: 
     k = next(k for k in dictionary if text.startswith(k)) 
     return dictionary[k] + huffmanDecode(dictionary, text[len(k):]) 
    return "" 

你也可以從你的代碼做一個正則表達式，並使用re.match查找下一個：

import re 
def huffmanDecode (dictionary, text): 
    p = "|".join(dictionary) # join keys to regex 
    res = "" 
    while text: 
     m = re.match(p, text) 
     res += dictionary[m.group()] 
     text = text[len(m.group()):] 
    return res 

注意：這兩個都沒有正確的錯誤處理，並且如果代碼執行會失敗或永遠循環不符合信息，但這應該讓你開始。

Answer 2

使用bitarray模塊你霍夫曼恩/解編碼免費，可能比什麼都更有效率：

from bitarray import bitarray 

huffman_dict = { 
    '!': bitarray('01110'), 'B': bitarray('01111'), 
    'l': bitarray('10100'), 'q': bitarray('10110'), 
    'y': bitarray('10111') 
} 

a = bitarray() 
a.encode(huffman_dict, 'Bylly!') 
print(a) 

dec = bitarray('011111011101110').decode(huffman_dict) 
print(dec) 
print(''.join(dec)) 

# # output: 
# bitarray('011111011110100101001011101110') 
# ['B', 'y', '!'] 
# By! 

，如果你不想安裝模塊，請閱讀下面的部分。

---

這裏是使用哈夫曼樹解碼一個變種 - 該程序作品，但有可能是更好的變種來表示二進制樹（我選擇了一個元組）。

這個版本可能更適合當你的代碼字長度不一樣時。關於二叉樹的另一個好處是，這裏顯然代碼是無前綴的。

您在樹形式的代碼如下所示（爲了使樹構造可見過度縮進）：使用可以再解碼

huffman_tree = \ 
    ( # 0 
     ( # 00 
      None, 
      # 01 
      ( # 010 
       None, 
       # 011 
       ( # 0110 
        None, 
        # 0111 
        ( # 01110 
         '!', 
         # 01111 
         'B')))), 
     # 1 
     ( # 10 
      ( # 100 
       None, 
       # 101 
       ( # 1010 
        ( # 10100 
         'l', 
         # 10101 
         None 
        ), 
        # 1011 
        ( # 10110 
         'q', 
         # 10111 
         'y'))), 
      # 11 
      None)) 

有：

def huffman_decode(strg): 
    ret = '' 
    cur_node = huffman_tree 
    for char in strg: 
     cur_node = cur_node[int(char)] 
     if cur_node is None: 
      raise ValueError 
     elif isinstance(cur_node, str): 
      ret += cur_node 
      cur_node = huffman_tree 
    return ret 

print(huffman_decode('011111011101110')) 

如果解碼命中None發生了一些錯誤，並且引發了ValueError。只要解碼遇到一個字符串，當前節點cur_node被重置爲「根節點」，並且遊戲從樹的開始處開始。

只是因爲我可以：這裏是你的（不完整）huffman樹的視覺顯示（這可能有助於理解算法的作用：無論何時遇到0：向右+向下;每當遇到1：go右+向上）;如果您擊中了一個結束節點：返回該節點處的字符並在根節點處重新啓動。