基于局部過濾的字符串近似匹配算法和優(yōu)化技術.pdf_第1頁
已閱讀1頁,還剩74頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

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ù)據集上和如今三個主流的算法進行實驗。實驗結果顯示局部過濾方法的運行時間,過濾能力和索引大小都要

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論