首页 | 本学科首页   官方微博 | 高级检索  
     

支持带有通配符的字符串匹配算法
引用本文:运正佳,李轶男,杨晓春.支持带有通配符的字符串匹配算法[J].计算机科学与探索,2010,4(11):984-995.
作者姓名:运正佳  李轶男  杨晓春
作者单位:东北大学信息科学与工程学院,沈阳,110819
基金项目:国家自然科学基金,中央高校基本科研业务费专项资金
摘    要:研究了查询字符串中含有通配符"*"以及"?"两种情况下的字符串匹配问题,其中,"*"代表任意长度的字符串,"?"代表字母表中任意一个字符。由于gram索引结构在空间大小以及查询效率上的优势,将gram索引结构用于带通配符的字符串匹配问题。通过将带有通配符的查询字符串分解为若干不含通配符的查询片段,成功地将带有通配符的复杂查询问题转化为不含通配符的简单精确子串匹配问题。同时在片段查询过程中运用长度过滤、位置过滤以及计数过滤等方法来提高查询速度。

关 键 词:通配符  字符串匹配  q-gram索引
修稿时间: 

An Algorithm for Matching Strings with Wildcards
YUN Zhengjia,LI Yinan,YANG Xiaochun.An Algorithm for Matching Strings with Wildcards[J].Journal of Frontier of Computer Science and Technology,2010,4(11):984-995.
Authors:YUN Zhengjia  LI Yinan  YANG Xiaochun
Affiliation:College of Information Science and Engineering, Northeastern University, Shenyang 110819, China
Abstract:This paper focuses on the problem of strings matching with wildcards "*" and "?" in the query,where "*" matches any sequence and "?" matches any character.Since gram based index structure has advantages in both space and searching time,it proposes an algorithm to solve the problem of strings matching with wildcards based on gram index structure.The query string with wildcards is divided into several query segments without any wildcards.So the algorithm successfully changes this complex problem to a simple exact substring matching problem.The algorithm takes advantage of length filter,position filter,and count filter to speed up the query process.
Keywords:wildcard  matching strings  q-gram index
本文献已被 万方数据 等数据库收录!
点击此处可从《计算机科学与探索》浏览原始摘要信息
点击此处可从《计算机科学与探索》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号