XML文档树树中每个结点对应唯一ID号

概念：

（1）SLCA结点：最小的包含所有关键字的结点.

对于查询Q ={ a，b}来说,SCLA结点有：x1,x4

（2）ELCA结点：在排除以它的后代结点为根的子树中所有关键字之后,以它为根的子树仍然包含所有查询关键字

对于查询Q ={ a，b}来说,ELCA结点有：x1,x2,x4

一、求解所有的SLCA(最小最低公共祖先)结点

（1）stack算法

基本思想：先序遍历、后序（自底向上）处理所有包含关键字的结点

1. 从小到大遍历a,b两个关键字倒排表中的编码，依次入栈，比较相邻编码，编码中不同部分出栈，出栈时判断其

是否为真正的SLCA；

2. 判断一个结点是否为SLCA结点，需要知道其包含查询关键字的情况。若其没有包含所有关键字，则将包含关键

字的信息传递给其父亲；若其包含所有关键字，则其是一个候选的SLCA（事实上第一个候选SLCA就是一个真

正的SLCA），其包含关键字的信息不传递给其父亲；

3. 按照上面的过程求出下一个候选的SLCA，判断其与前一个SLCA之间的祖先后代关系，若不是祖先后代关系，则

说明其是一个真正的SLCA.

（2）IL算法

基本思想：

1. 比较a，b两个关键字倒排表的长度，依次取最短倒排表中的一个编码到次短倒排表中求左右匹配；

左匹配：比该编码小的最大的编码，右匹配：比该编码大的最小的编码

2. 该编码分别和左右匹配得到两个LCA结点，其中编码较长的LCA结点为候选的SLCA结点；

（若还有第三个关键字，则拿该LCA结点到最长倒排表中求左右匹配，同理得到两个LCA结点，其中编码较长

的LCA 结点为候选的SLCA结点）

3. 处理最短倒排中的第二个编码，同理得到一个候选的SLCA结点，根据它们的祖先后代关系判断前一个候选SLCA

结点是否为真正的SLCA结点。

IL算法与Stack算法的不同点：

IL算法是从左到右遍历最短倒排表，用后一个候选SLCA判断前一个候选SLCA是否为真正的SLCA结点；

Stack算法是自底向上进行求解，用前一个候选SLCA判断后一个候选SLCA是否为真正的SLCA结点。

二、求解所有的ELCA(排他的最低公共祖先)结点

HashCount算法

基本思想：

1. 建立关键字的hashcount索引，记录某个结点包含关键字的个数；

2. 比较a，b两个关键字倒排表的长度，依次取最短倒排表中的一个编码入栈，比较相邻编码，编码中不同部分出栈

，出栈时根据其包含关键字个数情况判断其是否为真正的ELCA；

3. 若是ELCA结点，则需要将其包含关键字个数信息传递给父亲结点；若不是ELCA结点，说明其父亲结点是一个潜

在的ELCA结点；

4. 直至最短倒排表被遍历完为止。