1. 十進制
1.1. 現代數學建立在十進制計數系統之上
2. 二進制
2.1. 二進制計數系統的作業原理與十進制計數系統一樣，唯一的區別是前者的基數為2，而后者的基數為10
2.2. 資料壓縮所做的就是盡可能減少表示特定資料集時所需的二進制位數量
2.3. 給定任意一個整數，我們都能將它轉換為二進制形式
3. 十六進制
3.1. 用字母A來表示10，用B表示11，以此類推，用F表示15
4. 資訊論
4.1. 一個數值所包含的資訊內容等于，為了在一個集合中唯一地確定這個數值，需要做出的二選一（是/否）決定的次數
5. 二分查找
5.1. 首先將陣列中的資料集分成兩半，然后判斷要找的數值10比處于中間位置的樞軸值是大還是小
5.2. 如果一個陣列包含偶數個元素，那么真正處于中間的元素是不存在的，可以根據喜好沖中間偏左或者偏右選擇一個
6. 熵
6.1. 物理學中的解釋
6.1.1. 一個熱力學量，表示的是一個系統中無法轉換為機械功的熱能的量，通常被解釋為該系統的無序度或隨機度
6.2. 資訊論中的解釋
6.2.1. 對在特定的訊息或語言中資訊傳輸速度的一種對數度量
6.3. 表示一個數所需要的最少二進制位數
6.4. 一個數所需要的二進制位數lb(x)=(log(x)/log(2))
6.4.1. 二進制位已經是資料的最小單位，能使用的最小的二進制位數就是1
6.4.2. 必須對這個值向上取整，也就是使用向上取整函式，即ceil（或ceiling）函式
6.5. LOG2(x)=ceil(log(x+1)/log(2))
6.6. 一個集合的熵
6.6.1. H(S)=-∑pi×lb(pi)
6.7. 為了使表示某個資料集所需的二進制位數最少，資料集中的每個符號平均所需的最小二進制位數就是熵
6.8. 以一種倒排序的方式建立在資料流中每個符號出現概率的估算之上的
6.8.1. 一個符號出現得越頻繁，它對整個資料集包含的資訊內容的貢獻就會越少
6.8.2. 很長的時間里沒有什么有用的資訊，真正有用的資訊偶爾才會出現
7. 資料壓縮演算法的藝術
7.1. 真正試圖去突破熵的限定
7.2. 將資料轉換成一種熵值更小的、新的表現形式
8. 突破熵
8.1. 按照香農對熵的定義，他只考慮了符號出現的概率，完全沒有考慮符號之間的排序
8.1.1. 對真實資料集來說，排序是一項基本的資訊，符號之間的關系同樣如此
8.2. 通過利用資料集的結構資訊將其轉換為一種新的表示形式，而這種新表示形式的熵比源資訊的熵小
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. 如果相鄰的值之間高度相關，那么用增量編碼的方法可以轉換資料，使其熵變得更小
8.3.2. 順序很重要
8.4. 符號分組
8.4.1. 用單詞作為符號，得到的熵值會更小
8.4.2. 如果資料集中存在連續值組合出現多次的情況，就可以利用這種情況來減小熵
8.4.3. 通過最佳符號分組預處理資料，會得到一個較小的熵值
8.5. 排列
8.5.1. 一個排列就是原來的集合打亂順序后的一個版本
8.5.2. 對數直接進行編碼時，共需要24個二進制位，而對下標編碼時，只需要18個二進制位，也就是節省了大約25% 的空間
9. 標準的數字長度
9.1. 用最少的二進制位數來表示一個數，在解碼相應的二進制字串時會產生混亂（因為我們并不知道該數對應的LOG2長度），會與硬體的執行性能相沖突，兩者不能兼顧
9.2. 折中的方案
9.2.1. 用固定長度的二進制位數來表示大小不同的整數
9.2.2. 最基本的存盤單元是一個位元組，由8個二進制位組成
9.3. 資訊論與實際實作層面的差別
9.3.1. 絕大多數演算法使用預先設定好的固定的二進制位長度，而不是通過LOG2函式計算出的二進制位長度
10. 柯爾莫哥洛夫復雜性
10.1. Kolmogorov complexity
10.2. 以數學家安德雷?柯爾莫哥洛夫（Andrey Kolmogorov）的名字命名，以紀念他在1963年發表了這方面的第一篇論文
10.3. 度量的是確定一個物件所需要的計算資源
10.3.1. 為了準確地生成資料，所需要的生成程式的大小
10.4. 任何字串的柯爾莫哥洛夫復雜性頂多比字串本身的長度大幾個位元組(基本上，也就是一個程式輸出字串的每個元素）
10.5. 邏輯綜合（logic synthesis）或者程式綜合（program synthesis）進行資料壓縮的時候，柯爾莫哥洛夫復雜性就開始真正起作用了
10.5.1. 本質上它取的是資料集以及反向生成產生字串的程式的二進制位流
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/553772.html
標籤：其他
下一篇：返回列表