1. 瓶頸

1.1. 在網路帶寬有限、存盤昂貴的時期

1.2. 移動設備正日益成為人們訪問互聯網的首選的今天

1.3. 資料壓縮成了緩解這些瓶頸的關鍵

2. 字典轉換

2.1. dictionary transforms

2.2. 完全改變了人們對資料壓縮的認知

2.2.1. 壓縮變成了一種對各種型別的資料都有用的演算法

2.3. 事實上今天所有的主流壓縮演算法（比如GZIP或者7-Zip）都會在核心轉換步驟中使用字典轉換

3. 基本字典轉換

3.1. 統計壓縮主要關注資料流中單個符號的出現概率

3.2. 這一概率與其周圍可能出現的符號無關

3.3. 符號字典

3.4. 任何出現可以重復使用的相似內容分組的地方，都會有“短語”存在

3.5. 步驟

3.5.1. 給定源資料流

3.5.2. 構建出單詞字典（而不是符號字典）

3.5.3. 再將統計壓縮應用到字典中的單詞上

3.6. 字典轉換并非是要去替代統計編碼

3.6.1. 只是你先應用到資料流上的一個轉換，這樣統計編碼演算法就能更有效地對其編碼

3.7. 實際是一個資料流的預處理階段

3.7.1. 生成的資料集會更小，比源資料流壓縮率更高

3.8. 當能識別出那些經常重復使用的長字串，并為它們分配最短的碼字時，字典轉換的效率最高

4. 分詞

4.1. tokenization

4.2. 是資訊論領域的一個研究分支

4.3. 一種暴力方法是讀取一組符號并搜索字串的剩余部分來確定該組符號的出現頻次

4.3.1. 對所有真實的資料流而言，這樣做不僅需要大量的記憶體，同時還需要花費很長的時間

4.4. 為了找到資料流的理想分詞，我們需要有某種方法來處理現有的和那些還沒有遇到的符號，并能以一種高效的方式將兩者合并為盡可能長的符號集

5. LZ演算法

5.1. 1977年，Abraham Lempel和Jacob Ziv提出

5.1.1. Jacob Ziv大學畢業于以色列理工學院，隨后于1961年獲得了麻省理工學院資訊論專業的博士學位

5.1.2. Abraham Lempel在以色列理工學院獲得了學士、碩士和博士學位

5.1.3. 1997年獲得了IEEE資訊理論學會的香農獎

5.2. LZ77 和LZ78

5.2.1. 找出最佳分詞方面非常高效，30多年來還沒有其他演算法可以取代它們

5.3. 衍生演算法

5.3.1. 每一種變體都是根據特殊的需要、性能要求的不同或者用例的不同，對LZ77基本演算法進行了一些小調整

5.3.1.1. 對資料集越了解，你就越能從中選擇出最適合的LZ變換

5.3.2. GIF影像格式中使用的LZW（即Lempel-Ziv-Welch）演算法

5.3.2.1. Terry Welch于1984年提出的，它采用了LZ78演算法的思想

5.3.2.2. 首個在計算機中廣泛采用的通用資料壓縮方法

5.3.3. 應用于7-Zip、xz等壓縮工具的LZM（即Lempel-Ziv-Markov chain）演算法

5.3.4. DEFLATE又應用于PNG影像格式、PKZIP、GZIP等壓縮工具及zlib庫中

5.3.5. PKZip、ARJ、RAR、ZOO和LHarc使用LZSS演算法

5.3.6. 圖

5.4. 真正吸引人的地方還在于它可以和統計編碼結合使用

5.4.1. 將記號中的偏移量、長度值以及字面值分開后，再按照型別合并，組成單獨的偏移量集、長度值集和字面值集，然后再對這些資料集進行統計壓縮

6. LZ演算法的作業原理

6.1. 通過在讀取的字串中尋找當前單詞的匹配來分詞

6.2. 與讀取一組符號然后向后查找它是否重復出現不同

6.2.1. LZ演算法向前查找當前單詞是否出現過

6.3. 在資料流的前半部分，由于我們見過的單詞很少，因此出現新單詞的可能性很大

6.4. 資料流的后半部分，由于已經有了很大的緩沖區，因此出現匹配的可能性更大

6.5. 向前尋找匹配可以讓我們找出“最長的匹配詞”

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/555281.html

標籤：其他

上一篇：網路傳輸中的重要引數-簡單的網路畫像

