c++ - 香农法诺编码算法生成的代码解码

Question

我已经使用 shannon fano 算法为文件中的不同符号生成了代码。现在我的问题是如何将这些代码存储到文件中(因为文件是以字节为单位的)，以便在阅读时，读者可以确保在某个时候，它是特定符号代码的结尾。这样多余的代码就不会被读取。

Answer 1

首先，您可以使用按位运算从字节数组中读取可变位数(不是 8 的倍数)。

其次，如果代码是有效的 Prefix code , 满足

there is no valid code word in the system that is a prefix (start) of any other valid code word in the set

然后您可以通过将前缀与表格进行比较来确定代码的结束位置。

---

通常，这是通过以下方式完成的:

• 假设代码长度为 1 到 16 位。
• 从文件中加载接下来的 16 位到变量。
• 将 16 位变量与包含以下值的表格进行比较。可以使用二进制搜索或基数搜索。
  • Key:Shannon-Fano 或 Huffman 代码，移位后最高位位于最高有效位。
  • KeyLength:Shannon-Fano 或 Huffman 码中的实际位数。这允许我们从变量中减去解码位数。
  • 值:代码将解码的值。
• 根据代码从变量中减去(移除)解码位。例如，如果代码有 9 位，我们将从 MSB 中删除 9 位并保留剩余的 7 位。
• 从文件中读取接下来的 9 位，与未解码的 7 位连接。
• 重复该过程。