支持带有通配符的字符串匹配算法

摘要：

研究了查询字符串中含有通配符"*"以及"?"两种情况下的字符串匹配问题,其中,"*"代表任意长度的字符串,"?"代表字母表中任意一个字符.由于gram索引结构在空间大小以及查询效率上的优势,将gram索引结构用于带通配符的字符串匹配问题.通过将带有通配符的查询字符串分解为若干不含通配符的查询片段,成功地将带有通配符的复杂查询问题转化为不舍通配符的简单精确子串匹配问题.同时在片段查询过程中运用长度过滤、位置过滤以及计数过滤等方法来提高查询速度.

关键词：通配符、字符串匹配、q-gram索引

所属期刊栏目：4

分类号：TP311.131(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant No.60828004,60973018;the Fundamental Research Funds for the Central Universities under Grant No.N090504004

在线出版日期：2010-12-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：984-995