字符串匹配算法通用并行加速技術(shù)研究.pdf

1、字符串匹配是計算機(jī)科學(xué)中最古老，研究最廣泛的問題之一。近年來，學(xué)術(shù)界對字符串匹配的研究興趣與日俱增，特別是在發(fā)展迅猛的信息檢索領(lǐng)域和計算生物學(xué)領(lǐng)域。形成這個現(xiàn)象的一個重要原因是需要處理的文本規(guī)模越來越大，以及網(wǎng)絡(luò)帶寬的日益增大，使得客觀上對字符串匹配性能的要求越來越高。
　　 本文主要對高性能精確單模式字符串匹配算法進(jìn)行研究。首先對現(xiàn)有精確單模式算法進(jìn)行分析與實(shí)現(xiàn)，再通過實(shí)駿得出在各種情況下性能最高的算法，并在具體數(shù)據(jù)基礎(chǔ)上分析

2、各算法得失。在這些工作的基礎(chǔ)上，本文提出了一種簡單并行加速的方法(改一次比較一個字符為一次比較若干字符，即并行比較)，并用該方法改進(jìn)了horspool算法和NEW算法(改進(jìn)算法分別命名為Phorspool算法和Phash算法)，實(shí)驗(yàn)證明，改進(jìn)算法有效的提高了原算法的性能。本文所提的并行方法還可用于其他算法以改進(jìn)性能。
　　 具體而言，本文的工作主要在于：
　　 1.總結(jié)了前人的研究成果，并通過實(shí)驗(yàn)數(shù)據(jù)對其進(jìn)行了深入的分析

3、；
　　 2.總結(jié)出影響字符串匹配算法性能的關(guān)健三要素：1)搜索窗口內(nèi)失配的概率和速度；2)搜索窗口跳躍的平均長度；3)內(nèi)存引用次數(shù)。
　　 3. 提出了一種簡單并行加速的方往。此方法意義在于并不局限于僅加速某種算法，其應(yīng)用范圍是普遍的(不局限于模式匹配算法，凡有進(jìn)行挨個比較過程的算法皆可使用)，能夠很好的利用CPU的字長，但缺點(diǎn)在于目前在除intel處理器以外的CPU上不能運(yùn)行(因?yàn)榈刂穼R問題)。
　　 4.