基于XML后缀数组构造算法
1 引言
XML（extensible markup language）是由W3C开发的一个标准，XML 1.0是全球接受的规范。XML文档是一个既包含数据，又包含描述数据结构标记的纯文本文档。任何两个要交换XML数据的应用程序都能进行交换，与平台或编程语言无关。因此，XML在WEB应用程序开发中得到了广泛的应用。后缀数组（Suffix Array）是一个简单，易于编码且性能良好的数据结构。广泛应用于文本和计算生物学等领域的字符串匹配问题[4,5]，包括：（1）Burrows-Wheeler压缩算法；（2）构造简洁且被压缩的索引；（3）在WEB查询中对用户的查询结果进行聚类；（4）用于计算生物学中的基因组分析。本文在构建XML文档索引机制的基础之上，介绍了一种简单易行且高效的后缀数组构造方法。
2 基于XML后缀数组构造算法
构造基于XML后缀数组一般分为两步：
（1）建立XML文档的索引；
（2）构建索引的后缀数组；
下面详细说明这两个过程。
2.1 XML文档索引机制的建立
在[6]中提出了一种搜索方法——相关文章链接技术，其原理是：对文档建立索引，可以是全文索引，或者是词（表达文章主要概念的词）索引。这些词可以是名词、动词、形容词等实词（连词、助词等不包含具体意义的虚词被过滤掉）。在进行相关文章链接处理时，首先对输入的文档进行分析，找到有意义的索引词，再到索引库中查找与之相关的文档，并记录查询的结果。然后根据每篇文档中包含的索引词的多少、词频、文档长度信息来计算相似度。最后根据相似度的大小进行排序，就可以找到最相似的文档。构造XML文档的后缀数组首先应该建立其索引。由于XML文档结构相似性，下面以一个XML格式描述的[1]“书标记“为例来说明XML文档索引机制的建立规则：
<book >
<sn>23124</sn>
<title>software engineering</title>
<author>Angela Yochem</author>
<price unit=”yuan” >56</price>
<sum unit=”piece”>10</sum>
</book>
有关XML合法性规则参见http://www.w3.org/xml/schema 。对于XML格式的数据，标签经常描述实体的属性名，计量单位等特性，而PCDATA中则经常描述的是各种重要的数值。结束标签在逻辑上仅仅表示一个信息单位的结束。因此，在XML格式文档中建立索引的位置有：
（1） 每个开始标签“字“，如book，sn
（2） 在开始标签中所含的每个由空格分开的“字“或“短语“，如currenty
（3） PCDATA中的“每个字符“,例如<name>与</name>之间的每个字符都应建立索引，以便能迅速找到包含在它中的任一个字符串子集。
在上例中若用户输入查询关键字”book”，则查询器应输出位于<book>和</book>之间的全部内容；若用户输入查询关键字“unit”,则应显示{price unit="yuan"，sum unit="piece"}。
用上面提出的3条规则对XML文档建立索引，上面的“书标记”XML文档索引为：book,sn,author,software,engineering, price,unit,sum。
2.2 后缀数组的构造算法
为了便于理解该算法，首先来看几个定义[2]：
定义1 后缀数组（suffix array）是字符串处理应用中使用的各种数据结构的基础。S'表示在字符集∑上的一个字符串，$ ∑是唯一的终结符且小于字符集∑中的任一字符，S=S'$是在字符串S'的末尾加上终结符得到的一个新字符串，如果|S|表示字符串的长度，S[i]表示S的第i个字符，那么suffi=S[i]S[i+1]…S[|S|]是字符串S的第i个后缀数组。例如：S'=“asdfgh”，在其后增加一个结束符$，得到S=“asdfgh$”，那么，S 2=“dfgh$”是S的第2个后缀数组。
定义2 索引数组I（index array）： 描述后缀数组位置的数组。如果数组I[0..n]是后缀数组Si的索引数组,那么，在I中定义了后缀数组Si在排序过程中的位置变化。其值是通过对后缀数组中的字符串的前k个字符比较得出的长度小于k的后缀顺序，因此，必须满足以下3个条件：
1） 若0〈=l〈k， x[i..i+l-1]=x[j..j+l-1]且x[i+l]<x[j+l],则Si<k Sj;
2） 若0〈=l〈k， x[i..i+l-1]=x[j..j+l-1]且x[i..i+k-1]=x[j..j+k-1],则Si=k Sj;
3） 若0〈=l〈k， x[i..i+l-1]=x[j..j+l-1]且x[i+l]>x[j+l],则Si>k Sj;
定义3 信号数组V（signal array）：是排序进行程度的标志。V是一个与S长度相等的数组,通过该数组中元素值是否相等来表示排序的结束与否。经过k次迭代后，如果V中存在相等的元素，则将具有相同V值的元素划分为一组，表明该数组元素的前k个字符一定是相同的；如果在V中，所有元素均不相等,则表示字符串已经有序，排序过程结束。因此,该数组必须满足以下的三个条件：
1） 若Xi<Xj，则 V[i]<=V[j]；
2） 若Xi>Xj， 则 V[i]>=V[j]；
3） 若Xi!=Xj，则 V[i]!=V[j]；
定义4 规模数组L （size array）：表示该组元素规模的数组，为了提高排序算法的时间性能而引入的。对于无序组L[f]=I[f..g]=g-f+1；对于有序的组：L[f]=I[f..g]=-（g-f+1）。
为了提高算法的空间复杂度，必须更新每一个数组的值，在进行第j次排序时，k=2j-1，表示用小于k的次序来遍历所有的分组，第一组以索引0开始,元素个数表示为L[0],用V[s+k]对组 I[0..size-1]中的后缀进行排序；下一组从索引g=size处开始,对组I[g..g+S[g]-1]中的后缀进行排序；当遍历了所有不同的分组后,将其划分为小于2k有序，如果同一分组g中连续的I[i]和I[i+1]具有不同的值，即V[I[i]+k]！=V[I[i+1]+k]，则在索引i和i+1之间划分分组，同时更新每一分组中元素的个数，最后，更新V[I[i]]的值。
2.3 构造算法的步骤如下：
1） 通过第一个字符对Si进行排序，初始化各数组的值；
2） 对于j=1，k=21-1=1，用基于比较的排序算法对在同一组中无序的元素用第二个字符进行排序；
3） 划分分组并更新数组V；
4） 将连续的有序分组合并为一个分组；
5） 如果L中的元素值的绝对值等于所有元素个数n，则说明所有元素已经有序，排序过程结束；
6） 否则，j=j+1；k=2j-1=2*k；转向[2]；
3 算法的实例与实验结果分析
3.1 算法的实例
以S=“upcfpsopuupcf$”为例，构造其后缀数组的过程如表1所示：
表1：构造S的后缀数组
kk
i
xi
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13
u u p c f p s o p u u p c f $
I[iV[I[i]+k]]
S[L[i]
V[V[I[i]]
1313 2 11 3 12 6 1 4 7 10 5 0 8 9
-1-1 2 2 -1 4 -1 3
0 1 1 3 3 5 6 6 6 6 10 11 11 11
1
VV[I[i]+k]]
I[I[i]
S[L[i]
V[V[I[i]]
3 3 6 0 1 10 11 1 6 11 6
2 11 12 3 1 10 4 7 0 9 8
-1-1 2 -3 2 -3 2 -1
1 1 3 4 6 6 8 9 11 11 13
222
V V[I[i]+k]]
I[I[i]
S[L[i]
V[V[I[i]]
8 0 4 3 1 1
11 2 10 1 0 9
-1-11 2 -1
1 2 6 7 11 11
444
VV[[I[i]+k]]
I[I[i]
s[L[i]
V[V[I[i]]
8 0
9 0
-1-14
11 12
I[i
1313 11 2 12 3 6 10 1 4 7 5 9 0 8
S的后缀数组为[13，11，2，12，3，6，10，1，4，7，5，9，0，8]。
3.2实验结果
在Intel(R) 4 CPU,256MB内存的计算机上，用本文介绍的方法对3个不同大小的XML文档建立后缀数组并在此基础上进行搜索，运行结果如表2所示：
表2 运行结果
文件(Byte）
构造索引的时间（s）
构造后缀数组的时间（s）
检索时间
492，644
1119
13951
<1
884，579
3360
44504
<0.1
1，822，577
13481
203571
<0.1
实验结果表明：随着文档的逐渐增大，该构造算法的性能更优。对于体积为n的文本文件，该算法的空间复杂度是5n，时间复杂度为O(nlogn)。
4 结论
本文在提出建立XML文档索引机制的基础上，介绍了一种快速构造后缀数组的算法，并以实验表明了该算法适用于XML文档，为开发基于XML文档的WEB搜索引擎提供了一种方案。如何快速的构造个别字符修改的索引文件的后缀数组是下一步的研究方向。
