字典編碼課件

1、第五章字典編碼迄今為止，我們大多假設(shè)符號是獨立的但這對許多常見數(shù)據(jù)類型來說是不對的如：文本、圖像和源代碼文件基本思想標識經(jīng)常出現(xiàn)的符號模式保存于字典中對這些常出現(xiàn)的模式采用更有效的編碼方式用其在字典中的索引作為碼字而對其它部分采用缺省（不太有效）的編碼方式以期總的編碼效率更高注意這對如文本這樣的信源是合理的顯然對（接近）隨機數(shù)據(jù)不會有效1例考慮某英文文本信源26 字母和6個標點符號單字符，定長碼5 比特/字符4字符模式，定長碼20比特/模式 (324 = 220 = 1,048,576)假設(shè)為非均勻分布字典：256個最常出現(xiàn)的模式，每個用8比特編碼對其它模式用20比特編碼再增加1比特用于指示是

2、上述兩種情況中的哪種2例 (2)若用p 表示使用字典的概率，則比特率為R = 9p + 21(1-p) = 21 - 12p壓縮 21 - 12p p 0.084還不太壞在等概率假設(shè)下，p = 0.00025 p越大，性能越好 選擇最可能出現(xiàn)的模式存于字典中為了達到好的性能，需要知道信源的結(jié)構(gòu)信息有足夠的先驗信息， 靜態(tài)字典否則，在編碼過程中獲得信源的知識 自適應(yīng)字典3靜態(tài)字典靜態(tài)字典對信源的結(jié)構(gòu)有足夠的先驗知識時，利用先驗知識構(gòu)造字典對特定應(yīng)用特別有效只對針對其設(shè)計的特定應(yīng)用和數(shù)據(jù)有效例：電話號碼的區(qū)號例：學(xué)校的學(xué)生信息表地 區(qū)長途區(qū)號北京市 010上海市021天津市022重慶市023沈陽市

3、024南京市025烏魯木齊市0991喀什市 0998 4自適應(yīng)字典有許多場合，開始時不知道要編碼數(shù)據(jù)的統(tǒng)計特性，也不一定允許事先知道它們的統(tǒng)計特性。字典編碼的思路：根據(jù)數(shù)據(jù)本身包含有重復(fù)代碼的特性例：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮如果用一些簡單的代號代替這些字符串，就可以實現(xiàn)壓縮，實際上就是利用了信源符號之間的相關(guān)性。字符串與代號的對應(yīng)表就是字典。實用的字典編碼算法的核心就是如何動態(tài)地形成字典，以及如何選擇輸出格式以減小冗余。5自適應(yīng)字典開始Jacob Ziv / Abraham Lempel1977 (LZ77/LZ1), 1978 (LZ78/LZ2)1984 Terry Welch

4、 (LZW)LZ77 vs. LZ78兩種不同的方法有很多變種是很多主流壓縮的基礎(chǔ)6LZ77基本方法：字典為先前已編碼序列的一部分搜索緩沖區(qū)為當前字典，通常為幾千字節(jié)機制：滑動窗口搜索緩沖區(qū)( Search buffer)、前向（look ahead）緩沖區(qū)、搜索指針(search pointer)目標：在搜索緩沖區(qū)中，尋找與搜索指針指向的字符串匹配的最長串，并對其進行編碼基本原理：如果某些模式在局部重復(fù)出現(xiàn)，能得到更有效的表示7LZ77 (2)(o)ffset = search ptr - match ptr = 7(l)ength = 連續(xù)匹配的字符數(shù) = 4(c)odeword = C(

5、r)編碼 = If |search buff| = S, |A| = A, S + |LA buff| = W定長碼：log2S + log2W + log2ASearch pointer8LZ77 編碼舉例序列cabracadabrarrarradW = 13, S = 7|cabraca|dabrar|rarrad對d，沒有匹配的字符串發(fā)送 (可以做得更好?) |abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|abrarr|rarrad發(fā)送 9LZ77 編碼舉例 (2)|cadabra

