利用無理數壓縮數據是否可行？

01-07

第一步先取一個無理數，比如π；
第二步將待壓縮數據進行分片，比如128位一段；
第三步將第零段位元組在π中比對找到其出現的位置，比如在100位到227位和第零段相同，記錄100；
重複至文件結尾，生成壓縮文件。
所以需要壓縮包里的數據就是[無理數標識,分片大小,位置0,位置1,位置2,···]

解壓軟體的數據就是[計算π等無理數的函數實現演算法]
壓縮率根據分片大小確定，這個例子里貌似可以達到10%。
今天壓縮數據時候想到的問題，用算力換空間，把文件轉化成一個表達式，不知道有什麼問題，請各位大佬幫忙解答下，後期準備寫個實現的代碼測試下。
當然也可以私信我@萌萌噠蘿蔔絲
謝謝！

騷年，你這個主意已經不新鮮了，有人都實現出來了

https://github.com/philipl/pifs

凡人，不要挑戰香農

128位分組意味著不管你怎麼表示，這一個分組都需要有2^128種不同的符號來表示，如果分組結果是均勻分布的，你表示這2^128種不同的符號必然需要128位。跟你用不用無理數毫無聯繫。

更普遍地來說，一段信息X，在你通訊雙方共同已知Y的情況下，至少需要H(X|Y)的信息量才能傳輸過去，不可能比這更少了。

多學點數學。

額，你會發現，後期你用來保存存位置的「索引」(比如你那個100)才是數據源。

很多人都在打擊題主，其實誰沒有腦洞大開的時候呢？只要真有興趣，後面再去讀讀這方面的著作，認識到不足就好了。

我曾經為了壓縮資料庫想出了PiXiu，有興趣的人可以看看我的GitHub。後來發現這不過是LZ77的變種。回頭來想，如果沒有這次腦洞與大量實踐，是不是這輩子都不會去了解壓縮與信息是怎麼一回事呢？

題主，我認為你的問題在於現在肯定認為自己碉堡了，誰的話大概也不會聽（我當初就是，笑）。這裡推薦兩本書，&和&。

現在來說說，你的想法問題究竟在哪裡？

「信息」的本質是離散的

三體中的某個故事是，在飛船上某個點做個標記，讀出無限精確的長度就能存儲無限的信息。這個在資訊理論的角度來看是沒有意義的，不是說這種方式不行，而是，這不是數學上對於信息的定義。如果哪天人類真的掌握了相當逆天的觀測能力，這個方式未嘗不可，甚至可能是上萬億刀的大買賣。但目前為止，從現實與實踐出發，信息的表現形式就是離散的數組。比如，00010101。

想像下，你有一個相當完美的小數0.123456789，但最終也必須轉換為某種數組存儲，除了用IEEE規定的浮點數，也可以用數學定義的二進位小數。為了不丟失信息，你必然要採用後者，那麼越小的小數，需要的二進位Bit越多。有疑問？試著把0.1與0.00000001轉換為二進位小數。

這有了一個非常強烈的暗示，表示信息的長度一定是有下限的。這個工作就由香農在很多年前完成，叫做Entropy（熵）。我寫了一個簡介，資訊理論基礎及霍夫曼編碼，可以看下。

用數來表現信息的方式，叫做算術編碼

題主，你和這個方法思路上很類似了，可惜大約60年前就有人實現過了。科研就像在沙灘上撿貝殼，容易找到的，很早就被找到了。只有多學習，走到無人處，才更容易發現真正有價值的成果。

完美的信息熵在實踐中是幾乎不可計算的

拿Pi來說，3.1415926...，在不知道圓周率的情況下，這是一個無限長的離散數組才能表示的數列，因此預期信息量為無限大。但如果信息的接收雙方都知道Pi，那麼也許幾個Bit的數據就可以了。不變的是數學理想狀態下的熵，變化的是我們對於熵的預期。

再舉個例子，Entropy這個單詞，我如果就只打Entrop，英語不錯的人都會反應到這是Entropy。發現了么？Entropy這個單詞被壓縮成了Entrop。如果能再環顧上下文，可能我打個E，接收方就能得知E -&> Entropy。

為什麼會這樣？香農錯了么？不。香農的資訊理論天才之處在於通過巧妙的定義規避了討論這一問題的必要，直接將信息描述為消除不確定性的能力，建議看前面提到的我寫的簡介。你還需要看看一個很簡單的概念，「柯氏複雜度」。直接統計單個數字的頻率得出的熵，叫做一階統計熵。

你是怎麼被繞進去的？

在針對Pi的時候，你是在思考柯氏複雜度，然後發現柯氏複雜度&<&<(遠小於)一階統計熵。然後，你希望可以將通用數據映射到Pi上，使得數據具有Pi的柯氏複雜度性質。

