4ioi試題講解無損壓縮初探

1、清華大學(xué) 交叉信息研究院盧嘯塵RIOI試題選講、無損壓縮初探1. IOI15 day2 試題講解Horses - Description 有0到N，N+1個(gè)時(shí)刻。 在時(shí)刻0你有1匹馬。 時(shí)刻i和時(shí)刻i+1之間的時(shí)間段內(nèi)，經(jīng)過繁殖，你的每匹馬會(huì)變成Xi匹。 在時(shí)刻i+1你可以以Yi的單價(jià)賣出馬。 最大化賣馬所得。答案對(duì)109+7取模。 M個(gè)修改，每次修改一個(gè)Xi或一個(gè)Yi，在所有修改前和每次修改后各回答一次。 N500,000，M100,000，0Xi,Yi109。Horses - Analysis 觀察：至少存在一個(gè)最優(yōu)解，其中所有馬在同一個(gè)時(shí)刻中被賣出。 證明： 考慮某個(gè)解，其中所有馬至少分

2、成兩批被賣出。 假設(shè)最晚的賣出時(shí)刻是時(shí)刻q，數(shù)量為Q，次晚的賣出時(shí)刻是時(shí)刻p，數(shù)量為P。 由于時(shí)刻p賣馬后馬的數(shù)目是整數(shù)，所以Q是R=(piq)Xi的倍數(shù)。 比較Yp/R與Yq。 當(dāng)Yp/RYq，則(P+Q/R)YpPYp+QYq。 否則，YpRYq，則PYp+QYq109。Horses - Full Algorithm 對(duì)Y維護(hù)線段樹。 對(duì)X維護(hù)一個(gè)map，其中： key為某個(gè)X值不為1的下標(biāo)； value為在Y的線段樹中對(duì)這個(gè)下標(biāo)為左界（含）直至下一個(gè)下標(biāo)或末尾為右界（不含）的區(qū)間做RMQ的結(jié)果。 對(duì)于每個(gè)詢問，在map中暴力從后向前掃30步或直至X之積超過109。 對(duì)于每個(gè)對(duì)X的修改，做

3、至多兩個(gè)RMQ。 對(duì)于每個(gè)對(duì)Y的修改，做一個(gè)bound和一個(gè)RMQ。 復(fù)雜度O(NlogN)初始化-O(logVlogN)每詢問-O(logN)每操作Sorting - Description 有一個(gè)0,N)排列。現(xiàn)在要對(duì)其進(jìn)行排序。 你每次可以選擇一對(duì)元素（可以相同）并交換它們，當(dāng)你交換結(jié)束時(shí)若排列有序，則過程結(jié)束。 每次你行動(dòng)前，會(huì)有一個(gè)熊孩子選擇一對(duì)元素并交換它們。 熊孩子每次選擇的元素和當(dāng)前排列無關(guān)，只和你的目前操作次數(shù)（輪數(shù)）有關(guān)。 數(shù)據(jù)保證你進(jìn)行不超過M次操作就可以完成排序。你預(yù)先得到M對(duì)整數(shù)，代表熊孩子在每一輪將進(jìn)行的交換的元素對(duì)應(yīng)的下標(biāo)。 要求一個(gè)最短方案。 N200,000，

4、M=3N。Sorting - Analysis 觀察：如果有i步的解，那么就有i+1步的解。 證明： 對(duì)于已有的i步的解，在后面接上一個(gè)和熊孩子的第i個(gè)操作相同的操作就得到了一個(gè)i+1步的解，因?yàn)檫@樣一來第i輪的兩個(gè)操作互相抵消了。 這就是說：可以進(jìn)行二分答案。 注：當(dāng)提到k步的時(shí)候，指的是0到k-1這k個(gè)步，當(dāng)提到第k步的時(shí)候，指的是1-indexed下的第k+1步，第k輪同理，下同。Sorting, As a decision problem 派生判定問題：是否有i步的解？ 追蹤j步后（j1/2）為例。 這個(gè)二值函數(shù)對(duì)應(yīng)的序列出現(xiàn)概率的對(duì)數(shù)的分布由二點(diǎn)分布f(logq)=q,f(logp)

