支持大規(guī)模壓縮序列的在線子串查詢處理與優(yōu)化技術(shù).pdf

1、隨著社會的進(jìn)步和科學(xué)的發(fā)展，信息數(shù)據(jù)量呈爆炸性增長，特別是基因序列這樣的數(shù)據(jù)，其增長速度已經(jīng)超出了人們的想象，給數(shù)據(jù)存儲和傳輸造成了很大的壓力，各種壓縮技術(shù)被提出來解決這樣的問題。在壓縮序列上進(jìn)行子串查詢處理對于基因序列分析和關(guān)鍵字搜索等實(shí)際應(yīng)用非常有意義。這些序列數(shù)據(jù)往往以壓縮形式存儲，給子串查詢造成一定的難度，使得該研究領(lǐng)域面臨著巨大的挑戰(zhàn)。
　　本文所研究的內(nèi)容是基于最近提出的一種無損壓縮技術(shù)，對于多個(gè)非常相似的字符序列，只

2、需保留一個(gè)參照序列，然后利用參照序列上的編輯操作來編碼這些相似序列與參照序列的差異。該技術(shù)對于基因這種大規(guī)模的字符序列能夠起到非常好的壓縮效果。這種壓縮技術(shù)是新穎而且重要的，那么如何在這種大規(guī)模壓縮序列上進(jìn)行在線子串查詢處理是本文要解決的問題。
　　針對上述大規(guī)模無損壓縮序列，本文針對參照序列是否在線被處理這兩種情況，分別提出相應(yīng)的在線子串查詢處理與優(yōu)化技術(shù)。在未索引參照序列的情況下，通過改進(jìn)經(jīng)典的BM算法，提出了支持單壓縮序列的