Re: [問卦] WinRAR不買正式版會怎樣?

[roger29 (=======中間選民=======)]

因為壓縮的比例存在著理論上的極限

假如我現在有A B C D 四個符號

要表示成數位資料的話  直觀的方法是讓A=00 B=01 C=10 D=11

ASCII code就是類似的7碼等長度編碼方法


不過呢 這五個符號出現的機率可能不是一樣的

假設Pr(A)=0.5  Pr(B)=0.2  Pr(C)=0.2  Pr(D)=0.1

那麼用上面直觀的方法編碼

我的codeword平均長度是 0.5*2+0.2*2+0.2*2+0.1*2=2



那麼我們有沒有辦法讓我的平均長度變得更小一點呢(也就是達到所謂的資料壓縮)

有的  我們可以善用A B C D四個符號出現機率不相等的特性

A出現的機率最高  所以我直觀上希望表示A的二進位長度可以短一點才有效率

D出現的機率最低  所以我就會希望表示D的二進位長度可以長一點沒關係

那麼換一個方式表示：A=0  B=10  C=110  D=111

這樣表示的話我新的codeword平均長度就是 0.5*1+0.2*2+0.2*3+0.1*3=1.8

比原本每個符號都用2個bits來表現還要更小

(註：這個編碼方法為著名的Huffman code)


所以我們可以發現  如果能善用資料間的相關性

是可以減少用數位來表示這些資料所需要的資料大小

但是當然不可能無限制的縮小

根據偉大的數學家  消息理論的開山始祖  Claude Shannon的source coding theorem

簡單來說

給定一個discrete memoryless source S  就像我上面的四個字母

那麼我們能夠達到的平均codeword長度會大於等於S的entropy

S的entropy定義成            n
                           ---
                    H(S)=  \   Pr(si)*log[1/p(si)]
                           /
                           ---
                           i=1


上面的例子它的entropy就是(log的底數為2  因為單位是bit)

H(S)=0.5*log(1/0.5)+0.2*log(1/0.2)+0.2*log(1/0.2)+0.1*log(1/0.1)=1.761

等長度編碼方法和Huffman code編碼的平均codeword長度分別是2和1.8

的確都比H(S)還要更大


所以  資料壓縮不可能無窮盡的壓縮

能夠壓縮多少  除了取決於壓縮編碼的演算法

還有就是你的資料裡面data的相關度和符號出現的頻率

假如現在A B C D的機率都是一樣的每個都是1/4

那麼這樣H(S)=4*0.25*log(1/0.25)=2

這樣的話不管怎麼做  我們的codeword平均長度都一定會大於等於2

就沒辦法達到剛才的1.8了





※ 引述《mynameisdick (我就是屌)》之銘言：
: : 我都沒理他結果也沒怎樣
: : 有沒有WinRAR不買正式版會怎樣的八卦?
: 比起買不買正式版
: 哥更好奇的是，壓縮軟體這麼多年了怎麼都沒有進展?
: WinRAR，了不起幫你把一個50mb的檔案壓到48.Xmb
: 在這個網路時代，有壓和沒壓根本差不多
: 如果是工作上需要傳大檔案，除了用Dropbox或是用SKYPE、FTP慢慢傳
: 根本就沒有其他方法去傳大檔案
: 那幹嘛還花這個心力去省個幾mb
: 有這幾年來，壓縮軟體沒有任何進步沒有競爭力的八卦嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.249.98.123
※ 文章網址: http://www.ptt.cc/bbs/Gossiping/M.1404056805.A.8CE.html
推 LIONDODO:This is an apple...
推 SDNS:看八卦漲知識
→ qcuteba:看無,我只知道要一直按關閉挺麻煩的
推 liaon98:Huffman只是其中一種吧
是的  Huffman code其實是二位元編碼中最佳的

而且非常容易理解  當初是從Huffman在MIT修課時的期末作業誕生的
推 alog:XDDDD...八卦優質認真文 不給你推不行 雖然很快又被洗掉了
推 softseaweed:
→ tigertiger:稱呼Shannon數學家? 跟稱呼科P是醫師一樣不尊敬
其實哪要叫他工程師  電腦科學家還是什麼都可以啦