5、=p所描述。 在卷積的意義上求f的n次方，就得到了長度n的序列的出現(xiàn)概率的對(duì)數(shù)的分布，這樣得到的是一個(gè)經(jīng)過X軸方向拉伸和平移的二項(xiàng)分布B(n,p)，它的方差和n成正比。 而我們知道二項(xiàng)分布B(n,p)漸進(jìn)于正態(tài)分布，這個(gè)分布的方差也和n成正比。為了求平均概率對(duì)數(shù)值，我們對(duì)這個(gè)分布在X軸方向上做1/n倍拉伸，得到方差和n成反比的正態(tài)分布。 當(dāng)n+，方差趨向于0，因此概率將愈加集中在位置參數(shù)附近。使得這個(gè)分布的圖像看起來幾乎就是單點(diǎn)分布。理性認(rèn)識(shí)一下 上述感性認(rèn)識(shí)利用的是棣莫佛拉普拉斯定理，它指出二項(xiàng)分布以正態(tài)分布為極限。 而有一個(gè)更加強(qiáng)的，關(guān)于獨(dú)立同分布的林德伯格列維中心極限定理，它指出獨(dú)立同分

6、布也以正態(tài)分布為極限。棣拉定理實(shí)質(zhì)上就是林列定理的一個(gè)特例。 從林德伯格列維中心極限定理就可以輕松地推出AEP定理。典型和非典型 根據(jù)AEP定理，對(duì)于充分大的n，除了一系列出現(xiàn)概率無限小的非典型序列，幾乎所有長度為n的序列的出現(xiàn)概率都恰為 。 這就是這個(gè)名字的由來： 漸進(jìn)：對(duì)于充分大的n； 均分：幾乎所有事件以同一幾率發(fā)生。 這些事件的序列被稱為典型序列。它們構(gòu)成典型集。 信息論的主要考察對(duì)象就是典型集。典型集的行為在平均的意義上決定了整個(gè)樣本的行為因?yàn)榈湫图瘜?duì)應(yīng)的事件幾乎必然發(fā)生。 而典型序列滿足的性質(zhì)使得利用熵對(duì)其分析是有效的，因?yàn)樗鼈兯哂械男畔⒘壳『檬怯伸厮枋龅钠谕畔⒘俊?(2Xn

7、H漸進(jìn)均分性，在不甚極限的場(chǎng)合 在前面我們說明了，對(duì)于充分大的n有幾乎完全均分的性質(zhì)。 而對(duì)于不是那么大的n，也有關(guān)于典型集的定義。 具體的，定義正小量，則可以定義典型集 ，包含所有滿足以下性質(zhì)的序列： 其概率p滿足 。 根據(jù)概率p的下界，典型集 中至多包含 個(gè)元素。 根據(jù)AEP的描述，當(dāng)n充分大，典型序列總概率將達(dá)到 。)(nA)()(22XHnXHnp)(nA)(2XHn1AEP的一個(gè)和數(shù)據(jù)壓縮相關(guān)的推論 我們考慮一種編碼。這種編碼對(duì)于典型集元素和非典型集元素給予不同的編碼。 這里的典型集指的是剛才定義的，那個(gè)粗略的 。 首先用一個(gè)bit指出被編碼序列是否屬于典型集。 如果屬于典型集，由于

8、典型集元素?cái)?shù)目上界為 ，可以用 （向下取整）個(gè)bit描述是哪一個(gè)元素。 否則，直接根據(jù)序列編碼，設(shè)取值空間為，則需要使用的bit數(shù)目是 。 顯然我們得到一個(gè)單射。這是一種可逆的編碼，盡管編碼和解碼的過程都相當(dāng)復(fù)雜，但至少是理論上可能的。)(nA)(2XHn1)(xHn1|lognAEP的一個(gè)和數(shù)據(jù)壓縮相關(guān)的推論 我們考慮 和 之間的大小關(guān)系。由于是一個(gè)極小量，前者大于后者只能說明 ，這種情況是平凡的。因此認(rèn)為前者小于后者。 因此現(xiàn)在對(duì)以至少 概率出現(xiàn)的典型序列，可以使用不超過（實(shí)際上是下取整） 個(gè)bit來描述。以 概率出現(xiàn)的序列（包括所有非典型序列和一部分典型序列），可以使用不超過 個(gè)bit來

9、描述。 期望編碼長度不超過 。 將第一個(gè)系數(shù)放縮到1： 。 整理： ，選取參數(shù)可令后一項(xiàng)趨向0。 結(jié)論：理論上平均地，用 bit可以編碼長為n的序列。1)(xHn1|logn|log)(xH12)(xHn2|logn2|log)()1 (nxHn2|log)(nnxnH)2|log()(nxHn)(xnH小結(jié) 首先我們引入了熵的概念。 同時(shí)說明了為什么要以這種方式定義熵。 公理化定義方法。 然后我們講到漸進(jìn)均分性（AEP），AEP定理說明：用熵來分析獨(dú)立同分布序列是靠譜的，因?yàn)槟切┨乩ǚ堑湫托蛄校┏霈F(xiàn)的概率漸進(jìn)地趨向于0。 然后用AEP的一個(gè)推論說明了：在理論上，對(duì)于獨(dú)立同分布列，平均每元素

