壓縮方法

Question

我知道大多數壓縮方法都依賴一些重複的數據才能生效。例如，刺痛的「AAAAAaaaQWERTY」可以被表示爲「5A3aQWERTY」用於無損和諸如「8aqwerty」用於有損（這些僅僅是例如，不是實際的工作方法）。據我所知，所有的壓縮算法都依賴於 - >常量< - 字符串的重複。

這裏帶有字符串「ABCDEFGHIJKLMNOPQRSTUVWXYZ」的問題。這裏沒有什麼重複，但正如你可能看到的字符串中的信息可以用更短的方式表示。在類似正則表達式的str中。將會是「[a-z]」，或者可能是「for（x = 0; x < 25; ++）{ascii（97 + x）}」。

也考慮字符串「0149162536496481100121」 - 它可以用「for（x = 0; x <11; ++）{x * x}」表示。

字符串 「ABEJQZer」 可表示爲 「爲（X = 0; 8; ++）{ASCII（64 + X * X）}」

最後兩個是知道的算法的例子，它可以重現原始字符串。我知道一般算法（如果它們是高效的）比它們可以產生的數據佔用的空間要小得多。

像在svg圖像（它只有在文件中的算法）的大小小於jpeg。

我的問題是有壓縮的一種方式，這需要數據和tryes找到高效的算法，可以代表它。像向量化光柵圖像（如http://vectormagic.com/），也可以與其他數據一起使用。考慮音頻數據（因爲它可以壓縮有損） - 一些音頻編輯器（例如，大膽度）項目文件包含諸如「從時間0到時間2分鐘45.6秒產生具有0.8幅度的120Hz恆定頻率」的信息（大膽性商店信息以xml格式）。這個元數據佔用的內存非常少，當項目導出爲wav或mp3時，程序會將信息「呈現」爲導出格式的實際樣本。

在這種情況下，壓縮機應該反轉渲染過程。它應該採用wav或mp3文件，找出哪些算法可以表示樣本（如果它是有損的，則算法必須產生樣本的一些近似值 - 就像vectormagic.com合成圖像一樣）並生成壓縮文件。

據我所知，壓縮時間將是令人難以置信的長，但是否有這樣的（或類似）的壓縮算法？

Answer 1

所有壓縮方法是這樣的：輸出是一組用於呈現所述輸入，或類似的東西的輸入的一組算法參數。

例如，MP3音頻編解碼器將輸入分成576個採樣塊，並將每個塊轉換爲頻率幅度空間，並且修剪人類聽不到的音頻。輸出相當於「在接下來的13毫秒播放頻率x，y，z中振幅爲a，b，c」。這對於音頻數據非常有用，JPEG中使用的類似方法適用於照片圖像。

類似的方法可以應用於您提到的情況。例如987654或010409162536等序列由多項式的連續值生成，可以表示爲多項式的係數，第一個爲9-x的（9，-1），第二個爲（1， 2,1）爲1 + 2x + x 2。

爲簡單起見，用於生成輸入的算法的選擇往往是固定的，並且爲用戶量身定製。例如，如果您正在處理使用數碼相機拍攝的照片圖像，則甚至無法嘗試生成矢量輸出。

Answer 2

當試圖無損壓縮一些數據，你總是以壓縮在人類語言中的一些文本時創建的模型，例如啓動，您認爲，這實際上有沒有那麼多的話，它重複一遍又一遍。但是，很多算法試圖在旅途中學習模型的參數。就像它不依賴於這些單詞實際會是什麼一樣，它會嘗試爲給定的輸入找到它們。所以算法不依賴於實際使用的語言，但它確實依賴於事實，即它實際上是一種人類語言，它遵循一些模式。

一般情況下，沒有任何完美的算法，它可以無損壓縮什麼，它是數學上的證明。對於任何算法，都存在一些壓縮結果比數據本身更大的數據。

Answer 3

您可以嘗試重複數據刪除：http://en.m.wikipedia.org/wiki/Data_deduplication。這是一個有點不同，更智能的數據壓縮。