【文章內(nèi)容簡介】 that K(xx) ? K(x) + c, for every string x. 雙倍串的的復(fù)雜度 不比原串的復(fù)雜度 大很多，直觀地，增加一句話， ‖輸出重復(fù)一次 ‖ 但把上述觀察敘述清楚，應(yīng)該如下敘述： Proof: Take the TM M that given input Nx: 1) Calculate the output s of N on x 2) Output ss Let d(x) be the minimum description of x, then Md(x) will give a description of xx. Hence, K(xx) ? |M| + |d(x)| = K(x) + c. Univ. 可計算理論 2020/11/17 35/77 Concatenation 一個意料之外的例子 You would expect that for all strings x and y: K(xy) ? K(x) + K(y) + c, for some c ？ However, this is not true. 要多花一些代價 The problem lies –again– in the separation between d(x) and d(y). Instead, we have a constant c such that: K(xy) ? K(x) + K(y) + 2log(K(x)) + c, for all strings x and y. X的編碼長度的 2倍 為 l 描述 X,Y的分割點付出的代價，下頁 Univ. 可計算理論 2020/11/17 36/77 Log Cost of Concatenation ep216 cp147 Theorem (log): There is a c such that K(xy) ? K(x) + K(y) + 2log(K(x)) + c, for all x,y. 自學(xué)（不難，意義較?。? Proof: Let m be the logarithm of |d(x)|, then the string ―1m0 |d(x)| d(x)‖ gives a selfdelimitin－ description of x. (We need 2m bits to indicate the length of d(x).) Hence the input ―1m0 |d(x)| d(x) d(y)‖ gives an unambiguous description of xy. Univ. 可計算理論 2020/11/17 37/77 Log Cost of Concatenation ep216 cp147 Theorem (log): There is a c such that K(xy) ? K(x) + K(y) + 2log(K(x)) + c, for all x,y. 自學(xué)（不難，意義較?。? Proof: Let m be the logarithm of |d(x)|, then the string ―1m0 |d(x)| d(x)‖ gives a selfdelimitin－ description of x. (We need 2m bits to indicate the length of d(x).) Hence the input ―1m0 |d(x)| d(x) d(y)‖ gives an unambiguous description of xy. Univ. 可計算理論 2020/11/17 38/77 不可壓縮串 ? X是串， c0 , K(x)|x|c, 稱 x是 C可壓縮（長度壓了 C） ? 反之 不可 c壓縮 , c=1時 稱為不可壓縮的， 最小描述比原串長度小 C 反過來， 對不可壓縮的串 x。描述就不能太小。 一個圖靈機 M ,M 長度 2020 , 一個串 w 復(fù)雜度2020,且不可壓縮， M 一定不能描述 W. 我們稱為 小馬 拉 大車 這一直觀感覺 在后面有用 許多軟件。增加能力，增加 EXE的字節(jié)數(shù)（ Win) 升級軟件要求升級硬盤。符合這一深層次的信息壓縮定理。 1k長的程序不能描述 windows Univ. 可計算理論 2020/11/17 39/77 不可壓縮串 ? X是串， c0 , K(x)|x|c, 稱 x是 C可壓縮（長度壓了 C） ? 反之 不可 c壓縮 , c=1時 稱為不可壓縮的， 最小描述比原串長度小 C 反過來 ， 對不可壓縮的串 x。描述就不能太小。 一個圖靈機 M ,M 長度 2020 , 一個串 w 復(fù)雜度2020,且不可壓縮， M 一定不能描述 W. 我們稱為 小馬 拉 大車 這一直觀感覺 在后面有用 許多軟件。增加能力后， EXE的字節(jié)數(shù)增加了。（ Win) 升級軟件要求升級硬盤。符合這一深層次的信息壓縮定理。 1k長的程序不能描述 windows Univ. 可計算理論 2020/11/17 40/77 不可壓縮串 ? X是串， c0 , K(x)|x|c, 稱 x是 C可壓縮（長度壓了 C） ? 反之 不可壓縮 c, c=1時 稱為不可壓縮的， 最小描述比原串長度小 C 反過來 ， 對不可壓縮的串 x。描述就不能太小。 一個圖靈機 M ,M 長度 2020 , 一個串 w 復(fù)雜度2020,且不可壓縮， M 一定不能描述 W. 適當(dāng)規(guī)定 大小 概念。則 小馬 不能拉 大車 這一直觀感覺 在后面有用 許多軟件。增加能力后， EXE的字節(jié)數(shù)增加了。（ Win) 升級軟件要求升級硬盤 。 符合這一深層次的信息壓縮定理。 1k長的程序不能描述 windows Univ. 可計算理論 2020/11/17 41/77 Inpressibility 不可壓縮的串 ep217,cp149 Theorem : For every n there exists at least one inpressible string x?{0,1}n with K(x)?n. 存在任意長的不可壓縮串 Proof (by pigeonhole argument): 用 鴿巢原理 – There are 2n different strings x in {0,1}n. – There is one description of length 0, two descriptions of length 1,…, and 2 n–1 descriptions of length n–1. In total: 2n–1 descriptions of length smaller than , there has to be an x?{0,1}n that has a minimal description of at least n bits. 長度從 1(n1)的串比長度為 n的串的個數(shù)少 Univ. 可計算理論 2020/11/17 42/77 Inpressibility 不可壓縮的串 ep217,cp149 Theorem : For every n there exists at least one inpressible string x?{0,1}n with K(x)?n. 存在任意長的不可壓縮串 Proof (by pigeonhole argument): 用 鴿巢原理 – There are 2n different strings x in {0,1}n. 1+2+4+…,+ 2 n–1= 2n–1 2n 長度從 1(n1)的串的總數(shù) ， 長度為 n的串的總數(shù) 目標(biāo) 待壓 Univ. 可計算理論 2020/11/17 43/77 Indexing Trick Compression idea: If S is a small set that is easy to describe, then we can describe an x?S by: description of enumeration of S index of x in S Let S = {s1,…,s N}. We can indicate every x?S by the 1?j?N such that sj=x. 用編號 j代替字符串 sj ， 就短多了。 設(shè) N=2m,N個符號只要編碼成長度為 log(N) =m的串 Hence K(x) ? cS + log(N) = cS + log(|S|), with constant cS depending on the description of S. Univ. 可計算理論 2020/11/17 44/77 Indexing Trick （ 監(jiān)獄中犯人編號，不呼真名） Compression idea: If S is a small set that is easy to describe, then we can describe an x?S by: description of enumeration of S index of x in S Let S = {s1,…,s N}. We can indicate every x?S by the 1?j?N such that sj=x. 用編號 j代替字符串 sj ， 就短多了。 例： ASCII用碼代替 字符位圖 設(shè) N=2m,N個符號只要編碼成長度為 log(N) =m的串 1024個串用 10位編碼就可區(qū)別了， Hence K(x) ? cS + log(N) = cS + log(|S|), with constant cS depending on the description of S. Univ. 可計算理論 2020/11/17 45/77 Frequency Compression 頻率壓縮 Let x ?{0,1}n with 75% zeros and 25% ones. 高頻率者用短碼，低頻率用長碼，使得總體碼長較小 Consider the set S?{0,1}n of all such strings. The description of S requires ? c + 2log(n) bits. The size of S is |S| ? . The description of x requires no more than c + 2log(n) + log(|S|) = c + 2log(n) + bits. For large enough n: K(x) ? (approximately). Univ. 可計算理論 2020/11/17 46/77 Shannon Entropy of Strings 桑龍 串熵 ep217 We can press a bitstring ?{0,1}n, depending on the 0/1 distribution. The Shannon entropy of this distribution (p,1–p) gives an upper bound on the Kplexity. Univ. 可計算理論 2020/11/17 47/77 Best Splits (Cont.) 補充 熵概念 ? 用 8=23個字符（ a1,..a8)寫密碼信 , 需要壓縮編碼，節(jié)約資源 ? 用 huffman編碼，編碼長度與使用頻度反比，用得頻繁的碼長短 ， ? 設(shè) 8 各字符出現(xiàn)的為頻率分布如表。 ? 編碼 如下頁 k i 1 pilog2 pi 字符 頻率 A1 188。 A2 188。 A3 1/8 A4 1/8 A5 1/16 A6 1/16 A7 1/16 A8 1/16 Univ. 可計算理論 2020/11/17 48/77 Best Splits (Cont.)