2018, Vol. 39
2. 东北大学 计算机科学与工程学院, 辽宁 沈阳 110169
2. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
近似字符串匹配和连接技术, 即在给定的字符串集合中搜索相似的字符串和在两个字符串集合中搜索近似的字符串对, 在数据清洗[1]、拼写检查[2]、Web检索[3]、近似拷贝检测[4]、近似命名实体识别[5]、信息检索和生物信息学[6-7]中具有十分重要的应用.因此, 近年来近似字符串匹配[8-11]和近似字符串连接技术[12-13]受到了数据库领域研究人员的高度关注.
字符串索引技术是近似字符串匹配算法的基础和算法高效性的保障.后缀树、后缀数组、BWT、倒排链表及其变形和hash表技术等字符串索引技术被广泛应用.B+树和小波树等数据结构也被应用到BWT及其索引字符串的技术中.其中, 基于BWT的字符串索引技术及基于该技术的确切子串的查找算法因其高压缩、灵活和适应大规模数据的特点被广泛地应用到生物信息学中来解决read mapping问题, 取得了良好的效果[5-7].
本文研究基于BWT的支持字符串集合上带有匹配字符串长度和匹配子串位置约束的子串查找问题的高效大规模索引方法.该问题较基因组上的BWT索引结构增加了字符串集合中字符串长度、字符串上子串位置等限制条件.本文在保持基于BWT的索引方法的优点的同时, 提出了针对上述约束条件的优化方法.实验结果表明, 本文的索引方法能够高效地解决带有上述约束条件的子串的精确匹配查找, 为进一步解决字符串近似匹配算法中最优种子选择或最优segment分段提供了快速的频率计算方法.
1 问题定义定义1(带有长度和位置约束的子串的查找问题):设S={s1, s2, …, sn}表示一个字符串集合; r表示一个查询字符串; rsub是r的一个子串；τ表示查找的编辑距离门限.下面的公式表示在字符串集合S上的带有长度和位置约束条件的确切的子串的查找结果,
|
(1) |
式(1)满足如下关系:
1) SID[posi, posi+|rsub|-1]=rsub;
2) abs(|sID(-|r|)≤τ;
3) abs(posi-pos(rsub))≤τ.
定义1给出了带有字符串长度和位置约束的子串确切查找问题, 该问题是现存的大多数近似字符串匹配及生物序列比对方法的基础问题.为了快速地解决定义1中的问题, 现有算法较多利用倒排链表对字符串集合进行索引；然而, 倒排链表索引具有如下的问题:①索引的子串长度通常是固定的, 无法实现对任意长度的子串进行索引；②索引的大小随着支持的子串的长度迅速增长, 从而无法应用到大规模的字符串集合.另一方面, 基于BWT和后缀数组的索引结构被大量地应用到基因组的序列比对问题中.该索引能够应对任意长度子串的查找, 并以其良好的压缩性能能够应对大规模的字符串数据.
2 索引算法 2.1 BWT和后缀数组设Σ表示字符串X对应的字母表.＄表示一个不属于Σ, 且比Σ中所有字符都要小的字符.字符串X=a0a1…an－1以字符＄结尾, 即an-1=’＄’.X[i]=ai表示X的第i个字符.X[i, j]=ai, …, aj表示X的一个子串, Xi=ai, …, an－1表示X中从ai开始的后缀.字符串X的后缀数组SA是一个由n个数字{0, 1, …, n－1}的一个排列构成的整数数组.SA[i]等于X中第i小的后缀的开始位置.字符串X的BWT把X变成字符串B, 字符串B满足条件B[i]=X[SA[i]-1], 如果SA[i]≠0, 则B[i]=’＄’.
2.2 确切子串查找设C(a)表示在X[0, n-2]中比a小的字符出现的总的次数.OCC(a, i)表示B[0, i]中字符a出现的总的次数.假设[L(W), H(W)]表示子串W在X出现的后缀数组区间.Ferragina和Manzini证明了aW的后缀数组区间可以由下面的公式进行计算[14]:
|
(2) |
|
(3) |
其中, aW表示字符串W前面再加一个字符形成的字符串.若L(aW)>H(aW), 表明aW不是X的子串.因此, 子串W在X出现的后缀数组区间可以通过反复调用上面的式(2)和式(3), 从W的最后一个字符开始求解.如果计算到某一步出现L(aW)>H(aW), 计算可以终止, 并且可以得出aW不是X的子串的结论.
2.3 利用BWT索引字符串数组BWT和后缀数组是对一个字符串的变换和索引结构.当直接利用该方法解决定义1中的问题时, 将字符串集合S中的所有字符串连接成一条长的字符串, 记为Sup(S)，并对Sup(S)建立索引和应用.2.2节中给出了确切子串查找方法，这样做出现了如下的问题:①索引到很多假阳性结果.例如:在字符串集合S中存在相邻的两个字符串ai="abcd"和ai+1="efgh", 当查找子串rsub="cdef"时, 会查找到上面两个字符串给出的假阳性结果.②给出的结果并不一定满足字符串长度和子串位置的约束条件, 并且进一步计算比较耗时.例如:在一个例子中, 处理url字符串集合, 该集合中字符串绝大多数包含“http”, “com”和“www”等子串, 若要查找包含“http”的长度不超过10的字符串, 上面的方法返回的却是所有的包含“http”的字符串.对于子串的位置, 结果也是一样的.③上述方法给出的后缀数组区间表示Sup(S)上的位置.如何将该位置映射到具体的字符串ID和该字符串上的位置，由于在近似字符串查找算法中该操作是十分频繁的, 因此即使高效的hash表的方法, 也是十分耗时的.很好地解决以上具体应用中的3个问题是利用BWT方法高效地索引字符串集合来回答带有字符串长度和子串位置等约束条件的子串查找问题的关键.为了克服上述的问题, 本文提出了如下方法:
1) 将字符串集合中的字符串按照长度进行分组.首先将所有的字符串按照长度进行排序, 然后从首个字符串开始按照Lg个不同长度的字符串分为一组的方式进行分组, 假设分组后的字符串组分别为G1, G2, …, Gk.lenstart(i)和lenend(i)表示Gi组的字符串的最小长度和最大长度.为了解决定义1中的问题, 首先验证(lenstart(i), lenend(i))与(|r|-τ, |r|+τ)是否有交集; 如果交集不为空, 利用式(2), 式(3)计算该组的后缀数组区间, 否则不进行计算.这样实现在较小的长度范围内进行确切的子串查找.
2) 设Π表示一个不属于Σ, 且比Σ中所有字符都要大的字符.对于每一组字符串Gi, 在每个字符串的尾部都插入一个字符Π.
3) 设lenend(i)表示第i组字符串集合中最长的字符串的长度.经过步骤2), 所有的字符串的长度均增加一个, 最长的字符串的长度变为lenend(i)+1.在Gi中所有长度小于lenend(i)+1的字符串的尾部插入字符Π, 使得所有的字符串的长度均为lenend(i)+1.这样每组字符串集合中的字符串长度都相等, 且均为lenend(i)+1.
经过以上3个步骤, 将每组字符串按照原来的排列顺序进行连接, 形成一个长串, 记为Sup(Gi).每组建立字符串Sup(Gi)的BWT索引, 记为index_BWT(Gi)={SA, OCCi, Ci, Bi}, 将多组字符串的索引称为分组补全分隔符的BWT索引, 记作G_BWT(S)={index_BWT(Gi)}.
2.4 G_BWT(S)性能分析1) 利用字符串集合S的分组补全分隔符的BWT索引G_BWT(S)进行确切子串rsub的查找时调用式(2)和式(3)的最小和最大次数分别为|rsub|×⌊(2τ+1)/Lg」+λ和|rsub|×「(2τ+1)/Lg」+λ, 其中λ=1；如果(2τ+1)/Lg < 1, λ=2.其次, 假设共查找n组, 则检索到的不符合条件的字符串的长度数量占符合条件的长度的比例为nLg /(2τ+1)-1.
2) 利用G_BWT(S)检索到的结果不会出现假阳性结果.原因是任意两个相邻的字符串之间至少有一个分隔符连接.其次, 假设rsub在Gi中检索到的后缀数组区间为[1, h], 那么∀j∈[1, h], 位置SAi[j]对应的Gi中字符串的ID为SAi[j]/(lenend(i)+1), 该位置所对应在这个字符串上的位置为SAi[j]/%(lenend(i)+1), 即通过一次除法和一次取余运算即可得到(IDi, posi)信息.
3) 对于没有压缩的BWT索引, 即SAi, OCCi完全存储的情况下, 分组补全分隔符的索引与不做任何操作直接建立BWT索引的存储空间花费是相同的.因为每个组只需要存储字母表Σ中字符所对应的后缀数组部分, 补全的分隔符部分位于整个后缀数组的最后, 不需要进行存储.OCCi, Bi也是仅需要存储Σ中字符对应的行和W串.但是, 当索引进行压缩存储时, 由于需要利用lf-mapping来计算后缀数组的值, 会用到字符Π对应的后缀位置和OCC的值, 因此需要每个组存储补全分隔符连接长串的完整index.这时索引的大小要有所增加, 但也可通过分组的大小和索引的压缩参数来控制索引的大小, 对索引性能的影响很小.
3 实验结果与讨论 3.1 数据集和实验环境本文方法在Win7x64位操作系统下Visual Studio2010编程环境下利用C++语言实现.CPU配置为Intel(R) Core(TM) i7-2600 CPU processor @3.40 GHz并配备16 GB内存.数据集见表 1.
|
表 1 数据集 Table 1 Dataset |
表 1中, N和n分别表示各个数据集中包含的待查询字符串和查询字符串的数量.本文所有的测试结果均在单线程的设置条件下测得.
3.2 构建索引G_BWT(S)对每个字符串集合数据进行分组.在分组实验中考察两个指标:①每组集合的大小; ②每组字符串覆盖的长度范围.由于分组字符串集合的大小直接决定构建G_BWT(S)过程中对内存的需求, 所以将最大的字符串集合分组的大小设置为50 MB.另外, 尝试了各种长度范围Lg的取值, 在查询范围1≤τ≤12的情况下, 通过实验测得Lg=5对应的实验结果是最优的.在这样的条件下, DBLP, PubMed和URL数据集分别被分成了80, 61和20个组.
对于每个组, 首先计算SAi, 然后利用公式B[i]=X[SA[i]-1]计算B[i], 最后计算OCCi和Ci两个数组.其中SAi是最耗时的, 计算SAi的过程实质是一个排序过程.由于排序的后缀数量太大, 并且有些后缀需要比较多次才能得出大小关系, 所以, 通常花费很长的时间.本文利用C++语言编写程序, 利用B+Tree数据结构计算SAi.得到的最终G_BWT(S)信息见表 2和表 3.OCC和SA分别需要|Σ|·|X|和|X|个整数的存储空间.如果按照一个整数需要4个Bytes, 一个字符需要1个Byte来计算, OCC和SA分别需要原字符串X的104和4倍的存储空间.对于PubMed和DBLP数据集, 分别需要大约9 GB和33 GB的存储空间.因此, 对其进行压缩存储.表 2中, OCCgap和SAgap分别表示OCC和SA压缩存储的参数.
|
|
表 2 G_BWT(S)参数 Table 2 Parameters of G_BWT(S) |
|
|
表 3 G_BWT(S)大小 Table 3 Size of G_BWT(S) |
为了验证G_BWT(S)的可用性和高效性, 利用其进行近似字符串查找.表 1中给出了各个数据集上的查询个数.在PubMed和DBLP数据集上的查询范围为1≤τ≤12, URL数据集上的查询范围为1≤τ≤5.为了验证本文检索方法的高效性, 利用直接连接数据集, 构建BWT索引的方法进行了对比实验.由于直接连接字符串时, 各个字符串的长度不同, 利用哈希算法实现从后缀位置到字符串ID和该位置在该字符串上的位置的计算.实验中, 对于查询范围τ, 将查询字符串分为τ+1段segments, 利用本文提出的方法和上述对比方法计算每段segments的后缀数组区间, 并对其中每个位置计算对应字符串的ID和位置POS.图 1给出了确切子串的查询时间.随着τ的增加, 每个query字符串被分成τ+1个segments, segment的长度变得更短, 因此, 查询更加频繁.要计算的后缀位置的数量迅速增加.图 1给出了在每个τ值下, 计算所有segments匹配的后缀位置及映射成数据库中字符串的ID和POS的总的计算时间.因此, 随着τ的增加, 时间花费快速增加.图 1中“*_a”表示本文提出的索引方法.“*_b”表示直接连接数据库中字符串并构建BWT索引的方法.图 1表明, 本文所提方法具有较高的实用性和高效性.
|
图 1 确切子串查询时间 Fig.1 Time cost for exact substring query (a)—URL数据集；(b)—DBLP和PubMed数据集. |
1) 优化后索引, 在没有压缩存储的情况下和元索引大小相同.当进行压缩存储时, 索引大小可以通过分组和压缩参数来进行控制.
2) 克服了结果中出现假阳性的问题, 并仅用一次除法和取余运算实现从后缀数组位置到字符串ID和字符串上子串匹配位置的计算.
3) 在DBLP, PubMed和URL三个数据集上, 在没有增加索引大小的情况下, 索引速度均有所加快, 索引速度提升3~5倍, 实现了更加高效的索引.
| [1] |
Chaudhuri S, Ganti V, Kaushik R. A primitive operator for similarity joins in data cleaning[C]// International Conference on Data Engineering. Atlanta, 2006: 5-17.
|
| [2] |
Xiao C, Wang W, Lin X, et al. Efficient similarity joins for near duplicate detection[C]// International Conference on World Wide Web. Beijing, 2008: 131-140.
|
| [3] |
Chaudhuri S, Ganjam K, Ganti V, et al. Robust and efficient fuzzy match for online data cleaning[C]//ACM SIGMOD International Conference on Management of Data. San Diego, 2003: 313-324.
|
| [4] |
Deng D, Li G, Feng J. A pivotal prefix based filtering algorithm for string similarity search[C]//ACM SIGMOD International Conference on Management of Data. San Diego, 2014: 673-684.
|
| [5] |
Li C, Wang B, Yang X. VGRAM: improving performance of approximate queries on string collections using variable-length grams[C]// International Conference on Very Large Data Bases. Vienna, 2007: 303-314.
|
| [6] |
Li H, Durbin R.
Fast and accurate short read alignment with Burrows-Wheeler transform[J]. Bioinformatics, 2009, 25(14): 1754–1760.
DOI:10.1093/bioinformatics/btp324 |
| [7] |
Qin J, Wang W, Lu Y, et al. Efficient exact edit similarity query processing with the asymmetric signature scheme[C]// ACM SIGMOD International Conference on Management of Data. Athens, 2011: 1033-1044.
|
| [8] |
Sarawagi S, Kirpal A. Efficient set joins on similarity predicates[C]// ACM SIGMOD International Conference on Management of Data. Paris, 2004: 743-754.
|
| [9] |
Sokol D, Benson G, Tojeira J.
Tandem repeats over the edit distance[J]. Bioinformatics, 2007, 23(2).
|
| [10] |
Wang W, Xiao C, Lin X, et al. Efficient approximate entity extraction with edit distance constraints[C]// ACM SIGMOD International Conference on Management of Data. Rhode, 2009: 759-770.
|
| [11] |
Wang W, Qin J, Xiao C, et al.
VChunkJoin:an efficient algorithm for edit similarity joins[J]. Transactions on Knowledge & Data Engineering, 2013, 25(8): 1916–1929.
|
| [12] |
Xiao C, Wang W, Lin X.
Ed-Join:an efficient algorithm for similarity joins with edit distance constraints[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 933–944.
DOI:10.14778/1453856 |
| [13] |
Yang X, Wang Y, Wang B, et al. Local filtering: improving the performance of approximate queries on string collections[C]// ACM SIGMOD International Conference on Management of Data. Victoria, 2015: 377-392.
|
| [14] |
Ferragina P, Manzini G. Opportunistic data structures with applications[C]// Foundations of Computer Science. Beijing, 2002: 390-399.
|