10、使用H(x)個(gè)bit的編碼是可能實(shí)現(xiàn)的。 有這樣一種說法：上世紀(jì)中葉Shannon指出了數(shù)據(jù)壓縮的極限，半個(gè)世紀(jì)以來一大批TCS和工程師做的就是在實(shí)踐中逼近這個(gè)極限。極限？ 為什么H(x)比特每元素是數(shù)據(jù)壓縮的極限？ 數(shù)據(jù)處理不等式。 如果Z只依賴于Y，和X無關(guān)，稱X，Y，Z依序構(gòu)成Markov鏈（類似于DP中的無后效性），記做XYZ。 在這種情況下：I(X;Y)I(X;Z)。 換言之，不能對(duì)Y做任何操作，使得得到的Z中蘊(yùn)含了關(guān)于X的更多信息。 “對(duì)數(shù)據(jù)進(jìn)行處理只可能把信息弄丟，不可能憑空創(chuàng)造信息” 證明：考慮互信息I(X;Y,Z)，其中的Y,Z可以根據(jù)鏈?zhǔn)椒▌t通過兩種方式展開。 I(X;Y,

11、Z)=I(X;Y)+I(X;Z|Y)=I(X;Z)+I(X;Y|Z)。 由于XYZ帶來的無后效性，I(X;Z|Y)=0。 所以I(X;Y)=I(X;Z)+I(X;Y|Z)，得I(X;Y)I(X;Z)。極限？ 我們知道壓縮和解壓縮的過程都是一種數(shù)據(jù)處理。 為了保持信息無損，壓縮后的數(shù)據(jù)Y需要蘊(yùn)含源數(shù)據(jù)X的所有信息。 對(duì)壓縮過程：I(X;Y)I(X;X)=H(X) 對(duì)解壓縮過程：I(X;Y)I(X;X)=H(X) 得I(X;Y)=H(X)。 如果源數(shù)據(jù)中蘊(yùn)含了H(X)的信息量，那么壓縮后自然也就需要至少H(X)個(gè)bit以蘊(yùn)含這么多信息。 所以無損數(shù)據(jù)壓縮的極限至少是H(X)bit。 又由AEP的推

