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

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

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