霍夫曼存儲位代碼

我建立了霍夫曼樹。但我不知道如何將代碼存儲到位，因爲我不知道如何處理可變長度。霍夫曼存儲位代碼

我想創建一個表，存儲huffman代碼位打印編碼的結果。

我不能使用像bitset這樣的STL包含器。

我已經嘗試這樣的

void traverse(string code = "")const 
    { 
     if(frequency == 0) return; 
     if (left) { 
      left->traverse(code + '0'); 
      right->traverse(code + '1'); 
     } 
     else {//leaf node 
      huffmanTable[ch] = code; 
     } 
    }

你能給我一些算法來處理呢？

我想存儲'0'使用1位和「1」使用1位。

Thx提前。

來源

2012-12-10 Liang-Yu Pan

上面粘貼的代碼使用字符串來保存位模式有什麼問題？ –

哦，我想存儲它的位，我不知道如何使用，因爲我不知道確切的長度。 –

有點只是一個值，只能是一個零或一個。一個只包含零和一個字符串的字符串是一串位。 –

您需要一個緩衝區，一個以字節爲單位跟蹤緩衝區大小的變量，以及一個用於跟蹤緩衝區中有效位數的變量。

存儲一位：

檢查平添幾分會增加存儲的字節數。如果不是，請跳到步驟4.
緩衝區中是否有空間來存儲額外的字節？如果是這樣，請跳至步驟4.
將存儲緩衝區重新分配幾個字節。複製現有數據。增加保存緩衝區大小的變量。
計算下一位將被存儲的字節位置和位位置。根據需要設置或清除該位。
遞增保存存儲位數的變量。

來源

2012-12-11 00:02:41

在重新實現這個之前，我建議看看'std :: vector '，它應該基本上按照你的建議來做。 – Mario

它的確如此！這取決於您正在使用的實現，但通常以8個向量條目存儲在一個字節內（即每位信息1位）的方式實現。（http://www.cplusplus.com/reference/vector/vector-bool/） – Mario

您可以使用一個固定大小的結構來存儲表，只是位存儲編碼輸入：

struct TableEntry { 
    uint8_t size; 
    uint8_t code; 
}; 

TableEntry huffmanTable[256]; 

void traverse(uint8_t size; uint8_t code) const { 
     if(frequency == 0) return; 
     if (left) { 
      left->traverse(size+1, code << 1); 
      right->traverse(size+1, (code << 1) | 1); 
     } 
     else {//leaf node 
      huffmanTable[ch].code = code; 
      huffmanTable[ch].size = size; 
     } 
}

對於編碼，可以使用發表David的算法。

來源

2012-12-11 00:03:20 perreal

可能是錯誤的，但不應該爲'code'設置/提供'1'的默認值？否則，您無法確定您使用「左」節點的頻率（例如，左5 + 1右3左+ 1右）。 – Mario

我認爲尺寸會做到這一點，對吧？ – perreal

是的，應該這樣做，雖然它不是非常有效，這取決於你的最大尺寸/深度/長度，因爲它與'uint8_t'的大小相比是1位。 – Mario

基本上我會用這裏的兩種不同的方法，根據樹的最大密鑰長度/深度：

如果你已經有了一個固定的長度，它比你的可用整數短數據類型（如long int），您可以使用perreal顯示的方法。
如果你不知道最大深度，並認爲你可能會用完空間，我會使用std::vector<bool>作爲代碼值。這是使用每個值一位的向量的特殊實現（實質上是David的方法）。

來源

2012-12-11 00:12:02 Mario

霍夫曼存儲位代碼

回答

相關問題