12、論，確實(shí)存在H(X)bit的方案，因此得到以下結(jié)論： 對(duì)于i.i.d的隨機(jī)變量序列，無損數(shù)據(jù)壓縮的極限恰好是H(X)bit每元素。隨機(jī)過程、馬爾可夫鏈 定義隨機(jī)過程為一系列隨機(jī)變量的序列，其中諸元素之間可能具有任意的關(guān)聯(lián)。 稱一個(gè)隨機(jī)過程為馬爾可夫鏈，如果一個(gè)變量的概率分布只依賴于前一個(gè)變量的取值，與更前面的變量條件獨(dú)立。 進(jìn)一步地，如果前一個(gè)時(shí)刻的變量取值相同，每個(gè)時(shí)刻的概率分布都一致，則稱這個(gè)馬爾可夫鏈時(shí)間不變。 約定：若非特殊說明，提到馬爾可夫鏈時(shí)都保證時(shí)間不變性。 如果Xi是馬爾可夫鏈，則稱Xn為n時(shí)刻的狀態(tài)?？吹竭@個(gè)名字，你們可以畫個(gè)轉(zhuǎn)移圖或者轉(zhuǎn)移矩陣感受一下。各態(tài)歷經(jīng)性、平穩(wěn)分布、

13、平穩(wěn)過程 對(duì)于一個(gè)馬爾可夫鏈，如果從任意狀態(tài)都能以一個(gè)正的概率轉(zhuǎn)移到任意狀態(tài)，稱其具有不可約性。 對(duì)于一個(gè)馬爾可夫鏈，如果對(duì)于每一個(gè)點(diǎn)，要么包含它的所有回路的長度的最大公約數(shù)為1，要么不存在包含它的回路，稱其具有非周期性。 對(duì)于一個(gè)馬爾可夫鏈，如果它具有不可約性和非周期性，稱其具有各態(tài)歷經(jīng)性。 如果一個(gè)馬爾可夫鏈?zhǔn)歉鲬B(tài)歷經(jīng)的，那么它存在平穩(wěn)分布。平穩(wěn)分布是一個(gè)向量，在乘上轉(zhuǎn)移矩陣之后得到它本身。 如果一個(gè)馬爾可夫鏈的初概率分布是平穩(wěn)分布，稱其具有平穩(wěn)性。熵率、AEP的擴(kuò)展 定義熵率為以下極限，如果存在： 熵率描述了n充分大情況下的每字符熵，扮演了獨(dú)立同分布的AEP定理中的H(X)的角色。 有S

14、hannon-McMillan-Breiman定理（“廣義AEP”）： 對(duì)于有限平穩(wěn)馬爾可夫鏈， 。 證明略去，參見原書16.8節(jié)。 根據(jù)廣義AEP，可以把AEP那個(gè)時(shí)候講的話重新講一遍： 對(duì)于有限平穩(wěn)馬爾可夫鏈，無損數(shù)據(jù)壓縮的極限恰好是H()bit每元素 此外，由于各態(tài)歷經(jīng)馬爾可夫鏈最終都會(huì)趨向平穩(wěn)分布，而上面的描述又是漸進(jìn)的，上面這句話中的平穩(wěn)性也就可以削弱成各態(tài)歷經(jīng)性。),(1lim)(21nnXXXHnH依概率)(),(log121HXXXpnn擴(kuò)展到高階 根據(jù)廣義AEP，我們說明了由AEP得到的結(jié)論可以直接套用在有限各態(tài)歷經(jīng)馬爾可夫鏈上。 實(shí)際上，我們還可以將其擴(kuò)展到一個(gè)狀態(tài)和前k個(gè)

15、狀態(tài)相關(guān)的情形?？紤]n個(gè)狀態(tài)、每個(gè)狀態(tài)和前k個(gè)相關(guān)的，不可約和非周期的隨機(jī)過程，我們發(fā)現(xiàn)它等價(jià)于一個(gè)有nk個(gè)狀態(tài)的各態(tài)歷經(jīng)馬爾可夫鏈。 于是我們離“任意隨機(jī)過程”的距離又近了一步。小結(jié) 在引入了數(shù)據(jù)處理不等式后，我們說明了無損數(shù)據(jù)壓縮的輸出應(yīng)當(dāng)具有完整的源數(shù)據(jù)的信息。 通過i.i.d序列的AEP定理，說明了i.i.d序列的無損壓縮極限恰為H(X)bit每元素。 然后將i.i.d序列這種特殊的隨機(jī)過程推廣到馬爾可夫鏈，在其上定義熵率H()的概念，通過平穩(wěn)過程的廣義AEP定理，將i.i.d的壓縮極限概念推廣到了一切有限各態(tài)歷經(jīng)馬爾可夫過程。 至此基本理論結(jié)束，正如1848年的K. Marx一般，1

