數(shù)據(jù)壓縮中未探索的領域

數(shù)據(jù)壓縮中未探究的領域［譯者注：本文原作者提出的三個數(shù)據(jù)壓縮方面有些讓人腦洞大開的感覺，假如對數(shù)據(jù)壓縮原理很有興趣的同學，建議看看這篇文章。］RichGeldreich是我一個很厲害的同事，近來發(fā)布了一篇很存心思的文章，論述了他對將來無損壓縮技術的看法和看法。而后，我自己有些按捺不住了，也想說說我的看法~~（嘿嘿，這正是互聯(lián)網(wǎng)的魅力，不是么？）在我看來，當前數(shù)據(jù)壓縮領域比較熱門研究點有兩大塊：第一大塊是找編解碼性能和數(shù)據(jù)壓縮比的均衡點（比方LZHAM、Brotli、LZFSE這些壓縮算法)。從適用角度看，這個出發(fā)點毫無疑問是沒問題的。并且我以為這正是數(shù)據(jù)壓縮系統(tǒng)的價值所在，因此，往這個方向努力的確是正確的。第二大塊是試試將神經(jīng)網(wǎng)絡理論用在數(shù)據(jù)壓縮領域中。自然，像ZPAQ［譯者注：一種特別合適用來做增量壓縮備份的壓縮工具，官網(wǎng)］和其余的鑒于ContextMixing的編碼算法其實不合適開發(fā)人員做一些平時的壓縮操作（主假如因為需要較大的內(nèi)存和較長的履行時間），但在壓縮比方面，這些壓縮算法卻代表著最前沿的技術。他們的原理就是只需供給足夠多統(tǒng)計模型，ContextMixing算法就能夠獲得相當不錯的壓縮比。(這是圖的下標題)看到top15的大文本數(shù)據(jù)壓縮工具都是鑒于ContextMixing算法的，而鑒于BWT的只好排進前20，是否是感覺有些驚艷?。浚圩g者注：BWT基來源理是將字符串變?yōu)樽址仃嚕髮ψ址仃囘M前進行排序和變換，也是數(shù)據(jù)壓縮領域的一個熱門］總而言之，當前在數(shù)據(jù)壓縮領域的全部大動作都是針對我們已知的東西。基本上都是聯(lián)合數(shù)據(jù)變換、鑒于統(tǒng)計特點的編碼，以及contextmixing算法去獲取更好的結(jié)果可是這些都沒有戳中我的重點。第一要認可全部這些工作都很棒，可是此刻貌似有慢慢迷失數(shù)據(jù)壓縮算法根本目標的趨向。有人說只需做到了某個程度就意味著壓縮的問題被解決了，關于這類說法我是不買賬的。近來已經(jīng)關注了好多好多這方面的研究點（可能太多了），越看越感覺我們離“問題被解決”的程度還差很遠很遠：數(shù)據(jù)壓縮領域還有好多大坑需要我們?nèi)ヌ??；蛟S我立刻列出的部分點有些太甚于理論以致于根本不現(xiàn)實，甚或是看上去有些瘋狂。但他們的確是我們此刻的信息理論和數(shù)據(jù)壓縮領域需要被關注的。擺列帶來的難題現(xiàn)代數(shù)據(jù)壓縮理論是環(huán)繞統(tǒng)計特點來設計的，真的追憶起來預計有200年的歷史了。這么多年下來，我們都沒有另辟門路，提出一個新看法的。更糟糕的是，我們的思想都被固化在這上邊了。想一想看，依據(jù)現(xiàn)代數(shù)據(jù)壓縮理論，一般以為一旦統(tǒng)計信息被提拿出來，我們根本沒方法進前進一步壓縮了。基本上就意味著，一旦我們達成了統(tǒng)計特點提取，這條路就走到頭了。這類看法?′?¤?2???????￥è??é恰好正是我們最大的死穴?？纯催@個經(jīng)典的擺列[5,7,1,4,6,3,2,0]。依據(jù)信息論，這個擺列是不可以壓縮的：由于每個符號都出現(xiàn)了，并且沒有重復出現(xiàn)的。從統(tǒng)計特點的角度看，我們只好做到這一步了。一個擺列，以及它的一種循環(huán)表示方法像這樣的擺列，鑒于統(tǒng)計的編碼算法（霍夫曼編碼,arithmetic【譯者注：這里不是算術的意思，是一種壓縮編碼算法】,ANS）都力所不及了。亦或許是更高層的數(shù)據(jù)變換算法也不可以，比方LZ，BWT和RLE。Delta壓縮可能會表現(xiàn)好一些，可是實質(zhì)應用中成效其實不顯然。針對二進制的ContextMixing可能表現(xiàn)會更好一些，前提是能將更長的bit序列映照到特定模式。但基本上，我們此刻全部數(shù)據(jù)壓縮的理論模型碰到這樣的擺列時，都沒能有更大作為。這方面的困難性致使幾乎沒人在研究它。我能夠很一定的說，沒人真的在意這個課題，我的意思是想要在這樣的擺列眼前獲得打破性進展的概率特別特別低，因此大多半研究者都不會考慮這個問題。但在我看來，真的很奇異，像擺列這么簡單的一個看法竟然會對我們現(xiàn)有的數(shù)據(jù)壓縮領域會有這么大的困難。2為何沒有更多近似于BWT的算法？不知道為何，我們現(xiàn)有的壓縮系統(tǒng)大多半都被限制在了線性數(shù)據(jù)上。正確說來，全部壓縮算法是在考慮以某種形式將信息的上下文組織起來，而后用這類組織方式來實現(xiàn)壓縮，沒有人真實考慮將數(shù)據(jù)流中的數(shù)據(jù)打亂的。致使這一現(xiàn)象的原由是對次序的編碼是很困難的，需要額外的數(shù)據(jù)來支撐。意思就是假如我能夠?qū)⒁獕嚎s的數(shù)據(jù)先排好序，那么全部算法都獲得更好的壓縮率?？墒窃趺磳⑴判蚝玫臄?shù)據(jù)給恢復回去需要大批的數(shù)據(jù)來做協(xié)助。而這些協(xié)助數(shù)據(jù)就是上一小節(jié)中提到的經(jīng)典擺列（我們已經(jīng)知道它有多災壓縮了）。?′?¤?2???????￥è??éBWT是當前最合用于人類基因組信息的壓縮算法我就是很奇異為何沒有更多近似于BWT的算法。在字母擺列領域，只有BWT獨家一份。自然，也有少量算法對它做了一些改正，可是沒有像LZ算法那樣有個變體。有沒有其余對排序變換的算法呢？坦率來說，這方面的多樣性缺失是有它的道理的，連BWT的作者自己都說不清他們是如何找到這個算法的，因此我們也不可以希望隨意冒出來個工程師在未做大量試試的狀況下就能提出個近似的算法?？墒俏业闹攸c是，像這類種類的算法，不應只有BWT

