1、串匹配問題是計(jì)算機(jī)科學(xué)中的一個(gè)基本問題。精確串匹配技術(shù)要求模式與正文子串完全匹配，不允許有錯(cuò)誤。但是在許多實(shí)際情況中，并不要求模式與文本子串完全精確匹配，因此人們引入了近似串匹配技術(shù)。在許多實(shí)際應(yīng)用中，正文串的規(guī)模很大，即使利用最快的近似串匹配順序算法也很耗時(shí)，因此需要設(shè)計(jì)高效的近似串匹配并行算法以快速求解這類問題。由于機(jī)群計(jì)算系統(tǒng)具有高性能和低成本的特點(diǎn)，所以在異構(gòu)機(jī)群系統(tǒng)上研究近似串匹配的并行處理具有重要的現(xiàn)實(shí)意義。這種粗粒度并行的

2、近似串匹配技術(shù)的關(guān)鍵問題是如何恰當(dāng)?shù)貏澐终拇⑵浞峙涞胶线m的處理機(jī)上，以使得從分配正文串開始到所有處理機(jī)完成近似串匹配所經(jīng)歷的時(shí)間最短。 基于可分負(fù)載理論的最優(yōu)原則，在假定正文串分配順序固定的前提下，考慮處理機(jī)節(jié)點(diǎn)具有不同計(jì)算速度、不同通信能力的情況，提出異構(gòu)機(jī)群計(jì)算環(huán)境下的最優(yōu)正文串單輪分配策略并給出最優(yōu)正文串分配的閉合解；進(jìn)一步地，對(duì)于節(jié)點(diǎn)具有不同計(jì)算速度、不同通信能力、不同存儲(chǔ)容量的異構(gòu)機(jī)群系統(tǒng)，建立正文串最優(yōu)分配的線

3、性規(guī)劃模型；并且針對(duì)幾種特殊情況討論正文串的最優(yōu)分配順序。算法分析與實(shí)驗(yàn)結(jié)果表明，與平均分配正文串策略以及按照從處理機(jī)能力分配正文串策略相比，利用本文提出的最優(yōu)正文串單輪分配策略進(jìn)行單模式單正文串近似匹配并行處理所需的時(shí)間分別縮短了10～40％和5～20％。 在給定正文串分配輪數(shù)的前提下，考慮處理機(jī)節(jié)點(diǎn)具有不同計(jì)算速度、不同通信能力的情況，根據(jù)是否允許處理機(jī)重疊執(zhí)行計(jì)算和通信操作，本文提出異構(gòu)機(jī)群計(jì)算環(huán)境下的最優(yōu)正文串多輪分配策