編碼機制

編碼是信息從一種形式或格式轉換為另一種形式的過程，也稱為計算機程式語言的代碼簡稱編碼。用預先規定的方法將文字、數字或其它對象編成數碼，或將信息、數據轉換成規定的電脈衝信號，這個方法就是編碼機制。

基本介紹

• 中文名：編碼機制
• 外文名：encoding mechanism
• 編碼：信息從一種格式轉為另一種的過程
• 字元編碼機制：ASCII 碼、非ASCII 碼、Unicode
• 實質：將文字對象編成數碼的方法
• 套用領域：生物學、基礎科學、計算機科學

編碼機制

ASCII碼

在在計算機內部，所有的信息最終都表示為一個二進制的字元串。每一個二進制位(bit)有0和1兩種狀態，因此八個二進制位就可以組合出256種狀態，這被稱為一個位元組(byte)。也就是說，一個位元組一共可以用來表示256種不同的狀態，每一個狀態對應一個符號，就是256個符號，從0000000到11111111。

上個世紀60年代，美國制定了一套字元編碼，對英語字元與二進制位之的關係，做了統一規定。這被稱為ASCII碼，一直沿用至今。

ASCII碼一共規定了128個字元的編碼，比如空格"SPACE〃是32(二進制00100000)，大寫的字母A是65(二進制01000001)。這128個符號（包括32個不能列印出來的控制符號），只占用了一個位元組的後面7位，最前面的1位統規定為0。

非ASCII編碼

英語用128個符號編碼就夠了，但是用來表示其他語言，128個符號是不夠的。比如，在法語中，字母上方有注音符號，它就無法用ASCII碼錶示。於是，一些歐洲國家就決定，利用位元組中閒置的最高位編入新的符號。比如，法語中的6的編碼為130(二進制10000010)。這樣一來，這些歐洲國家使用的編碼體系，最多可以表示256個符號。

但是，這裡又出現了新的問題。不同的國家有不同的字母，因此，哪怕它們都使用256個符號的編碼方式，代表的字母卻不一樣。比如，130在法語編碼中代表了ě，在希伯來語編碼中卻代表了字母Gimel()，在俄語編碼中又會代表另一個符號。但是不管怎樣，所有這些編碼方式中，0-127表示的符號是一樣的，不一樣的只是128-255的這一段。

至於亞洲國家的文字，使用的符號就更多了，漢字就多達10萬左右。一個位元組只能表示256種符號，肯定是不夠的，就必須使用多個位元組表達一個符號比如，簡體中文常見的編碼方式是GB2312，使用兩個位元組表示一個漢字，所以理論上最多可以表示256x256=65536個符號。

這裡指出，雖然都是用多個位元組表示一個符號，但是GB類的漢字編碼與Unicode和UTF-8是毫無關係的。

Unicode

世界上存在著多種編碼方式，同一個二進制數字可以被解釋成不同的符號。因此，要想打開一個文本檔案，就必須知道它的編碼方式否則用錯誤的編碼方式解讀，就會出現亂碼。為什麼電子郵件常常出現亂碼?是因為發信人和收信人使用的編碼方式不一樣。

可以想像，如果有一種編碼，將世界上所有的符號都納入其中。每一個符號都給予一個獨一無二的編碼，那么亂碼問題就會消失。這就是Unicode，就像它的名字都表示的，這是一種所有符號的編碼。

Unicode當然是一個很大的集合，規模可以容納100多萬個符號。每個符號的編碼都不一樣，比如，U+0639表示阿拉伯字母Ain，U+0041表語的大寫字母A，U+4E25表示漢字"嚴"。

遺傳算法

遺傳算法

遺傳算法(GeneticAlgorithms，簡稱GA)以自然選擇和遺傳理論為基礎，結合適者生存規律與染色體的隨機信息交換機制。從本質而言，它是一種求解問題的並行全局的最佳化搜尋算法。遺傳算法在函式最佳化、自動控制、圖象識別、機器學習、規劃策略、信號處理、人工神經網路、分子生物學、最佳化調度等諸多領域顯示出了無比的優越性。毫無疑問，遺傳算法在21世紀的智慧型計算技術中占有重要的地位。

編碼機制是遺傳算法套用中的首要問題，它對遺傳算法的性能影響很大。

編碼機制分析

定義1　如果染色體的基因碼串為0和1的排列，則稱此染色體為二進制編碼染色體，相應的染色體編碼方法稱為二進制編碼.

定義2　如果染色體的基因碼串為0到9的排列，則稱此染色體為十進制編碼染色體，相應的染色體編碼方法稱為十進制編碼.

