(資料圖片)

1.十進(jìn)制

1.1.現(xiàn)代數(shù)學(xué)建立在十進(jìn)制計數(shù)系統(tǒng)之上

2.二進(jìn)制

2.1.二進(jìn)制計數(shù)系統(tǒng)的工作原理與十進(jìn)制計數(shù)系統(tǒng)一樣，唯一的區(qū)別是前者的基數(shù)為2，而后者的基數(shù)為10

2.2.數(shù)據(jù)壓縮所做的就是盡可能減少表示特定數(shù)據(jù)集時所需的二進(jìn)制位數(shù)量

2.3.給定任意一個整數(shù)，我們都能將它轉(zhuǎn)換為二進(jìn)制形式

3.十六進(jìn)制

3.1.用字母A來表示10，用B表示11，以此類推，用F表示15

4.信息論

4.1.一個數(shù)值所包含的信息內(nèi)容等于，為了在一個集合中唯一地確定這個數(shù)值，需要做出的二選一（是/否）決定的次數(shù)

5.二分查找

5.1.首先將數(shù)組中的數(shù)據(jù)集分成兩半，然后判斷要找的數(shù)值10比處于中間位置的樞軸值是大還是小

5.2.如果一個數(shù)組包含偶數(shù)個元素，那么真正處于中間的元素是不存在的，可以根據(jù)喜好沖中間偏左或者偏右選擇一個

6.熵

6.1.物理學(xué)中的解釋

6.1.1.一個熱力學(xué)量，表示的是一個系統(tǒng)中無法轉(zhuǎn)換為機(jī)械功的熱能的量，通常被解釋為該系統(tǒng)的無序度或隨機(jī)度

6.2.信息論中的解釋

6.2.1.對在特定的消息或語言中信息傳輸速度的一種對數(shù)度量

6.3.表示一個數(shù)所需要的最少二進(jìn)制位數(shù)

6.4.一個數(shù)所需要的二進(jìn)制位數(shù)lb(x)=(log(x)/log(2))

6.4.1.二進(jìn)制位已經(jīng)是數(shù)據(jù)的最小單位，能使用的最小的二進(jìn)制位數(shù)就是1

6.4.2.必須對這個值向上取整，也就是使用向上取整函數(shù)，即ceil（或ceiling）函數(shù)

6.5.LOG2(x)=ceil(log(x+1)/log(2))

6.6.一個集合的熵

6.6.1.H(S)=-∑pi×lb(pi)

6.7.為了使表示某個數(shù)據(jù)集所需的二進(jìn)制位數(shù)最少，數(shù)據(jù)集中的每個符號平均所需的最小二進(jìn)制位數(shù)就是熵

6.8.以一種倒排序的方式建立在數(shù)據(jù)流中每個符號出現(xiàn)概率的估算之上的

6.8.1.一個符號出現(xiàn)得越頻繁，它對整個數(shù)據(jù)集包含的信息內(nèi)容的貢獻(xiàn)就會越少

6.8.2.很長的時間里沒有什么有用的信息，真正有用的信息偶爾才會出現(xiàn)

7.數(shù)據(jù)壓縮算法的藝術(shù)

7.1.真正試圖去突破熵的限定

7.2.將數(shù)據(jù)轉(zhuǎn)換成一種熵值更小的、新的表現(xiàn)形式

8.突破熵

8.1.按照香農(nóng)對熵的定義，他只考慮了符號出現(xiàn)的概率，完全沒有考慮符號之間的排序

8.1.1.對真實數(shù)據(jù)集來說，排序是一項基本的信息，符號之間的關(guān)系同樣如此

8.2.通過利用數(shù)據(jù)集的結(jié)構(gòu)信息將其轉(zhuǎn)換為一種新的表示形式，而這種新表示形式的熵比源信息的熵小

8.2.1.[Q,U,A,R,K] 和[K,R,U,Q,A] 這兩個集合有相同的熵

8.2.2.[Q,U,A,R,K] 這個集合表示的是英語中一個有意義的單詞

8.3.增量編碼（delta coding）

8.3.1.如果相鄰的值之間高度相關(guān)，那么用增量編碼的方法可以轉(zhuǎn)換數(shù)據(jù)，使其熵變得更小

8.3.2.順序很重要

8.4.符號分組

8.4.1.用單詞作為符號，得到的熵值會更小

8.4.2.如果數(shù)據(jù)集中存在連續(xù)值組合出現(xiàn)多次的情況，就可以利用這種情況來減小熵

8.4.3.通過最佳符號分組預(yù)處理數(shù)據(jù)，會得到一個較小的熵值

8.5.排列

8.5.1.一個排列就是原來的集合打亂順序后的一個版本

8.5.2.對數(shù)直接進(jìn)行編碼時，共需要24個二進(jìn)制位，而對下標(biāo)編碼時，只需要18個二進(jìn)制位，也就是節(jié)省了大約25% 的空間

9.標(biāo)準(zhǔn)的數(shù)字長度

9.1.用最少的二進(jìn)制位數(shù)來表示一個數(shù)，在解碼相應(yīng)的二進(jìn)制字符串時會產(chǎn)生混亂（因為我們并不知道該數(shù)對應(yīng)的LOG2長度），會與硬件的執(zhí)行性能相沖突，兩者不能兼顧

9.2.折中的方案

9.2.1.用固定長度的二進(jìn)制位數(shù)來表示大小不同的整數(shù)

9.2.2.最基本的存儲單元是一個字節(jié)，由8個二進(jìn)制位組成

9.3.信息論與實際實現(xiàn)層面的差別

9.3.1.絕大多數(shù)算法使用預(yù)先設(shè)定好的固定的二進(jìn)制位長度，而不是通過LOG2函數(shù)計算出的二進(jìn)制位長度

10.柯爾莫哥洛夫復(fù)雜性

10.1.Kolmogorov complexity

10.2.以數(shù)學(xué)家安德雷?柯爾莫哥洛夫（Andrey Kolmogorov）的名字命名，以紀(jì)念他在1963年發(fā)表了這方面的第一篇論文

10.3.度量的是確定一個對象所需要的計算資源

10.3.1.為了準(zhǔn)確地生成數(shù)據(jù)，所需要的生成程序的大小

10.4.任何字符串的柯爾莫哥洛夫復(fù)雜性頂多比字符串本身的長度大幾個字節(jié)(基本上，也就是一個程序輸出字符串的每個元素）

10.5.邏輯綜合（logic synthesis）或者程序綜合（program synthesis）進(jìn)行數(shù)據(jù)壓縮的時候，柯爾莫哥洛夫復(fù)雜性就開始真正起作用了

10.5.1.本質(zhì)上它取的是數(shù)據(jù)集以及反向生成產(chǎn)生字符串的程序的二進(jìn)制位流