6、r|rarrad|cadabrar|rarrad|cadabrar|rarrad|發(fā)送 可以做得更好?發(fā)送 !總結(jié)：三種情況沒有匹配匹配匹配串超過了搜索緩沖區(qū)10LZ77 解碼舉例 輸入 輸出cabraca解碼：增加一個 d: c|abracad|解碼： 從第一個a開始，拷貝4個字母，解碼C(r)cabrac|adabrar|解碼： 從第一個r開始，拷貝3個字母 cabracada|brarrar|再拷貝2個字母cabracadabr|arrarar|解碼C(d)：cabracadabrarrarard11LZ77編碼小結(jié)使用固定大小窗口進行詞語匹配，而不是在所有已經(jīng)編碼的信息中匹配，是因為匹

7、配算法的時間消耗往往很多，必須限制詞典的大小才能保證算法的效率；隨著壓縮的進程滑動詞典窗口，使其中總包含最近編碼過的信息，是因為對大多數(shù)信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。LZ77解碼器比編碼器簡單得多（非對稱壓縮）維持一個與編碼器窗口大小相同的緩沖區(qū)，并在緩沖區(qū)中找出匹配串，將匹配串及第3個字段的字符寫入輸出流，同時移進緩沖區(qū)在如文件壓縮（一次壓縮，多次還原）的場合很有用12LZ77的變種迄今為止自適應(yīng)模型，沒有先驗知識漸近 接近知道信源統(tǒng)計知識的情況但是，局部性起到了很大作用改進變長編碼offset: 各數(shù)值基本均勻分布，一般用定長碼length: 可用Huffm

8、an碼/Golomb碼/Exp-Golomb碼PKZip, Zip, Lharcm ONG, gzip, ARJ可變緩沖區(qū)大小需設(shè)計較完善的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)對大緩沖區(qū)的快速搜索LZSS：搜索緩沖區(qū)（字典）用對分查找樹保持，前向緩沖區(qū)用循環(huán)隊列表示取消 LZSS：只需增加1一個標記位，用于指示是否為單字符13LZ78LZ77假設(shè)模式滿足局部性LZ78:沒有搜索緩沖區(qū)代之以顯式的字典編碼器/解碼器必須同步建立字典 如沒有匹配，將字典原有詞條+當前沒有匹配的字符 字典的新詞條編碼：i = 字典索引同LZ77，i=0 表示在字典中沒有找到匹配的詞條c = 下一字符的碼字14LZ78舉例索引條目字典：輸入

9、：wabbawabbawabbawabbawoowoowoo輸出：15LZ78舉例 (2)索引條目1w字典：輸入： wabbawabbawabbawabbawoowoowoo輸出：16LZ78舉例 (3)索引條目1w2a字典：輸入： -abbawabbawabbawabbawoowoowoo輸出：17LZ78舉例 (4)索引條目1w2a3b字典：輸入： -bbawabbawabbawabbawoowoowoo輸出：18LZ78舉例 (5)索引條目1w2a3b4ba字典：輸入： -bawabbawabbawabbawoowoowoo輸出：19LZ78舉例 (6)索引條目1w2a3b4ba5字典：

10、輸入： -wabbawabbawabbawoowoowoo輸出：20LZ78舉例 (7)索引條目1w2a3b4ba56wa字典：輸入： -wabbawabbawabbawoowoowoo輸出：21LZ78舉例 (8)索引條目1w2a3b4ba56wa7bb字典：輸入： -bbawabbawabbawoowoowoo輸出：22LZ78舉例 (9)索引條目1w2a3b4ba56wa7bb8a字典：輸入： -awabbawabbawoowoowoo輸出：23LZ78舉例 (10)索引條目1w2a3b4ba56wa7bb8a9wab字典：輸入： -wabbawabbawoowoowoo輸出：24LZ7