定義3　設自然數m，M滿足2≤m<M，如果染色體的基因碼串為0，1，2，…，m-1的排列，則稱此染色體為m進制編碼染色體，相應的染色體編碼方法稱為m進制編碼；如果染色體的基因碼串為0，1，2，…，M-1的排列，則稱此染色體為M進制編碼染色體，相應的染色體編碼方法稱為M進制編碼.

因為假設m<M，所以中有時稱m進制編碼為低進制編碼，稱M進制編碼為高進制編碼。

研究表明，基於二進制編碼的遺傳算法與十進制編碼的遺傳算法相比，通常情況下前者的搜尋效率高，較易收斂到最優值，並且尋優結果對交叉機率和變異機率魯棒性好。進一步地分析表明，低進制編碼遺傳算法在搜尋效率和最佳化結果魯棒性方面普遍優於高進制編碼遺傳算法.因此，在工程套用實踐中宜選用低進制編碼的遺傳算法。

文檔編碼

XML是一種專門為網際網路所設計的標記語言，它的重點是管理信息的數據本身，數據的顯示交給其他技術解決。隨著近些年WebService的蓬勃發展，XML越來越多地活躍在數據交換和存儲領域。

XML文檔編碼機制是指為XML文檔樹的每個節點賦予一個特定的編碼，以便於能夠通過編碼直接判斷XML文檔樹中的節點之間的祖先一後裔關係，而不需要對原XML文檔進行導航遍歷。依據編碼的原理，可以分為基於區間的編碼機制和基於路徑的編碼機制。基於區間的編碼機制將每個節點編碼為一個區間，而基於路徑的編碼機制則是依據節點的路徑將每個節點編碼為一個數字。

基於區間的編碼機制

有關文檔編碼的早期研究多集中在區間編碼法上。其主要思想在於為XML文檔樹中的每一個節點賦予一對正整數begin和end，編碼形式為[begin，end]。所有節點的編碼區間都是其祖先節點的編碼區間的子集。也就是說，節點a是節點d的祖先的充分必要條件是a．hegin≤d．begin並且a．end>，d．end。

Li．Moon(xiss)編碼機制的主要思想在於：XML文檔樹T中的每個節點被賦予二元組(order，size)，order是節點的擴展先序遍歷序號，size是節點的後裔範圍。因此，文檔樹中節點a和節點d存在祖先一後裔關係，若且唯若a．order<d．order且d．order+d．size≤a．order+a．sizeo另外，每個節點被賦予一個大於或者等於零的值depth，其表示該節點在文檔樹中的層次。

Zhang編碼機制的主要思想在於：XML文檔樹T中的每個節點被賦予二元組(begin，end)，begin是節點在XML文檔中的開始位置，end是節點在XML文檔中的結束位置。因此，文檔樹中節點a和節點d存在祖先-後裔關係，若且唯若a．begin<a．end且a．end>d．end。另外，每個節點被賦予一個大於或者等於零的值depth。其表示該節點在文檔樹中的層次。

Wan編碼機制的主要思想在於：XML文檔樹T中的每個節點被賦予二元組(order，maxOrder)。order是節點的擴展先序遍歷序號，maxOrder是節點的後裔編碼中擴展先序遍歷序號的最大值。因此，文檔樹中節點a和節點d存在祖先-後裔關係，若且唯若a．order<d．order且d．maxOrder≤a．maxOrder。

Dietz編碼機制的主要思想在於：XML文檔樹T中的每個節點被賦予二元組(pre，post)，pre是節點的先序遍歷序號，post是節點的後序遍歷序號。因此，文檔樹中節點a和節點d存在祖先一後裔關係，若且唯若a．pre<d．pre且d．post<a．post。

基於預留算法的編碼機制的主要思想在於：XML文檔樹T中的每個節點被賦予二元組(order，size)，order是節點的擴展先序遍歷序號，size是預留的編碼空間。基於數據模式和更新模式進行一定運算，從而獲得預留的編碼空間。

區間編碼機制根據區間判斷節點關係，其優點是編碼簡單，節點編碼的平均長度為O(log(n))；缺點是使用非等值比較進行節點關係判斷，並且需要單獨提供層次信息。

位向量編碼機制

位向量編碼機制的主要思想在於：XML文檔樹T中的每個節點與一個n位向量y對應，n是樹T中節點的數目。在向量的某個位置i上值“1”惟一標識了第i個節點，並且每一個後裔節點繼承了其祖先的所有“1”位。若節點a是d的祖先，若且唯若a．v&d．v=a．v；若節點d是a的後裔，若且唯若d．va．v=d．v。位向量編碼將節點與忍位向量對應，其優點是容易判斷節點間的層次關係；缺點是不支持更新操作，編碼空間較大。

