如何使用Python将Huffman编码写入文件？

Question

我用Python编写了一个使用霍夫曼算法压缩文本的脚本。假设我有以下字符串：

string = 'The quick brown fox jumps over the lazy dog'

运行我的算法会返回以下“位”：

result = '01111100111010101111010011111010000000011000111000010111110111110010100110010011010100101111100011110001000110101100111101000010101101110110111000111010101110010111111110011000101101000110111000'

通过比较结果的位数和输入字符串，该算法似乎是有效的：

>>> print len(result), len(string) * 8
194 344

现在问题来了：我如何将这个编码写入文件，同时仍然能够解码。你只能按字节写入文件，而不是按位。通过将“编码”写入字节，根本没有压缩！我对计算机科学还很陌生，网络资源对我来说并不太有用。非常感谢您的帮助！

编辑：请注意，我的编码类似于以下内容（针对另一个输入字符串'xxxxxxxyzz'）：

{'y': '00', 'x': '1', 'z': '10'}

我创建最终字符串的方式是按输入字符串的顺序连接这些代码：

result = '1111111001010'

如何从这个结果中恢复原始字符串？或者我完全理解错了吗？谢谢！

- Pim Klaassen

---

这可能对你有用：https://dev59.com/g3vaa4cB1Zd3GeqPD30N - Green Cloak Guy

当然，像那样的字符串可以被转换，但这真的是你想要做的吗？临时结果仍然会很大。 - harold

@harold 把文件存储为25字节而不是43字节，这是一个约40%的改进，看起来很值得。你指的是哪个临时结果？ - MoxieBall

@MoxieBall 是的，一块一块地，当他附加个别代码时 - 然后在内存中保存的字符串永远不会变得非常大。实际上，也可以使用整数算术来完成，而不是字符串，这样就不再需要进行任何转换了。 - harold

嘿，大家好，感谢你们的回答。我编辑了我的帖子，以便更清楚地表达我的问题。 - Pim Klaassen

Answer 1

首先，您需要将输入字符串转换为字节:

def _to_Bytes(data):
  b = bytearray()
  for i in range(0, len(data), 8):
    b.append(int(data[i:i+8], 2))
  return bytes(b)

接下来，以二进制模式打开一个文件进行写入：

result = '01111100111010101111010011111010000000011000111000010111110111110010100110010011010100101111100011110001000110101100111101000010101101110110111000111010101110010111111110011000101101000110111000'
with open('test.bin', 'wb') as f:
  f.write(_to_Bytes(result))

现在，将原始字符串写入文件，可以进行字节比较：

import os
with open('test_compare.txt', 'a') as f:
  f.write('The quick brown fox jumps over the lazy dog')

_o = os.path.getsize('test_compare.txt')
_c = os.path.getsize('test.bin')
print(f'Original file: {_o} bytes')
print(f'Compressed file: {_c} bytes')
print('Compressed file to about {}% of original'.format(round((((_o-_c)/_o)*100), 0)))

输出：

Original file: 43 bytes
Compressed file: 25 bytes
Compressed file to about 42.0% of original

为了恢复原始内容，可以编写一个函数来确定字符的可能排序：

d = {'y': '00', 'x': '1', 'z': '10'}
result = '1111111001010'
from typing import Generator
def reverse_encoding(content:str, _lookup) -> Generator[str, None, None]:
  while content:
    _options = [i for i in _lookup if content.startswith(i) and (any(content[len(i):].startswith(b) for b in _lookup) or not content[len(i):])]
    if not _options:
      raise Exception("Decoding error")
    yield _lookup[_options[0]]
    content = content[len(_options[0]):]

print(''.join(reverse_encoding(result, {b:a for a, b in d.items()})))

输出：

'xxxxxxxyzz'

- Ajax1234

---

谢谢您的回答！我编辑了我的帖子，以澄清关于文件解码的问题。 - Pim Klaassen

谢谢，这正是我在寻找的！ - Pim Klaassen

@PimKlaassen 很高兴能帮忙。 - Ajax1234