獨家一份。就像有那么一句話說的：“不足為奇”，不過我們還沒有發(fā)現(xiàn)罷了。柯氏復雜性［譯者注：柯氏復雜性是一種權衡想要表達一個序列的復雜度的指標，這句話有點拗口，有興趣的同學自行百度一下，想要更為深入認識的能夠看看文章開頭我給出的那篇文章］熵不是一種很好的權衡手段，看看［0，1，2，3］和［0，3，1，2］這兩個序列，他們的熵值同樣，可是很顯然我們能夠看到此中有一個能夠有更短的表示形式?？率蠌碗s性是個很存心思的權衡指標，簡單來說，它是用來權衡你的數(shù)占有多大，能夠用多大的程序來生成你需要的數(shù)據(jù)。這關于數(shù)據(jù)壓縮領域來說是個新方向：怎么把這個思想用到數(shù)據(jù)流中，從而用到數(shù)據(jù)壓縮算法中？?′?¤?2???????￥è??é上圖完整部是由Fractal算法生成的，生成這個圖片的程序特別特別小，比最好的這是一個完整未被探究過的空間，只需我們能將數(shù)據(jù)塊切割中多個部分，每個部分都能夠用一個很小的程序來生成，那么全部程序的大小將比本來數(shù)據(jù)的體積小好多。但我預計這個想法有些過于科幻，就我所知的現(xiàn)有計算機能力而言，我不確立是否是能達成這樣的任務?？墒?，不論如何，這個想法仍是挺激感人心的。我們的路還很長這三個問題告訴我們，數(shù)據(jù)壓縮領域還沒有達到“問題被解決”的程度，我們不過關注我們能做哪些