將位串轉換爲字節（霍夫曼編碼）

Question

在用於解壓縮的霍夫曼編碼中，您必須將比特流與幾個值（前綴空白）進行比較。我試圖在python中實現一個huffman編碼器解碼器，這是我的代碼將比特流轉換爲ascii-values。

c = '' 
l = 0 
x = 1 
stime = time.time() 
while l<len(string): 
    if string[l:l+x] in table: 
     c+=table[string[l:l+x]] 
     l+=x 
     x = 1 
    else: 
     x+=1 

我該怎麼做才能使這個循環更有效率？

Answer 1

快速：

首先，確保你已經建立了一個規範Huffman編碼，其中較短的代碼來數值較長碼之前。首先將您的霍夫曼代碼描述爲每個符號的位數，這很容易實現。然後按照符號順序將霍夫曼編碼分配給最短編碼，然後按照符號順序編碼下一個最短編碼，依此類推。例如。

Symbol Bits 
    A  2 
    B  4 
    C  3 
    D  3 
    E  2 
    F  3 
    G  4 

排序比特，由符號保持排序：

Symbol Bits 
    A  2 
    E  2 
    C  3 
    D  3 
    F  3 
    B  4 
    G  4 

分配霍夫曼碼，從零開始：

Symbol Bits Code 
    A  2  00 
    E  2  01 
    C  3  100 
    D  3  101 
    F  3  110 
    B  4  1110 
    G  4  1111 

該規範的方法提供了一種傳輸霍夫曼碼的緊湊裝置從壓縮器到解壓縮器，因爲您不必發送實際代碼或樹 - 只是每個符號的代碼長度。然後代碼可以如上構建在另一端。

現在我們創建解碼錶，符號表，Symbol[] = "AECDFBG"和代碼索引表：

Bits Start  Index 
    2 0000 (0)  0 
    3 1000 (8)  2 
    4 1110 (14) 5 

現在解碼，就可以從2至4位的循環，看看你的代碼小於下一個比特大小的起始碼。我們從流中拉出4位，並將其稱爲nyb（如果流中沒有四個位，只需附加零位來填充）。在僞使用代碼if的，而不是循環，>>裝置轉換位下：

if nyb < Start[Bits are 3] (= 8) then 
    output Symbol[Index[Bits are 2] (= 0) + (nyb - Start[Bits are 2] (= 0)) >> 2] 
    remove top two bits from bitstream 
else if nyb < Start[Bits are 4] (= 14) then 
    output Symbol[Index[Bits are 3] (= 2) + (nyb - Start[Bits are 3] (= 8)) >> 1] 
    remove top three bits from bitstream 
else (must be four bits) 
    output Symbol[Index[Bits are 4] (= 5) + (nyb - Start[Bits are 4] (= 14))] 
    remove top four bits from bitstream 

它應該是很容易看到如何把它轉換成一個循環，從最短的代碼長度將第二最長代碼長度，如果你沒有找到它，它必須是最長的代碼長度。

更快：

構建查找表，其長度爲2 **（最長的碼的長度）。表中的每個條目都包含代碼中的位數和結果符號。您將比特流的多個比特用作索引。同樣，如果比特流沒有剩下那麼多比特，那麼用零填充。然後，您只需輸出該索引條目中的符號，並從比特流中刪除該索引條目中的位數（可能少於您爲索引提取的位數 - 請確保將未使用的位保留在比特流）。重複，現在您要從剩餘比特流中取出第一個未使用的比特。

在下一級的複雜程度，你可以做zlib做什麼。如果最長的代碼相對較長（在zlib中最多可以達到15位），但與以下方法相比，創建表格所用的時間可能不會節省解碼時間。有一個兩級表，其中第一級表覆蓋n位，其中n小於最長代碼。 （在zlib中，對於15位代碼，最佳選擇結果爲n == 9）。然後，如果代碼爲n位或更少，表項將提供符號和位數，然後按上述步驟繼續。如果代碼的位數大於n，那麼您將轉到該位處的子表，該位處理剩餘的位，如上所述。該表項指示爲子表拉取多少位，並定義該子表的大小，將其稱爲k。您從流中刪除頂部的n位，並拉下一個k位，並將其用作子表的索引。然後你得到代碼中剩餘位的符號和數量，並像在單級表中一樣繼續。請注意，n+k不一定是每個子表的最長代碼的長度，因爲該子表可能只覆蓋較短的代碼。只有最後一個或幾個子表的n+k等於最長代碼的長度。

這可能相當快，因爲​​通過構建霍夫曼代碼，較短的代碼更可能。大多數情況下，你會在第一級獲得符號，並且偶爾需要進入第二級。要填入主表和所有子表中的表條目總數可能比大表中包含全部代碼長度的條目數少得多。準備解碼的時間隨後減少。

如果你有更長的霍夫曼代碼（例如32位），你可以有更多級別的子表。需要進行一些實驗來確定子表的最佳斷點，這取決於發送新代碼的頻率和表的建立頻率。

Answer 2

如果您準備花費更多時間建立表格，您可以更快地進行解碼，因爲您可以構建一組表格以便一次處理一個字節的比特流，而且不必移位或屏蔽輸入流以挑選出單個位。

你想建立一組表，使得解碼的字節流是這樣的：

state = 0 
for (input in inputBytes) 
    output += outputTable[state][input] 
    state = stateTable[state][input] 

輸出。這裏將是ASCII值的一個可變長度的字符串。 State必須記住前一個字節或尚未變成輸出數據的字節中的所有信息。構建這些表的一種方法是使狀態0成爲初始狀態 - 當您剛剛讀取輸入數據的第一個字節時。然後，對於每個字節，儘可能多地解碼並使用它來生成outputTable [0] [byte]。現在查看字節末尾所有未使用位的字符串。對於這些字符串中的每一個，您都需要分配一個新的狀態，並且您需要針對所有可能的字節對這些狀態中的每個狀態執行相同類型的表構建。當你這樣做時，解碼後你最終還會得到未使用的比特串。如果這些是位串，你已經爲狀態分配了狀態，你可以忽略它們並繼續。如果不是，則需要分配更多狀態。最終你會建立表格來處理所有可能的狀態。