四川理工学院学报（自然科学版）
四川理工學院學報（自然科學版）
사천리공학원학보（자연과학판）
JOURNAL OF SICHUAN UNIVERSITY OF SCIENCE & ENGINEERING(NATURAL SCIENCE EDITION)
2013年
2期
78-81
,共4页
字符串%模式匹配%倒序字符匹配%Sunday算法
字符串%模式匹配%倒序字符匹配%Sunday算法
자부천%모식필배%도서자부필배%Sunday산법
字符匹配效率是很多计算机应用系统的性能瓶颈,研究设计高效的匹配算法有助于提高相应系统的应用性能.在分析典型Sunday匹配算法的基础上,对其进行了较为有效的改进.改进算法在字符串匹配前先计算模式串的倒序特征值,也就是以此计算出模式串的最后s个字符在本模式串中倒序除自己以外的下一次出现的位置.每一次字符匹配都采用倒序匹配并利用这种匹配的结果,匹配结果结合倒序特征值可以直接决定特征串的下一次位移数.在进行完一次字符匹配后,采用增加一个遍历字符的Sunday算法来遍历模式串以计算下一次位移数,以此尽可能地排除无效匹配.实验结果表明改进算法的效率比Sunday算法有一定提高.
字符匹配效率是很多計算機應用繫統的性能瓶頸,研究設計高效的匹配算法有助于提高相應繫統的應用性能.在分析典型Sunday匹配算法的基礎上,對其進行瞭較為有效的改進.改進算法在字符串匹配前先計算模式串的倒序特徵值,也就是以此計算齣模式串的最後s箇字符在本模式串中倒序除自己以外的下一次齣現的位置.每一次字符匹配都採用倒序匹配併利用這種匹配的結果,匹配結果結閤倒序特徵值可以直接決定特徵串的下一次位移數.在進行完一次字符匹配後,採用增加一箇遍歷字符的Sunday算法來遍歷模式串以計算下一次位移數,以此儘可能地排除無效匹配.實驗結果錶明改進算法的效率比Sunday算法有一定提高.
자부필배효솔시흔다계산궤응용계통적성능병경,연구설계고효적필배산법유조우제고상응계통적응용성능.재분석전형Sunday필배산법적기출상,대기진행료교위유효적개진.개진산법재자부천필배전선계산모식천적도서특정치,야취시이차계산출모식천적최후s개자부재본모식천중도서제자기이외적하일차출현적위치.매일차자부필배도채용도서필배병이용저충필배적결과,필배결과결합도서특정치가이직접결정특정천적하일차위이수.재진행완일차자부필배후,채용증가일개편력자부적Sunday산법래편력모식천이계산하일차위이수,이차진가능지배제무효필배.실험결과표명개진산법적효솔비Sunday산법유일정제고.
