查看單個文章
舊 2011-07-15, 09:37 PM   #6 (permalink)
米奇
列管會員
榮譽勳章
UID - 262935
在線等級: 級別:100 | 在線時長:10579小時 | 升級還需:26小時級別:100 | 在線時長:10579小時 | 升級還需:26小時級別:100 | 在線時長:10579小時 | 升級還需:26小時級別:100 | 在線時長:10579小時 | 升級還需:26小時級別:100 | 在線時長:10579小時 | 升級還需:26小時級別:100 | 在線時長:10579小時 | 升級還需:26小時級別:100 | 在線時長:10579小時 | 升級還需:26小時級別:100 | 在線時長:10579小時 | 升級還需:26小時級別:100 | 在線時長:10579小時 | 升級還需:26小時級別:100 | 在線時長:10579小時 | 升級還需:26小時
註冊日期: 2007-03-03
文章: 10025
精華: 0
現金: 6807 金幣
資產: 118863 金幣
預設



或許從壓縮及基本原理來看,應該更能釐清樓主的疑惑

底下是一說明例子:

以我們熟悉的信息類型—單詞—為例子。

甘乃迪(John F. Kennedy)在1961年的就職演說中曾說過下面這段著名的話:

Ask not what your country can do for you——ask what you can do for your country.(不要問國家能為你做些什麼,而應該問自己能為國家做些什麼。)

這段話有17個單詞,包含61個字母、16個空格、1個破折號和1個句點。如果每個字母、空格或標點都佔用1個內存單元,那麼文件的總大小為79個單元。為了減小文件的大小,我們需要找出冗餘的部分。
  我們立刻發現:
如果忽略大小寫字母間的區別,這個句子幾乎有一半是冗餘的。九個單詞(ask、not、what、your、country、can、do、for、you)幾乎提供了組成整句話所需的所有東西。為了構造出另一半句子,我們只需要拿出前半段句子中的單詞,然後加上空格和標點就行了。
大多數壓縮程序使用基於自適應字典的LZ算法來縮小文件。 “LZ”指的是此算法的發明者Lempel和Ziv,“字典”指的是對數據塊進行歸類的方法。
排列字典的機制有很多種,它也可以像編號列表那樣簡單。在我們檢查甘乃迪這句著名講話時,可以挑出重複的單詞,並將它們放到編號索引中。然後,我們直接寫入編號而不是寫入整個單詞。
  因此,如果我們的字典是:

  ask
  what
  your
  country
  can
  do
  for
  you

 我們的句子現在就應該是這樣的:

  1 not 2 3 4 5 6 7 8-- 1 2 8 5 6 7 3 4

如果您了解這種機制,那麼只需使用該字典和編號模式即可輕鬆重新構造出原始句子。這就是在展開某個下載文件時,計算機中的解壓縮程序所做的工作。你可能還遇到過能夠自行解壓縮的壓縮文件。若要創建這種文件,編程人員需要在被壓縮的文件中設置一個簡單的解壓縮程序。在下載完畢後,它可以自動重新構造出原始文件。
但是使用這種機制究竟能夠節省多少空間呢? “1 not 2 3 4 5 6 7 8——1 2 8 5 6 7 3 4”當然短於“Ask not what your country can do for you-- ask what you can do for your country.”,但應注意的是,我們需要隨文件一起保存這個字典。
在實際壓縮方案中,計算出各種文件需求是一個相當複雜的過程。讓我們回過頭考慮一下上面的例子。每個字符和空格都佔用1個內存單元,整個原句要佔用79個單元。壓縮後的句子(包括空格)佔用了37個單元,而字典(單詞和編號)也佔用了37個單元。也就是說,文件的大小為74個單元,因此我們並沒有把文件大小減少很多。
  
