文章來源地址http://www.zghlxwxcb.cn/news/detail-464103.html

1.?十進制

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

2.?二進制

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

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

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

3.?十六進制

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

4.?信息論

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

5.?二分查找

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

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

6.?熵

6.1.?物理學中的解釋

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

6.2.?信息論中的解釋

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

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

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

6.4.1.?二進制位已經是數(shù)據(jù)的最小單位，能使用的最小的二進制位數(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ù)集所需的二進制位數(shù)最少，數(shù)據(jù)集中的每個符號平均所需的最小二進制位數(shù)就是熵

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

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

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

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

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

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

8.?突破熵

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

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

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

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.?如果相鄰的值之間高度相關，那么用增量編碼的方法可以轉換數(shù)據(jù)，使其熵變得更小

8.3.2.?順序很重要

8.4.?符號分組

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

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

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

8.5.?排列

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

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

9.?標準的數(shù)字長度

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

9.2.?折中的方案

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

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

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

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

10.?柯爾莫哥洛夫復雜性

10.1.?Kolmogorov complexity

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

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

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

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

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

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

到了這里，關于讀數(shù)據(jù)壓縮入門筆記02_二進制和熵的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！