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

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

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

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