摘要
带有通配符的模式匹配问题(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.
出处
《模式识别与人工智能》
EI
CSCD
北大核心
2012年第6期1013-1021,共9页
Pattern Recognition and Artificial Intelligence
基金
国家自然科学基金项目(No.60828005
60975034
61273292)
中央高校基本科研业务费专项资金项目(No.2011HGZY0003)资助
关键词
模式特征
完备性
通配符
模式匹配
Pattern Feature, Completeness, Wildcard, Pattern Matching
