一种改进的Wu-Manber多关键字匹配算法.pdfVIP

第23卷第1期 中文信息学报 VoI．23。No．1 2009年1月 OFCHINESEINFORMATIONPROCESSINGJan．，2009 JOURNAL 文章编号：1003一0077(2009)01—0030—05 一种改进的Wu-Manber多关键字匹配算法 莫德敏1，刘耀军2 (1．太原科技大学计算机科学与技术学院，山西太原030024；2．太原师范学院计算机系，山西太原030012) 摘 要：针对Wu—Manber算法在处理公共子后缀模式情况下的不足，该文提出了一种基于非空公共子后缀模式的 处理算法。该算法把有非空公共子后缀的模式汇集在一起，进一步减小了next链表的平均长度。在匹配过程中减 少了字符比较的次数，从而提高算法的运行效率。该文对搜狗实验室给出的相关文档进行全文检索实验，并和原 wu—Manber算法、孙晓山等提出的改进算法进行比较。实验结果表明，该文提出的改进算法有效地减少了匹配过 程中字符比较的次数，从而提高匹配的速度和效率。 关键词：计算机应用}中文信息处理；Wu-Manber算法；多关键字匹配；模式匹配；字符串匹配 中图分类号：TP391 文献标识码：A An ofWu-ManberPatterns Improvement Multiple MatchingAlgorithm MODe-minl，LIUud Yao-j of Scienceand (1．DepartmentComputer technology，TaiyuanUniversity ofSienceand of Technology，Taiyuan，Shanxi030024，China；2．DepartmentComputer Scienceand of 030012，China) Technology，TeachersCollegeTaiyuan，Taiyuan，Shan】【i on subsuffixfor Abstract：This amodifiedWu—Manber basedthee—free paperproposes algorithm multiplepatterns reducestheamountof withcommonsubsuffix．The matching．Thealgorithm stringmatchingbycollectingpatterns basedondocuments indicatethatthe can experiments providedbySogou suggestedalgorithmsignificantlyimprove the of withthe Wu-Manberanditsmodifiedversion． matchingcompared original algorithm efficiencystring information mate+ Keywords：computerapplication；Chinesepro