http://hi.baidu.com/uejwncfuebbprwe/item/30cafb2d3d2e5584af48f54a

本節介紹幾個常見的壓縮算法。

（一） 字典算法
　　字典算法是最為簡單的壓縮算法之一。它是把文本中出現頻率比較多的單詞或詞匯組合做成一個對應的字典列表，并用特殊代碼來表示這個單詞或詞匯。例如：
　　有字典列表：
　　00=Chinese
　　01=People
　　02=China
　　源文本：I am a Chinese people,I am from China 壓縮后的編碼為：I am a 00 01,I am from 02。壓縮編碼后的長度顯著縮小，這樣的編碼在SLG游戲等專有名詞比較多的游戲中比較容易出現，比如《SD高達》。
（二） 固定位長算法（Fixed Bit Length Packing）
　　這種算法是把文本用需要的最少的位來進行壓縮編碼。
比如八個十六進制數：1，2，3，4，5，6，7，8。轉換為二進制為：00000001，00000010，00000011，00000100，00000101，00000110，00000111，00001000。每個數只用到了低4位，而高4位沒有用到（全為0），因此對低4位進行壓縮編碼后得到：0001，0010，0011，0100，0101，0110，0111，1000。然后補充為字節得到：00010010，00110100，01010110，01111000。所以原來的八個十六進制數縮短了一半，得到4個十六進制數：12，34，56，78。
這也是比較常見的壓縮算法之一。

（三） RLE算法
　　這種壓縮編碼是一種變長的編碼，RLE根據文本不同的具體情況會有不同的壓縮編碼變體與之相適應，以產生更大的壓縮比率。

　　變體1：重復次數+字符
文本字符串：A A A B B B C C C C D D D D，編碼后得到：3 A 3 B 4 C 4 D。

　　變體2：特殊字符+重復次數+字符
文本字符串：A A A A A B C C C C B C C C，編碼后得到：B B 5 A B B 4 C B B 3 C。編碼串的最開始說明特殊字符B，以后B后面跟著的數字就表示出重復的次數。

　　變體3：把文本每個字節分組成塊，每個字符最多重復 127 次。每個塊以一個特殊字節開頭。那個特殊字節的第 7 位如果被置位，那么剩下的7位數值就是后面的字符的重復次數。如果第 7 位沒有被置位，那么剩下 7 位就是后面沒有被壓縮的字符的數量。例如：文本字符串：A A A A A B C D E F F F。編碼后得到：85 A 4 B C D E 83 F（85H= 10000101B、4H= 00000100B、83H= 10000011B）

　　以上3種不RLE變體是最常用的幾種，其他還有很多很多變體算法，這些算法在Winzip Winrar這些軟件中也是經常用到的。

（四） LZ77算法
　　LZ77算法是由 Lempel-Ziv 在1977發明的，也是GBA內置的壓縮算法。LZ77算法有許多派生算法(這里面包括 LZSS算法)。它們的算法原理上基本都相同，無論是哪種派生算法，LZ77算法總會包含一個動態窗口（Sliding Window）和一個預讀緩沖器（Read Ahead Buffer）。動態窗口是個歷史緩沖器，它被用來存放輸入流的前n個字節的有關信息。一個動態窗口的數據范圍可以從 0K 到 64K，而LZSS算法使用了一個4K的動態窗口。預讀緩沖器是與動態窗口相對應的，它被用來存放輸入流的前n個字節，預讀緩沖器的大小通常在0 – 258 之間。這個算法就是基于這些建立的。用下n個字節填充預讀緩存器（這里的n是預讀緩存器的大小）。在動態窗口中尋找與預讀緩沖器中的最匹配的數據，如果匹配的數據長度大于最小匹配長度 （通常取決于編碼器，以及動態窗口的大小，比如一個4K的動態窗口，它的最小匹配長度就是2），那么就輸出一對〈長度（length），距離（distance）〉數組。長度(length)是匹配的數據長度，而距離(distance)說明了在輸入流中向后多少字節這個匹配數據可以被找到。

　　例如：（假設一個 10個字節的動態窗口, 以及一個5個字節的預讀緩沖器）
文本：A A A A A A A A A A A B A B A A A A A
--------------------- =========
動態窗口 預讀緩存器
動態窗口中包含10個A ，這就是最后讀取的10個字節。預讀緩沖器包含了 B A B A A。編碼的第一步就是尋找動態窗口與預讀緩存器相似長度大于2的字節部分。在動態窗口中找不到B A B A A，所以B就被按照字面輸出。然后動態窗口滑過1個字節，現在暫時輸出了一個B。
第二步：A A A A A A A A A A A B A B A A A A A
--------------------- =========
動態窗口 預讀緩存器
現在預讀緩沖器包含A B A A A，然后再和動態窗口進行比較。這時，在動態窗口找到了相似長度為2的A B，因此一對〈長度, 距離〉就被輸出了。長度(length)是2 并且向后距離也是2，所以輸出為<2,2>，然后動態窗口滑過2個字節。現在已經輸出了B <2,2>。
第三步：A A A A A A A A A A A B A B A A A A A
--------------------- =========
動態窗口 預讀緩存器
繼續上面的方法得到輸出結果<5,8>。現在已經輸出了B <2,2> <5,8>。
最終的編碼結果是：A A A A A A A A A A A B <2,2> <5,8>。
但數組是無法直接用二進制來表示的，LZ77會把編碼每八個數分成一組，每組前用一個前綴標示來說明這八個數的屬性。比如數據流：A B A C A C B A C A按照LZ77的算法編碼為：A B A C<2,2> <4,5>，剛好八個數。按照LZ77的規則，用“0”表示原文輸出，“1”表示數組輸出。所以這段編碼就表示為：00001111B（等于0FH），因此得到完整的壓縮編碼表示：F A B A C 2 2 4 5。雖然表面上只縮短了1個字節的空間，但當數據流很長的時候就會突出它的優勢，這種算法在zip格式中是經常用到。

　　除此之外還有很多壓縮算法，像霍夫曼編碼（Huffman Encoding）等等。這些編碼也是非常的著名而且壓縮效率極高，不過這些編碼的算法相對比較繁瑣，規則也很復雜，由于篇幅就不逐一介紹了。如果大家對這方面感興趣可以到網站相關網站查詢資料。

　　小結：這一節介紹的幾種算法在GBA上是比較容易遇到的典型算法，但絕不是說只有這幾種，還是有很多時候都得自己ASM跟蹤進行分析，這里介紹給大家希望能拓展大家的思維，方便進行程序分析，對于一切的問題ASM才是萬能的。