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

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

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

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