16、948年的C. Shannon給我們指出了進(jìn)行無損數(shù)據(jù)壓縮時(shí)的最終發(fā)展目標(biāo)。接下來的就是實(shí)際操作部分了。由于我比較鶸接下來的內(nèi)容也會(huì)很鶸。編碼 一個(gè)信源編碼C是從取值空間到字母表D的Kleene閉包D*上的映射。 用C(x)代表x對(duì)應(yīng)的碼字，用l(x)代表C(x)的長度。 對(duì)于串SC*，定義C(S)為S中各元素的碼字的順次連接。 可以定義一個(gè)信源編碼C的期望長度L(C)如下： 不失一般性，假定d元字母表D=0,1,.,d-1xxlxpCL)()()(編碼的性質(zhì) 若C滿足，對(duì)所有x,yC，x!=y，有C(x)!=C(y)，則C是非奇異的。否則稱其為奇異的。 若C滿足，對(duì)所有X,YC*，X!=Y，

17、有C(X)!=C(Y)，則C是唯一可譯的。唯一可譯性蘊(yùn)含非奇異性。 若C滿足，對(duì)所有x,yC，x!=y，C(x)和C(y)互不為前綴，則C是即時(shí)的。即時(shí)性蘊(yùn)含唯一可譯性。 唯一可譯性不蘊(yùn)含即時(shí)性。如C=01,110是唯一可譯的，但不是即時(shí)的。 非奇異性不蘊(yùn)含唯一可譯性。如C=00,100是非奇異的，但不是唯一可譯的。Kraft不等式 對(duì)于d元字母表上的即時(shí)碼C，有以下不等式成立： 我大膽假設(shè)來參加這個(gè)冬令營的大爺都會(huì)寫trie，所以都會(huì)證明這個(gè)不等式。 逆命題：如果有一組l滿足上述不等式，一定可以構(gòu)造出對(duì)應(yīng)的即時(shí)碼C。 我依然假設(shè)你們都會(huì)證，或者說都會(huì)構(gòu)造。1)(xxld最優(yōu)碼長的下界 根據(jù)K

18、raft不等式的逆命題，我們只需要找出一組符合Kraft不等式的碼長序列就可以構(gòu)造一個(gè)相應(yīng)編碼。 這就是說，求最優(yōu)碼就是在受到Kraft約束的情況下最小化L(C)。 令 。 我們自然希望 都相等，不然就可以找到兩個(gè)使之不同的l(x)進(jìn)行改進(jìn)。 這個(gè)值是 ，去掉常數(shù)就是 。 于是得到最優(yōu)解： 。這個(gè)解剛好令G(x)等于1。)()(, )()()()(xldxGxlxpCLxFGxlxlF)()(ddxpxlln)()()()(xldxp)(log)(xpxld最優(yōu)碼長的下界 于是我們得到：最優(yōu)碼符合 。 這時(shí) 。 然而考慮到l必須是整數(shù)，有時(shí)這個(gè)極限并不能取到。 于是我們只能說： 。)(log)

19、(xpxld)()(1log)(XHxpECLdd)()(minXHCLd最優(yōu)碼長的上界 構(gòu)造碼長序列為理論最優(yōu)碼長的上取整，顯然符合Kraft不等式。 這時(shí)： 。 這個(gè)構(gòu)造使得我們可以說： 。 但這并不意味著最優(yōu)碼長就是熵的上取整之類的，因?yàn)長(C)本身就不一定是整數(shù)，并且在很多時(shí)候并不是整數(shù)。1)( 1)(1log)(1(log)(XHxpExpCeilECLddd1)()(min)(XHCLXHddKraft不等式，擴(kuò)展到唯一可譯碼類 由于唯一可譯碼的Kleene閉包是非奇異的，因此它的子集自然也是非奇異的，我們?nèi)〈笳麛?shù)K，為唯一可譯碼C構(gòu)造K次串聯(lián)的CK。 將C的Kraft不等式左側(cè)做

