一种外存后缀数组结构算法工程实现及特性评估

《一种外存后缀数组结构算法工程实现及特性评估》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一种外存后缀数组结构算法工程实现及特性评估第一章绪论1.1研究背景与意义随着对后缀数组研究的不断深入，后缀数组在处理文本数据时所具备的优势日益凸显，被广泛的应用于生物信息学、网络检索、频繁字符串挖掘以及顺序分析和聚类分析等领域。在生物信息学中，DNA序列可以看作是一个在{A、C、G、T}字符集上的文本数据。这样，对DNA的处理也就相当于对一个文本数据进行处理。例如，我们要判断一个小的DNA片段属于哪一个完整的DNA序列时，我们需要将小的DNA片段与每一个完整的DNA序列进行配对，如果将DNA如上面所说看成是一个由A、C、G、T四个字母组成的文本数据，那么这个DNA匹配

2、问题就可以转化为如何在一个文本数据集（DNA库）中找出某个特定字符串（DNA片段）所在位置的问题。在网络检索中，搜索引擎的主要工作就是从海量的网络数据资源中快速、准确地检索出用户所查找的信息，而这实际上也是在一个文本数据集（网络资源）中找出某个特定字符串（用户输入的关键字）的问题。为了解决这类问题，后缀树和后缀数组作为两种文本数据索引结构被提了出来。后缀树与后缀数组是文本数据处理中两个强有力的工具。后缀树的概念最早由anber和Myers[1]提出了一种用来替代后缀树的数据结构，即后缀数组。他们将一个字符串的后缀数组定义为该字符串所有后缀按字典序排列的次序。1.2后缀

3、数组构造算法的研究现状在后缀数组被提出以前，后缀树在文本数据处理的相关领域被广泛应用。但后缀树的建立与存储需要占用大量的空间，并且各领域需要处理的文本数据日益增长，后缀树空间效率低的劣势越发凸显，导致了后缀树构造算法内存瓶颈[5]问题的产生，极大的限制了后缀树的应用范围。为解决这一问题，人们开始寻找一种结构精简的、具有很高空间效率、并且具有后缀树所具备功能的数据结构来替代后缀树。后缀数组提出后，凭借其结构精简、编程实现简单以及空间效率高等特性，使其成为后缀树一种很好的替代[6]。自后缀数组的概念被提出以后，大量的后缀数组构造算法被提了出来，这些后缀数组构造算法的主题思

4、想大体上分为三类[7]：倍增算法、归纳拷贝算法、分治递归算法。倍增算法是在后缀数组概念提出之初被提出的，其大致构造思想是：对字符串所有长度为2k(k=0)的子串进行排序，再利用基数排序或多关键字快速排序等方法，在O(n)时间内计算出其所有长度为2(k+1)的子串的排名情况，进而可以递推出字符串所有长度为2(k+2)的子串的排名情况，经过log2n步，一直到2(k+m)≧n，就可以得到字符串所有后缀的排名。因为倍增算法总共需要进行log2n步，每一步的时间复杂度为O(n)，所以算法的总体时间复杂度为O(nlog2n)。但是倍增算法是对字符串所有长度为2k的子串进行排序，

5、在算法执行过程中需要利用大量额外的空间对这些子串进行存储，所以倍增算法的空间复杂度一般较大。典型的倍增算法有：U.Manber与G.Myers提出的MM算法[1]、R.M.Karp，R.E.Miller与A.L提出的KMR算法[8]、J.N.Larsson与K.Sadakane提出的LS算法[9]等。..第二章几种主流后缀数组构造算法介绍2.1相关名词及符号介绍哨兵[20]：为了便于处理，需要在字符串s的末尾添加一个特殊字符，该字符不属于s所属字符集，并且小于s中任意一个字符，我们把这一字符称之为哨兵。（在后缀数组构造算法中，哨兵已经被广泛采用[7]）。前继字符：在字

6、符串s中，位于字符s(i)或者后缀suf(s,i)前面的字符，我们把该字符称为s(i)或者suf(s,i)的前继字符，表示为prec(s,i)。显然，prec(s,i)=s(i-1)，并且s(0)没有前继字符。L型字符与S型字符[20]：如果字符s(i)满足i=n-1或者满足s(i)<s(i+1)，则该字符为S型字符；如果s(i)>s(i+1)，该字符为L型字符；如果s(i)=s(i+1)，则s(i)与s(i+1)的类型相同。LMS字符[20]：如果字符s(i)是S型，并且字符s(i-1)为L型，则字符s(i)为LMS字符。L型后缀、S型后缀和LMS型后缀

7、[20]：每个后缀与该后缀的首字符具有相同的类型，例如，如果s(i)为L型，则字符suf(s,i)也为L型。LMS子串[20]：如果一个子串s[i...j]中，s[i]和s[j]都是LMS型字符，并且在s[i]与s[j]之间没有其他的LMS字符，则子串s[i...j]为LMS子串。特殊的，哨兵也是一个LMS子串。LMS前缀[20]：如果s的一个子串s[ij]，i<j，满足字符s[j]是LMS字符，并且在子串s[i+1j-1]中没有一个LMS字符，那么我们把子串s[ij]称为LMS前缀，记为pref(s,i)。LMS前缀的类型与其首字符s[i]的