哪种算法最适合大型文本压缩?



目前,我正在寻找一种适用于大量文本的无损压缩算法,该算法将由AES进一步加密并用作隐写术中的有效载荷。

编辑:

基于文本压缩算法的比较研究,似乎 算术编码在统计压缩技术中更可取,而LZB建议用于字典压缩技术。

所以现在我想知道统计压缩还是字典压缩在压缩比和易于实现方面更适合大型英语文本压缩。

我已经搜索了,但仍然对合适的算法几乎一无所知。非常感谢您抽出时间回答。有好的一天。:)

你在这个问题中描述的许多算法都被称为熵编码器(Shannon-Fano、Huffman、算术等)。熵编码器用于压缩符号序列(通常是字节),其中某些符号比其他符号更频繁。用于压缩自然语言的符号(字母)的简单熵编码只会产生大约 2:1 的压缩。

相反,流行的现代文本无损压缩技术包括 LZ77、LZW 和 BWT 等方法。粗略地说,LZ 系列涉及构建一个重复出现的短符号序列字典(我们称之为"单词"),然后使用指针来引用这些单词。LZ的一些实现,如LZ77和LZW,编码起来相当简单,但可能不会产生最高的压缩比。例如,请参阅此视频:https://www.youtube.com/watch?v=j2HSd3HCpDs。在频谱的另一端,LZMA2 是一种相对更复杂的变体,具有更高的压缩比。

Burrows-Wheeler变换(BWT)为字典方法提供了一种聪明的替代方案。我会推荐你参考维基百科的文章,https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform

简而言之,它产生了原始字节序列的(可逆)排列,通常可以通过运行长度编码后跟熵编码器非常有效地压缩。

如果我必须从头开始编写压缩技术,为了简单起见,我可能会使用 LZW 或 LZ77。

Shannon-Fano 编码、霍夫曼编码、算术编码、范围编码和非对称数字系统编码都是在您首次对数据进行建模应用的零阶熵编码器,利用了固有的冗余。

对于文本,冗余是数据中的重复字符串和高阶相关性。有几种方法可以对文本进行建模。最常见的是Lempel-Ziv 77,它寻找匹配的字符串,Burrows-Wheeler变换(查找描述)和部分匹配的预测。

查看大文本压缩基准测试,查看压缩、压缩速度、使用的内存和解压缩速度方面的比较。

相关内容

  • 没有找到相关文章

最新更新