11、8舉例 (11)索引條目1w2a3b4ba56wa7bb8a9wab10ba字典：輸入： -bawabbawoowoowoo輸出：25LZ78舉例 (12)索引條目1w2a3b4ba56wa7bb8a9wab10ba字典：輸入： -wabbawoowoowoo輸出：11wabb26LZ78舉例 (13)字典：輸入： -awoowoowoo輸出：11wabb12aw索引條目1w2a3b4ba56wa7bb8a9wab10ba27LZ78舉例 (14)字典：輸入： -oowoowoo輸出：11wabb12aw13o索引條目1w2a3b4ba56wa7bb8a9wab10ba28LZ78舉例 (15

12、)字典：輸入： -owoowoo輸出：11wabb12aw13o14o索引條目1w2a3b4ba56wa7bb8a9wab10ba29LZ78舉例 (16)字典：輸入： -woowoo輸出：11wabb12aw13o14o15wo索引條目1w2a3b4ba56wa7bb8a9wab10ba30LZ78舉例 (17)字典：輸入： -owoo輸出：11wabb12aw13o14o15wo16ow索引條目1w2a3b4ba56wa7bb8a9wab10ba31LZ78舉例 (18)字典：輸入： -oo輸出：11wabb12aw13o14o15wo16ow17oo索引條目1w2a3b4ba56wa7b

13、b8a9wab10ba32LZ78觀察：如果繼續(xù)編碼，字典將繼續(xù)增長實用的選擇停止增長字典相當于從此成為一個靜態(tài)字典策略刪除一些較早用過的項如基于使用統(tǒng)計（但還沒有好的算法決定哪些項該刪）將字典全部刪除，從空字典開始重建字典如果沒有信源的特定知識，任何方法可能都不會工作得很好！33LZ78的變種：LZWTerry Welch (1984)基本思想：只對i編碼，而不是編碼 算法：/初始化字典為包含所有字母 Seed dictionary with all alphabet letters, p = null while( !done)a = get_next_symbolif( p a) is

14、in dictionary /在字典中，繼續(xù)用更長的字符串匹配p = p aelsesend out index of p /不在字典中，輸出已匹配部分，從a 重新開始p.a is added to dictionary p = aendwhile34LZW編碼索引條目12a3b4o5w678910字典：輸出：輸入： wabbawabbawabbawabbawoowoowoop = 35LZW編碼(2)索引條目12a3b4o5w678910字典：輸出：輸入： wabbawabbawabbawabbawoowoowoop = w 36LZW編碼(3)索引條目12a3b4o5w6wa78910字典

15、：輸出：5 (w)輸入： -abbawabbawabbawabbawoowoowoop = wa37LZW編碼(4)索引條目12a3b4o5w6wa7ab8910字典：輸出：5 (w)2 (a)輸入： -bbawabbawabbawabbawoowoowoop = ab38LZW編碼(5)索引條目12a3b4o5w6wa7ab8bb910字典：輸出：5 (w)2 (a)3 (b)輸入： -bawabbawabbawabbawoowoowoop = bb39LZW編碼(6)索引條目12a3b4o5w6wa7ab8bb9ba10字典：輸出：5 (w)2 (a)3 (b)3 (b)輸入： -awab

16、bawabbawabbawoowoowoop = ba40LZW編碼 (7)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)輸入： -wabbawabbawabbawoowoowoop = a41LZW編碼 (8)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()輸入： -wabbawabbawabbawoowoowoo索引條目11w121314151617181920p = w42LZW編碼 (9)索引條目12a3b4o5w6wa7ab8bb9ba

17、10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()輸入： -abbawabbawabbawoowoowoo索引條目11w121314151617181920p = wa43LZW編碼 (10)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)輸入： -bbawabbawabbawoowoowoo索引條目11w12wab1314151617181920p = wab44LZW編碼 (11)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b

