代碼優化和數據壓縮之間的關係

Question

我在互聯網上搜索了這個問題，並發現一些研究人員使用數據壓縮算法進行編譯優化，如霍夫曼編碼。

我的問題是更普遍的：

我們可以考慮代碼優化有損壓縮類型的？

Answer 1

在具體的水平上，它是蘋果和橘子。但在抽象層面，這是一個有趣的問題。

數據壓縮處理冗餘，這是數據和信息之間的差異。它試圖通過修改信息的編碼來減少不必要的冗餘。 通常，這種編碼的工作方式是採用一個公共子字符串並製作引用它的代碼，而不是重複該子字符串。

編譯器優化（速度）尋求減少不必要的週期。 一種方法是，如果某些計算的結果需要兩次或更多次， 確保它保存在某個地址或寄存器（記憶）中，因此可以在更少的週期內重新使用它。

編碼數字的另一種形式是所謂的「一元符號」，其中只有一個數字，數字通過重複表示。例如，數字「三」和「四」是「111」和「1111」，取N個數字。 該代碼通過切換爲二進制進行了優化，如在「011」和「100」中，這取得了log（N）數字（當然是基數2）。

與此類似的編程是線性和二分搜索的區別。 線性搜索需要O（N）比較。每個比較都可以產生大量的信息或者很少 - 平均遠遠少於一點。 二進制搜索需要O（log（N））比較，每個比較產生一個比特。

有了一些想法，應該有可能找到其他類似的東西。