【正文】 w 2 a 3 b 4 ba 5 6 wa 7 bb 8 a 9 wab 10 ba 28 LZ78舉例 (14) 字典： 輸入： oo?woo?woo 輸出： 0, C(w) 0, C(a) 0, C(b) 3, C(a) 0, C( ) 1, C(a) 3, C(b) 2, C( ) 6, C(b) 4, C( ) 9, C(b) 8, C(w) 0, C(o) 11 wabb 12 a w 13 o 索引 條目 1 w 2 a 3 b 4 ba 5 6 wa 7 bb 8 a 9 wab 10 ba 29 LZ78舉例 (15) 字典： 輸入： o?woo?woo 輸出： 0, C(w) 0, C(a) 0, C(b) 3, C(a) 0, C( ) 1, C(a) 3, C(b) 2, C( ) 6, C(b) 4, C( ) 9, C(b) 8, C(w) 0, C(o) 13, C( ) 11 wabb 12 a w 13 o 14 o 索引 條目 1 w 2 a 3 b 4 ba 5 6 wa 7 bb 8 a 9 wab 10 ba 30 LZ78舉例 (16) 字典： 輸入： woo?woo 輸出： 0, C(w) 0, C(a) 0, C(b) 3, C(a) 0, C( ) 1, C(a) 3, C(b) 2, C( ) 6, C(b) 4, C( ) 9, C(b) 8, C(w) 0, C(o) 13, C( ) 1, C(o) 11 wabb 12 a w 13 o 14 o 15 wo 索引 條目 1 w 2 a 3 b 4 ba 5 6 wa 7 bb 8 a 9 wab 10 ba 31 LZ78舉例 (17) 字典： 輸入： o?woo 輸出： 0, C(w) 0, C(a) 0, C(b) 3, C(a) 0, C( ) 1, C(a) 3, C(b) 2, C( ) 6, C(b) 4, C( ) 9, C(b) 8, C(w) 0, C(o) 13, C( ) 1, C(o) 14, C(w) 11 wabb 12 a w 13 o 14 o 15 wo 16 o w 索引 條目 1 w 2 a 3 b 4 ba 5 6 wa 7 bb 8 a 9 wab 10 ba 32 LZ78舉例 (18) 字典： 輸入： oo 輸出： 0, C(w) 0, C(a) 0, C(b) 3, C(a) 0, C( ) 1, C(a) 3, C(b) 2, C( ) 6, C(b) 4, C( ) 9, C(b) 8, C(w) 0, C(o) 13, C( ) 1, C(o) 14, C(w) 13, C(o) 11 wabb 12 a w 13 o 14 o 15 wo 16 o w 17 oo 索引 條目 1 w 2 a 3 b 4 ba 5 6 wa 7 bb 8 a 9 wab 10 ba 33 LZ78 ? 觀察：如果繼續(xù)編碼，字典將繼續(xù)增長 ? 實用的選擇 ? 停止增長字典 ?相當(dāng)于從此成為一個靜態(tài)字典策略 ? 刪除一些較早用過的項 ? 如基于使用統(tǒng)計（但還沒有好的算法決定哪些項該刪） ? 將字典全部刪除，從空字典開始重建字典 ? 如果沒有信源的特定知識，任何方法可能都不會工作得很好！ 34 LZ78的變種： LZW ? Terry Welch (1984) ? 基本思想： ? 只對 i編碼，而不是編碼 i, c ? 算法： ? //初始化字典為包含所有字母 Seed dictionary with all alphabet letters, p = null while( !done) a = get_next_symbol if( p a) is in dictionary //在字典中，繼續(xù)用更長的字符串匹配 p = p a else send out index of p //不在字典中，輸出已匹配部分，從 a 重新開始 is added to dictionary p = a endwhile 35 LZW編碼 索引 條目 1 2 a 3 b 4 o 5 w 6 7 8 9 10 字典： 輸出： 輸入： wabba?wabba?wabba?wabba?woo?woo?woo p = 36 LZW編碼 (2) 索引 條目 1 2 a 3 b 4 o 5 w 6 7 8 9 10 字典： 輸出： 輸入： wabba?wabba?wabba?wabba?woo?woo?woo p = w 37 LZW編碼 (3) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 8 9 10 字典： 輸出： 5 (‘w’) 輸入： abba?wabba?wabba?wabba?woo?woo?woo p = wa 38 LZW編碼 (4) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 ab 8 9 10 字典： 輸出： 5 (‘w’) 2 (‘a(chǎn)’) 輸入： bba?wabba?wabba?wabba?woo?woo?woo p = ab 39 LZW編碼 (5) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 ab 8 bb 9 10 字典： 輸出： 5 (‘w’) 2 (‘a(chǎn)’) 3 (‘b’) 輸入： ba?wabba?wabba?wabba?woo?woo?woo p = bb 40 LZW編碼 (6) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 ab 8 bb 9 ba 10 字典： 輸出： 5 (‘w’) 2 (‘a(chǎn)’) 3 (‘b’) 3 (‘b’) 輸入： a?wabba?wabba?wabba?woo?woo?woo p = ba 41 LZW編碼 (7) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 ab 8 bb 9 ba 10 a 字典： 輸出： 5 (‘w’) 2 (‘a(chǎn)’) 3 (‘b’) 3 (‘b’) 2 (‘a(chǎn)’) 輸入： ?wabba?wabba?wabba?woo?woo?woo p = a 42 LZW編碼 (8) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 ab 8 bb 9 ba 10 a 字典： 輸出： 5 (‘w’) 2 (‘a(chǎn)’) 3 (‘b’) 3 (‘b’) 2 (‘a(chǎn)’) 1 (‘ ’) 輸入： wabba?wabba?wabba?woo?woo?woo 索引 條目 11 w 12 13 14 15 16 17 18 19 20 p = w 43 LZW編碼 (9) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 ab 8 bb 9 ba 10 a 字典： 輸出： 5 (‘w’) 2 (‘a(chǎn)’) 3 (‘b’) 3 (‘b’) 2 (‘a(chǎn)’) 1 (‘ ’) 輸入： abba?wabba?wabba?woo?woo?woo 索引 條目 11 w 12 13 14 15 16 17 18 19 20 p = wa 44 LZW編碼 (10) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 ab 8 bb 9 ba 10 a 字典： 輸出： 5 (‘w’) 2 (‘a(chǎn)’) 3 (‘b’) 3 (‘b’) 2 (‘a(chǎn)’) 1 (‘ ’) 6 (‘wa’) 輸入： bba?wabba?wabba?woo?woo?woo 索引 條目 11 w 12 wab 13 14 15 16 17 18 19 20 p = wab 45 LZW編碼 (11) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 ab 8 bb 9 ba 10 a 字典： 輸出： 5 (‘w’) 2 (‘a(chǎn)’) 3 (‘b’) 3 (‘b’) 2 (‘a(chǎn)’) 1 (‘ ’) 6 (‘wa’) 輸入： ba?wabba?wabba?woo?woo?woo 索引 條目 11 w 12 wab 13 14 15 16 17 18 19 20 p = bb 46 LZW編碼 (12) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 ab 8 bb 9 ba 10 a 字典： 輸出： 5 (‘w’) 2 (‘a(chǎn)’) 3 (‘b’) 3 (‘b’) 2 (‘a(chǎn)’) 1 (‘ ’) 6 (‘wa’) 8 (‘bb’) 輸入： a?wabba?wabba?woo?woo?woo 索引 條目 11 w 12 wab 13 bba 14 15 16 17 18 19 20 p = bba 47 LZW編碼 (13) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 ab 8 bb 9 ba 10 a 字典： 輸出： 5 (‘w’) 2 (‘a(chǎn)’) 3 (‘b’) 3 (‘b’) 2 (‘a(chǎn)’) 1 (‘ ’) 6 (‘wa’) 8 (‘bb’) 輸入： ?wabba?wabba?woo?woo?woo 索引 條目 11 w 12 wab 13 bba 14 15 16 17 18 19 20 p = a 48 LZW編碼 (14) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 ab 8 bb 9 ba 10 a 字典： 輸出： 5 (‘w’) 2 (‘a(chǎn)’) 3 (‘b’) 3 (‘b’) 2 (‘a(chǎn)’) 1 (‘ ’) 6 (‘wa’) 8 (‘bb’) 10 (‘a(chǎn) ’) 輸入： wabba?wabba?woo?woo?woo 索引 條目 11 w 12 wab 13 bba 14 a w 15 16 17 18 19 20 p = a w 49 LZW編碼 (15) 索引 條目 1 2 a 3 b 4 o 5 w 6 wa 7 ab 8 bb 9 ba 10 a 字典： 輸出： 5 (‘w’