20、K次方就可以得到CK的Kraft不等式的左側(cè)。 由于CK的非奇異性，如果對(duì)CK畫出trie，這個(gè)trie具有0到KMaxl這些層，其中0層沒有碼字。下面的KMaxl層中，每層至多為CK的Kraft不等式左側(cè)提供1的值。于是C的Kraft不等式左側(cè)至多為KMaxl的K次方根。 當(dāng)K趨向無窮大，這個(gè)值就不斷地趨近于1。將這族不等式合在一起就得到1這一個(gè)結(jié)果，于是唯一可譯碼類服從Kraft不等式。 這同時(shí)說明，之前的上下界同樣可以應(yīng)用在唯一可譯碼類上。 這說明唯一可譯碼類對(duì)于優(yōu)化壓縮效率并沒有什么卯月。Shannon-Fano-Elias編碼 Shannon-Fano-Elias編碼是一個(gè)次優(yōu)即時(shí)編

21、碼。利用Trie的區(qū)間模型可以很容易地理解其構(gòu)造。 將所有的p當(dāng)成相應(yīng)長度的區(qū)間排成一個(gè)序列，這個(gè)序列的總長度是1，每個(gè)字符管轄區(qū)間中的一段。取 ，則顯然有 。那么在管轄區(qū)間內(nèi)必然完整包含了某一個(gè)l(x)層節(jié)點(diǎn)所對(duì)應(yīng)的區(qū)間。將這個(gè)元素編碼成這個(gè)區(qū)間對(duì)應(yīng)的節(jié)點(diǎn)的對(duì)應(yīng)的串。 易得 ，這證明Shannon-Fano-Elias編碼必定不可能是最優(yōu)碼。 一種通用信源編碼，算術(shù)編碼，直接繼承了Shannon-Fano-Elias編碼的精神，并具有相同的冗余，它具有可增量的優(yōu)點(diǎn)。1)(log)(xpxl)(212)(xpxl2)()(1)(XHCLXHHuffman編碼最優(yōu)的即時(shí)碼 我大膽假設(shè)你們都考過N

22、OIp初賽，都知道Huffman編碼是啥。 引理：至少有一個(gè)最優(yōu)的即時(shí)碼滿足以下條件 小概率元素的碼長至少為大概率元素的碼長。 如若不然，交換可使L(C)減小。 最長的兩個(gè)碼字具有相同的長度。 如若不然，把最長碼字減短到次短可使L(C)減小。 請(qǐng)注意即時(shí)性。 最長的兩個(gè)碼字僅在最后一位上有所差別，它們對(duì)應(yīng)著兩個(gè)最小可能發(fā)生的字符。 如果對(duì)于某個(gè)最長碼字，沒有相應(yīng)的末位不同的碼字，那么可以把最后一位去掉，這樣L(C)就減小了。Huffman編碼最優(yōu)的即時(shí)碼 如果一個(gè)即時(shí)碼是最優(yōu)的，那么由引理(3)，可以找到兩個(gè)最小元素，它們的編碼只差最后一位?？紤]將它們進(jìn)行合并，那么由于原即時(shí)碼的最優(yōu)性，新得到

23、的即時(shí)碼，在它的概率分布下也應(yīng)該是最優(yōu)的。 相應(yīng)的，當(dāng)我們得到合并后的概率的一個(gè)最優(yōu)碼C，也就可以斷言合并前的相應(yīng)編碼C的最優(yōu)性。如果C不是最優(yōu)的，則最優(yōu)的方案D的合并后的D將優(yōu)于C無論是C和D中，最小的兩個(gè)概率，從其數(shù)值上來說是一致的，因此L(C)-L(C)=L(D)-L(D)。 于是我們證明了Huffman編碼的最優(yōu)性。 同時(shí)根據(jù)之前得到的最優(yōu)碼長的界，可得到Huffman編碼的L(C)的界。針對(duì)特定文段的優(yōu)化 實(shí)際上，Huffman編碼的最優(yōu)是建立在被壓縮文段是i.i.d序列這一性質(zhì)上的。 在實(shí)踐中，許多需要壓縮的文段是自然語言片段。 這些片段顯然是不服從i.i.d的，舉個(gè)例子，根據(jù)直覺

