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

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

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

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