基于Appgram的字符串近似搜索與連接的研究與改進(jìn).pdf

1、在傳統(tǒng)數(shù)據(jù)庫(kù)中進(jìn)行查詢(xún)時(shí)，選擇與連接被視為最重要的幾個(gè)操作之一，而在實(shí)際情況中，由于可能的錯(cuò)誤或由不同數(shù)據(jù)格式導(dǎo)致數(shù)據(jù)呈現(xiàn)不一致，如果使用精確的選擇與連接操作，由于數(shù)據(jù)字段無(wú)法完全匹配，數(shù)據(jù)查詢(xún)可能無(wú)法返回結(jié)果。針對(duì)上述情形，通過(guò)采用一定容錯(cuò)機(jī)制，近似選擇與連接被引入查詢(xún)處理中。然而字符串近似搜索與連接不僅僅可以用于數(shù)據(jù)庫(kù)中，同時(shí)在許多領(lǐng)域都有著廣泛的應(yīng)用，例如DNA序列分析、時(shí)間序列處理、重復(fù)Web頁(yè)面檢測(cè)、拼寫(xiě)檢查、數(shù)據(jù)清洗、數(shù)據(jù)集

2、成以及搜索引擎中查詢(xún)建議等等。
　　針對(duì)現(xiàn)有算法處理字符串近似搜索與連接問(wèn)題時(shí)間開(kāi)銷(xiāo)過(guò)大的情況，本文基于Appgram算法框架，以提高算法性能為主要目標(biāo)，簡(jiǎn)要闡述字符串近似搜索與連接問(wèn)題定義、涉及的相關(guān)概念、算法常用框架以及性能評(píng)估等之后，對(duì)算法處理時(shí)性能瓶頸及各解決方案可行性進(jìn)行了深入研究并加以改進(jìn)。
　　(1)通過(guò)將字符串結(jié)構(gòu)信息引入，設(shè)計(jì)了新的倒排索引結(jié)構(gòu)，實(shí)現(xiàn)對(duì)字符串計(jì)數(shù)過(guò)濾的改進(jìn)，進(jìn)而可以有效避免某些情況下對(duì)出現(xiàn)頻

3、次的重復(fù)計(jì)數(shù)，減少了識(shí)別階段需處理的候選串集合大小，降低了算法執(zhí)行時(shí)間，有效提高性能。
　　(2)通過(guò)在算法第二輪過(guò)濾中將原有過(guò)濾擴(kuò)展為多層近似過(guò)濾，充分利用原有邊界條件，給候選串集合制定一個(gè)更加嚴(yán)格的準(zhǔn)入約束，減少了最終需要識(shí)別的候選串?dāng)?shù)目，降低了算法執(zhí)行時(shí)間，有效提高性能。
　　(3)對(duì)前兩步驟中提出的算法進(jìn)行擴(kuò)展，使原先用于字符串近似搜索問(wèn)題的算法可以應(yīng)用到字符串集合近似自連接問(wèn)題中，與此同時(shí)，為了解決最終結(jié)果集中出現(xiàn)