计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2009年
8期
1341-1348
,共8页
串匹配%精确单模式%算法设计%位并行%文本搜索
串匹配%精確單模式%算法設計%位併行%文本搜索
천필배%정학단모식%산법설계%위병행%문본수색
串匹配问题是计算机科学的基础问题之一,是网络安全、信息检索与过滤、计算生物学等众多领域的核心问题,其中,高速精确单模式匹配算法设计又是各种串匹配问题的基础.基于SBNDM2,通过修改位掩码有效位到无符号整数的高位,将BNDM算法核心循环化简至最简形式(5指令/字符),并引入越界保护机制,提出S2BNDM系列精确单模式匹配算法.实验结果显示,S2BNDM系列算法在任何情况下都快于SBNDM2,对于英文语料(m<32)和DNA序列(m<8),S2BNDM系列算法为现有已知最快算法.
串匹配問題是計算機科學的基礎問題之一,是網絡安全、信息檢索與過濾、計算生物學等衆多領域的覈心問題,其中,高速精確單模式匹配算法設計又是各種串匹配問題的基礎.基于SBNDM2,通過脩改位掩碼有效位到無符號整數的高位,將BNDM算法覈心循環化簡至最簡形式(5指令/字符),併引入越界保護機製,提齣S2BNDM繫列精確單模式匹配算法.實驗結果顯示,S2BNDM繫列算法在任何情況下都快于SBNDM2,對于英文語料(m<32)和DNA序列(m<8),S2BNDM繫列算法為現有已知最快算法.
천필배문제시계산궤과학적기출문제지일,시망락안전、신식검색여과려、계산생물학등음다영역적핵심문제,기중,고속정학단모식필배산법설계우시각충천필배문제적기출.기우SBNDM2,통과수개위엄마유효위도무부호정수적고위,장BNDM산법핵심순배화간지최간형식(5지령/자부),병인입월계보호궤제,제출S2BNDM계렬정학단모식필배산법.실험결과현시,S2BNDM계렬산법재임하정황하도쾌우SBNDM2,대우영문어료(m<32)화DNA서렬(m<8),S2BNDM계렬산법위현유이지최쾌산법.