18、)3 (b)2 (a)1 ()6 (wa)輸入： -bawabbawabbawoowoowoo索引條目11w12wab1314151617181920p = bb45LZW編碼 (12)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)輸入： -awabbawabbawoowoowoo索引條目11w12wab13bba14151617181920p = bba46LZW編碼 (13)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (

19、a)1 ()6 (wa)8 (bb)輸入： -wabbawabbawoowoowoo索引條目11w12wab13bba14151617181920p = a47LZW編碼 (14)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)輸入： -wabbawabbawoowoowoo索引條目11w12wab13bba14aw151617181920p = aw48LZW編碼 (15)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)

20、2 (a)1 ()6 (wa)8 (bb)10 (a)輸入： -abbawabbawoowoowoo索引條目11w12wab13bba14aw151617181920p = wa49LZW編碼 (16)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)輸入： -bbawabbawoowoowoo索引條目11w12wab13bba14aw151617181920p = wab50LZW編碼 (17)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)

21、3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)輸入： -bawabbawoowoowoo索引條目11w12wab13bba14aw15wabb1617181920p = wabb51LZW編碼 (18)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)輸入： -awabbawoowoowoo索引條目11w12wab13bba14aw15wabb1617181920p = ba52LZW編碼 (19)索引條目12a3b4o5w

22、6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)輸入： -wabbawoowoowoo索引條目11w12wab13bba14aw15wabb16ba17181920p = ba53LZW編碼 (20)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)輸入： -wabbawoowoowoo索引條目11w12wab13bba14aw15wabb1

23、6ba17181920p = w54LZW編碼 (21)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)輸入： -abbawoowoowoo索引條目11w12wab13bba14aw15wabb16ba17wa181920p = wa55LZW編碼 (22)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba

24、)11 (w)輸入： -bbawoowoowoo索引條目11w12wab13bba14aw15wabb16ba17wa181920p = ab56LZW編碼 (23)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)輸入： -bawoowoowoo索引條目11w12wab13bba14aw15wabb16ba17wa18abb1920p = abb57LZW編碼 (24)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：

25、輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)輸入： -awoowoowoo索引條目11w12wab13bba14aw15wabb16ba17wa18abb1920p = ba58LZW編碼 (25)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)輸入： -woowoowoo索引條目11w12wab13bba14aw15wab

26、b16ba17wa18abb1920p = ba59LZW編碼 (26)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)輸入： -woowoowoo索引條目11w12wab13bba14aw15wabb16ba17wa18abb19baw20p = baw60LZW編碼 (27)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8

27、 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)輸入： -oowoowoo索引條目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = wo5 (w)61LZW編碼 (28)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)輸入： -owoowoo索引條目11w12wab13bba14aw15wabb16ba17wa18abb19baw

28、20wop = oo5 (w)4 (o)索引條目21oo22232425262728293062LZW編碼 (29)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)輸入： -woowoo索引條目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = o5 (w)4 (o)4 (o)索引條目21oo22o232425262728293063LZW編碼 (30)索引條目12a3b

29、4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)輸入： -woowoo索引條目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = w5 (w)4 (o)4 (o)索引條目21oo22o232425262728293064LZW編碼 (31)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)1

30、0 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)輸入： -oowoo索引條目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = wo5 (w)4 (o)4 (o)11 (w)索引條目21oo22o23wo2425262728293065LZW編碼 (32)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)輸入： -owoo索引條目11w12wab

31、13bba14aw15wabb16ba17wa18abb19baw20wop = oo5 (w)4 (o)4 (o)11 (w)索引條目21oo22o23wo2425262728293066LZW編碼 (33)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)輸入： -woo索引條目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = oo5 (w)4 (o)4 (o)11

