能否通过已知未压缩数据前缀匹配Deflate压缩数据的初始字节?
我在研究Deflate压缩时陷入了瓶颈,但仍认为相关流程存在优化空间。
目前我的理解
def lz77(uncompressed): # 查找重复字符并替换为引用 # 输出格式示例:m0,0 a0,0 l0,0 3,1 return lz77 encoded data def huffmanencode(lz_data): # 编码数据 # 在每个块开头添加块类型标识符 # 写入Huffman编码数据 # 写入块结束或新块标识符
场景设定
原始未压缩输入文本为:
I am considered a loser in this society, entrapped evilness inside of me now you gimmick you are not what i try to be. Drug deals in back
alleys like a demented game of hide and seek Toast an average rape on
a bad day, i haven't even begun to ride my peek But moving into adult
hood my future is bleak.
使用7zip或WinRAR的默认参数对其进行Deflate压缩。
但我仅知晓未压缩数据的前缀部分:
I am considered a loser in this society, entrapped evilness inside of
me
我需要通过该已知前缀获取原始压缩数据的前若干字节。
我的假设
由于已知数据位于未压缩内容的最开头,理论上可针对Deflate压缩的第一步LZ77寻求突破。LZ77(原始未压缩数据)与LZ77(已知前缀)的输出应共享最高有效位。
最困难的部分是Huffman编码输出——测试中其结果经常变化,但如果我知晓重建Huffman树所需的近似长度或编码,且长度小于4字节,便可进行暴力破解。
结论:若LZ77输出开头部分一致,获取Huffman树信息后,必定能得到相同的最高有效位。
我一直在研究Pyflate工具,试图解析压缩时使用的Huffman编码信息,但理解起来存在困难。
核心问题
仅通过原始输入数据的前缀部分,能否获取压缩数据中相同的最高有效位?
实际目标
利用以下已知前缀内容:
MIME-Version: 1.0 Date: Sun, 18 Feb 2024 15:02:54 +0200 From:
获取完整内容压缩后的最高有效位,完整内容为:
MIME-Version: 1.0 Date: Sun, 18 Feb 2024 15:02:54 +0200 From: Bluebird <servicing@app.bluebird.com> Subject: Your monthly statement is available Thread-Topic: Your monthly statement is available Message-ID: <20240218130253.16d4687e27ab5f61@app.bluebird.com> To: "tfanklin0@gmail.com" <tfanklin0@gmail.com>
若无法实现,我需要知晓上述内容对应的Huffman编码或树的大小。
内容的提问来源于stack exchange,提问作者terry franklin

