基于劃分的雙向過濾-驗證字符串相似連接.pdf

1、字符串相似連接是指在字符串集中按照指定的相似性度量方法找出所有相似度滿足給定閾值的字符串對，具有廣泛的應用領域。例如：相似網(wǎng)頁檢測、實體解析、協(xié)同過濾、數(shù)據(jù)整合與清洗等。相似連接作為許多應用的基本操作，其效率是影響數(shù)據(jù)處理性能的關鍵，已成為數(shù)據(jù)管理研究領域的熱點問題之一。
　　在最近幾年提出的相似連接算法中，基于劃分的過濾-驗證方法（PassJoin）脫穎而出。它既能適用于長字符串，也能適用于短字符串，是目前最為高效的相似連接算法

2、。該方法按照字符串長度遞增的順序訪問字符串集合，通過查找一個字符串的劃分塊是否存在于另一個字符串中，快速篩選出可能相似的字符串對（候選集），然后利用編輯距離進行相似性驗證。
　　經(jīng)我們研究發(fā)現(xiàn)，按照字符串長度遞減的順序進行過濾（長度遞減過濾）產(chǎn)生的候選集與按照長度遞增的順序過濾（長度遞增過濾）產(chǎn)生的候選集不同，并且長度遞減過濾效果優(yōu)于長度遞增過濾。由此推出：雙向過濾能產(chǎn)生更小的候選集。為了充分利用雙向過濾帶來的優(yōu)勢，本文提出基于

3、pipeline方式的雙向過濾-驗證機制：在過濾階段，首先執(zhí)行長度遞減過濾，并在長度遞減過濾結果的基礎上進行長度遞增過濾，這樣做既可以獲得最小的候選集，也能最大限度地降低雙向過濾的開銷；其中采用基于雙向過濾的多匹配感知子串選擇算法為字符串選擇與劃分塊相匹配的子串。在驗證階段，利用雙向過濾產(chǎn)生的兩對劃分塊和其匹配子串分隔字符串對，將字符串劃分成五個部分，再分別對分隔開的子串進行相似性驗證，如此可以減小需要驗證的字符串的長度，加速驗證過程。