Dietz编码机制的主要思想在于:XML文档树T中的每个节点被赋予二元组(pre,post),pre是节点的先序遍历序号,post是节点的后序遍历序号。因此,文档树中节点a和节点d存在祖先一后裔关系,当且仅当a.pre
基于预留算法的编码机制的主要思想在于: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)。
基础性
以“声”为纲,通过“形”“声”组配的造字方法将不断地认识到的、有上下位概念关系的现实现象编制成语言的“码”,这是汉语基础性编码机制的忠实反映,因而在长期的历史发展过程中能以不变应万变,历经假借、拼音化、外语借字、计算机语言信息处理等等的冲击而屹立不动。
这种造字体系,尽管有诸多复杂的情况需要人们进行具体的分析,但仍不失为汉语基础性的语汇、语义研究的一根重要的拐棍。这种以“声”为纲而辅之以“形”的造字原则,每一个字的字义清楚、明确,专门指称某一类特定的现实现象(请比较上述“曾”声各字的字义关系),满足了人们认知现实的需要,但是不可否认,它也隐含有一些严重的弱点。这主要表现为:“声”的表义性功能负荷过重,往往要兼表若干个不同的意义(如“曾”声“多含重义加义高义”),这在语言中的反映就是出现大量的同音字,而在文字上的反映就是随着社会的发展和人们对现实现象的认识的加深,字族的造字范围不断扩大,同一类事物往往因其某些特征的差异而需要造不同的字,因而字数过多。
这就是说,以“声”为纲的编码机制,“声”的功能负荷过重,而“形”的功能负荷却相对较轻,因为一个“形”只辅助表示“声”义的一个下位概念。不同的字形虽然可以在书面语中区别同音字,但无法减轻口语中字音的功能负荷,无法减轻人们的记忆负担。在社会生活比较简单的情况下,这种编码原则是能够满足人们的交际要求的。