基本介紹
- 中文名：符號方法
- 外文名：symbolic method
- 學科：計算機科學
- 定義：通過估計符號的機率值來壓縮文本
- 特點：同一時間只對一個符號編碼
- 領域：文本壓縮
定義,哈夫曼編碼,算術編碼,文本壓縮,有關術語,摩爾斯電碼,機率,
定義
符號方法是一種外部壓縮方法，通常基於哈夫曼編碼或算術編碼，主要的不同之處在於如何估計符號的機率。符號機率值估計越難，壓縮效果越好。為了獲得更好的壓縮效果，機率估計常常要根據符號出現的上下文進行。機率估計的工作叫做建模，而建立一個好的模型對於實現好的壓縮效果是至關重要的。把機率轉化為比特流以供傳輸的過程叫做摩斯碼。
哈夫曼編碼
Huffman編碼將出現機率高的字元編成較短的碼字，而出現機率較低的字元則被編成較長的碼字，這樣做可使得平均每字元的碼長最短。Huffman剛提出來時是以單字元為編碼單位的，並且假定字元之間是不相關的。這樣得到的碼效率還不夠高，因此後來出現了以字元良朵熱串(詞)作為編碼單位的Huffman算法，這樣平均每字元的編碼長度變小了，但是同時編碼碼本的大小也顯著變大了。另外，這種做法的通用性也比較弱。Huffman原來是靜態的，它轎踏旬要求先對信源字元流進行掃描以確定各個字元(串)的出現頻度，用它來估計各個字元(串)的分布機率，並根據它來構造碼本。在這一過程完成以後，才進行第二次掃描，用已得到的碼本來給各個字元(串)編碼。靜態Huffman的缺斷海店辣陷除了要進行兆淋充兩次掃描之外，還在於它要在每個編碼結果中附上相應的碼本，這樣解碼器才能正確地恢復壓縮前的字元流。為了克服以上兩個缺陷，自適應Huffman編碼被提了出來，它只需要對待編碼字元流進行一次掃描，在掃描的過程中對字元(串)的出現機率進行估計，同時自適應地構造、更新碼本，並用這個動態變化的碼本來對掃描到的字元(串)進行編碼。自適應Huffman編碼除了複雜度要比靜態Huffman要高之外，由於其對字元出現機率估計並不能像靜態Huffman那么準確，所以它能達到的編碼效率也要低一些。Huffman編碼器為每個待編碼的符號(串)所分配的碼字的位數只能是整數的。這個特點妨礙Huffman編碼的平均碼長對信源熵的逼近。而以下的算術編碼法則較好地解決了這個問顧。
算術編碼
算術編碼是在世紀年代後期提出，並在20世紀80年代得以流行的一種編碼方法。算術編碼是一種高效清除字串冗餘的算法。它用一個單獨的浮點輸出數值代替一串輸入符號，從而每個符號對於輸出代碼的貢獻可以相當於一個小數位數。這使得編碼的平均碼長從理論上可以任意逼近於信源的熵，避開了Huffman編碼中比特數必須取整的問題。類似於Huffman編碼，算術編碼也要對待編碼數據流進行兩次掃描。第一次掃描統計各個字元的出現頻度，估計其出現機率。第二次掃描則糠尋按照上述的映射規則來對數據流進行編碼。所以算術編碼的輸出碼流中也要附上相應的編碼碼本以作為解碼的依據。
算術編碼器也可以採用自適應的方式，這時不需要在編碼輸出中附加編碼碼本。但是，自適應算術編碼的複雜度較高，不利於實現。實踐中，算術編碼並不是用浮點數形式來實現的，它的編碼和解碼都是用整數來實現。由於算法中包含了乘除法，所以對算法的時間性能很不利。常用的做法是愉記糠採用加法和移位操作來代替乘除法操作。
但辯汗少端是算術編碼的實現有兩大缺陷：很難在具有固定精度的計算機完成無限精度的算術操作。高度複雜的計算量不利於實際套用。例如，對一個簡單的信號源進行觀察，得到的統計模型如下：
- 60%的機會出現符號 中性
- 20%的機會出現符號 陽性
- 10%的機會出現符號 陰性
10%的機會出現符號 數據結束符. (出現這個符號的意思是該信號源'內部中止'，在進行數據壓縮時這樣的情況是很常見的。當第一次也是一次看到這個符號時，解碼器就知道整個信號流都被解碼完成了)。
算術編碼可以處理的例子不止是這種只有四種符號的情況，更複雜的情況也可以處理，包括高階的情況。所謂高階的情況是指當前符號出現的機率受之前出現符號的影響，這時候之前出現的符號，也被稱為上下文。比如在英文文檔編碼的時候，例如，在字母Q或者q出現之後，字母u出現的機率就大大提高了。這種模型還可以進行自適應的變化，即在某種上下文下出現的機率分布的估計隨著每次這種上下文出現時的符號而自適應更新，從而更加匹配實際的機率分布。不管編碼器使用怎樣的模型，解碼器也必須使用同樣的模型。
文本壓縮
文本壓縮屬於無損壓縮，是數據壓縮的一個分支。它要求能夠由壓縮後形成的編碼無失真地恢復壓縮前的原始數據。對文本壓縮的研究己有很久的歷史，並且前人己經取得了不少的研究成果，有很多己經得到了實際的套用，其中一些有著優良性能的技術正在被廣泛地套用。然而，根據Shannon編碼定理以及用各種方法估計出來的文本信源的嫡，現有技術還沒有達到編碼效率的極限，還有很大的發展空間。而且，現有技術大多是由西方國家科學工作者開發出來的，它們即使套用於西方語言文本時能獲得較好的性能，當套用於大字元集的文本(例如中文、日文、韓文以及Unicode文本)時，性能卻都會大大地降低。因此很有必要發展適用於大字元集文本的文本壓縮技術，特別是既適用於西文文本又適用於大字元集文本的文本壓縮技術。在電子技術、計算機技術和網路技術蓬勃發展，各種數據的數位化和網路化的步伐邁得越來越大。越來越多的網上圖書館和網上資料庫出現了，通過網路傳輸的電子文檔也越來越多了。因此，改進文本壓縮技術，節省存儲空間，提高網路頻寬的利用率是非常有必要的。
有關術語
摩爾斯電碼
摩爾斯電碼（又譯為摩斯密碼，Morse code）是一種時通時斷的信號代碼，通過不同的排列順序來表達不同的英文字母、數字和標點符號。它發明於1837年，發明者有爭議，是美國人塞繆爾·莫爾斯或者艾爾菲德·維爾。 摩爾斯電碼是一種早期的數位化通信形式，但是它不同於現代只使用零和一兩種狀態的二進制代碼，它的代碼包括五種： 點、劃、點和劃之間的停頓、每個詞之間中等的停頓以及句子之間長的停頓。最早的摩爾斯電碼是一些表示數字的點和劃。數字對應單詞，需要查找一本代碼表才能知道每個詞對應的數。用一個電鍵可以敲擊出點、劃以及中間的停頓。雖然摩爾斯發明了電報，但他缺乏相關的專門技術。他與艾爾菲德·維爾簽定了一個協定，讓他幫自己製造更加實用的設備。艾爾菲德·維爾構思了一個方案，通過點、劃和中間的停頓，可以讓每個字元和標點符號彼此獨立地傳送出去。他們達成一致，同意把這種標識不同符號的方案放到摩爾斯的專利中。這就是我們所熟知的美式摩爾斯電碼，它被用來傳送了世界上第一條電報。
這種代碼可以用一種音調平穩時斷時續的無線電信號來傳送，通常被稱做“連續波”（Continuous Wave），縮寫為CW。它可以是電報電線里的電子脈衝，也可以是一種機械的或視覺的信號（比如閃光）。
一般來說，任何一種能把書面字元用可變長度的信號表示的編碼方式都可以稱為摩爾斯電碼。但這一術語只用來特指兩種表示英語字母和符號的摩爾斯電碼：美式摩爾斯電碼被使用在有線電報通信系統；還在使用的國際摩爾斯電碼則只使用點和劃（去掉了停頓）。
機率
又稱或然率、機會率或幾率、可能性，是數學機率論的基本概念，是一個在0到1之間的實數，是對隨機事件發生之可能性的度量。
機率常用來量化對於某些不確定命題的想法，命題一般會是以下的形式：“某個特定事件會發生嗎？”，對應的想法則是：“我們可以多確定這個事件會發生？”。確定的程度可以用0到1之間的數值來表示，這個數值就是機率。因此若事件發生的機率越高，表示我們越認為這個事件可能發生。像丟銅板就是一個簡單的例子，正面朝上及背面朝上的兩種結果看來機率相同，每個的機率都是1/2，也就是正面朝上及背面朝上的機率各有50%。
這些概念可以形成機率論中的數學公理（參考機率公理），在像數學、統計學、金融、博弈論、科學（特別是物理）、人工智慧/機器學習、計算機科學及哲學等學科中都會用到。機率論也可以描述複雜系統中的內在機制及規律性。
但是算術編碼的實現有兩大缺陷：很難在具有固定精度的計算機完成無限精度的算術操作。高度複雜的計算量不利於實際套用。例如，對一個簡單的信號源進行觀察，得到的統計模型如下：
- 60%的機會出現符號 中性
- 20%的機會出現符號 陽性
- 10%的機會出現符號 陰性
10%的機會出現符號 數據結束符. (出現這個符號的意思是該信號源'內部中止'，在進行數據壓縮時這樣的情況是很常見的。當第一次也是一次看到這個符號時，解碼器就知道整個信號流都被解碼完成了)。
算術編碼可以處理的例子不止是這種只有四種符號的情況，更複雜的情況也可以處理，包括高階的情況。所謂高階的情況是指當前符號出現的機率受之前出現符號的影響，這時候之前出現的符號，也被稱為上下文。比如在英文文檔編碼的時候，例如，在字母Q或者q出現之後，字母u出現的機率就大大提高了。這種模型還可以進行自適應的變化，即在某種上下文下出現的機率分布的估計隨著每次這種上下文出現時的符號而自適應更新，從而更加匹配實際的機率分布。不管編碼器使用怎樣的模型，解碼器也必須使用同樣的模型。
文本壓縮
文本壓縮屬於無損壓縮，是數據壓縮的一個分支。它要求能夠由壓縮後形成的編碼無失真地恢復壓縮前的原始數據。對文本壓縮的研究己有很久的歷史，並且前人己經取得了不少的研究成果，有很多己經得到了實際的套用，其中一些有著優良性能的技術正在被廣泛地套用。然而，根據Shannon編碼定理以及用各種方法估計出來的文本信源的嫡，現有技術還沒有達到編碼效率的極限，還有很大的發展空間。而且，現有技術大多是由西方國家科學工作者開發出來的，它們即使套用於西方語言文本時能獲得較好的性能，當套用於大字元集的文本(例如中文、日文、韓文以及Unicode文本)時，性能卻都會大大地降低。因此很有必要發展適用於大字元集文本的文本壓縮技術，特別是既適用於西文文本又適用於大字元集文本的文本壓縮技術。在電子技術、計算機技術和網路技術蓬勃發展，各種數據的數位化和網路化的步伐邁得越來越大。越來越多的網上圖書館和網上資料庫出現了，通過網路傳輸的電子文檔也越來越多了。因此，改進文本壓縮技術，節省存儲空間，提高網路頻寬的利用率是非常有必要的。
有關術語
摩爾斯電碼
摩爾斯電碼（又譯為摩斯密碼，Morse code）是一種時通時斷的信號代碼，通過不同的排列順序來表達不同的英文字母、數字和標點符號。它發明於1837年，發明者有爭議，是美國人塞繆爾·莫爾斯或者艾爾菲德·維爾。 摩爾斯電碼是一種早期的數位化通信形式，但是它不同於現代只使用零和一兩種狀態的二進制代碼，它的代碼包括五種： 點、劃、點和劃之間的停頓、每個詞之間中等的停頓以及句子之間長的停頓。最早的摩爾斯電碼是一些表示數字的點和劃。數字對應單詞，需要查找一本代碼表才能知道每個詞對應的數。用一個電鍵可以敲擊出點、劃以及中間的停頓。雖然摩爾斯發明了電報，但他缺乏相關的專門技術。他與艾爾菲德·維爾簽定了一個協定，讓他幫自己製造更加實用的設備。艾爾菲德·維爾構思了一個方案，通過點、劃和中間的停頓，可以讓每個字元和標點符號彼此獨立地傳送出去。他們達成一致，同意把這種標識不同符號的方案放到摩爾斯的專利中。這就是我們所熟知的美式摩爾斯電碼，它被用來傳送了世界上第一條電報。
這種代碼可以用一種音調平穩時斷時續的無線電信號來傳送，通常被稱做“連續波”（Continuous Wave），縮寫為CW。它可以是電報電線里的電子脈衝，也可以是一種機械的或視覺的信號（比如閃光）。
一般來說，任何一種能把書面字元用可變長度的信號表示的編碼方式都可以稱為摩爾斯電碼。但這一術語只用來特指兩種表示英語字母和符號的摩爾斯電碼：美式摩爾斯電碼被使用在有線電報通信系統；還在使用的國際摩爾斯電碼則只使用點和劃（去掉了停頓）。
機率
又稱或然率、機會率或幾率、可能性，是數學機率論的基本概念，是一個在0到1之間的實數，是對隨機事件發生之可能性的度量。
機率常用來量化對於某些不確定命題的想法，命題一般會是以下的形式：“某個特定事件會發生嗎？”，對應的想法則是：“我們可以多確定這個事件會發生？”。確定的程度可以用0到1之間的數值來表示，這個數值就是機率。因此若事件發生的機率越高，表示我們越認為這個事件可能發生。像丟銅板就是一個簡單的例子，正面朝上及背面朝上的兩種結果看來機率相同，每個的機率都是1/2，也就是正面朝上及背面朝上的機率各有50%。
這些概念可以形成機率論中的數學公理（參考機率公理），在像數學、統計學、金融、博弈論、科學（特別是物理）、人工智慧/機器學習、計算機科學及哲學等學科中都會用到。機率論也可以描述複雜系統中的內在機制及規律性。