但問題在於，你的映射成本考慮到了么？對於特定數列來說，你可以找到無理數替代，而不用付出高昂成本。Pi的尾數均勻分布，100個Bit的數據，數學預期是2^100位的時候才出現第一個匹配，表示第2^100位就要100個Bit了。就是說，對於隨機非特殊的數列，映射的預期長度就是等於原數據了。而且，我真不敢想像什麼PC能計算長度2^100Bits的Pi。

有沒有別的路？

有啊。努力發現數據本身的柯式複雜度，土點，叫做找規律。這個問題，我認為至少是NP(Hard)的。AI可能有點用，但目前最先進的做法無非是訓練馬爾可夫狀態轉移矩陣罷了。還遠沒有到計算機能自己發現，3.1415...是某個有理數或者{1,2,3,4,5}是等差數列這樣的程度。

腦洞時間：

用彩虹表存儲一些數列到無理數的變換來壓縮數據

不可行。

無法造出某種壓縮方式，使得可以壓縮所有數據。

現有的各種壓縮方式，都是由於數據有特殊性質，因此可以壓縮。

例如，AAAAABBBBB，我們可以寫成「5A5B」，這是因為「AAAAABBBBB」是很有規則的。但是我們壓縮成的「5A5B」，卻非常無序。

這是類似於熵的東西。我們以無序來換有序，藉此節約空間，實現「壓縮」。如果題主實現過哈夫曼編碼，應該對這件事有切身的體會。

現在來證明為什麼通用壓縮是不可能的：

假設我們有某種手段，對於任意輸入的二進位串，都壓縮成一個更小的二進位串輸出，且通過輸出文件能還原出輸入文件。

那麼我們給定A，把它壓縮成B，然後把B壓縮成C……由於B比A小，C比B小，這樣操作下去，我們最終可以得到一個長度為1的二進位串（不是0就是1）。

最終得到的二進位串只有兩種，但輸入的情況有無窮多種，無法一一對應，違反了我們的假設。

最後，無論是哪個學科都不存在天上掉餡餅的事情。一切都在於交換，你得到了什麼東西，就必須為此付出代價——例如把有序變得無序。

通用壓縮和永動機是一樣的想法。關於永動機的研究，可以去百度貼吧民科吧一睹風采。

----------------------------------分割線---------------------------------------------

題目描述里的做法，現在已經有一個實現，在 http://www.angio.net/pi/piquery 。這個網站很有意思，它會從pi的前兩億位裡面尋找你給定的字元串。

例如，「19260817」最先出現在pi的小數點後69943588位。（為了方便討論，在下面的分析中，我們把「從第 $i$ 位開始匹配」簡稱為「在第 $i$ 位匹配」。）

不過上面這個例子，「69943588」已經和「19260817」一樣長了。現在我們來分析一下用無理數來壓縮數據是否可行。為了直觀一些，下面的討論都在十進位下進行。

我不知道pi是不是正規數，但是我知道 $sqrt 2$ 是正規數。因此， $sqrt 2$ 的任何一位，出現0~9的概率是均等的。

假設我們要匹配長度為 $d$ 的串。那麼，對於任意一個 $i$ ，在第 $i$ 位匹配的概率是 $10^{-d}$ 。因此，在 $[1,n]$ 位內都不匹配的概率是 $(1-10^{-d})^n$ 。

換言之，在 $[1,n]$ 位內可以匹配的概率是 $1-(1-10^{-d})^n$ 。

假設我們要編碼一個長度為100的串，那麼根據上面的式子，即使 $n=10^{100000000}$ ，在 $n$ 位以內匹配成功的概率也極為渺茫。也就是說，我們為了編碼100位數字，要付出遠大於100000000位的代價來存下它出現的位置。

因此這個問題的答案就很明確了：得不償失。

你的問題：

第一步先取一個無理數，比如π；
第二步將待壓縮數據進行分片，比如128位一段；
第三步將第零段位元組在π中比對找到其出現的位置，比如在100位到227位和第零段相同，記錄100；
重複至文件結尾，生成壓縮文件。
所以需要壓縮包里的數據就是[無理數標識,分片大小,位置0,位置1,位置2,···]
解壓軟體的數據就是[計算π等無理數的函數實現演算法]
壓縮率根據分片大小確定，這個例子里貌似可以達到10%。
今天壓縮數據時候想到的問題，用算力換空間，把文件轉化成一個表達式，不知道有什麼問題，請各位大佬幫忙解答下，後期準備寫個實現的代碼測試下。
當然也可以私信我
@萌萌噠蘿蔔絲
謝謝！

不現實的地方：存儲你所說的「位置0」、「位置1」、「位置2」等可能就需要幾倍於原文件的空間了。這就不叫壓縮演算法了。

具體地說，假設你要存儲 1234567890 這個串，但是這個串第一次出現在 1908728019234 位置上（兩個數字都是隨意舉的），你存儲壓縮後的結果所需的空間就多於存儲原數據所需的空間了。

