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

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

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

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