|
|||||
|
|
| 模式特征对带有通配符和长度约束的模式匹配问题的影响 | |
| 引用本文： | 王海平,胡学钢,谢飞,郭丹,吴信东. 模式特征对带有通配符和长度约束的模式匹配问题的影响[J]. 模式识别与人工智能, 2012, 25(6): 1013-1021 |
| 作者姓名： | 王海平 胡学钢 谢飞 郭丹 吴信东 |
| 作者单位： | 1。合肥工业大学计算机与信息学院计算机科学与技术系合肥230009 2。合肥师范学院计算机科学与技术系合肥230601 3。DepartmentofComputerScience，TheUniversityofVermont，Burlington05405 |
| 基金项目： | 国家自然科学基金项目(No.60828005,60975034,61273292);中央高校基本科研业务费专项资金项目(No.2011HGZY0003)资助 |
| 摘 要： | 带有通配符的模式匹配问题(PMWL)模式定义的灵活性给用户提供方便，却也造成求解上的困难。目前没有任何多项式算法能得到该问题的完备解，同时也缺少足够的完备性分析。文中认为模式特征是影响PMWL完备性的关键因素，并提出模式重复度的概念，记为rep。证明在rep=0的限定条件下PMWL的完备性，同时分析rep>0时PMWL不完备的原因。实验以近似比为指标，说明rep对PMWL完备性的影响。 |
| 关 键 词： | 模式特征 完备性 通配符 模式匹配 |
| 收稿时间： | 2011-07-26 |
Impact of Pattern Feature on Pattern Matching Problem with Wildcards and Length Constraints |
|
| WANG Hai-Ping,HU Xue-Gang,XIE Fei,GUO Dan,WU Xin-Dong. Impact of Pattern Feature on Pattern Matching Problem with Wildcards and Length Constraints[J]. Pattern Recognition and Artificial Intelligence, 2012, 25(6): 1013-1021 | |
| Authors: | WANG Hai-Ping HU Xue-Gang XIE Fei GUO Dan WU Xin-Dong |
| Affiliation: | 1. Department of Computer Science and Technology,School of Computer Science and Information,Hefei University of Technology,Hefei 230009 2.Department of Computer Science and Technology,Hefei Normal University,Hefei 230601 3. Department of Computer Science,The University of Vermont,Burlington 05405 |
| Abstract: | 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 proved to 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. |
| Keywords: | Pattern Feature Completeness Wildcard Pattern Matching |
| 本文献已被 CNKI 等数据库收录！ | |
| 点击此处可从《模式识别与人工智能》浏览原始摘要信息 | |
| 点击此处可从《模式识别与人工智能》下载全文 | |