壓縮算法的完整描述

我正在尋找一種壓縮算法（對於編程競賽），我需要如何實現它的全部描述（所有技術細節），任何無損和免專利算法都可以做到，但便於實現是一個獎金:)壓縮算法的完整描述

（儘管可能是無關緊要的）我計劃實現在C++算法...

在此先感謝。

編輯：我會被壓縮純文本文件，沒有其他類型的文件...

2009-07-15 Lawand

RFC 1951描述了充氣/放氣，包括壓縮機算法的簡要描述。 Antaeus Feldspar的An Explanation of the Deflate Algorithm提供了更多的背景。

此外，zlib源代碼發行版在contrib/puff/puff.c中包含一個簡化的參考inflater，它可以幫助閱讀以準確理解比特的排列方式（但不包含放氣，只是充氣）。

2009-07-15 13:28:06 puetzk

我在Google上搜索Google之前搜索了Google，發現了Feldspar的解釋，但它缺乏知道如何實現DEFLAT所需的「技術細節」，但第一個鏈接似乎正是我所要找的，謝謝 – Lawand 2009-07-15 13:40:25

我在維基百科開始here。

有很多選擇，但不知道更多關於你想要什麼，它很難幫助更多。你是壓縮文本，圖像，視頻還是隨機文件？每個人都有自己的一套技術和挑戰，以獲得最佳效果。

如果易用性是我使用「filecopy」壓縮的唯一標準。保證壓縮比正好是1：1，並且實現簡單...

2009-07-15 13:17:21 Roddy

Huffman很好，如果你壓縮純文本。以下所有的評論者向我保證它的實現;D

2009-07-15 13:18:57

我已經實現了它，實際上我認爲它非常乾淨，並且一旦理解了算法就不會那麼困難。 – 2009-07-15 14:11:59

與放氣，任何類型的算術編碼或Burrows-Wheeler轉換相比，這是非常容易的。唯一比較容易的是運行長度編碼，這對文本來說很糟糕。 – 2009-07-24 16:54:30

直線LZ77（僅回溯，4位超3長度和12位回溯）比霍夫曼容易，解碼更快。然而，編碼很慢，而且天真的做法。 – Nosredna 2009-07-24 17:58:30

好一個歡樂，我不能走那麼遠，完成了比賽你，但請查看這篇文章的wiki：Run Length Encoding。這是迄今爲止最簡單的數據壓縮方法之一，儘管並不總是有效的。壓縮也是領域特定的，即使在無損算法中，您會發現什麼您正在壓縮確定如何最好來編碼它。

2009-07-15 13:19:04

同意！壓縮明文與例如機器語言之間存在巨大差異。 – 2009-07-15 14:12:13

如果您在互聯網瀏覽器的「查看」下，應該選擇「縮小」或縮小文本。

選擇那些和一個...

BAM！

你剛剛在同一屏幕上獲得更多文本！耶壓縮！

2009-07-15 13:32:24 samoz

Security Now! podcast最近推出了一集突出顯示數據壓縮算法。 Steve Gibson對Huffman和Lempel-Ziv壓縮技術的基礎做了很好的解釋。您可以收聽音頻播客或閱讀Episode 205的成績單。

2009-07-24 17:32:50 spoulson

易用性：霍夫曼，如前所述。我相信LZW不再受專利保護，但我不確定。這是一個相對簡單的算法。雖然LZ77應該可用。最後，Burrows-Wheeler變換允許壓縮，但實現起來要困難得多。

2009-07-24 17:36:06

2009-07-24 17:54:42

回答