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

"In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper ""A Method for the Construction of Minimum-Redundancy Codes."" Huffman became a member of the MIT faculty upon graduation and was later the founding member of the Computer Science Department at the University of California, Santa Cruz, now a part of the Baskin School of Engineering. Huffman coding uses a specific method for choosing the representation for each symbol, resulting in a prefix-free code (sometimes called ""prefix codes"") (that is, the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol) that expresses the most common characters using shorter strings of bits than are used for less common source symbols. Huffman was able to design the most efficient compression method of this type: no other mapping of individual source symbols to unique strings of bits will produce a smaller average output size when the actual symbol frequencies agree with those used to create the code. A method was later found to do this in linear time if input probabilities (also known as weights) are sorted. For a set of symbols with a uniform probability distribution and a number of members which is a power of two, Huffman coding is equivalent to simple binary block encoding, e.g., ASCII coding. Huffman coding is such a widespread method for creating prefix-free codes that the term ""Huffman code"" is widely used as a synonym for ""prefix-free code"" even when such a code is not produced by Huffman's algorithm. Although Huffman coding is optimal for a symbol-by-symbol coding with a known input probability distribution, its optimality can sometimes accidentally be over-stated. For example, arithmetic coding and LZW coding often have better compression capability. Both these methods can combine an arbitrary number of symbols for more efficient coding, and generally adapt to the actual input statistics, the latter of which is useful when input probabilities are not precisely known[@more@]"

"人工智慧真空吸塵器 今天收到一封廣告信，是 iRobot 公司出的 Roomba 智慧吸塵機器的廣告。先前讀到一些這方面的產品，就趁這個機會介紹一下好了，希望對於懶得打掃家裡地板的人有幫助 :p Roomba 和一般的智慧吸塵機器一樣，都是做成圓餅的形狀，主要還是為了在探索地型時撞到牆仍能順利轉彎。這類產品最基本的技術還是在於如何建立環境地圖，以及避開危險的地形；更進階的是要辨認什麼是需要清潔的，而什麼又是不能清理的(試想家中的博美狗被吸塵器抓住的樣子…) Roomba 用的概念很單純；它會先利用螺旋狀的路徑擴大自己的虛擬視野，試著找出房間的邊界在哪裡，同時記住自己走過的距離。當撞到東西時，它會先向後退一點點，轉一點點彎，再向前進。找到邊界之後，它會開始利用直線前進，並清掃記憶中還沒有打掃的區域。 在 Roomba 中比較有趣的是它還提供一個""虛擬牆""(Virtual Wall)的裝置；由於 Roomba 會儘量找出牆的範圍，所以如果門開著它搞不好就會跑出去了，若是我們希望門可以不要關，又不要它跑出房間，就可以把 Virtual Wall 放在門口，這樣它就不會跑出去了。Virtual Wall 其實是一個會發出不可見光的裝置，Roomba 感應到它的光線，就會當作那是禁區而轉彎了。 Roomba 這台能夠感測到樓梯之類的危險區域，而不會摔下去；當它在進行清掃的時候，會放音樂來降低它的噪音(還真貼心啊…-_-)，它的聲音大約是 80dB左右。 同樣的智慧型吸塵器是瑞典的 Electrolux 公司所做的 trilobite；這台紅色的小圓餅功能和 Roomba 類似，不過它不會避樓梯，而需要用鋪在地上磁毯來畫出禁區。不過它有個有趣的功能，就是會自己跑回去固定的""家""充電，真是很可愛的功能 :p 看完這個，有沒有想去買一個來玩看看丫xd[@more@]"

"這算是它的應用吧~~ 教電腦怎麼走路 現今充斥於電影或是電玩中的人物或角色，大多都無法避免要走得""像人""；當傳統的方法繁瑣而缺乏彈性，基因演算法再一次為動畫製片指出一條簡單易用的路…。 傳統上，要做出動畫中的人物走路的畫面，通常都需要仔細描述每個畫面怎麼走、或是把真人的動作拍攝下來再輸入進去。然而這種做法太繁瑣也缺乏彈性，所以 Torsten Reil 決定運用基因演算法，來教導他的人物走路。 首先必須建立環境；把重力和人物的肌肉結構都做好關連之後，每一個角色有七百組參數可以調整。他透過類神經網路來控制肌肉的運動，但是由於系統實在太複雜而不可能透過人來調整，所以這時就可以導入基因演算法來訓練。 由於系統中有重力等條件，所以系統評分的方法就採用人物走的步數來評分；走越多步的就越好，直到它跌倒為止。剛開始系統中的人物大都走不了一步，但至少有些會比其他晚一些倒下，這些表現比較好的個體會被複製二十份，再做一些細微的突變放到下一代。同時系統也會再產生八十個新的個體加入賽局。 但是由於評分標準是採用走的步數，所以有些角色就會發展出奇怪的走法，例如仆伏前進或是翻筋斗之類的，所以他再進一步把遊戲規則加入一條，就是重心不能低於某個高度。 經過二十回合，系統已經能夠產生走得非常順暢的角色了；我們不需要知道它內部的類神經網路怎麼排列，但可以確定的是演化的力量再一次的快速替我們找到一個解答。[@more@]"