下一篇：返回列表

讀資料壓縮入門筆記05_字典轉換

1. 瓶頸

1.1. 在網路帶寬有限、存盤昂貴的時期

1.2. 移動設備正日益成為人們訪問互聯網的首選的今天

1.3. 資料壓縮成了緩解這些瓶頸的關鍵

2. 字典轉換

2.1. dictionary transforms

2.2. 完全改變了人們對資料壓縮的認知

2.2.1. 壓縮變成了一種對各種型別的資料都有用的演算法

2.3. 事實上今天所有的主流壓縮演算法（比如GZIP或者7-Zip）都會在核心轉換步驟中使用字典轉換

3. 基本字典轉換

3.1. 統計壓縮主要關注資料流中單個符號的出現概率

3.2. 這一概率與其周圍可能出現的符號無關

3.3. 符號字典

3.4. 任何出現可以重復使用的相似內容分組的地方，都會有“短語”存在

3.5. 步驟

3.5.1. 給定源資料流

3.5.2. 構建出單詞字典（而不是符號字典）

3.5.3. 再將統計壓縮應用到字典中的單詞上

3.6. 字典轉換并非是要去替代統計編碼

3.6.1. 只是你先應用到資料流上的一個轉換，這樣統計編碼演算法就能更有效地對其編碼

3.7. 實際是一個資料流的預處理階段

3.7.1. 生成的資料集會更小，比源資料流壓縮率更高

3.8. 當能識別出那些經常重復使用的長字串，并為它們分配最短的碼字時，字典轉換的效率最高

4. 分詞

4.1. tokenization

4.2. 是資訊論領域的一個研究分支

4.3. 一種暴力方法是讀取一組符號并搜索字串的剩余部分來確定該組符號的出現頻次

4.3.1. 對所有真實的資料流而言，這樣做不僅需要大量的記憶體，同時還需要花費很長的時間

4.4. 為了找到資料流的理想分詞，我們需要有某種方法來處理現有的和那些還沒有遇到的符號，并能以一種高效的方式將兩者合并為盡可能長的符號集

5. LZ演算法

5.1. 1977年，Abraham Lempel和Jacob Ziv提出

5.1.1. Jacob Ziv大學畢業于以色列理工學院，隨后于1961年獲得了麻省理工學院資訊論專業的博士學位

5.1.2. Abraham Lempel在以色列理工學院獲得了學士、碩士和博士學位

5.1.3. 1997年獲得了IEEE資訊理論學會的香農獎

5.2. LZ77 和LZ78

5.2.1. 找出最佳分詞方面非常高效，30多年來還沒有其他演算法可以取代它們

5.3. 衍生演算法

5.3.1. 每一種變體都是根據特殊的需要、性能要求的不同或者用例的不同，對LZ77基本演算法進行了一些小調整

5.3.1.1. 對資料集越了解，你就越能從中選擇出最適合的LZ變換

5.3.2. GIF影像格式中使用的LZW（即Lempel-Ziv-Welch）演算法

5.3.2.1. Terry Welch于1984年提出的，它采用了LZ78演算法的思想

5.3.2.2. 首個在計算機中廣泛采用的通用資料壓縮方法

5.3.3. 應用于7-Zip、xz等壓縮工具的LZM（即Lempel-Ziv-Markov chain）演算法

5.3.4. DEFLATE又應用于PNG影像格式、PKZIP、GZIP等壓縮工具及zlib庫中

5.3.5. PKZip、ARJ、RAR、ZOO和LHarc使用LZSS演算法

5.3.6. 圖

5.4. 真正吸引人的地方還在于它可以和統計編碼結合使用

5.4.1. 將記號中的偏移量、長度值以及字面值分開后，再按照型別合并，組成單獨的偏移量集、長度值集和字面值集，然后再對這些資料集進行統計壓縮

6. LZ演算法的作業原理

6.1. 通過在讀取的字串中尋找當前單詞的匹配來分詞

6.2. 與讀取一組符號然后向后查找它是否重復出現不同

6.2.1. LZ演算法向前查找當前單詞是否出現過

6.3. 在資料流的前半部分，由于我們見過的單詞很少，因此出現新單詞的可能性很大

6.4. 資料流的后半部分，由于已經有了很大的緩沖區，因此出現匹配的可能性更大

6.5. 向前尋找匹配可以讓我們找出“最長的匹配詞”