PBiTree編碼機制的主要思想在於：將XML文檔樹T轉化為完全二叉樹。然後按照”自底向上，自左至右”的順序為每個節點進行編號。PBiTree編碼按照節點在文檔樹中的位置進行編碼，其優點在於編碼簡單，節點編碼的平均長度為O(n)；並且使用等值比較進行節點關係判斷。缺點是不支持更新操作，需要單獨提供層次信息。

Dewey編碼機制(前綴編碼機制)的主要思想在於：將XML文檔樹中父節點的編碼直接作為其子節點編碼的前綴，也稱為前綴編碼。因此，文檔樹中節點a和節點d存在祖先．後裔關係，若且唯若a．code是d．code的前綴。Dewey編碼將XML文檔樹中父節點的編碼直接作為其子節點編碼的前綴，其優點是編碼簡單，節點編碼的平均長度為O(n)；支持更新操作。缺點是前綴操作比算術操作運算速度慢，因此該編碼方法效率較低。

素數編碼機制的主要思想在於：在自底向上素數編碼方法中，將每個XML文檔樹的葉節點按順序賦予不問素數，將父節點編碼為子節點編碼的乘積；在自頂向下素數編碼方法中，將根節點編碼為1，將每個節點編碼為來自父親的”父標記(parent-label)”和來自素數列的”個人標記(self-label)”的乘積。另外，當文檔樹過高的時候，可以對樹進行”分解(treedecomposition)。在自底向上素數編碼方法中，文檔樹中節點a和節點d存在祖先一後裔關係，當H僅當(a．code)mod(d．code)==0；在自頂向下素數編碼方法中，文檔樹中節點a和節點d存在祖先．後裔關係，若且唯若(d．code)mod(a．code)==0。素數編碼採用整除運算判斷祖先一後裔關係，其突出的優點是較好地支持更新操作，並且對於XML樹的扇出不敏感；整除判斷運算速度較快。其缺點是編碼長度較大。

BBT編碼機制的主要思想在於：將根節點編碼為1。將某節點的最左兒子節點編碼為其父節點編碼的2倍，其他兒子節點的編碼為其最近左兄弟節點編碼乘以2再加1。還提出支持更新的BBT編碼方法，其主要思想在於：提供額外的信息來表示一個節點在其兄弟節點中的位置序號，而不能利用BBT編碼本身所包含的兄弟節點的位置信息。另外，為了節省存儲空間，BBT編碼可以採用分塊存儲的方法。BBT編碼機制的優點是祖先．後裔關係的判斷採用計算機常用的移位操作，具有很高的運算速度；較好地支持更新操作，僅在刪除非最左葉節點或者添加節點到非最左位置時會導致同一層兄弟節點之間的順序錯誤，為了更好地支持更新，可以增加分量記錄節點在其所在層中的順序。其存在的問題在於編碼長度較長，對於節點數為n的文檔樹而言，BBT編碼的長度為O(n)。

基礎性

以“聲”為綱，通過“形”“聲”組配的造字方法將不斷地認識到的、有上下位概念關係的現實現象編製成語言的“碼”，這是漢語基礎性編碼機制的忠實反映，因而在長期的歷史發展過程中能以不變應萬變，歷經假借、拼音化、外語借字、計算機語言信息處理等等的衝擊而屹立不動。

這種造字型系，儘管有諸多複雜的情況需要人們進行具體的分析，但仍不失為漢語基礎性的語彙、語義研究的一根重要的拐棍。這種以“聲”為綱而輔之以“形”的造字原則，每一個字的字義清楚、明確，專門指稱某一類特定的現實現象(請比較上述“曾”聲各字的字義關係)，滿足了人們認知現實的需要，但是不可否認，它也隱含有一些嚴重的弱點。這主要表現為:“聲”的表義性功能負荷過重，往往要兼表若干個不同的意義(如“曾”聲“多含重義加義高義”)，這在語言中的反映就是出現大量的同音字，而在文字上的反映就是隨著社會的發展和人們對現實現象的認識的加深，字族的造字範圍不斷擴大，同一類事物往往因其某些特徵的差異而需要造不同的字，因而字數過多。

這就是說，以“聲”為綱的編碼機制，“聲”的功能負荷過重，而“形”的功能負荷卻相對較輕，因為一個“形”只輔助表示“聲”義的一個下位概念。不同的字形雖然可以在書面語中區別同音字，但無法減輕口語中字音的功能負荷，無法減輕人們的記憶負擔。在社會生活比較簡單的情況下，這種編碼原則是能夠滿足人們的交際要求的。