資源描述：
《異構(gòu)機(jī)群系統(tǒng)上多目標(biāo)和多模式近似串匹配并行算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、廣西大學(xué)碩士學(xué)位論文異構(gòu)機(jī)群系統(tǒng)上多目標(biāo)和多模式近似串匹配并行算法研究姓名：范曾申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)指導(dǎo)教師：鐘誠(chéng)20080628異構(gòu)機(jī)群系統(tǒng)上多目標(biāo)和多模式近似串匹配并行算法研究摘要串匹配是計(jì)算機(jī)科學(xué)中一個(gè)基本、重要的研究問(wèn)題。多目標(biāo)和多模式匹配是串匹配技術(shù)的重要研究?jī)?nèi)容。多目標(biāo)和多模式精確串匹配技術(shù)要求目標(biāo)串(正文串)與查詢串(模式串)完全一致匹配。但是，在很多實(shí)際應(yīng)用中，并不要求目標(biāo)串與模式完全精確匹配，于是引入了多目標(biāo)和多模式近似串匹配技術(shù)。許多應(yīng)用的正文串(目標(biāo)串)的規(guī)
2、模往往很大，需要設(shè)計(jì)高效的多目標(biāo)和多模式近似匹配并行算法來(lái)快速求解這類問(wèn)題。機(jī)群系統(tǒng)具有高性能、低成本、可擴(kuò)展性好的特點(diǎn)。本文將在處理機(jī)節(jié)點(diǎn)具有不同計(jì)算速度、不同通信延遲、不同存儲(chǔ)容量的異構(gòu)機(jī)群系統(tǒng)上，設(shè)計(jì)、實(shí)現(xiàn)高效的多目標(biāo)和多模式精確與近似串匹配并行算法，并分析和測(cè)試并行算法的性能。運(yùn)用基于孫子定理構(gòu)造的均勻Hash函數(shù)并繼承K唧．Rabin模式匹配思想，通過(guò)“篩選"方法，給出一種機(jī)群系統(tǒng)上多目標(biāo)串精確匹配并行算法。該算法將字符串映射成惟一的一對(duì)整數(shù)值并采用比較一對(duì)整數(shù)值來(lái)取代逐個(gè)字符比較模式和
3、目標(biāo)串的方法，使得比較過(guò)程快速且匹配結(jié)果是確定的。算法分析和實(shí)驗(yàn)結(jié)果表明該并行算法簡(jiǎn)明、高效和可擴(kuò)展。針對(duì)處理機(jī)節(jié)點(diǎn)具有不同的計(jì)算速度、通信延遲和存儲(chǔ)容量的情形，考慮計(jì)算和通信啟動(dòng)開(kāi)銷，給定處理機(jī)分配順序，基于可分負(fù)載理論，分別建立單層和兩層樹(shù)結(jié)構(gòu)模型的存儲(chǔ)受限異構(gòu)機(jī)群系統(tǒng)的目標(biāo)串最優(yōu)分配線性規(guī)劃模型，給出相應(yīng)的目標(biāo)串最優(yōu)分配方法，并討論了處理機(jī)最優(yōu)分配順序。異構(gòu)PC機(jī)群系統(tǒng)上的實(shí)驗(yàn)結(jié)果表明，本文提出的基于最優(yōu)分配方法的多目標(biāo)串近似匹配并行算法優(yōu)于平均分配算法，獲得了接近線性的加速，具有良好的可擴(kuò)
4、展性。對(duì)于給定的正文串和多個(gè)模式串，運(yùn)用均勻Hash函數(shù)將所有模式串的簽名映射成惟一的一對(duì)整數(shù)值并存儲(chǔ)于Hash表中，給出正文串窗口簽名Hash值的推算公式；在節(jié)點(diǎn)具有不同的計(jì)算速度、通信延遲、存儲(chǔ)容量的異構(gòu)機(jī)群系統(tǒng)上，考慮計(jì)算和通信啟動(dòng)開(kāi)銷，基于可分負(fù)載理論，建立正文串最優(yōu)分配線性規(guī)劃模型，提出一種允許1個(gè)錯(cuò)誤字符的多模式近似匹配并行算法。異構(gòu)PC機(jī)群系統(tǒng)上的實(shí)驗(yàn)結(jié)果表明，該算法獲得了較好的加速和可擴(kuò)展性，它比基于均勻分配正文串策略的多模式近似匹配并行算法平均快25％。關(guān)鍵詞：多目標(biāo)串近似匹配多
5、模式近似匹配異構(gòu)機(jī)群系統(tǒng)并行算法Hashing可分負(fù)載存儲(chǔ)受限lIstudyonParaHelAlgorithmsforApproximateMulti-ObjectandMulti-PatternMatchingonHeterogeneousClusterSystemsABSTRACTStringmatcIlingisoIleofthebaSicandimportantresearchproblemsincomputerscience．Multi-objectmatchinga11dmulti-
6、pa吮mmatchingareimport鋤tissuesiIlstringmatcllingfield．Exactmuni—objectmatchingandmIllti·pattemmatchingrequiretllattheobjectstringsorthesubstringsoftextmatchcompletely而ththeque巧嘶ngorpattemsa11ddon’ta110wanyerror．Butinmally印plications，meobjectstringsorth
7、esubstringsoftcXtcanmatch謝thtlleque盯stringorpa_ttemsallo、啊ngsomeerrors．SincethesizeofteXtortllem啪berofobjectstringsisoRenVe巧large，itisnecessa巧t0desi印KgmyemcientparallelalgoritIlIIlsfor印proximatemulti—objectandmulti-pattemmatching．ThecluStercomputingsy
8、stemshaVethecharaIcteriSticsofhi曲pe墑冊(cè)ance，lowcostandsCalabili夠11lisp印er姍iest0desi弘aIldimplementtliglllyemcientparallelalgoritl姍sforexactand印proximatemulti—object鋤dmulti-pattemmatchingonheterogeneouScluStersystemsthatprocessorshaVedifrerentcomp
