我正在尝试实现文件的霍夫曼压缩和解压缩，其中解压缩所需的所有信息都必须包含在压缩文件中。对于这个实现，我想在压缩文件中包括频率表，这样解压缩程序可以从这个频率表重建霍夫曼代码，然后解压缩文件。频率表看起来像这样，其中每个索引映射到ASCII字符的十进制表示：
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 847, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4183, 13, 0, 0, 0, 6, 0, 0, 26, 26, 0, 107, 84, 598, 124, 36, 72, 66, 42, 21, 8, 16, 9, 11, 10, 10, 46, 0, 0, 7, 0, 3, 0, 21, 30, 4, 20, 19, 30, 5, 34, 35, 0, 9, 19, 15, 7, 10, 9, 0, 8, 15, 19, 1, 9, 8, 2, 1, 8, 24, 29, 24, 23, 8, 0, 439, 189, 40, 252, 1514, 226, 241, 82, 462, 62, 353, 346, 306, 521, 436, 212, 0, 977, 512, 663, 100, 176, 24, 10, 53, 9, 23, 374, 23, 2, 0, 197, 0, 0, 0, 0, 3, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 65, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 90, 0, 124, 0, 0, 75, 14, 0, 0, 49, 0, 33, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 66, 0, 0, 34, 0, 0, 0, 0, 0, 0, 157, 154, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 49, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 200, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
也就是说，列表的索引32是4183，这告诉我SPACE(ASCI#32)在压缩文件中出现4183次。
我还准备了代码来创建霍夫曼代码，并将每个字符转换为其霍夫曼代码，然后将其附加到一个长比特串中。以下代码是有效的，它将比特串转换为字节数组并将其保存为二进制文件：
byte_array = bytearray()
for i in range(0, len(bitstring), 8):
byte = bitstring[i:i + 8]
byte_array.append(int(byte, 2))
with open(output_file_path, "wb") as compressed_file:
compressed_file.write(bytes(byte_array))
生成的二进制文件被成功地从17KB压缩到了10KB。
我的问题是试图在这个压缩文件的开头包含频率表。我尝试了几种解决方案，但遇到了问题，感觉很吃力。
有没有一种简单的方法可以在Python中的压缩文件的开头包含如上所述的频率表？对于可以用于实现这一点的方法或功能的任何提示都将不胜感激。
我想用频率表来实现这一点，而不是使用规范霍夫曼代码。同样，仅压缩文件和其他信息必须足以在不丢失的情况下解压缩文件。
我已经尝试了几种我发现的函数和方法，但我对处理字节还很陌生，我尝试过的每一种方法，例如将列表转换为字节数组，都失败了。因为该列表包括整数>255，它不会像比特串那样转换为字节数组。
编辑：
我现在发送的是霍夫曼树，而不是建议的频率表，但树并没有完全重建。大多数叶节点都放在正确的位置，但不是全部。
以下代码创建霍夫曼代码，同时创建表示霍夫曼树的位串：
def __create_huffman_codes(self, current_node, current_huffman_code):
if not current_node:
return
self.huffman_tree_binary += "0"
if current_node.char:
self.huffman_tree_binary += "1"
self.huffman_tree_binary += bin(current_node.char)[2:].rjust(8, "0")
self.huffman_codes[current_node.char] = current_huffman_code
self.__create_huffman_codes(current_node.left, current_huffman_code + "0")
self.__create_huffman_codes(current_node.right, current_huffman_code + "1")
这个方法在类的主方法中被调用如下：
huffman_tree_root = self.huffman_tree.pop()
current_huffman_code = ""
self.__create_huffman_codes(huffman_tree_root, current_huffman_code)
self.huffman_tree_binary += "00"
我加了两个尾随的零，因为霍夫曼树的二进制表示总是以350.75字节结束。
创建压缩字节的方法已更新：
def __create_bytes(self, bitstring):
byte_array = bytearray()
for i in range(0, len(self.huffman_tree_binary), 8):
byte = self.huffman_tree_binary[i:i + 8]
byte_array.append(int(byte, 2))
for i in range(0, len(bitstring), 8):
byte = bitstring[i:i + 8]
byte_array.append(int(byte, 2))
return byte_array
然后将字节写入一个二进制文件。
另一方面，为了重建树，我调用以下方法：
def huffman_decompress(self):
[... open file ...]
[... read bytes ...]
if self.huffman_tree_binary.pop(0) == "0":
self.huffman_tree_root = Node(None)
self.huffman_tree_root.left = Node(None)
self.huffman_tree_root.right = Node(None)
self.__rebuild_huffman_tree(self.huffman_tree_root.left)
self.__rebuild_huffman_tree(self.huffman_tree_root.right)
[... decompression ...]
def __rebuild_huffman_tree(self, current_node):
if len(self.huffman_tree_binary) == 0:
return
self.huffman_tree_binary.pop(0)
if self.huffman_tree_binary[0] == "1":
self.huffman_tree_binary.pop(0)
bits = ""
for _ in range(8):
bits += self.huffman_tree_binary.pop(0)
current_node.char = int(bits, 2)
else:
current_node.left = Node(None)
current_node.right = Node(None)
self.__rebuild_huffman_tree(current_node.left)
self.__rebuild_huffman_tree(current_node.right)
这肯定不是递归重建树的最优雅的实现，但我不明白为什么一小部分叶节点最终会出现在树中的不同位置。我想(自然地)我如何构建二进制表示预压缩或如何重建树肯定有问题，但我还没有弄清楚哪一个可能是错的。
否，您不希望将频率表包含在压缩数据中。您正在尝试压缩，因此希望使用尽可能少的位来提供解压缩所需的信息。发送频率表是最糟糕的方式。频率表包含重构霍夫曼码不需要的无关信息。许多不同的频率表将产生相同的霍夫曼代码。
相反，您希望发送根据频率表计算的霍夫曼代码的表示形式。两种最常见的方法是发送树，或者发送code length。
您可以非常容易地发送霍夫曼树，只需递归遍历树，就像创建霍夫曼代码所必须做的那样，并为遇到的每个节点发送0位，然后为遇到的每一个叶发送1位，再为编码的符号发送8位。就是这样。没有什么比这更容易的了。然后，您可以使用递归直接在另一端重建树，并使用该树进行解码。这个树表示是自终止的，因此后面紧跟着数据的代码。
在您的示例中，您正在对100个不同的符号进行编码。然后，树将具有99个节点和100个叶子，因此需要99+900=999个比特。为了进行比较，如果频率表表示为每个频率两个字节，则需要4096位。或者，如果每个频率四个字节，如这里的另一个答案所示，那么8192位！我可以想象用一个字节编码频率高达127，用两个字节编码更高的频率，并将其降低到2148位。仍然是999位的两倍多。
尽管您排除了它，但使用规范霍夫曼代码可以做得更好，在规范霍夫曼代码中，您只能根据每个符号的代码长度而不是树来构建代码。然后，您可以发送代码长度，并在解码结束时遵循相同的构建过程。然后，你可以在这些长度上使用霍夫曼编码，在它前面有一个非常小的霍夫曼代码表示。这就是放气压缩中所做的操作。Deflate用608位表示示例中的代码。
有问题的新代码的更新：
正如我上面所说的；为遇到的每个节点发送0比特，并为遇到的每一个叶编码的符号发送1比特后接8比特"；。每次呼叫__create_huffman_codes时，您总是发送一个0。如果是节点，则只发送0；如果是叶，则发送1，后跟符号only。此外，如果它是一个叶子，则不需要调用__create_huffman_codes。你完了。如果__create_huffman_codes是一个节点，则仅调用它(两次)。
此外，毫无理由地将这两个零相加以将树描述带到字节边界只是浪费比特，这会使解码变得复杂。只需在最后一个霍夫曼树比特之后立即发送第一个符号代码比特。
您可以在二进制文件的开头写入频率表，将整数转换为字节：
FREQ_TABLE_LEN = 256
def write_frequency_table(f, table):
assert len(table) == FREQ_TABLE_LEN
for e in table:
f.write(e.to_bytes(4, byteorder='little', signed=False))
def read_frequency_table(f):
read_table = []
for _ in range(FREQ_TABLE_LEN):
data = f.read(4)
number = int.from_bytes(data, 'little', signed=False)
read_table.append(number)
return read_table
以下是如何使用以前代码的示例：
with open('compressed_file.bin', 'wb') as f:
write_frequency_table(f, freq_table) # freq_table is the list of integers in your question
# write the real content of your file here
with open('compressed_file.bin', 'rb') as f:
freq_table = read_frequency_table(f)
# read the rest of your file