宅學習 - Social Learning Space 社交學習空間@FJU CSIE

"一、簡介：

資料的儲存和傳輸式資料處理的兩個重要的領域，它們都和資料量的大小息息相關，尤其是網際網路何多媒體結合的情況下，如何讓龐大的資料順利的流通於有限的頻寬上，更是重要的議題，同樣的資訊內容，如果我們可以用更少的資料來表示，不論是在儲存或是傳輸上都有很大的幫助，這就是資料壓縮的想法。

[@more@]

我們已ASCII為例，一般在做資料儲存時，每一個文字都是一個位元組(byte)，也就是八個位元(bit) ，但是實際上每個文字都使用頻率相差很大，我們如果用不同長度的位元數來儲存這些資料，也就是出現頻率越高的字母其長度越短，頻率越低的字其長度則越長，其資料量也就能大幅減少了。當然資料壓縮之後，字母和內碼依然是對應的，最後可以完全還原，才不至於改變資訊的內容。

二、霍夫曼樹介紹：

我們將使用二元數來進行資料壓縮的演算法，稱為霍夫曼(Huffman)編碼，這棵二元數也就稱為霍夫曼樹，它是根據每一個字母出現的頻率，重新定義一個字母的內碼，而每個字母的內碼並不完全相等，霍夫曼演算法相當的減當，而壓縮效果也很理想，根據實驗，霍夫曼演算法大概可以得到50%左右的壓縮率。

首先我們先介紹幾個相關的名詞，內部路徑長(internal path length)是指由數根到每個內部節點的路徑長度總和；外部路徑長(external path length) 是指由數根到每個外部節點的路徑長度總合；所以一棵如底下圖的二元樹，其內部路徑長度為   1 + 2 + 1 + 2，外部路徑長度為 2 + 3 + 3 + 2 + 3

如果每一個數夜節點都賦予一個加權數(weight)，每一個數葉節點的加權數乘上其路徑長的總和就稱為加權路徑長(weighted path length)，所以如果上圖節點加權數分別為 0.19*2 + 0.03*3 + 0.21*3 + 0.12*2 + 0.39*3 = 2.69 就是這棵樹的加權路徑長。

霍夫曼邊每的想法非常簡單，每一個字母出現的頻率就是他的加權數，將這些字母一一放到二元樹的樹葉節點，從根節點到數葉節點所走過的路徑就是他的編碼規則，如果路徑是往左邊，則編碼則為 0，往右邊則為1 ，所以上圖的每一個字母編碼分別為 00、010、011、10、110，霍夫曼編瑪就是要產生一棵最小的加權路徑長的二元樹，這棵二元樹將會讓我們得到更好的壓縮效果。

三、霍夫曼樹建立：

我們一開始將每個字母分別建成只有一個根節點的二元樹，根據其頻率由小到大排序；取出最前面的兩個節點，將它們分別連結到另一棵新的二元樹的左右子樹，新二元樹根節點就是左右子束的頻率和，依照新二元樹的頻率大小放回元串列中，並保持該串列由小到大的特性；重複上面的步驟直到所有節點都處理完畢為止。

假設 Ａ、Ｂ、Ｃ、Ｄ、Ｅ五個字母的頻率分別為　0.19、0.09、0.21、0.12、0.39

那們我們先將他們依序排列如下：

霍夫曼樹建立過程如下：

１.  取出最小的0.09和0.12，合併成另外一棵新的二元樹，其根節點的頻率為0.21

２.  在取出0.19和0.21合併後在得到0.10的新二元樹

３.  取出 0.21 和0.39的節點，產生頻率為0.60 的新節點

４.  最後在取出0.40和0.60 的節點，合併成頻率為1.0的節點，至此霍夫曼二元樹就算完成了

霍夫曼資料壓縮演算法的過程，首先是根據資料的出現頻率，建立一棵霍夫曼二元樹，其次根據這棵二元樹的走訪，建立一個字元與新碼的對照表，有了這個對照表，我們就能將一個ASCII碼的字元檔案轉換成新內碼的檔案，最後要將這個新內碼的檔案還原成為新的字元檔，同樣要以同一棵霍夫曼樹來解碼。

四、結論：

就以霍夫曼數的編碼模式的壓縮效率來說，並非為效率非常高的壓縮方式。假設以8位元資料為一個單位來說，無論壓縮的在怎麼好，頂多也子能壓縮到1/8而已。若將更多的位元來表示更多的位，也許會有更好的壓縮效率，但此時所出現的頻率表亦也會更大，故壓縮效率也無法提升到哪裡去。

也因為霍夫曼編碼有這樣的缺點，縮以此編碼方式一般皆不會拿來單獨使用，而長與其他的壓縮演算法配合使用。舉個例子來說，如常用的「LHA」當中就是以『霍夫曼編碼』與『LZ法』搭配使用。再例如，用於圖像的JPEG格式中最後要做編碼的時候，也常會使用霍夫曼來提升壓縮率。

"

"今天老師剛好講解了NP-Complete定理不過沒時間所以沒辦法講完，所以我就去找了這些資料，不過這裡面是基本的介紹，沒有課本上講的詳細。這個網頁裡面還會介紹最佳演算法。[@more@]參考資料：http://www.pws.stu.edu.tw/bangye/otherpaper/NPC1-bang2006.htm#_Toc144057689"

"Ant Algorithms(螞蟻演算法)
[@more@]演算法原理: 螞蟻可以由蟻穴到食物目的地找到一條最短路線, 它們用的不是視覺, 而是在走過的地方會殘留一種分泌物pheromone, 當以後的螞蟻經過時, 就有較高的機率選擇pheromone濃度高的方向, 因此隨著時間增長, 漸漸螞蟻會走同一路線(亦即最短路線)由蟻穴到食物目的地來回, 利用這種自然界的原理已有效率地解一些尋優問題(Optimization Problems)。

