本節書摘來自華章出版社《計算機科學概論》一書中的第3章，第3.3節文本表示法，作者［美]内爾·黛爾（nell dale）約翰·路易斯（john lewis），更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
3.3 文本表示法
一個文本文檔可以被分解為段落、句子、詞和最終的單個字元。要用數字形式表示文本文檔，隻需要表示每個可能出現的字元。文檔是連續（模拟）的實體，獨立的字元則是離散的元素，它們才是我們要表示并存儲在計算機記憶體中的。
現在，我們應該區分文本表示法的基本想法和文字處理的概念。當用microsoft word這樣的字處理程式建立文檔時，可以設定各種格式，包括字型、頁邊距、制表位、顔色等。 許多字處理程式還允許在文檔中加入自選圖形、公式和其他元素。這些額外資訊與文本存儲在一起，以便文檔能夠正确地顯示和列印出來。但核心問題是如何表示字元本身，是以，目前我們把重點放在表示字元的方法上。
要表示的字元數是有限的。一種表示字元的普通方法是列出所有字元，然後賦予每個字元一個二進制字元串。例如，要存儲一個特定的字母，我們将儲存它對應的位串。
那麼需要表示哪些字元呢？在英語中，有26個字母，但必須有差別地處理大寫字母和小寫字母，是以實際上有52個字母。與數字（0、1到9）一樣，各種标點符号也需要表示。即使是空格，也需要有自己的表示法。那麼對于非英語的語言又如何呢？一旦你考慮到這一點，那麼我們想表示的字元數就會迅速增長。記住，我們在本章的前面讨論過，要表示的狀态數決定了需要多少位來表示一種狀态。
字元集隻是字元和表示它們的代碼的清單。這些年來，出現了多種字元集，但隻有少數的幾種處于主導地位。在計算機制造商就關于使用哪種字元集達成一緻後，文本資料的處理變得容易多了。在接下來的小節中，我們将介紹兩種字元集，即ascii字元集和unicode字元集。
字元集（character set）：字元和表示它們的代碼的清單。
3.3.1 ascii字元集
ascii是美國資訊交換标準代碼（american standard code for information interchange）的縮寫。最初，ascii字元集用7位表示每個字元，可以表示128個不同的字元。每個位元組中的第八位最初被用作校驗位，協助確定資料傳輸正确。之後，ascii字元集進化了，用8位表示每個字元。這個8位版本的正式名字是latin-1擴充ascii字元集。該擴充字元集可以表示256個字元，包括一些重點字元和幾個補充的特殊符号。圖3-5展示了完整的ascii字元集。
**字元集迷宮
1960年，一篇關于acm通信的文章報道了字元集使用的調查，描述了60個不同的字元集。僅僅ibm公司的電腦生産線中，就存在9個内容和順序都不同的字元集。**［1］
這個圖表中的代碼是用十進制數表示的，但計算機存儲這些代碼時，将把它們轉換成相應的二進制數。注意，每個ascii字元都有自己的順序，這是由存儲它們所用的代碼決定的。每個字元都有一個相對于其他字元的位置（在其他字元之前或之後）。這個屬性在許多方面都很有用。例如，可以利用字元代碼對一組單詞按照字母順序排序。
這個圖表中的前32個ascii字元沒有簡單的字元表示法，不能輸出到螢幕上。這些字元是為特殊用途保留的，如回車符和制表符，處理資料的程式會用特定的方式解釋它們。
3.3.2 unicode字元集
ascii字元集的擴充版本提供了256個字元，雖然足夠表示英語，但是卻無法滿足國際需要。這種局限性導緻了unicode字元集的出現，這種字元集具有更強大的國際影響。
unicode的建立者的目标是表示世界上使用的所有語言中的所有字元，包括亞洲的表意符号。此外，它還表示了許多補充的專用字元，如科學符号。
現在，unicode字元集被許多程式設計語言和計算機系統采用。一般情況下，每個字元的編碼都為16位，但也是十分靈活的，如果需要的話每個字元可以使用更多空間，以便表示額外的字元。unicode字元集的一個友善之處就是它把ascii字元集作為了一個子集。圖3-6展示了unicode字元集中非ascii部分的幾個字元。
為了保持一緻，unicode字元集被設計為ascii的超集。也就是說，unicode字元集中的前256個字元與擴充ascii字元集中的完全一樣，表示這些字元的代碼也一樣。是以，即使底層系統采用的是unicode字元集，采用ascii值的程式也不會受到
影響。
3.3.3 文本壓縮
字母資訊（文本）是一種基本資料類型。是以，找到存儲這種資訊以及有效地在兩台計算機之間傳遞它們的方法是很重要的。下面的小節将分析三種文本壓縮類型：
關鍵字編碼
行程長度編碼
赫夫曼編碼
在本章後面的小節中我們還會談到，這些文本壓縮方法的基本思想也适用于其他類型的資料。
想想你在英語中使用“the”“and”“which”“that”和“what”的頻率。如果這些單詞占用更少的空間（即用更少的字元表示），文檔就會減小。即使每個單詞節省的空間都很少，但因它們在典型的文檔中太常用，是以節省出的總空間還是很可觀的。
一種相當直接的文本壓縮方法是關鍵字編碼，它用單個字元代替了常用的單詞。要解壓這種文檔，需要采用壓縮的逆過程，即用相應的完整單詞替換單個字元。
關鍵字編碼（keyword encoding）：用單個字元代替常用的單詞。
例如，假設我們用下列圖表對幾個單詞編碼：
單 詞 符 号 單 詞 符 号
as ^ must &
the ~ well %
and + these #
that $
讓我們對下列段落編碼：
the human body is composed of many independent systems, such as the circulatory system, the respiratory system, and the reproductive system. not only must all systems work independently, but they must interact and cooperate as well. overall health is a function of the well-being of separate systems, as well as how these separate systems work in concert.
編碼後的段落如下：
the human body is composed of many independent systems, such ^ ~ circulatory system, ~
respiratory system, + ~ reproductive system. not only & each system work independently, but they & interact + cooperate ^ %. overall health is a function of ~ %-being of separate systems, ^ % ^ how # separate systems work in concert.
原始段落總共有352個字元，包括空格和标點。編碼後的段落包括317個字元，節省了35個字元。這個例子的壓縮率是317/352，或約為0.9。
關鍵字編碼有幾點局限性。首先，用來對關鍵字編碼的字元不能出現在原始文本中。例如，如果原始段落中包括“$”，那麼生成的編碼就會有歧義。我們不知道“$”表示的是單詞“that”還是真正的美元符号。這限制了能夠編碼的單詞數和要編碼的文本的特性。
**昂貴的一晚
如果你曾入住假日酒店、假日快捷酒店或者皇冠假日酒店并在2002年10月24日到10月26日之間結賬離開，那麼你就很可能是被多收100倍價錢的26?000人中的一個，有些地方收費達到了每晚6500到21?000美元，小數點的删除導緻了信用卡處理的錯誤。**
此外，示例中的單詞“the”沒有被編碼為字元“~”，因為“the”與“the”不是同一個單詞。記住，在計算機上存儲的字母的大寫版本和小寫版本是不同的字元。如果想對“the”編碼，就必須使用另一個符号，或者采用更加複雜的替換模式。
最後，不要對“a”和“i”這樣的單詞編碼，因為那不過是用一個字元替換另一個字元。單詞越長，每個單詞的壓縮率就越高。遺憾的是，常用的單詞通常都比較短。另一方面，有些文檔使用某些單詞比使用其他單詞頻繁，這是由文檔的主題決定的。例如，在我們的示例中，如果對單詞“system”編碼，将節省很多空間，但在通常情況下，并不值得對它編碼。
關鍵字編碼的一種擴充是用特殊字元替換文本中的特定模式。被編碼的模式通常不是完整的單詞，而是單詞的一部分，如通用的字首和字尾“ex”“ing”和“tion”。這種方法的一個優點是被編碼的模式通常比整個單詞出現的頻率更高，但缺點同前，即被編碼的通常是比較短的模式，對每個單詞來說，替換它們節省的空間比較少。
在某些情況下，一個字元可能在一個長序列中反複出現。在英國文本中，這種重複不常見，但在大的資料流（如dna序列）中，這種情況則經常出現。一種名為行程長度編碼的文本壓縮技術利用了這種情況。行程長度編碼有時又稱為疊代編碼。
在行程長度編碼中，重複字元的序列将被替換為标志字元，後面加重複字元和說明字元重複次數的數字。例如，下面的字元串由7個a構成：
aaaaaaa
如果用*作為标志字元，這個字元串可以被編碼為：
*a7
行程長度編碼（run-length encoding）：把一系列重複字元替換為它們重複出現的次數。
标志字元說明這三個字元的序列應該被解碼為相應的重複字元串，其他文本則按照正常處理。是以，下面的編碼字元串
n5x9ccch6 some other text k8eee
将被解碼為如下的原始文本：
nnnnnxxxxxxxxxccchhhhhh some other text kkkkkkkkeee
原始文本包括51個字元，編碼串包括35個字元，是以這個示例的壓縮率為35/51，或約為0.68。
注意，這個例子中有三個重複的c和三個重複的e都沒有編碼。因為需要用三個字元對這樣的重複序列編碼，是以對長度為2或3的字元串進行編碼是不值得的。事實上，如果對長度為2的重複字元串編碼，反而會使結果串更長。
因為我們用一個字元記錄重複的次數，是以看來不能對重複次數大于9的序列編碼。但是，在某些字元集中，一個字元是由多個位表示的。例如，字元“5”在ascii字元集中表示為53，這是一個八位的二進制字元串00110101。是以，我們将次數字元解釋為一個二進制數，而不是解釋為一個ascii數字。這樣一來，能夠編碼的重複字元的重複次數可以是0到255的任何數，甚至可以是4到259的任何數，因為長度為2或3的序列不會被
編碼。
另一種文本壓縮技術是赫夫曼編碼，以它的建立者david huffman博士的名字命名。文本中很少使用字母“x”，那麼為什麼要讓它占用的位數與常用空格字元一樣呢？赫夫曼編碼使用不同長度的位串表示每個字元，進而解決了這個問題。也就是說，一些字元由5位編碼表示，一些字元由6位編碼表示，還有一些字元由7位編碼表示，等等。這種方法與字元集的概念相反，在字元集中，每個字元都由定長（如8位或16位）的位串表示。
這種方法的基本思想是用較少的位表示經常出現的字元，而将較長的位串留給不經常出現的字元，這樣表示的文檔的整體大小将比較小。
赫夫曼編碼（huffman encoding）：用變長的二進制串表示字元，使常用的字元具有較短的編碼。
例如，假設用下列赫夫曼編碼來表示一些字元：
那麼單詞doorbell的二進制編碼如下：
1011110110111101001100100
如果使用定長位串（如8位）表示每個字元，那麼原始字元串的二進制形式應該是8個字元×8位= 64位。而這個字元串的赫夫曼編碼的長度是25位，進而壓縮率為25/64，或約為0.39。
那麼解碼過程是怎樣的呢？在使用字元集時，隻要把二進制串分割成8位或16位的片段，然後檢視每個片段表示的字元即可。在赫夫曼編碼中，由于編碼是變長的，我們不知道每個字元對應多少位編碼，是以看似很難将一個字元串解碼。其實，建立編碼的方式已經消除了這種潛在的困惑。
赫夫曼編碼的一個重要特征是用于表示一個字元的位串不會是表示另一個字元的位串的字首。是以，在從左到右掃描一個位串時，每當發現一個位串對應于一個字元，那麼這個位串就一定表示這個字元，該位串不可能是更長位串的字首。
例如，如果下列位串是用上面的表建立的：
1010110001111011
那麼它隻會被解碼為單詞board，沒有其他的可能性。
那麼，赫夫曼編碼是如何建立的呢？雖然建立赫夫曼編碼的詳細過程不屬于本書的介紹範圍，但是我們可以讨論一下要點。由于赫夫曼編碼用最短的位串表示最常用的字元，是以首先需要列出要編碼的字元的出現頻率。出現頻率可以是字元在某個特定文檔中出現的次數（如352個e、248個s等），也可以是字元在來自特定領域的示例文本中出現的次數。頻率表則列出了字母在一種特定語言（如英語）中出現的頻率。使用這些頻率，可以建構一種二進制代碼的結構。建立這種結構的方法確定了最常用的字元對應于最短的位串。