32、(w)21 (oo)索引條目21oo22o23wo24oo25262728293067LZW編碼 (34)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)輸入： -woo索引條目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = w5 (w)4 (o)4 (o)11 (w)21 (oo)索引條目21oo22o23wo24oo25262728293068LZW編碼 (35)

33、索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)輸入： -oo索引條目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = wo5 (w)4 (o)4 (o)11 (w)21 (oo)索引條目21oo22o23wo24oo25262728293069LZW編碼 (36)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b

34、)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)輸入： -o索引條目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = woo5 (w)4 (o)4 (o)11 (w)21 (oo)23 (wo)索引條目21oo22o23wo24oo25 woo262728293070LZW編碼 (EOT)索引條目12a3b4o5w6wa7ab8bb9ba10a字典：輸出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba

35、)11 (w)7 (ab)16 (ba)輸入： -索引條目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = o5 (w)4 (o)4 (o)11 (w)21 (oo)23 (wo)4 (o)索引條目21oo22o23wo24oo25 woo262728293071LZW解碼索引條目12a3b4o5w678910字典：輸入： 5 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = 輸出：72LZW解碼 (2)索引條目12a3b4o5w678910字典：輸入： 5 2 3 3 2 1 6 8 10 12

36、 9 11 7 16 5 4 4 11 21 23 4p = w 輸出： w73LZW解碼 (3)索引條目12a3b4o5w6wa78910字典：輸入： - 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wa 輸出： wa74LZW解碼 (4)索引條目12a3b4o5w6wa7ab8910輸入： - - 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = ab 輸出： wab字典：75LZW解碼 (5)索引條目12a3b4o5w6wa7ab8bb910輸入： - - - 3 2 1 6 8 10

37、12 9 11 7 16 5 4 4 11 21 23 4p = bb 輸出： wabb字典：76LZW解碼 (6)索引條目12a3b4o5w6wa7ab8bb9ba10輸入： - - - - 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = ba 輸出： wabba字典：77LZW解碼 (7)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = a 輸出： wabba字典：78LZW解碼 (8)索引條目12a3b4o5w6wa7ab8bb9

38、ba10a 輸入： - - - - - - 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wa 輸出： wabbawa索引條目11w121314151617181920字典：79LZW解碼 (9)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - - - 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wa 輸出： wabbawa索引條目11w121314151617181920字典：80LZW解碼 (10)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - - -

39、 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wabb 輸出： wabbawabb索引條目11w12wab1314151617181920字典：81LZW解碼 (11)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - - - - 10 12 9 11 7 16 5 4 4 11 21 23 4p = bb 輸出： wabbawabb索引條目11w12wab1314151617181920字典：82LZW解碼 (12)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - - - - 10 12 9

40、 11 7 16 5 4 4 11 21 23 4p = bba 輸出： wabbawabba索引條目11w12wab13bba14151617181920字典：83LZW解碼 (13)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - - - - - 12 9 11 7 16 5 4 4 11 21 23 4p = bba 輸出： wabbawabba索引條目11w12wab13bba14151617181920字典：84LZW解碼 (14)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - - - - - 12 9 11

41、7 16 5 4 4 11 21 23 4p = a 輸出： wabbawabba索引條目11w12wab13bba14151617181920字典：85LZW解碼 (15)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - - - - - 12 9 11 7 16 5 4 4 11 21 23 4p = awab 輸出： wabbawabbawab索引條目11w12wab13bba14aw151617181920字典：86LZW解碼 (16)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - - - - - - 9 11 7

42、 16 5 4 4 11 21 23 4p = wab 輸出： wabbawabbawab索引條目11w12wab13bba14aw151617181920字典：87LZW解碼 (16)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - - - - - - 9 11 7 16 5 4 4 11 21 23 4p = wab 輸出： wabbawabbawab索引條目11w12wab13bba14aw151617181920字典：88LZW解碼 (17)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - - - - - - 9