出處：http://chern.ie.nthu.edu.tw/Ant_Algorithms.htm"

"

學了那麼多演算法，怎麼才是好的演算法，這裡我整理了出一些關於演算法的心得：

<定義>：
在有限步驟內解決數學問題的程序。

<特性>：
1.每一個運算處理必須是"明確"的，也就是說必須要明確的知道每一運算要做什麼處理。例如:5/0 沒有明確結果，便不能算是演算法。[@more@]2.需"有效性"，即為每一步驟都能夠用人和筆在有限的時間內完成。
例如:整數的運算就是有效的運算，但實數運算中有些實數有無窮個小數點位數，所以此類實數做四則運算就不為有效性。

3.演算法在"有限次"的運算後會終止。
若無”終止”的特性就稱之為計算程序，如作業系統的演算法。

<補充>:為何要學演算法？
舉個例子來說，若要在一個固定的區域內，於限時內找出指定的一樣東西，我們可以採用多種找法，如逐一檢視，或二分搜尋等方法....等。但並非每種方式都是適用的。當我們想要解決某一問題時，若事先知道問題屬於容易的，則可以用絕佳的。"

"因為對貪婪演算法的使用我還不是很清楚，所以我就查了有關貪婪法的資料，老師說貪婪法就是找最有利的方法去做，而貪婪演算法不是有prim's和kruskal's，這是目前我們上的兩個，將來應該還會接觸到其他的演算法，希望能了解更多，而這個網站簡單的說明了貪婪演算法，讓我更清楚了解這個演算法了[@more@]參考資料：http://freesf.tnc.edu.tw/mantalk/ckhung/b/al/greedy.shtml"

"霍夫曼編碼是我一開始學資料結構時最感興趣的一種方法，因為當時老師有列出兩種的比較，一種是沒有霍夫曼的方法，另外一種是使用固定長度的。不過再這演算法課堂上老師又講解了三種方法，有固定長度的還有就是使用prefix的方法再來就是霍夫曼。但是我心裡卻想，竟然可以利用演算法來讓資列壓縮，所以這讓我很感興趣，剛好這次我的project是要介紹霍夫曼編碼所以我就先講解大綱。[@more@]霍夫曼編碼法（Huffman’s Encode）是霍夫曼在1952年所提出的一種無失真壓縮技術，其原理是將欲壓縮之字串，先讀一遍，將字串中的每一相異單字元（Single Character）的出現頻率，做成統計，依此建構霍夫曼樹（Huffman’s Tree）。每一相異單字元，用0與1予以編碼，出現次數逾多者，給予較少的位元編碼，最後將這些位元串組合起來，並加上Huffman’s tree ，就成為壓縮檔案。Huffman編碼法為依資訊源符號出現機率，在對資訊源符號逐一編碼條件下(The symbols be coded one at a time)，最佳之編碼方法。參考網址：http://www.cc.chu.edu.tw/~u8702640/Huffman%BDs%BDX%AAk.htm"

"井字遊戲是幾乎每個人都玩過的遊戲，但是我們卻不能很直接接聯想到這其中的涵義。[@more@]

在底下我找到的資料就是在討論如何設計與製作井字遊戲的演算法，井字遊戲看起來很簡單，可是程式設計卻牽涉到基礎遊戲的製作、遊戲規則、人工智慧、資料結構、演算法等相關知識範圍，除了可以達到教學的目的外，還可以強化對撰寫程式的觀念。我還記得我大一時候，老師就出了這一提給我們寫，不過我學藝不精，還不會領悟到。

參考資料：http://www.wesoho.com/article.asp?id=638"

"

A*(A-Star)演算法是在Game中通常用來解決最短路徑(Shortest Path)問題的一種演算法，相對於另一個知名的Dijkstra演算法來說，Dijkstra演算法雖然可以保證找到一條最短的路徑，但不如A*演算法這樣簡捷快速。同時，Dijkstra的搜尋深度在某些情形下也容易顯得不適用。

[@more@]A*演算法便是為了這些情形而出現的，可以算是，Dijkstra演算法的一種改良。
對於我們這些大學生來說，遊戲是生活中不可或缺的一部份。我們資訊相關科系的學生，在玩遊戲之於，更可以透過課堂中學到的知識，配合上像A*這樣的演算法，嘗試著了解遊戲的製作過程，並動身學習，就是一種最佳的學習方法。 參考資料：http://blog.minstrel.idv.tw/2004/12/star-algorithm.html"

"

學了那麼多種演算法，怎麼才是好的演算法，這裡我整理了出一些關於演算法的心得：

<定義>：
在有限步驟內解決數學問題的程序。

<特性>：
1.每一個運算處理必須是"明確"的，也就是說必須要明確的知道每一運算要做什麼處理。例如:5/0 沒有明確結果，便不能算是演算法。[@more@]

2.需"有效性"，即為每一步驟都能夠用人和筆在有限的時間內完成。
例如:整數的運算就是有效的運算，但實數運算中有些實數有無窮個小數點位數，所以此類實數做四則運算就不為有效性。

3.演算法在"有限次"的運算後會終止。
若無”終止”的特性就稱之為計算程序，如作業系統的演算法。

<補充>:為何要學演算法？
舉個例子來說，若要在一個固定的區域內，於限時內找出指定的一樣東西，我們可以採用多種找法，如逐一檢視，或二分搜尋等方法....等。但並非每種方式都是適用的。當我們想要解決某一問題時，若事先知道問題屬於容易的，則可以用絕佳的。

"