Shannon其實就是個宅宅  個性陰鬱不愛講話(但是有取到老婆喔)
推 daxer:要跟著推 不然別人會以為我看不懂
推 snowcoat:八卦版優文...
推 wa007123456:她是講 00 01 10 11 這四種段碼出現的機率整合
推 NoWashing:這麼專業 怎麼不聊聊超強的圓周率壓縮演算法勒 XDDD
抱歉source coding不是我的專業  真要說的話channel coding可能比較熟一點點

但是都很不專業
推 goshfju:我是不是來錯板
推 john2557:精彩
推 searoar:知識
推 HvvH:推
→ tigertiger:到底哪裡專業了阿? 一個叫Shannon數學家的人 專業在哪?
→ tigertiger:八卦板怎麼了?
推 hhenry666:
→ alog:Claude Elwood Shannon -->  American mathematician,
推 BBBroflovski:看不懂 Orz
推 wa007123456:克勞德·夏農 沒錯阿 他也是一位數學家
→ alog:mathematician該翻做什麼??
※ 編輯: roger29 (111.249.98.123), 06/30/2014 00:00:31
→ orz811017:推演算法
噓 CCPenis:講中文好嗎
推 s9007555:文組崩潰
→ tigertiger:不尊敬阿 就像你會叫陳水扁律師嗎?
推 zz7856132:快推 不然人家以為我們看不懂
推 s0857168:略懂
→ liaon98:簡單來說 你一篇文章最常出現的字叫他為a 不常出現的字
→ tigertiger:還文組咧 連雪農最大貢獻是啥都不知道配稱理組喔
→ liaon98:你就把它改成叫長的字 這樣文章就會變短
推 LoveMoon:嗯嗯  跟我了解的差不多                       推專業
→ wind137:幹   這通訊系統好懷念
→ liaon98:以中文來說 可以說成 比較常用的字改的筆劃少一點
推 DEATHX:優質文，這種都該入精華區，誰還有上次RSA解說文的備份？
→ liaon98:然後少用的字筆畫多一點 這樣整體你會寫比較少畫
→ JCS15:我把我壓縮 輕輕把你也壓縮
推 drkkimo:霍夫曼編碼不是很基本的嗎 有什麼好特別專業?
沒有欸  我當初也很疑惑

有一堆很複雜的source code 像是Fano code  Shannon type code...

但是都沒有Huffman期末作業想出來的code直觀簡單又是最佳
推 sef96121:只能朝拜了！
推 NDSLite:優文
推 liar5566:不錯，實力跟我相當
推 alog:XDDD陰森宅宅是沙小la
→ tigertiger:什麼工程師 起碼也是數位教父好嗎 沒他哪來的0101
我文章裡有說他是消息理論開山始祖阿

我這篇文章真的不專業  修過課的人應該都知道我講的很簡單
※ 編輯: roger29 (111.249.98.123), 06/30/2014 00:02:32
→ tigertiger:交換電路
推 lolic:嗯摁 我也這樣想 可惜打到一半你先發文了
推 ppt0726:一優質文章
推 cybergenie:推 Shannon
推 FRX:
※ 編輯: roger29 (111.249.98.123), 06/30/2014 00:11:03
噓 kissyourbi:通訊系統最簡單的章節也可以拿來炫XD
→ kissyourbi:三大公式 H(s) 互消息 審農第三定律 背起來 100分
→ kissyourbi:連理解都不用理解 國中數學 秒殺 ZZZzzz
推 withfrog:長知識 謝啦
推 QueenYi:長知識推
噓 wa007123456:真的不專業就不要貼了
推 dgmnewlife:看不出來在炫阿... 不就是分享兒已@@
推 awen860836:通原讀得不錯喔
推 zyyym:研究所畢業後都忘光了
噓 kissyourbi:這章節 我大概半小時就融會貫通了 比你打文章還快
→ euripides31s:推
推 chen20:分享推!是在悲憤什麼