使用小字典的压缩算法

Question

我正在寻找一种适用于小于一个字节的符号的压缩算法。我做了一个关于压缩算法的快速研究，很难找出所用符号的大小。无论如何，有符号小于8位的流。是否有DEFLATE参数来定义其符号的大小？

Answer 1

明文符号不是一个字节的小

LZ77和LZ78的原始描述描述它们中的十进制数字（即大约一个字节的大小的一半符号）的序列方面。

如果你是谷歌的“DNA压缩算法”，你可以得到一些专门针对压缩文件的算法的信息，这些算法几乎完全由4个字母AGCT组成，一个4个符号的字典，每个约1/4小到一个字节。 也许其中一种算法可能适用于你，但调整相对较少。

在LZMA中使用的LZ77风格的压缩对于压缩的前几个符号似乎每个符号使用两个字节。 但是在压缩几百个明文符号 （自然语言文本的字母，或十进制数字的序列，或代表DNA碱基的4个字母的序列等）之后，两字节压缩的“块”即LZMA推出往往代表十几个或更多的明文符号。 （我怀疑所有类似算法也是如此，例如DEFLATE中使用的LZ77算法）。

如果您的文件只使用少于全部256个可能字节值的受限制字母表，则原则上程序员可以修改DEFLATE（或某种其他算法）的变体，以利用该字母表的信息生成压缩文件的大小比使用标准DEFLATE压缩的相同文件小几个比特。然而，许多面向字节的文本压缩算法--LZ77，LZW，LZMA，DEFLATE等构建了常用长字符串的字典，并且可以在该定制字符的几个百分比内给出压缩性能（具有足够大的源文件）自适应变体 - 通常使用标准压缩文件格式的好处值得牺牲几个百分比的潜在空间节省。

压缩符号不是一个字节的小

许多压缩算法，包括一些给出最佳已知的压缩上基准文件，输出的压缩信息的逐位（如大部分PAQ一系列压缩机的，以及某些类型的算术编码器），而另一些则输出可变长度的压缩信息而不考虑字节边界（如霍夫曼压缩）。

描述算术编码的一些方法讨论被压缩为“少于一位信息”的诸如单个位或像素的信息片段。

编辑： “计数参数”解释了为什么不可能将所有可能的字节，更少的所有可能的字节和一些常见的字节序列压缩成小于8位长的码字。然而，通过“牺牲”或“转义”不太常见的字节，几个压缩算法可以并且通常代表一些字节或者（更少见）代表一些字节序列，每个字节序列具有小于8位长的码字由其他码字（包括“逃逸”）表示的长度超过8位。

这种算法包括：

• 派克Text compression using 4 bit coding
• 面向字节霍夫曼
• 几个combination algorithms该执行文件的LZ77状解析成“符号”，其中每个符号代表的序列字节，然后Huffman压缩这些符号 - 例如DEFLATE，LZX，LZH，LZHAM等。

派克算法使用4位“01 01“来表示'e'（或在某些情况下为'E'），8位”0000 0001“表示单词”the“（4字节，包括之前的空格）（或在某些情况下为”The“或“THE”）等。 它包含一个包含约16个极其常见的英语单词的子词典的约200个最常用英语单词的小型词典， 。

当使用面向字节霍夫曼编码压缩英文文本时，序列“e”（e空间）被压缩为总共通常为6位的两个码字。当涉及霍夫曼编码时，我不能告诉你这些“小”码字的确切大小，甚至不能告诉你一个小码字表示什么字节或字节序列，因为它对于每个文件都是不同的。 通常，相同的码字表示同一文件中不同位置的不同字节（或不同的字节序列）。 解码器根据报头中压缩器留下的线索和目前解压缩的数据来决定码字表示哪个字节或字节序列。使用范围编码或算术编码，“码字”可能甚至不是整数个比特。

Answer 2

你可能想看看哥伦布代码。 golomb代码使用分而治之算法来压缩inout。这不是字典压缩，但值得一提。