分佈式文件壓縮

我一直在想一些關於數據冗餘的問題，只是想在寫完之前把所有東西都寫出來（並且仔細檢查這個想法是否已經付諸實踐）。分佈式文件壓縮

好的，所以在這裏。

互聯網充滿了冗餘數據，包括文本，圖像，視頻等。因此，通過HTTP進行gzip和bzip2即時壓縮和解壓縮的努力已經很多。像谷歌和Facebook這樣的大型網站有整個團隊，致力於讓他們的網頁加載速度更快。

我的「問題」涉及到的事實，壓縮在僅完成每個文件基礎（gzip file.txt產生file.txt.gz）。毫無疑問，在互聯網上看似無關的數據之間有許多共同之處。如果可以存儲這些常用塊並將它們（客戶端或服務器端）組合起來以動態生成內容，該怎麼辦？

爲了做到這一點，人們必須在因特網上找到最常見的「數據塊」。這些塊可以是任何大小的（這裏可能是最佳選擇），並且需要能夠表達任何可以想象的數據。

出於說明的目的，假設我們有以下5個常見數據塊 - a, b, c, d, and e。我們有兩個文件，只有包含這些塊。我們有叫做chunk和combine的程序。 chunk獲取數據，通過bzip2，gzip或其他壓縮算法壓縮數據，並輸出包含所述數據的數據塊（壓縮後）。 combine展開塊並解壓縮連接結果。下面是他們以何種方式使用：

$ cat gettysburg.txt 
"Four score and seven years ago...cont'd" 
$ cat test.txt 
"This is a test" 
$ chunk gettysburg.txt test.txt 
$ cat gettysburg.txt.ck 
abdbdeabcbdbe 
$ cat test.txt.ck 
abdeacccde 
$ combine gettysburg.txt.ck test.txt.ck 
$ cat gettysburg.txt 
"Four score and seven years ago...cont'd" 
$ cat test.txt 
"This is a test"

當發送通過HTTP文件，例如，服務器可以chunk的數據並將其發送給客戶，誰再有能力combine分塊的數據，並使其。

有沒有人試過這個？如果不是，我想知道爲什麼，如果是的話，請張貼你如何做這項工作。一個不錯的第一步就是詳細說明你如何弄清楚這些塊是什麼。一旦我們已經想出瞭如何得到這些塊，那麼我們就會弄清楚這兩個程序如何工作，如chunk和combine。

我可能會爲此付出代價（取決於接待），因爲我認爲這是一個非常有趣的現實世界問題。

來源

2009-12-27 Dan Loewenherz

能否詳細說明塊和聯合功能到底是做什麼的？ – Vitaliy 2009-12-27 21:47:54

剛剛添加了幾句話，說明他們在做什麼。 – 2009-12-27 21:54:54

你問，如果有人做了以前類似的東西，什麼塊大小應該是的，我想我會點你到來到我的腦海兩篇論文：

（A團隊） Google正試圖通過利用文檔間共享的數據來加速網絡請求。服務器將預先計算的字典傳送給客戶端，該客戶端包含文檔間通用的數據，並在稍後的請求中引用。這僅適用於單個域的時間，和 - 目前 - 只有谷歌瀏覽器：Shared Dictionary Compression Over HTTP
（A團隊），微軟在他們的工作Optimizing File Replication over Limited-Bandwidth Networks using Remote Differential Compression確定爲自己的文件系統同步的塊大小的情況下，大約2KiB運作良好。它們使用間接級別，以便重新創建文件所需的區塊列表本身被分割成多個區塊 - 這篇論文很吸引人，可能會爲您提供有關如何完成任務的新想法。

不知道它是否對您有幫助，但在這裏是爲了防止它。 :-)

來源

2009-12-27 22:16:31 DataWraith

你不必爲最常見的塊進行分析 - 事實上，這樣的分佈式決策確實很難。這是怎麼回事：

讓我們來看看HTTP數據傳輸的情況。將每個文件分塊爲10MiB塊（或者你關心的任何大小，我確信每種方式都有性能影響），並計算它們的SHA-256（或者一些你相當確信的散列應該是安全的以防止衝突）

例如，您具有文件F1，其中塊B1..Bn和校驗和C1..Cn。現在，HTTP服務器可以僅僅使用列表C1來響應對文件F1的請求。CN

爲了使這個真正有用的，客戶必須保持阻止已知的註冊表 - 如果校驗已經存在，只是在本地獲取該塊。完成。如果它不知道，可以從本地緩存中抓取它，或者從剛獲得校驗和列表的遠程HTTP服務器獲取塊。

如果你下載的這恰好共享一個塊中的任何服務器（甚至是完全不同的一個）另一個文件，你已經擁有它下載，那麼當你選擇了哈希算法的安全性。

現在，這並沒有解決在有偏移的情況下（例如，一個文件是

AAAAAAAA

和其他

BAAAAAAAA

其壓縮算法大概可以應付，但是也許如果你壓縮塊本身，你會發現，無論如何你得到了大部分的儲蓄...

想法？

來源

2009-12-27 21:34:09

與你的答案不完全相關，但你已經看到了這一點。微軟（和其他人）已經提供了邊緣網絡來託管jQuery庫。您可以引用這些相同的URI，並獲得用戶從不同站點訪問文件並使用瀏覽器進行緩存的好處。

但是，您指的是過去20分鐘內有人提及過多少內容（任意數量）？您可能會看到一個大公司中的一些好處，那裏有很多員工共享一個應用程序，但否則我認爲您會遇到困難確定您想要的組塊，並且這會超過分享它的任何好處。

來源

2009-12-27 22:55:29

有一個更簡單的方法來處理文本數據。目前，我們將文本存儲爲代表聲音的字母流。但是，語言的單位是單詞不健全。因此，如果我們有一個所有單詞的字典，然後將「指針」存儲到文件中的這些單詞，我們可以通過使用指針並查找單詞列表來動態地重新構成文本。

這應該將事物的大小減少3或4倍。在這種方法中，單詞與您所想的塊相同。下一步是諸如「這就是」，「我是」，「滿月」，「嚴肅的傢伙」，「哦寶貝」等常用詞組。

單詞列表還有助於拼寫檢查，應該是由操作系統實施。拼寫檢查程序不是操作系統的一部分，是否有任何理由？

來源

2009-12-27 22:57:04

分佈式文件壓縮

回答

相關問題