基于編輯距離字符串Top-k相似性搜索算法的研究.pdf

1、字符串相似性搜索在眾多的領(lǐng)域具有廣泛的應(yīng)用，例如：數(shù)據(jù)清洗、數(shù)據(jù)集成、拼寫檢查、抄襲檢測、生物序列分析等。到目前為止，有很多度量標(biāo)準(zhǔn)用來衡量字符串之間的相似程度，然而眾所周知不存在一個相似性函數(shù)在所有領(lǐng)域中都具有最好的性質(zhì)，編輯距離是所有被廣泛接受的相似性函數(shù)中的一個。因此本文通過編輯距離表示兩個字符串之間的相似程度。一般而言，字符串相似性搜索主要有兩種類型：范圍查詢和Top-k相似性搜索，本文主要研究Top-k搜索問題，即給定一個查詢

2、字符串q，Top-k搜索返回字符串集合S中k個字符串，滿足這k個字符串和查詢字符串q的編輯距離最小。
　　現(xiàn)如今解決字符串Top-k相似性搜索共有三類算法，AQ和Appgram基于n-gram模型，但這兩種方法忽略了n-gram的位置信息，同時AQ算法需要對不同長度n-gram建立多個索引導(dǎo)致很低的效率，Appgram不是精確查詢，往往會丟失結(jié)果，Bedtree算法基于B+樹結(jié)構(gòu)，由于過濾條件過于寬松導(dǎo)致遍歷過多節(jié)點，Range算

3、法和Hstopk算法針對短字符串很有效，當(dāng)處理長字符串集合時，為了提高查詢性能，這兩種算法需要很大的額外內(nèi)存空間。
　　針對現(xiàn)如今方法的缺陷，本文基于n-gram模型，結(jié)合n-gram位置信息，設(shè)計了新的倒排索引結(jié)構(gòu)，在這個新的索引結(jié)構(gòu)上設(shè)計了新的順序搜索和改進(jìn)的循環(huán)搜索算法；在過濾階段，加入了長度過濾，數(shù)量過濾和位置過濾，同時加入了新的過濾方式頻率過濾，實驗證明頻率過濾可以進(jìn)一步過濾掉大量候選字符串；同時本文針對top-k查詢的

4、初始化進(jìn)行了研究，結(jié)合字符串集合整體統(tǒng)計信息，將字符串集合分類，采用和查詢字符串同一類的字符串進(jìn)行初始化；最后設(shè)計了基于磁盤的索引構(gòu)建和查詢方法；最后本文在三個真實數(shù)據(jù)集上進(jìn)行了多組對比實驗驗證本文提出算法的高效性，首先測試各種算法在這三個真實數(shù)據(jù)集上內(nèi)存消耗，然后比較了各個算法查詢性能，同時對索引的兩種構(gòu)建方式，兩種搜索策略，堆的四種初始化算法進(jìn)行了對比實驗，然后對基于磁盤索引構(gòu)建時間和查詢性能進(jìn)行了測試，最后對長度過濾策略和頻率過濾