24、就知道，在英文片段中，一個(gè)小寫字母后面緊跟一個(gè)大寫字母的概率要遠(yuǎn)小于這個(gè)大寫字母直接出現(xiàn)的概率。 我們可以使用馬爾可夫鏈來逼近這些文本。k階逼近 我們定義一種新語言，這種語言中每個(gè)狀態(tài)的概率分布只和前k-1個(gè)相關(guān)（k=0時(shí)是i.i.d隨機(jī)序列），并且其中每個(gè)連續(xù)k元字符組的出現(xiàn)頻率與母語言中k元字符組的出現(xiàn)頻率一致。 這時(shí)，稱這種語言是母語言的k階逼近。 Huffman是母語言的1階逼近的最優(yōu)即時(shí)碼方案。 我做了一個(gè)關(guān)于英文的2階逼近的實(shí)驗(yàn)，并用它來測(cè)算英文的2階逼近的熵。 大概就是建立|個(gè)Huffman樹之類的，之后你們都懂了。數(shù)據(jù)分析 根據(jù)兩個(gè)原文長約3Mb的文本的平均數(shù)據(jù) 一階逼近：壓縮

25、率72.5%，推算熵率約4.35。 二階逼近：壓縮率58.3%，推算熵率約3.50。 可以看到2階逼近比樸素huffman有所改進(jìn)，但改進(jìn)不大。 根據(jù)書中數(shù)據(jù)，4階逼近的熵率在2.8對(duì)應(yīng)約47%的壓縮率，還不算字典。相比起來，RAR大法在實(shí)驗(yàn)文本中做到了38%的壓縮率。 這個(gè)數(shù)據(jù)說明，簡(jiǎn)單的字符層面的逼近的壓縮率并不好，況且高階逼近會(huì)帶來巨大的字典，這使得高階逼近缺乏實(shí)用性。單詞模型 據(jù)說英文的熵率在1.34左右。 剩下一半到哪去了？詞與詞之間的聯(lián)系。 定義一種自然語言的k階單詞模型，把k階逼近里的“字符組”換成“單詞組”。 你們感受一下單詞模型的字典大小動(dòng)態(tài)字典方法 從上面的逼近實(shí)驗(yàn)和單詞模

26、型中我們可以看到靜態(tài)字典方法的一個(gè)問題：為了提高壓縮率，需要更復(fù)雜的字典，而更大的字典反過來又影響了壓縮率。 考慮另一個(gè)選擇：動(dòng)態(tài)字典。在動(dòng)態(tài)字典方法中，并不顯式地描述一個(gè)字典（這種描述可能包括寫在程序中或?qū)懺趬嚎s后的數(shù)據(jù)中），而是伴隨壓縮和解壓縮過程構(gòu)造。 一方面，動(dòng)態(tài)字典方法為每個(gè)壓縮文本確定了單獨(dú)的字典； 另一方面，又不需要顯式地描述這個(gè)字典。 現(xiàn)代的無損壓縮算法有很大一部分源自動(dòng)態(tài)字典方法Lempel-Ziv算法。包括LZ77和LZ78。LZ77算法 LZ77算法又被稱為“帶滑動(dòng)窗口的Lempel-Ziv算法”。 它具有一個(gè)“滑動(dòng)窗口”，包括當(dāng)前指針位置之前的W（W是參數(shù)）個(gè)位置，所有

