資源描述：
《支持大規(guī)模壓縮序列的在線子串查詢處理與優(yōu)化技術(shù)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。
1、分類號UDC密級學位論文支持大規(guī)模壓縮序列的在線子串查詢處理與優(yōu)化技術(shù)作者姓名：指導教師：申請學位級別：學科專業(yè)名稱：論文提交日期：學位授予日期：評閱人：李中博楊曉春教授東北大學計算機軟件與理論研究所碩士學科類別：工學計算機應用技術(shù)2010年6月論文答辯日期：2010年7月2010年月答辯委員會主席：申德榮申德榮石祥濱東北大學2010年6月AThesisfortheDegreeofMasterinComputerSoftwareandTheoryProcessingandOptimizationTechniquesforOnline
2、SearchingSubsequencesonLargeCompressedSequencesByLiZhongboSupervisor：ProfessorYANGXiaochunNortheasternUniversityJune2010獨創(chuàng)性聲明本人聲明，所呈交的學位論文是在導師的指導下完成的。論文中取得的研究成果除加以標注和致謝的地方外，不包含其他人己經(jīng)發(fā)表或撰寫過的研究成果，也不包括本人為獲得其他學位而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均己在論文中作了明確的說明并表示謝意。學位論文作者簽名：如舟日期：矽f
3、9芻’，7目‘司學位論文版權(quán)使用授權(quán)書本學位論文作者和指導教師完全了解東北大學有關(guān)保留、使用學位論文的規(guī)定：即學校有權(quán)保留并向國家有關(guān)部門或機構(gòu)送交論文的復印件和磁盤，允許論文被查閱和借閱。本人同意東北大學可以將學位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索、交流。作者和導師同意網(wǎng)上交流的時間為作者獲得學位后：半年口一年口一年半口兩年√學位論文作者簽名：套嬸傅簽字日期：沙／ro．7、f導師簽名：檔邁勿彖簽字日期：陽知．7。莎東北大學碩士學位論文摘要支持大規(guī)模壓縮序列的在線子串查詢處理與優(yōu)化技術(shù)摘要隨著社會的進步和科學的發(fā)展，信息數(shù)據(jù)
4、量呈爆炸性增長，特別是基因序列這樣的數(shù)據(jù)，其增長速度已經(jīng)超出了人們的想象，給數(shù)據(jù)存儲和傳輸造成了很大的壓力，各種壓縮技術(shù)被提出來解決這樣的問題。在壓縮序列上進行子串查詢處理對于基因序列分析和關(guān)鍵字搜索等實際應用非常有意義。這些序列數(shù)據(jù)往往以壓縮形式存儲，給子串查詢造成一定的難度，使得該研究領(lǐng)域面臨著巨大的挑戰(zhàn)。本文所研究的內(nèi)容是基于最近提出的一種無損壓縮技術(shù)，對于多個非常相似的字符序列，只需保留一個參照序列，然后利用參照序列上的編輯操作來編碼這些相似序列與參照序列的差異。該技術(shù)對于基因這種大規(guī)模的字符序列能夠起到非常好的壓縮效果。這
5、種壓縮技術(shù)是新穎而且重要的，那么如何在這種大規(guī)模壓縮序列上進行在線子串查詢處理是本文要解決的問題。針對上述大規(guī)模無損壓縮序列，本文針對參照序列是否在線被處理這兩種情況，分別提出相應的在線子串查詢處理與優(yōu)化技術(shù)。在未索引參照序列的情況下，通過改進經(jīng)典的BM算法，提出了支持單壓縮序列的子串查詢算法。利用多個壓縮序列在參照序列上擁有許多公共片段的特點，進而提出了支持多壓縮序列的子串查詢算法。在索引參照序列的情況下，通過建立一個基于q．gram的倒排表索引，提出一個基本的子串查詢算法。針對其不足，采用對編輯操作的過濾技術(shù)，進而又提出了一個優(yōu)
6、化查詢算法。通過在一個基因數(shù)據(jù)集上的實驗，顯示出所提出的技術(shù)能夠高效地支持大規(guī)模無損壓縮序列的子串查詢處理。關(guān)鍵詞：壓縮序列；在線查詢；子串查詢；索引；過濾東北大學碩士學位論文AbstmctPrecessingandOptimizationTechniquesforOnlineSearchingSubsequencesonLargeCompressedSequencesAbstractWiththedevelopmentofsocietyandscience，theamountofinformationdataincreasesex
7、ponentially,especiallygenomicsequencesdata，itsincreasingrateisincredible，whichposesabigpressureonthestorageandtransmissionofdata,SOtherearemanycompressiontechniquesproposedtosolvethisproblem．Searchingsubsequencesoncompressedsequencesisveryimportantinpracticalapplicatio
8、nssuchasgenomicsequenceanalysisandkeywordsearching，wheretheirsequencedataisalwayskeptcompressedinordertoreducethegrea
