霍夫曼編碼：如何在Python中編寫二進制數據

Question

我已經嘗試過使用結構模塊的方法，如我的代碼中註釋掉的行所示，但它沒有解決。基本上我有兩種選擇：我可以通過代碼寫入二進制數據代碼（我的代碼是長度從3到13比特的比特序列），或者轉換整個字符串（本例中n = 25000 +），到二進制數據。但我不知道如何實現這兩種方法。代碼：

import heapq 
import binascii 
import struct 

def createFrequencyTupleList(inputFile): 
    frequencyDic = {} 

    intputFile = open(inputFile, 'r') 
    for line in intputFile: 
     for char in line: 
      if char in frequencyDic.keys(): 
       frequencyDic[char] += 1 
      else: 
       frequencyDic[char] = 1 

    intputFile.close() 
    tupleList = [] 
    for myKey in frequencyDic: 
     tupleList.append((frequencyDic[myKey],myKey)) 
    return tupleList 

def createHuffmanTree(frequencyList): 
    heapq.heapify(frequencyList) 
    n = len(frequencyList) 
    for i in range(1,n): 
     left = heapq.heappop(frequencyList) 
     right = heapq.heappop(frequencyList) 
     newNode = (left[0] + right[0], left, right) 
     heapq.heappush(frequencyList, newNode) 
    return frequencyList[0] 

def printHuffmanTree(myTree, someCode,prefix=''): 
    if len(myTree) == 2: 
     someCode.append((myTree[1] + "@" + prefix)) 
    else: 
     printHuffmanTree(myTree[1], someCode,prefix + '0') 
     printHuffmanTree(myTree[2], someCode,prefix + '1') 

def parseCode(char, myCode): 
    for k in myCode: 
     if char == k[0]: 
      return k[2:] 


if __name__ == '__main__': 
    myList = createFrequencyTupleList('input') 
    myHTree = createHuffmanTree(myList) 
    myCode = [] 
    printHuffmanTree(myHTree, myCode) 
    inputFile = open('input', 'r') 
    outputFile = open('encoded_file2', "w+b") 
    asciiString = '' 
    n=0 
    for line in inputFile: 
     for char in line: 
      #outputFile.write(parseCode(char, myCode)) 
      asciiString += parseCode(char, myCode) 
      n += len(parseCode(char, myCode)) 
    #values = asciiString 
    #print n 
    #s = struct.Struct('25216s') 
    #packed_data = s.pack(values) 
    #print packed_data 
    inputFile.close() 
    #outputFile.write(packed_data) 
    outputFile.close() 

Answer 1

您正在尋找這樣的：

packed_data = ''.join(chr(int(asciiString[i:i+8], 2)) 
         for i in range(0, len(asciiString), 8)) 

這將需要8位在同一時間從asciiString，其解釋爲整數，並輸出相應的字節。

這裏你的問題是這需要asciiString的長度是8位的倍數才能正常工作。如果不是，你會在最後幾位實際位之前插入零位。

所以你需要將位數存儲在最後一個字節的某個位置，所以你知道在返回時忽略這些位，而不是將它們解釋爲零。你可以嘗試：

packed_data = chr(len(asciiString) % 8) + packed_data 

然後，當你讀回：

packed_input = coded_file.read() 
last_byte_length, packed_input, last_byte = (packed_input[0], 
              packed_input[1:-1], 
              packed_input[-1]) 
if not last_byte_length: last_byte_length = 8 
ascii_input = ''.join(chain((bin(ord(byte))[2:].zfill(8) for byte in packed_input), 
         tuple(bin(ord(last_byte))[2:].zfill(last_byte_length),))) 
# OR 
# ascii_input = ''.join(chain(('{0:0=8b}'.format(byte) for byte in packed_input), 
#      tuple(('{0:0=' + str(last_byte_length) + '8b}').format(last_byte),))) 

編輯：您可能需要剝離由bin()返回字符串「0B」，或2.6或更高版本，最好使用我添加的新替代版本使用字符串格式代替bin()，切片和zfill()。

編輯：謝謝eryksun，很好用的鏈，以避免複製的ASCII字符串。另外，需要在bin()版本中調用ord(byte)。