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

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

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

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