一种适合中文模式匹配的扩展Horspool算法  

作　　者：宋云[1] 沈冲[2] 李峰[1] 

机构地区：[1]长沙理工大学计算机与通信工程学院,湖南长沙410076 [2]长沙市公安局交警支队科研所,湖南长沙410100

出　　处：《软件导刊》2009年第6期48-50,共3页Software Guide

基　　金：国家自然科学基金(10671211);湖南省自然科学基金(07JJ3005)

摘　　要：分析了各种模式匹配经典算法及其有效环境后,提出一种适合中文关键词搜索的尾字比较查表跳转的扩展Horspool算法,它具有O(n/m)最优复杂度和O(n/m(1-m/2σ))的平均复杂度。实验结果表明,在随机语言环境下,算法性能非常接近最优情况;在自然语言环境下,效率也达到最优情况的90%以上。

关 键 词：模式匹配 后缀搜索 HORSPOOL算法 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]