机电工程
機電工程
궤전공정
MECHANICAL & ELECTRICAL ENGINEERING MAGAZINE
2008年
9期
25-27
,共3页
W-M算法%多模式匹配%哈希函数%后缀
W-M算法%多模式匹配%哈希函數%後綴
W-M산법%다모식필배%합희함수%후철
Wu-Manber 算法是一种基于后缀搜索的多模式匹配算法,该算法采用查表的方法,通过跳跃不可能匹配的字符来加速匹配,W-M 算法对最短模式长度敏感,最短模式长度决定了它可以跳过的字符的最大距离.针对 W-M 算法的不足之处,提出了一个改进方法:新增了一个模式串末字符表,取得了比原算法更少的 hash 计算次数和更大的字符跳跃距离,从而加快了整个匹配过程的速度.最后,进行了设定模式串的最短长度和搜索文本长度的对比实验.实验结果显示,改进后的算法搜索效率明显高于原算法,特别是在模式串长度很短的情况下,效率提高非常明显.
Wu-Manber 算法是一種基于後綴搜索的多模式匹配算法,該算法採用查錶的方法,通過跳躍不可能匹配的字符來加速匹配,W-M 算法對最短模式長度敏感,最短模式長度決定瞭它可以跳過的字符的最大距離.針對 W-M 算法的不足之處,提齣瞭一箇改進方法:新增瞭一箇模式串末字符錶,取得瞭比原算法更少的 hash 計算次數和更大的字符跳躍距離,從而加快瞭整箇匹配過程的速度.最後,進行瞭設定模式串的最短長度和搜索文本長度的對比實驗.實驗結果顯示,改進後的算法搜索效率明顯高于原算法,特彆是在模式串長度很短的情況下,效率提高非常明顯.
Wu-Manber 산법시일충기우후철수색적다모식필배산법,해산법채용사표적방법,통과도약불가능필배적자부래가속필배,W-M 산법대최단모식장도민감,최단모식장도결정료타가이도과적자부적최대거리.침대 W-M 산법적불족지처,제출료일개개진방법:신증료일개모식천말자부표,취득료비원산법경소적 hash 계산차수화경대적자부도약거리,종이가쾌료정개필배과정적속도.최후,진행료설정모식천적최단장도화수색문본장도적대비실험.실험결과현시,개진후적산법수색효솔명현고우원산법,특별시재모식천장도흔단적정황하,효솔제고비상명현.