但這只是一個句子的情況!可以想像的是,如果用該壓縮程序處理完甘乃迪講話的其餘部分,我們會發現這些單詞以及其他單詞重複了更多次。而且,正如下一節所言,為了得到盡可能高的組織效率,可以對字典進行重寫。
在上一個的例子中,我們挑出了所有重複的單詞並將它們放在一個字典中。對於我們來說,這是最顯而易見的字典編寫方法。但是壓縮程序卻不這樣認為:它對單詞沒有概念——它只會尋找各個模式。為了盡可能減小文件的大小,它會仔細挑選出最優模式。
如果從這個角度處理該句子,我們最終會得到一個完全不同的字典。

如果壓縮程序掃描甘乃迪的這句話,它遇到的第一個冗餘部分只有幾個字母長。在ask not what your中,出現了一個重複的模式,即字母t後面跟一個空格——在not和what中。如果壓縮程序將此模式寫入字典,則每次出現“t”後面跟一個空格的情況時,它會寫入一個“1”。但是在這個短句中,此模式的出現次數不夠多,不足以將其保留為字典中的一個條目,因此程序最終會覆蓋它。
程序接下來注意到的內容是ou,在 you r和 country 中都出現了它。如果這是一篇較長的文檔,將此模式寫入字典會節省大量空間——在英語中ou是一個十分常見的字母組合。但是在壓縮程序看完整個句子後,它立即發現了一個更好的字典條目選擇:不僅ou發生了重複,而且 your 和 country 整個單詞都發生了重複,並且它們實際上是作為一個短語 your country 一起發生重複的。在本例中,程序會用 your country 條目覆蓋掉字典中的 ou 條目。

短語 can do for 也發生了重複,一次後面跟著 your,另一次跟著 you,因此我們又發現 can do for you 也是一種重複模式。這樣,我們可以用一個數字來代替15個字符(包含空格),而 your country 只允許我們用一個數字代替13個字符(包含空格),所以程序會用 r country 條目覆蓋 your country 條目,然後再寫入一個單獨的 can do for you 條目。程序通過這種方式繼續工作,挑出所有重複的信息,然後計算應該將哪一種模式寫入字典。基於自適應字典的LZ算法中的“自適應”部分指的就是這種重寫字典的能力。程序執行此工作的過程實際上非常複雜。
無論使用什麼方法,這種深入搜索機制都能比僅僅挑出單詞這種方法更有效率地對文件進行壓縮。如果使用我們上面提取出的模式,然後用“__”代替空格,最終將得到下面這個更大的字典:
  ask__
  what__­
  you
  r__country
  __can__do__for__you
  而句子則較短:
  “1not__2345__--__12354”
句子現在佔用18個內存單元,字典佔用41個單元。所以,我們將文件總大小從79個單元壓縮到了59個單元!這僅僅是壓縮句子的一種方法,而且不一定是最高效的方法。 (看看您能找到更好的方法嗎!)
  那麼這種機製到底有多好呢?文件壓縮率取決於多種因素,包括文件類型、文件大小和壓縮方案。

在世界上的大多數語言中,某些字母和單詞經常以相同的模式一起出現。正是由於這種高冗餘性,而導致文本文件的壓縮率會很高。通常大小合適的文本文件的壓縮率可以達到 50% 或更高。大多數編程語言的冗餘度也很高,因為它們的命令相對較少,並且命令經常採用一種設定的模式。對於包含大量不重複信息的文件(例如圖像或 MP3 文件),則不能使用這種機制來獲得很高的壓縮率,因為它們不包含重複多次的模式。

因此想平均分割壓縮檔個人覺是有其難處,除非能將以上的變數先作一次精確的演算
而且最後一壓縮檔是否為平均數,個人認為似無絕對必要

淺見一篇請多指教

此帖於 2011-07-16 11:18 PM 被 米奇 編輯.
米奇 目前離線  
送花文章: 33547, 收花文章: 8703 篇, 收花: 40416 次
回覆時引用此帖
有 8 位會員向 米奇 送花:
a471 (2011-07-16),fcya (2011-07-17),GaMNiA (2011-07-16),getter (2011-07-17),grc45 (2011-07-18),rw5767 (2011-07-28),丹楓 (2011-07-16),羅迪 (2011-07-15)
感謝您發表一篇好文章