嗯……你這個分法，128位的數據共有 $2^{128}$ 種不同的可能形式。也就是說為了保證你的每個數據段不重複，對每個128位的數據段你需要用128位的索引來存儲……

等等，所以這真的是壓縮嗎？

這個想法我也有過，但仔細思考，你會發現

要麼，你的壓縮方法不具有普適性

要麼，索引信息不短於目標信息長度

有時能壓縮，有時會反而變長。

沒有免費午餐。

一個分片128bit，也就是有2^128種情況，就算你選取的無理數非常理想，剛好這麼多分片都集中在前部，那麼要存的位置序號也是0~2^128-1，所以，位置序號佔用空間的期望值也是128bit，這還是最好情況下，事實上不可能存在一個萬能演算法將任何文件都壓縮到更小的大小，證明也很簡單，如果存在這種演算法，那麼對任何文件進行重複壓縮，都可以壓到1位元組？顯然不成立，任何一個演算法下，大多數文件都會越壓越大的

正常的文件大多數可以壓縮得比原來小，是因為絕大多數人類用到的文件都是有規律的（比如英文文本會存在大量重複單詞），要提高壓縮率，一般需要利用這種規律，而題主的演算法和需要壓縮的文件的內容沒有特定聯繫，比如說，你選π做種子，那麼文件第一段所在位置就可能已經很遠了，而很近的位置卻不一定是常見的文件分片內容

如果這個分片位置在幾萬億位數之後呢？那麼你就需要很大的空間來存這個數字吧？

有奇思妙想是好事,不過永遠記住Talk is cheap, show me the code.

上一個提類似問題的人想的是用無理數加密.

不管你怎麼搞,反正首先要預編碼成數字對吧,不管用ASCII,UTF還是直接Binary分段.

然後就是數字映射到位數.

這是個加密過程. 以給定無理數為密匙.

我們有個猜想: 所有非超越無理數必定是正規數.

然後,正規數服從均勻分布,假如是128位分段的話預計 $[128H(128) approx 695]$ 個數字就能給出這張映射表.

從這上看出映射完絕對比原來的儲存方式更加低效.

我當時寫了個加密demo,把其中生成映射表的函數拉下來.

find=SequencePosition[First@RealDigits[Pi,10,10000],#,1]; ass=First/@Flatten[find/@PadLeft[IntegerDigits/@Range[#],{#,IntegerLength[#]}],1];

比如對Pi,Well,你選了個壓縮率最高的,足足 $851\%$ !

============================

Update

私以為題主說的是二進位128位...

如果是說10進位128位的話...這麼長的映射表能不能存出來還兩說...

問你一個最簡單的問題，比如我分段得到的第一個數如此平淡無奇，是個1 ，就是0x0000000000000000000000000000001 你放哪裡？（我0打暈了錯了請見諒）

描述pi在實軸上的位置需要無限的信息，你想用這些信息去壓縮數字，可以。但是由於這個信息和你要壓縮的數字之間的相似度幾乎為0，所以你不可能得到一個更小的描述方式。另外由於我們平時記錄數字的方法本身是貼合我們生活場景的，越常用的數字一般越小，越小的數字寫起來越短。你實際上是劣化了信息儲存的方式。。。

去讀讀資訊理論吧，腦洞很好，缺乏基礎。

這麼天才的設想，壓縮率一定怎麼著也得百分之一百起，上不封頂。

不說無理數就說隨機得到一個128位的數要等於你給出的128位數的概率幾乎是0啊

可想而知在一個無理數中去找一個128位匹配你給出的128位數首先你能證明一定存在么就算一定存在

這個序列所在的位置應該是一個天文數字可能遠大於128位數能表達的最大的數字

你光存儲這個位置都不划算啊

更別說你如何在可接受的時間內匹配到這個序列所在的位置了

讓我想起了我曾經不知道哪裡看過的一個說法:說一個超級外星文明如何記錄一本紅樓夢，他會首先把紅樓夢編碼，比如紅=487，樓=315...，然後找一個鐵棍（不會發生任何形變），然後在這根鐵棍的合適位置劃一道刻痕使刻痕兩段的長度比值等於0.48731572167348731573131.......，然後測量這個這個比值就能恢復出紅樓夢了。

不可行。因為壓縮時間要無窮長。計算pi很費時的，不然為什麼要有superpi。

如果用常用無理數，位置信息的長度的數學期望等於分片大小，壓縮大量數據所需的空間基本不變；如果用專門搜索出來的數，存儲「這個數的計算方式」本身需要的空間加上位置信息的長度會高於輸入數據的信息量，相當於變相實現了一個弱化的Huffman演算法

假設樓主你用了pi。

那麼……請幫我寫出「HelloWorld」在pi的那幾個位可以完美表示？

這麼做當然有可能性。任何一段數據必然是一個無理數的一個片段。

也就是說，我們只需要一個定界就完成了。

但是，壓縮和解壓時間都是無窮大的。不具備現實意義。