| 基于组合策略的单模式串精确匹配算法 |
| |
| 引用本文： | 许秀林,胡克瑾.基于组合策略的单模式串精确匹配算法[J].计算机应用,2008,28(1):232-235. |
| |
| 作者姓名： | 许秀林 胡克瑾 |
| |
| 作者单位： | 1. 南通职业大学,电子工程系,江苏,南通,226007
2. 同济大学,经济管理学院,上海,200092 |
| |
| 摘 要： | 以仅使用后缀有限自动机的RF算法作为参照对象，对采用组合策略的LDM、ILDM1、ILDM2等算法时间复杂度进行了比较研究。实验表明，LDM和ILDM1算法的时间复杂度要差于RF算法，即组合策略是失效的。实验还发现，ILDM2算法中把模式前缀长度R是否超过模式长度m的1/ 2作为正向有限自动机暂停匹配的条件，对于中小字母表的模式串的匹配也不是最佳策略。
|
| 关 键 词： | 模式匹配 LDM算法 后缀自动机 有限状态自动机 |
| 文章编号： | 1001-9081(2008)01-0232-04 |
| 收稿时间： | 2007-08-10 |
| 修稿时间： | 2007年8月10日 |
Single pattern string exact matching algorithms based on hybrid strategy |
| |
| XU Xiu-lin,HU Ke-jin.Single pattern string exact matching algorithms based on hybrid strategy[J].journal of Computer Applications,2008,28(1):232-235. |
| |
| Authors: | XU Xiu-lin HU Ke-jin |
| |
| Affiliation: | XU Xiu-lin1,HU Ke-jin2(1. Department of Electronic Engineering,Nantong Vocation College,Nantong Jiangsu 226007,China,2. College of Economic , Management,Tongji University,Shanghai 200092,China) |
| |
| Abstract: | It is researched by comparing their time complexities of LDM, ILDM1, ILDM2 algorithm etc. with RF algorithm that only uses a smallest suffix automaton. The experiment shows that the time complexities of LDM, ILDM1 algorithms are poorer than that of RF algorithm, and there is no efficiency for the hybrid strategy in LDM, ILDM1. The experiment also finds that it is not the best strategy for middle and small alphabet that the forward finite state automaton is suspended when the length of pattern prefixes-R is not greater than half of m, the length of pattern string, in ILDM2 algorithm. |
| |
| Keywords: | pattern matching Linear DAWG Matching (LDM) algorithm suffix automaton finite state automaton |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
|
