1、串匹配是計算機科學中一個基本、重要的研究問題。多目標和多模式匹配是串匹配技術的重要研究內容。多目標和多模式精確串匹配技術要求目標串(正文串)與查詢串(模式串)完全一致匹配。但是，在很多實際應用中，并不要求目標串與模式完全精確匹配，于是引入了多目標和多模式近似串匹配技術。許多應用的正文串(目標串)的規(guī)模往往很大，需要設計高效的多目標和多模式近似匹配并行算法來快速求解這類問題。機群系統(tǒng)具有高性能、低成本、可擴展性好的特點。本文將在處理機節(jié)點

2、具有不同計算速度、不同通信延遲、不同存儲容量的異構機群系統(tǒng)上，設計、實現高效的多目標和多模式精確與近似串匹配并行算法，并分析和測試并行算法的性能。 運用基于孫子定理構造的均勻Hash函數并繼承Karp-Rabin模式匹配思想，通過“篩選”方法，給出一種機群系統(tǒng)土多目標串精確匹配并行算法。該算法將字符串映射成惟一的一對整數值并采用比較一對整數值來取代逐個字符比較模式和目標串的方法，使得比較過程快速且匹配結果是確定的。算法分析和實驗

3、結果表明該并行算法簡明、高效和可擴展。 針對處理機節(jié)點具有不同的計算速度、通信延遲和存儲容量的情形，考慮計算和通信啟動開銷，給定處理機分配順序，基于可分負載理論，分別建立單層和兩層樹結構模型的存儲受限異構機群系統(tǒng)的目標串最優(yōu)分配線性規(guī)劃模型，給出相應的目標串最優(yōu)分配方法，并討論了處理機最優(yōu)分配順序。異構PC機群系統(tǒng)上的實驗結果表明，本文提出的基于最優(yōu)分配方法的多目標串近似匹配并行算法優(yōu)于平均分配算法，獲得了接近線性的加速，具有良

4、好的可擴展性。 對于給定的正文串和多個模式串，運用均勻Hash函數將所有模式串的簽名映射成惟一的一對整數值并存儲于Hash表中，給出正文串窗口簽名Hash值的推算公式；在節(jié)點具有不同的計算速度、通信延遲、存儲容量的異構機群系統(tǒng)上，考慮計算和通信啟動開銷，基于可分負載理論，建立正文串最優(yōu)分配線性規(guī)劃模型，提出一種允許1個錯誤字符的多模式近似匹配并行算法。異構PC機群系統(tǒng)上的實驗結果表明，該算法獲得了較好的加速和可擴展性，它比基于均