一种带有长度和位置约束的字符串索引方法

doi:10.12068/j.issn.1005-3026.2018.07.010

东北大学学报:自然科学版 ›› 2018, Vol. 39 ›› Issue (7): 959-963.DOI: 10.12068/j.issn.1005-3026.2018.07.010

一种带有长度和位置约束的字符串索引方法

于长永¹，高明¹，柏禄一¹，赵宇海²

(1. 东北大学秦皇岛分校计算机与通信工程学院，河北秦皇岛066004; 2. 东北大学计算机科学与工程学院，辽宁沈阳110169)

收稿日期:2017-05-24 修回日期:2017-05-24 出版日期:2018-07-15 发布日期:2018-07-11
通讯作者: 于长永
作者简介:于长永(1981-)，男，辽宁海城人，东北大学副教授.冯明杰(1971-)，男，河南禹州人，东北大学副教授; 王恩刚(1962-)，男，辽宁沈阳人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(61772124，61332014，61401080，61402087)；河北省自然科学基金资助项目(F2015501049)；河北省教育厅项目(QN2014339)；中央高校基本科研业务费专项资金资助项目(N150402002).国家自然科学基金资助项目(51171041).

A String Collection Indexing Method with String Length and Position Constraint

YU Chang-yong¹， GAO Ming¹， BAI Lu-yi¹， ZHAO Yu-hai²

1. School of Computer and Communication Engineering， Northeastern University at Qinhuangdao， Qinhuangdao 066004， China; 2. School of Computer Science & Engineering， Northeastern University， Shenyang 110169， China.

Received:2017-05-24 Revised:2017-05-24 Online:2018-07-15 Published:2018-07-11
Contact: YU Chang-yong
About author:-
Supported by:
-

摘要/Abstract

摘要： 提出了一种基于BWT(Burrows-wheeler-transform)的字符串集合的索引方法，以解决带有匹配字符串长度和匹配子串位置约束的子串确切匹配查找问题.讨论了BWT和基于BWT索引进行确切子串查找的基本原理.分析了字符串集合、匹配字符串长度和匹配子串位置约束对原BWT索引的影响.重点解决了快速地从匹配后缀位置到字符串ID和匹配子串位置的计算问题.在3个真实的数据集上进行了比对实验，结果表明:所提出的基于BWT索引方法在没有增加原索引大小的情况下，大大提升了带有匹配字符串长度和匹配位置约束的确切子串的查找的性能，因此该算法更加适用于大规模的字符串集合的索引进行近似字符串匹配和连接.

关键词: BWT, 字符串索引, 倒排链表, 字符串近似匹配, 序列比对

Abstract: An index method of string collection was proposed based on BWT (Burrows-wheeler-transform) for solving the exact substring queries with string length and matching position constraints. Firstly， the BWT and exact string query based on it were discussed. Then the impact of string collection， string length and substring position upon the original BWT index was analyzed. Finally， the fast calculation problem was discussed and solved from the position of the matching suffix to the string ID and position on the string of the matching substring. The approximate string matching was conducted on three real string collections and compared the results of index method proposed and the original one. The experimental results showed that the method proposed based on BWT speeded up the process of exact substring queries with string length and matching position constraints considerably in the case of keeping the index size. Therefore， the proposed method was suitable for indexing large-scale string collection for string similarity match and joint.

Key words: BWT (Burrows-Wheeler-transform), string index, inverted list, string similarity match, sequence alignment

中图分类号:

TP311.131

于长永，高明，柏禄一，赵宇海. 一种带有长度和位置约束的字符串索引方法[J]. 东北大学学报:自然科学版, 2018, 39(7): 959-963.

YU Chang-yong， GAO Ming， BAI Lu-yi， ZHAO Yu-hai. A String Collection Indexing Method with String Length and Position Constraint[J]. Journal of Northeastern University Natural Science, 2018, 39(7): 959-963.

参考文献

[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.
[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):e30-e35.
[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.
[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.

一种带有长度和位置约束的字符串索引方法

A String Collection Indexing Method with String Length and Position Constraint

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	于长永，金建宇，刘鹏，赵宇海. 基于最小边集的De Bruijn图定位算法[J]. 东北大学学报（自然科学版）, 2022, 43(2): 153-159.
[2]	王佳英，王斌，李晓华，杨晓春. 采用BWT的多核并行的子串匹配算法[J]. 东北大学学报:自然科学版, 2016, 37(5): 624-628.