結合無損數據壓縮算法

Question

我想知道我們可以採取多大程度的無損數據壓縮;我無法找到無損算法的在線模擬器來執行一些經驗測試。 我可以自己做一個，但不幸的是我在這段時間沒有足夠的時間;仍然我很好奇我有一個直覺，我將解釋。

讓我們只用兩個更流行的算法：Huffman Coding和Run-lenght Enconding。

讓我們假設我們有一個數量的字母A符號，並從該字母符號的任意長的順序：例如：現在

Alphabet = {A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, X, W, Y, Z} 
Sequence1 = SFBJNERUSNJGSDKKDEIJGNMSDJDDSUSJNF 
Sequence2 = MNMNMNREGUHSDFJUF 
Sequence3 = MMMMMNNNNNASDUERJGASIUJMMMNNNUNS 

，如果我們只是用一個固定lengh代碼中的每個符號字n位我們有未壓縮的序列，那就是說，N位。

如果我們使用霍夫曼編碼序列，我們將使用H位而不是N位，節省(1-H/N)*100%位空間。

如果我們使用RLE編碼相同的序列，我們將使用R位，節省(1-R/N)*100%。

我想知道，如果我們應用或Huffman + RLE會發生什麼情況，我們可以比僅使用其中一個節省更多空間。

對我來說這似乎是一個非常基本的想法，但是使用谷歌搜索，我沒有找到任何關於此主題的內容。

編輯：嗯，我可能並不認爲如果我先使用RLE，我將無法使用霍夫曼，因爲單個符號的固定長度代碼的聲明將會丟失;但仍然應該可以先使用霍夫曼和RLE。

順便說一句我對它的邏輯感興趣，我的意思是使用系列多個無損壓縮算法。

編輯2：當我評論馬克阿德勒的回覆時，我意識到我可能已經找到了我的問題的答案。這是它：

霍夫曼，它是一個符號符號代碼如何影響檢測？

假設我們有以下代碼：AABCABAAB。 在純二進制中，它將被編碼爲00 00 01 10 00 01 00 00 01（obv空格僅用於可讀性目的）。霍夫曼將其編碼爲0 0 11 10 0 11 0 0 11。空間顯示了更多字符串沒有被改變的情況，所以假設我們正在接近這個範​​圍的代碼（符號方式），可以檢測到相同數量的重複。

這引發了我另一個觀點（我不會在這裏討論，因爲這已經是一個非常長的評論）：按位分析代碼。因此，我實際上認爲我得出了一個結論：正如我們所知，任何字典（或基於替代的）編碼器將可變數量的符號分組爲固定長度的碼字，而霍夫曼（或任何其他熵編碼器）碼將固定長度的符號分成可變數量的比特，從而將熵逼近到最小值; ergo，讓Huffman先運行是沒有意義的（也只是浪費計算），因爲其他算法很可能會引入更多冗餘的霍夫曼可能能夠減少。

當然，這只是一個理論論文，因爲在實踐中我們可以考慮其他因素（例如計算時間）......更不用說要編碼的字符串的不同配置會導致不同的結果。但是，呃...對我來說很有意義。 :)

Answer 1

這些種類的組合是按慣例完成的。你應該閱讀一些關於壓縮的書籍。

LZ77是一種更一般的RLE形式，它可以複製以前字符串的重複。 （距離1和長度的匹配n編碼的運行n最後字節的副本）。LZ77通常在霍夫曼，算術或範圍編碼之後。

霍夫曼應該遵循LZ77或RLE，而不是先於它。霍夫曼編碼會使檢測重複變得更難，更不容易。爲了首先使用RLE，您只需將文字擴展到文字之外即可。作爲一個例子，在zip，gzip，zlib等中使用的Deflate格式具有設置爲對256個字面字節，29個長度前綴碼和流代碼的一端進行編碼的286符號。 29個長度前綴代碼中的每一個代碼都包含一個0到5位後綴，該代碼後面的代碼將添加到基本值以獲取長度。長度碼及其後綴的存在意味着後面跟着另一個霍夫曼碼，它是30個距離碼前綴之一，每個後綴都有一個0到13位的後綴，用於指定匹配的距離。

還有很多其他的變換（它們自己可能壓縮也可能不壓縮）之後是熵編碼。這些包括經常遵循BWT的Burrows-Wheeler變換（BWT），移動到前部變換（MTF），用於圖像的離散餘弦變換（其可以無損地完成，但最常用於有損壓縮算法中）等等。以可逆的方式轉換數據中的組共同性，爲熵編碼步驟提供更多的增益。