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

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

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

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