43、11 7 16 5 4 4 11 21 23 4p = wab 輸出： wabbawabbawab索引條目11w12wab13bba14aw151617181920字典：89LZW解碼 (18)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - - - - - - 9 11 7 16 5 4 4 11 21 23 4p = wabba 輸出： wabbawabbawabba索引條目11w12wab13bba14aw15wabb1617181920字典：90LZW解碼 (19)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - -

44、- - - - - - 11 7 16 5 4 4 11 21 23 4p = ba 輸出： wabbawabbawabba索引條目11w12wab13bba14aw15wabb1617181920字典：91LZW解碼 (20)索引條目12a3b4o5w6wa7ab8bb9ba10a 輸入： - - - - - - - - - - - 11 7 16 5 4 4 11 21 23 4p = baw 輸出： wabbawabbawabbaw索引條目11w12wab13bba14aw15wabb16ba17181920字典：92LZW解碼 (21)索引條目12a3b4o5w6wa7ab8bb9ba

45、10a 輸入： - - - - - - - - - - - - 7 16 5 4 4 11 21 23 4p = w 輸出： wabbawabbawabbaw索引條目11w12wab13bba14aw15wabb16ba17181920 字典：最后得到與編碼器輸入一致的字符串93LZW特殊情況上述解碼器簡單、有效，但是，有時會出錯不過可以修復(fù)例：A = a, b輸入序列：abababab 開始字典索引條目1a2b94LZW特殊情況：編碼索引條目1a2b字典：輸出： 輸入：abababababab p =95LZW特殊情況：編碼(2)索引條目1a2b輸出：輸入： abababababab p =

46、 a字典：96LZW特殊情況：編碼(3)索引條目1a2b3ab輸出：1 (a)輸入： -bababababab p = ab字典：97LZW特殊情況：編碼(4)索引條目1a2b3ab4ba輸出：1 (a)2 (b)輸入： -ababababab p = ba字典：98LZW特殊情況：編碼 (5)索引條目1a2b3ab4ba輸出：1 (a)2 (b)輸入： -babababab p = ab字典：99LZW特殊情況：編碼 (6)索引條目1a2b3ab4ba5aba輸出：1 (a)2 (b)3 (ab)輸入： -abababab p = aba字典：100LZW特殊情況：編碼 (7)索引條目1a2

47、b3ab4ba5aba輸出：1 (a)2 (b)3 (ab)輸入： -bababab p = ab字典：101LZW特殊情況：編碼 (8)索引條目1a2b3ab4ba5aba輸出：1 (a)2 (b)3 (ab)輸入： -ababab p = aba字典：102LZW特殊情況：編碼 (9)索引條目1a2b3ab4ba5aba6abab輸出：1 (a)2 (b)3 (ab)5 (aba)輸入： -babab p = abab字典：103LZW特殊情況：解碼索引條目1a2b輸入： 1 2 3 5 p = 輸出：字典：104LZW特殊情況：解碼 (2)索引條目1a2b輸入： 1 2 3 5 p =

48、a 輸出： a字典：索引在字典中存在：輸出索引對應(yīng)的詞條前綴+當前詞條的第一個字符 字典的新詞條105LZW特殊情況：解碼 (3)索引條目1a2b3ab輸入： - 2 3 5 p = ab 輸出： ab字典：106LZW特殊情況：解碼 (4)索引條目1a2b3ab4ba輸入： - - 3 5 p = bab 輸出： abab字典：107LZW特殊情況：解碼 (5)索引條目1a2b3ab4ba輸入： - - - 5 p = ab 輸出： abab字典：108LZW特殊情況：解碼 (6)索引條目1a2b3ab4ba輸入： - - - 5 p = ab? 輸出： abab?字典：109LZW特殊情況

