模式特征对带有通配符和长度约束的模式匹配问题的影响  

Impact of Pattern Feature on Pattern Matching Problem with Wildcards and Length Constraints

作　　者：王海平[1] 胡学钢[1] 谢飞[1,2] 郭丹[1] 吴信东[1,3] 

机构地区：[1]合肥工业大学计算机与信息学院计算机科学与技术系,合肥230009 [2]合肥师范学院计算机科学与技术系,合肥230601 [3]Department of Computer Science,The University of Vermont,burlington05405

出　　处：《模式识别与人工智能》2012年第6期1013-1021,共9页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金项目(No.60828005;60975034;61273292);中央高校基本科研业务费专项资金项目(No.2011HGZY0003)资助

摘　　要：带有通配符的模式匹配问题(PMWL)模式定义的灵活性给用户提供方便,却也造成求解上的困难.目前没有任何多项式算法能得到该问题的完备解,同时也缺少足够的完备性分析.文中认为模式特征是影响PMWL完备性的关键因素,并提出模式重复度的概念,记为rep.证明在rep=0的限定条件下PMWL的完备性,同时分析rep>0时PMWL不完备的原因.实验以近似比为指标,说明rep对PMWL完备性的影响.Pattern matching with wildcards and length constraints （PMWL） provides more convenience to users since its flexibility in definition which also leads to difficulties in solving problem. Currently, to our knowledge, no polynomial algorithms obtain the complete solution of this problem, and the analysis for completeness is far from sufficient. In this paper, the pattern feature is provedto be the key factor for the completeness of PMWL and a concept, denoted as rep, is provided which measures the repetitions in the pattern. The completeness of PMWL is proved under a certain condition when rep = 0. And the reason of incompleteness under the condition of rep〉0 is also explained clearly. In the experiments, approximation ratio is utilized as a measurement to demonstrate the impact of rep on the PMWL problem.

关 键 词：模式特征 完备性 通配符 模式匹配 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]