相似字符串匹配過(guò)濾算法研究.pdf

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

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

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