49、：解碼 (7)第5個詞條應(yīng)該以 ab開始 需將其加到 p 并繼續(xù)解碼索引條目1a2b3ab4ba5ab輸入： - - - 5 p = ab? 輸出： abab?字典：110LZW特殊情況：解碼 (8)索引條目1a2b3ab4ba5aba輸入： - - - 5 p = abab? 輸出： abab?字典：111LZW特殊情況：解碼 (9)索引條目1a2b3ab4ba5aba輸入： - - - 5 p = ababa 輸出： abab?字典：112LZW特殊情況：解碼 (10)索引條目1a2b3ab4ba5aba輸入： - - - - p = aba 輸出： abababa解碼器必須用一個額外的句

50、柄用于處理該情況索引不在字典中：前綴+前綴的的第一個字符 字典的新詞條輸出索引對應(yīng)的詞條字典：113LZW解碼算法LZW譯碼算法可用偽碼表示如下：Dictionaryj all n single-character, j =1，2，n j n + 1cW first code from CodestreamCharstream DictionarycWpW cWWhile (cW next Code word) != NULL) If cW is in Dictionary Charstream DictionarycW Prefix DictionarypW cW first Charact

51、er of DictionarycW Dictionaryj Prefix.cW j n + 1 pW cW else Prefix DictionarypW cW first Character of Prefix Charstream Prefix.cW Dictionaryj Prefix.cW pW cW j n + 1114字典結(jié)構(gòu)字典越大，能存儲更多的字符串，也就能匹配更長的字符串，但其代價是指針更長（標識需要的位數(shù)越多），搜索起來也更慢對字典而言，最好的數(shù)據(jù)結(jié)構(gòu)是樹：trie 115字典結(jié)構(gòu)在編碼時，編碼器逐個輸入字符并累積成字符串I（相當于偽代碼中的Prefix ）只要在字典中

52、能找到變量I的字符串，編碼器就不斷地輸入字符并將其串接到I中，直到某個輸入字符x與I連接后使搜索失?。ㄗ址甀x不在字典中），然后將Ix加到字典中。添加到字典中去的每個字符串僅有效增加了一個新字符x，即對每個不止一個字符的字符串，字典中有一個比它只少一個字符的“母串”。116字典結(jié)構(gòu)用樹trie表示時，樹是動態(tài)建立的，且樹中每個節(jié)點可能存在多個子節(jié)點。因此數(shù)據(jù)結(jié)構(gòu)應(yīng)該設(shè)計成一個節(jié)點可擁有任意個子節(jié)點，但無需為其預(yù)留空間：將樹駐留在一個節(jié)點數(shù)組中，每個數(shù)據(jù)結(jié)構(gòu)有兩個字段：一個字符和指向母節(jié)點的指針數(shù)據(jù)結(jié)構(gòu)中沒有指向子節(jié)點的指針，沿著樹從一個節(jié)點到其子節(jié)點的操作可用一個散列過程實現(xiàn)，該過程把指向節(jié)

53、點的指針和子節(jié)點的字符散列以生成一個新指針，因此需添加一個新字段：散列索引117字典結(jié)構(gòu)實用中，每個節(jié)點有3個字段：樹用數(shù)組dict表示，數(shù)組下標用pointer表示，所以dictpointer表示一個節(jié)點dictpointer.parentdictpointer.indexdictpointer.symbol母節(jié)點（parent）索引（index）字符（symbol）118字典結(jié)構(gòu)例：字符串“ababab” (a: 1 b: 2)Step 0：將從3個位置開始的所有字典位置標記為“未使用” Step 1：將第一個字符a輸入到變量I。 “a”的碼字為1，因此I = 1。因為是第一個字符，編碼器假定它已在字典中，故無需搜索Step 2：將第二個字符b輸入到J，所以J = 2。編碼器在字典中搜索字符串a(chǎn)b，執(zhí)行 pointer:=hash(I,J)，假設(shè)結(jié)果為5。因為位置5仍然是空的，字段dictpointer.index標記為“未使用”，因此串a(chǎn)b不在字典中，將其添加到字典中： dictpointer.parent:=I;dict