27、窗口中的位置的后綴的前綴構(gòu)成了字典甚至還包括這些后綴的延伸。 舉個(gè)例子：原文本是2332332331。窗口大小是3 那么得到的輸出可能是這樣的： (false,2)(false,3)(true,1,1)(true,3,6)(false,1)。 三個(gè)false括號(hào)分別描述了三個(gè)未匹配的字符。第三個(gè)括號(hào)聲明后綴2和后綴2-1之間有1的公共前綴（3）。第四個(gè)括號(hào)聲明后綴3和后綴3-3之間有6的公共前綴（233233）。如何描述整數(shù) 在操作中自然不可能打一堆括號(hào)逗號(hào)。在實(shí)踐中，我們把false和true表示成0和1，把括號(hào)逗號(hào)去掉。 如果能夠找到一種正整數(shù)的唯一可譯碼，那么解壓縮程序就可以每輪讀入一個(gè)

28、整數(shù)，然后讀入相同數(shù)目的整數(shù)，構(gòu)成一個(gè)單元。 這可以遞歸地做到。將每個(gè)整數(shù)表示成它的二進(jìn)制長度-1的表示加上這個(gè)整數(shù)的二進(jìn)制表示，其中第一部分遞歸。如： 0-0，1-01，2-0110，3-0111，4-0110100，32- 。 根據(jù)下一個(gè)bit是否是0判斷這個(gè)整數(shù)的描述是否結(jié)束。描述整數(shù)的復(fù)雜度 為了說明LZ77算法的復(fù)雜度，我們需要以下結(jié)論： 存在一種編碼令對(duì)整數(shù)n，碼長在logn+2loglogn+O(1)以內(nèi)。 為此我們找到第一個(gè)n令2logloglogn+1 loglogn，將常數(shù)項(xiàng)取作這之前的n對(duì)應(yīng)的常數(shù)項(xiàng)的最大值，并對(duì)后面部分做數(shù)學(xué)歸納即可。 于是我們可以說明存在一個(gè)c令這種編

29、碼的長度滿足l(n)logn+2loglogn+c。Kac引理 這個(gè)名字大概和某個(gè)OIer沒有關(guān)系。 由幾何分布的期望值，當(dāng)序列服從i.i.d，從某個(gè)位置向負(fù)方向觀察，找到某個(gè)字符的期望長度等于這個(gè)字符出現(xiàn)的概率的倒數(shù)。 Kac引理說明，即使不服從i.i.d，只滿足平穩(wěn)性，這一性質(zhì)依然成立。 下面給出其證明： 預(yù)先給定一個(gè)字符x，我們定義Q(l)為從某個(gè)位置向負(fù)方向看，看到的第一個(gè)x是l距離上的。 由于平穩(wěn)性這個(gè)Q(l)和具體的下標(biāo)位置無關(guān)。Kac引理證明 考慮任何一個(gè)位置，比如0。 設(shè)j為從0向負(fù)方向看看到的第一個(gè)x的下標(biāo)的相反數(shù)； 設(shè)k為從-1向正方向看看到的第一個(gè)x的下標(biāo)的相反數(shù)。 取到

30、特定j和k可以拆分成以下兩個(gè)事件 k位置為x；并且 -j是從k向負(fù)方向看到的第一個(gè)x。 這個(gè)概率是 。由于平穩(wěn)性，第一個(gè)系數(shù)對(duì)一切k相等，因此可以將其簡(jiǎn)單記成 。)()(kjQxXpk)()(kjQxpKac引理證明 將j取遍正整數(shù)，將k取遍非負(fù)整數(shù)。由于各態(tài)歷經(jīng)性，這樣的取值幾乎可以覆蓋一切情況。 這就是說，刻意構(gòu)造的使得j或k無定義的情況的概率是0。 于是： 。改為枚舉j和k的和i。 得： 右邊正是所求的長度期望。于是得證。 這個(gè)定理可以擴(kuò)展到一個(gè)子序列的情形。10)()(1jkkjQxp1111)()(1)()(1)()(1iiiijiiQxpiiQxpiQxpLZ77漸進(jìn)最優(yōu)性證明 我們考慮一個(gè)非實(shí)用的版本參數(shù)W無窮大。 在序列足夠長的情況下，最后我們總是能為當(dāng)前匹配找到一個(gè)足夠長的相匹配的序列。 在n足夠大的情況下，考察 丟掉括號(hào)里顯然低于n的項(xiàng)，得到 。 由