相似字符串匹配過濾算法研究.pdf

1、相似字符串匹配是計算機科學中的一個基礎(chǔ)問題,它在很多領(lǐng)域都有廣泛的應(yīng)用,如信息檢索、計算生物學和模式識別等。研究快速、準確和低耗的相似字符串匹配算法對這些方向的發(fā)展有一定的推動作用。
　　 q-gram索引具有語言獨立性和高容錯性,適合中文處理。過濾算法能根掘過濾條件快速拋棄文本中與匹配無關(guān)的文本片段,適合大庫查找。q-gram索引和過濾算法經(jīng)常結(jié)合使用,q-gram過濾算法因其簡單、快速而得到廣泛應(yīng)用。為對中文語料庫進行相似字

2、符串匹配,提高q-gram過濾算法的匹配速度,本文主要從中文索引結(jié)構(gòu)、索引優(yōu)化、匹配區(qū)域特征挖掘等方面進行研究。
　　 為對中文語料庫進行相似字符串匹配,本文提出一種中文Bigram二級哈希索引結(jié)構(gòu),索引中使用哈希函數(shù)把中文GB2312編碼表中的所有漢字映射到一維連續(xù)的整數(shù)空間中,并采用二級存儲方式存儲中文Bigram項。
　　 為提高索引速度和減少索引占用空間,本文對索引進行了優(yōu)化。采用鏈表式內(nèi)存管理方案對地址列表的內(nèi)

3、存分配進行管理,這種方法提高了內(nèi)存的使用效率。采用了索引壓縮技術(shù)減少索引占用的內(nèi)存空間,實驗中針對多種壓縮算法進行對比,得出了適合三元組地址列表的中文Bigram索引壓縮方法。
　　 為通過提高過濾算法的過濾效率加快匹配速度,提出一種基于匹配區(qū)域特征的過濾算法。該算法將模式串和文本串都分割成固定長度的邏輯塊,并從各塊中提取了新的匹配區(qū)域特征。新算法利用新特征優(yōu)化了基礎(chǔ)過濾準則,提高了算法的過濾效率,并改進了基于分塊策略的過濾區(qū)確