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

本節(jié)介紹幾個(gè)常見的壓縮算法。

（一） 字典算法
　　字典算法是最為簡單的壓縮算法之一。它是把文本中出現(xiàn)頻率比較多的單詞或詞匯組合做成一個(gè)對應(yīng)的字典列表，并用特殊代碼來表示這個(gè)單詞或詞匯。例如：
　　有字典列表：
　　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游戲等專有名詞比較多的游戲中比較容易出現(xiàn)，比如《SD高達(dá)》。
（二） 固定位長算法（Fixed Bit Length Packing）
　　這種算法是把文本用需要的最少的位來進(jìn)行壓縮編碼。
比如八個(gè)十六進(jìn)制數(shù)：1，2，3，4，5，6，7，8。轉(zhuǎn)換為二進(jìn)制為：00000001，00000010，00000011，00000100，00000101，00000110，00000111，00001000。每個(gè)數(shù)只用到了低4位，而高4位沒有用到（全為0），因此對低4位進(jìn)行壓縮編碼后得到：0001，0010，0011，0100，0101，0110，0111，1000。然后補(bǔ)充為字節(jié)得到：00010010，00110100，01010110，01111000。所以原來的八個(gè)十六進(jìn)制數(shù)縮短了一半，得到4個(gè)十六進(jìn)制數(shù)：12，34，56，78。
這也是比較常見的壓縮算法之一。

（三） RLE算法
　　這種壓縮編碼是一種變長的編碼，RLE根據(jù)文本不同的具體情況會(huì)有不同的壓縮編碼變體與之相適應(yīng)，以產(chǎn)生更大的壓縮比率。

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

　　變體2：特殊字符+重復(fù)次數(shù)+字符
文本字符串：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后面跟著的數(shù)字就表示出重復(fù)的次數(shù)。

　　變體3：把文本每個(gè)字節(jié)分組成塊，每個(gè)字符最多重復(fù) 127 次。每個(gè)塊以一個(gè)特殊字節(jié)開頭。那個(gè)特殊字節(jié)的第 7 位如果被置位，那么剩下的7位數(shù)值就是后面的字符的重復(fù)次數(shù)。如果第 7 位沒有被置位，那么剩下 7 位就是后面沒有被壓縮的字符的數(shù)量。例如：文本字符串：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這些軟件中也是經(jīng)常用到的。

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

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

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

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