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