使用小字典的壓縮算法

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。這不是字典壓縮，但值得一提。