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

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

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

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

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