基于局部過濾的字符串近似匹配算法和優(yōu)化技術(shù).pdf

1、隨著計(jì)算機(jī)的發(fā)展，社會(huì)中各行各業(yè)都離不開計(jì)算機(jī)，同時(shí)計(jì)算機(jī)可以給人們帶來很大的方便和創(chuàng)新。字符串在計(jì)算機(jī)領(lǐng)域中是一種重要且基礎(chǔ)的存儲(chǔ)結(jié)構(gòu)?，F(xiàn)如今大量的數(shù)據(jù)都是以字符串這種數(shù)據(jù)結(jié)構(gòu)的形式存放的。如何在給定的大規(guī)模字符串集合中高效率地找到與用戶輸入相匹配的字符串一直是個(gè)重要的研究問題。
　　尤其是實(shí)現(xiàn)對(duì)字符串的近似匹配具有重要的現(xiàn)實(shí)意義和技術(shù)挑戰(zhàn)。文本著重研究基于編輯距離的近似字符串匹配問題，研究高效率的匹配算法。
　　本文首先

2、綜述了經(jīng)典的支持編輯距離的近似字符串匹配技術(shù)，并分析出現(xiàn)有的方法都采用公共匹配因子進(jìn)行過濾的思想。基于此，提出了局部過濾的匹配思想，即兩個(gè)不相似的字符串一定由若干個(gè)不相似的片段組成。為了過濾掉不相似的字符串對(duì)，需要找到一些不相似的片段。本文首先定義局部距離的概念以用來度量?jī)蓚€(gè)字符串之間的局部不相似這個(gè)特性。根據(jù)局部距離的定義提出了局部距離的累加定理來進(jìn)行過濾。提出了帶有位置約束的局部過濾以提高算法的過濾能力。本文還設(shè)計(jì)了一種索引結(jié)構(gòu)Bi

3、tTree來管理帶有位置約束的局部距離。根據(jù)這個(gè)索引結(jié)構(gòu)設(shè)計(jì)兩種算法對(duì)字符串集合中的字符串進(jìn)行過濾。另外，局部距離同樣可以在驗(yàn)證階段使用。由于BitTree索引結(jié)構(gòu)存儲(chǔ)空間很大，本文提出了新的索引結(jié)構(gòu)PBitTree索引和CoreBitmap索引來減少空間復(fù)雜度，同時(shí)設(shè)計(jì)出一種局部過濾的估計(jì)算法來進(jìn)行字符串的過濾。
　　本文在三個(gè)真實(shí)的數(shù)據(jù)集上和如今三個(gè)主流的算法進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果顯示局部過濾方法的運(yùn)行時(shí)間，過濾能力和索引大小都要