基于组合策略的单模式串精确匹配算法  

Single pattern string exact matching algorithms based on hybrid strategy

作　　者：许秀林[1] 胡克瑾[2] 

机构地区：[1]南通职业大学电子工程系,江苏南通226007 [2]同济大学经济管理学院,上海200092

出　　处：《计算机应用》2008年第1期232-235,共4页journal of Computer Applications

基　　金：江苏省高校自然科学研究指导性计划项目(05KJD520172)

摘　　要：以仅使用后缀有限自动机的RF算法作为参照对象,对采用组合策略的LDM、ILDM1、ILDM2等算法时间复杂度进行了比较研究。实验表明,LDM和ILDM1算法的时间复杂度要差于RF算法,即组合策略是失效的。实验还发现,ILDM2算法中把模式前缀长度R是否超过模式长度m的1/2作为正向有限自动机暂停匹配的条件,对于中小字母表的模式串的匹配也不是最佳策略。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.

关 键 词：模式匹配 LDM算法 后缀自动机 有限状态自动机 

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