另一個使用者想要向硬碟寫入一條新數據，但他沒有足夠的可用空間來執行此操作。 我也不想刪除任何東西，因為「一切都非常重要和必要」。 我們該用它做什麼？
沒有人有這個問題。 我們的硬碟上有數 TB 的訊息，而且這個數量不會減少。 但它有多獨特呢？ 最後，所有檔案都只是一組具有一定長度的位，並且很可能新檔案與已儲存的檔案沒有太大區別。
顯然，搜尋已儲存在硬碟上的資訊即使不是失敗，也至少不是一項有效的任務。 另一方面，如果差異很小，那麼你可以稍微調整一下...
TL;DR - 第二次嘗試談論使用 JPEG 檔案優化資料的奇怪方法，現在以更容易理解的形式。
關於位和差
如果您取得兩個完全隨機的數據，那麼它們包含的平均位元有一半是一致的。 事實上，在每對（'00'）的可能佈局中，恰好有一半具有相同的值，這裡一切都很簡單。
但是，當然，如果我們只取出兩個文件並將其中一個放入第二個文件中，那麼我們將丟失其中一個。 如果我們保存更改，我們將簡單地重新發明 ，儘管它通常不用於相同的目的，但即使沒有我們，它也可以完美地存在。 我們可以嘗試將較小的序列嵌入到較大的序列中，但即使如此，如果我們不顧一切地使用它，我們也會面臨丟失關鍵資料片段的風險。
那麼什麼和什麼之間的差異可以消除嗎？ 嗯，也就是說，使用者編寫的新檔案只是一個位元序列，我們不能用它本身做任何事情。 然後，您只需要在硬碟上找到可以更改的位，而無需儲存差異，這樣您就可以在損失後倖存下來，而不會造成嚴重後果。 不僅要更改 FS 本身上的文件，還要更改其中的一些不太敏感的信息，這是有意義的。 但是哪一個以及如何實現呢？
裝配方法
有損壓縮檔可以解決這個問題。 所有這些 jpeg、mp3 和其他檔案雖然是有損壓縮，但都包含一堆可以安全更改的位元。 可以使用先進的技術在編碼的各個階段不知不覺地修改其組件。 等待。 先進的技術...難以察覺的修改...一點一點變成另一點......幾乎就像 !
事實上，將一種訊息嵌入另一個訊息讓人想起她的方法，這是獨一無二的。 人類感官發生的難以察覺的變化也給我留下了深刻的印象。 路徑分歧的地方是保密的：我們的任務歸結為使用者在他的硬碟上輸入附加資訊；這只會傷害他。 他又會忘記。
因此，雖然我們可以使用它們，但我們需要進行一些修改。 然後我將使用現有方法之一和通用文件格式的範例來告訴和展示他們。
關於豺狼
如果你真的擠壓它，它是世界上最可壓縮的東西。 當然，我們談論的是 JPEG 檔案。 不僅有大量的工具和現有方法可以將資料嵌入其中，而且它是這個星球上最受歡迎的圖形格式。
但是，為了不從事狗的繁殖，您需要在這種格式的文件中限制您的活動領域。 沒有人喜歡由於過度壓縮而出現的單色方塊，因此您需要限制自己使用已壓縮的文件， 避免重新編碼。 更具體地說，對於整數係數，在負責資料遺失的操作之後仍然保留 - DCT 和量化，這在編碼方案中完美地顯示（感謝鮑曼國家圖書館的 wiki）：
有許多可能的方法來優化 jpeg 檔案。 有無損優化（jpegtran），有優化”「，這實際上貢獻了其他東西，但我們不關心它們。 畢竟，如果用戶準備將一種資訊嵌入到另一種資訊中以增加可用磁碟空間，那麼他要么很久以前就優化了圖像，要么根本不想這樣做，因為擔心品質下降。
F5
一整套演算法都符合這些條件，您可以熟悉一下 。 其中最先進的是演算法 由 Andreas Westfeld 設計，使用亮度分量的係數，因為人眼對其變化最不敏感。 而且，它使用基於矩陣編碼的嵌入技術，這使得在嵌入相同量的信息時，所使用的容器的尺寸越大，可以進行更少的改變。
這些變更本身歸結為在某些條件下（即並非總是）將係數的絕對值減少 5，這允許您使用 FXNUMX 來優化硬碟上的資料儲存。 關鍵是，由於 JPEG 中值的統計分佈，這種變化後的係數在霍夫曼編碼後很可能會佔用更少的比特，並且新的零在使用 RLE 對其進行編碼時會帶來增益。
必要的修改歸結為消除負責保密的部分（密碼重新排列），這可以節省資源和執行時間，並添加一種處理多個文件而不是一次處理一個文件的機制。 讀者不太可能對更詳細的變更過程感興趣，所以讓我們繼續描述實作。
高科技
為了示範這種方法的工作原理，我用純C 實作了該方法，並在執行速度和記憶體方面進行了許多最佳化（即使在DCT 之前，您也無法想像這些圖片在不壓縮的情況下有多重） 。 使用庫組合實現跨平台 , и ，為此我們感謝他們。 所有這些都是透過「make」組合在一起的，因此 Windows 使用者希望自己安裝一些 Cygwin 進行評估，或自行處理 Visual Studio 和程式庫。
該實作以控制台實用程式和庫的形式提供。 有興趣的人可以在 Github 存儲庫的自述文件中找到有關使用後者的更多信息，我將在帖子末尾附加該鏈接。
如何使用？
小心。 用於打包的影像是透過在給定根目錄中使用正規表示式搜尋來選擇的。 完成後，可以在其範圍內隨意移動、重命名和複製文件，更改文件和作業系統等。但是，您應該非常小心，不要以任何方式更改直接內容。 即使遺失一位的值也可能導致無法恢復資訊。
完成後，該實用程式會留下一個特殊的存檔文件，其中包含解包所需的所有信息，包括有關所用圖像的數據。 它本身重約幾千字節，對佔用的磁碟空間沒有任何重大影響。
您可以使用「-a」標誌分析可能的容量：「./f5ar -a [搜尋資料夾] [Perl 相容的正規表示式]」。 使用指令“./f5ar -p [搜尋資料夾] [Perl 相容正規表示式] [打包檔] [檔案名稱]”完成打包，並使用“./f5ar -u [檔案] [復原檔案名稱”解包]'。
作品展示
為了展示方法的有效性，我從該服務上傳了 225 張完全免費的狗照片集 並在文件中找到了第二卷45米的大pdf 克努塔。
該序列非常簡單：
$ du -sh knuth.pdf dogs/
44M knuth.pdf
633M dogs/
$ ./f5ar -p dogs/ .*jpg knuth.pdf dogs.f5ar
Reading compressing file... ok
Initializing the archive... ok
Analysing library capacity... done in 17.0s
Detected somewhat guaranteed capacity of 48439359 bytes
Detected possible capacity of upto 102618787 bytes
Compressing... done in 39.4s
Saving the archive... ok
$ ./f5ar -u dogs/dogs.f5ar knuth_unpacked.pdf
Initializing the archive... ok
Reading the archive file... ok
Filling the archive with files... done in 1.4s
Decompressing... done in 21.0s
Writing extracted data... ok
$ sha1sum knuth.pdf knuth_unpacked.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth_unpacked.pdf
$ du -sh dogs/
551M dogs/粉絲截圖
解壓縮後的檔案仍然可以且應該被讀取：
正如你所看到的，從硬碟上原來的633 + 36 == 669 MB 數據，我們來到了更令人愉快的551。這種根本性的差異是由係數值的減小來解釋的，這影響了它們的隨後的無損壓縮：逐一減少可以輕鬆地「從最終檔案中刪除幾個位元組」。 然而，這仍然是一種資料遺失，儘管損失非常小，但您必須忍受。
幸運的是，它們是肉眼絕對看不見的。 在劇透下（因為 habrastorage 無法處理大檔案），讀者可以透過肉眼及其強度來評估差異，透過從原始值中減去更改組件的值來獲得： , , （顏色越暗，塊內差異越小）。
取而代之的是結論
考慮到所有這些困難，購買硬碟或將所有內容上傳到雲端似乎是解決問題的更簡單的方法。 但即使我們現在生活在如此美好的時代，也不能保證明天仍然可以上網並將所有額外數據上傳到某個地方。 或去商店再買一個 XNUMX TB 的硬碟給自己。 但您始終可以使用現有的房屋。
->
來源： www.habr.com