Pattern Matching with Wildcards and Length Constraints

具有通配符和长度约束的模式匹配

• 批准号: 0514819
• 负责人: Xindong Wu
• 金额: $ 20万
• 依托单位: University of Vermont & State Agricultural College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-15 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0514819&HistoricalAwards=false
• 关键词: Pattern; Matching; Wildcards; Length; Constraints

ABSTRACT0514819PI: Xindong Wu; Co-PIs: Abdullah N. Arslan and Xingquan ZhuU of Vermont & State Agricultural CollegePattern Matching with Wildcards and Length ConstraintsThis research defines a unique problem of pattern matching with wildcards and length constraints, and aims to design efficient algorithms for the problem. Given a pattern P and a text T, a substring S in T is a matching string of P if (1) the number of wildcards between each two consecutive pattern letters in S and (2)the length of S are both bounded by the user's specifications. The project seeks to find the maximum number of ``distinct'' occurrences of P in T. This is a complex problem that integrates both local constraints(in the form of gaps between consecutive pattern letters) and global length constraints in pattern matching.The research team will start with an existing preliminary design and further investigate the pattern matching problem, by (1) exploring the time complexity of the problem, (2) designing new, efficient algorithms to deal with some special cases, and (3) applying these efficient algorithms in practical problems in text indexing, gene sequence analysis, network security and stream data mining.

摘要0514819PI：吴欣东；联合PI：佛蒙特州立农业学院的Abdullah N. Arslan和Xingquan ZhuU带有通配符和长度约束的模式匹配这项研究定义了带有通配符和长度约束的模式匹配的独特问题，旨在为该问题设计有效的算法。 给定模式 P 和文本 T，如果 (1) S 中每两个连续模式字母之间的通配符数量和 (2) S 的长度都受用户的限制，则 T 中的子字符串 S 是 P 的匹配字符串。规格。 该项目寻求找到 T 中 P 出现的最大“不同”次数。这是一个复杂的问题，集成了模式匹配中的局部约束（以连续模式字母之间的间隙形式）和全局长度约束。研究团队将从现有的初步设计开始，进一步研究模式匹配问题，通过（1）探索问题的时间复杂度，（2）设计新的、高效的算法来处理一些特殊情况，以及（3）应用这些算法文本索引、基因等实际问题的高效算法序列分析、网络安全和流数据挖掘。