中文名：编码机制

外文名：encodingmechanism

编码：信息从一种格式转为另一种的过程

字符编码机制：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，编码形式为。所有节点的编码区间都是其祖先节点的编码区间的子集。也就是说，节点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)。

以“声”为纲，通过“形”“声”组配的造字方法将不断地认识到的、有上下位概念关系的现实现象编制成语言的“码”，这是汉语基础性编码机制的忠实反映，因而在长期的历史发展过程中能以不变应万变，历经假借、拼音化、外语借字、计算机语言信息处理等等的冲击而屹立不动。

这种造字体系，尽管有诸多复杂的情况需要人们进行具体的分析，但仍不失为汉语基础性的语汇、语义研究的一根重要的拐棍。这种以“声”为纲而辅之以“形”的造字原则，每一个字的字义清楚、明确，专门指称某一类特定的现实现象(请比较上述“曾”声各字的字义关系)，满足了人们认知现实的需要，但是不可否认，它也隐含有一些严重的弱点。这主要表现为:“声”的表义性功能负荷过重，往往要兼表若干个不同的意义(如“曾”声“多含重义加义高义”)，这在语言中的反映就是出现大量的同音字，而在文字上的反映就是随着社会的发展和人们对现实现象的认识的加深，字族的造字范围不断扩大，同一类事物往往因其某些特征的差异而需要造不同的字，因而字数过多。

这就是说，以“声”为纲的编码机制，“声”的功能负荷过重，而“形”的功能负荷却相对较轻，因为一个“形”只辅助表示“声”义的一个下位概念。不同的字形虽然可以在书面语中区别同音字，但无法减轻口语中字音的功能负荷，无法减轻人们的记忆负担。在社会生活比较简单的情况下，这种编码原则是能够满足人们的交际要求的。