"今天在看 PostgreSQL 的文件時，發現有個章節在講運用基因演算法(Genetic Algorithms) 來最佳化資料庫的查詢方法(Query Plan)，就來介紹一下 PostgreSQL 是如何應用的。 所謂的 Query Plan(查詢方法)，是指資料庫管理程式如何由現存的 Table 中，做出使用者想要的資料。Query Plan中最難以處理的是 Join 這個動作。Join 這個動作，簡而言之就是把兩個相關的 Table 合成一張大的 Table；例如我們有一個 Table 記錄 ""人名-居住城市""，另一個""人名-喜好""，今天如果我們要找出""住台北、又喜歡寫 Blog""的人，就可以利用 Join 這個指令，以人名當作索引值，合成一張同時具有我們所需要資料的 Table。 Join 有很多種方法可以做到，最差的狀況就是把所有的可能性都列出來，再刪掉不正確的。舉例來說，住址 Table 有一千筆，喜好資料也有一千筆，那麼就先產生一百萬筆的表格，再一一刪去；相對的，如果我們知道人名都沒有重覆、居住城市表格中，同一個人也只會有一筆資料、每個人也只有一個喜好，那麼甚至可能幾千筆就做出來了。 但並不是每一個 Query Plan 都是如此的顯而易見，當需要比對的 Table 越來越多，到底是先 Join 哪一個 Table、先 Join 哪兩個 Join 完的結果，會變成一個需要把全部的可能性都列出來，才知道哪個最好的問題，我們稱這種解法叫做""窮盡搜""(Exhaustiive Search)，意思就是得把所有的組合都找出來才行。 更慘的是 Query Plan 的數量又隨著 Table 的增加而大幅增加，當需要 Join 的 Table 由兩個變三個、四個甚至到十幾個時， Query Plan 的總量就像 1*2*3*4 這樣呈指數成長，到最後要找出所有的可能解答本身所花的時間，搞不好都比資料庫查詢時間來得長了。 在德國的 University of Mining and Technology 自動控制學院設計了一個電力控制系統，用 PostgreSQL 來當作決策系統的資料庫，但是因為決策系統需要運用大量的 Join 來進行推理的運算，為了兼顧效率，他們把基因演算法引入資料庫的設計之中，用來快速產生有效率的 Query Plan。 關於基因演算法的基本概念在此略過，請參考本站相關文章。 Query Plan 最佳化的作法和著名的 Traveling Salesman Problem(TSP) 問題很類似，先將可能的解法變成數字的字串，例如 4-1-3-2 就表示先讓 Table 4 和 Table 1 做 Join，再和 Table 3、2 做 Join。 演化時採用穩態演化，也就是每次只把表現最差的一個 Plan 淘汰掉；而子代的產生則是運用 ""edge recombination crossover[註二]""，而突變的機制在這裡並不使用。 運用基因演算法，資料庫可以在合理的時間中找出有效的 Query Plan來進行 Join 的動作，然而除了找出最好的 Query Plan 之外，電腦的的Computation Time也是一個很重要的因素，不同的參數對於系統也會有不同的影響。 從這個例子可以看到基因演算法所運用的場合，還是脫離不開""在合理的時間""、""複雜度高的狀況下""、""找到合理可接受的解法""的特色。 註一：PostgreSQL 是一個 GPL 的資料庫，最早是由 Berkeley 所發展的，如今和 MySQL 同為網路上最受歡迎的 GPL 資料庫軟體，官方網站在 http://www.postgresql.org。 註二：關於 edge recombination crossover 的說明，請參考這裡。 參考資料： Genetic Query Optimization 相關閱讀： 上帝的靈藥─基因演算法(一) 上帝的靈藥─基因演算法(二) June 26th 2003 Posted to 基因演算法[@more@]"