检索规则说明:AND代表“并且”;OR代表“或者”;NOT代表“不包含”;(注意必须大写,运算符两边需空一格)
检 索 范 例 :范例一: (K=图书馆学 OR K=情报学) AND A=范并思 范例二:J=计算机应用与软件 AND (U=C++ OR U=Basic) NOT M=Visual
机构地区:[1]上海交通大学计算机科学与工程系,上海200030
出 处:《上海交通大学学报》2002年第4期516-520,共5页Journal of Shanghai Jiaotong University
基 金:国家"8 6 3"计划资助项目 ( 86 3-30 6 -ZD0 3-0 4-1)
摘 要:以基于有限自动机的多模式匹配算法 (DFSA)为基础 ,结合 Boyer- Moore(BM)和 QuickSearch (QS)快速单模式匹配算法的优点 ,提出了一种快速的多模式字符串匹配算法 .在一般情况下 ,该算法不需要匹配目标文本串中的每个字符 ,能充分利用匹配过程中本次匹配不成功的信息和已经匹配成功的信息 ,跳过尽可能多的字符 .实验表明 ,模式串较短时 ,本算法所需时间为 DFSA算法的 1 /2~ 1 /3 ;模式串较长时 ,其所需时间为 DFSA算法的 1 /3~ 1A fast algorithm to perform multiple patterns match in a string was described. The proposed match algorithm is based on the concept of deterministic finite state automata (DFSA), combining the advantages of Boyer Moore's algorithm and Quick Search algorithm, the two fast algorithms for single pattern matching. In general, it does not need inspect each character of the string. It skips as many characters as possible by making full use of the succeeded match information and failure information during the matching. The proposed algorithm achieves excellent performance in the cases of both short patterns and long patterns. The actual experiments show that in the case of short patterns the time it takes to search a string is 1/2~1/3 of the time DFSA method takes, and in the case of long patterns the time is only 1/3~1/5 of the time by DFSA method.
分 类 号:TP391.1[自动化与计算机技术—计算机应用技术]
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在链接到云南高校图书馆文献保障联盟下载...
云南高校图书馆联盟文献共享服务平台 版权所有©
您的IP:216.73.216.229