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

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

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