[發(fā)明專利]一種Web環(huán)境下的字符串相似度的分析方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 200910011738.7
• 申請(qǐng)日: 2009-05-27
• 公開（公告）號(hào): CN101561813A
• 公開（公告）日: 2009-10-21
• 發(fā)明（設(shè)計(jì)）人: 于戈;申德榮;朱命冬;寇月;聶鐵錚;王振華
• 申請(qǐng)（專利權(quán)）人: 東北大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30;G06F17/22
• 代理公司: 沈陽(yáng)東大專利代理有限公司
• 代理人: 李運(yùn)萍

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)Web數(shù)據(jù)庫(kù)領(lǐng)域，特別適用于Web數(shù)據(jù)庫(kù)集成系統(tǒng)重復(fù)記錄識(shí)別過(guò)程中兩條記錄相似度的判定。

背景技術(shù)

在web環(huán)境中，對(duì)于需要進(jìn)行相似度匹配的字符串，常常會(huì)遇到拼寫錯(cuò)誤、關(guān)鍵詞順序顛倒、縮寫詞或省略詞匹配等情況，導(dǎo)致應(yīng)用于web環(huán)境下的字符串相似度分析方法面臨很多困難。因?yàn)榈湫偷某Ｓ米址嗨贫确治龇椒ㄍǔＶ会槍?duì)某一特定情況。如：Levenshteindistance較適合于拼寫錯(cuò)誤，Jaro?distance?metric較適合于縮寫詞或省略詞識(shí)別。在應(yīng)用中，常常需要人工來(lái)判斷何種環(huán)境下使用什么樣的算法。然而，web環(huán)境中多是半結(jié)構(gòu)和無(wú)結(jié)構(gòu)數(shù)據(jù)，具體字符串的類型不容易判斷，因此無(wú)法保證應(yīng)用已有字符串匹配算法計(jì)算的字符串匹配的準(zhǔn)確度。

Levenshtein?Distance算法是首先由俄國(guó)科學(xué)家提出。在該方法中，求兩字符串之間的相似度的基本步驟如下：首先，建立編輯距離矩陣，然后，依次由左向右，由上向下計(jì)算矩陣單元的值，最后，矩陣中最右下矩陣單元的值即為兩字符串的編輯距離。該算法為較傳統(tǒng)的算法，優(yōu)點(diǎn)為過(guò)程簡(jiǎn)單，易于使用，但對(duì)逆序，縮寫詞匹配時(shí)效果不太好。

著名的Smih-Waternan算法，是在傳統(tǒng)的Levenshtein?distance基礎(chǔ)上改進(jìn)的算法。其基本步驟和Levenshtein?Distance算法只在計(jì)算矩陣單元值時(shí)不同。Smih-Waternan算法通過(guò)引入刪除補(bǔ)償、插入補(bǔ)償和替換補(bǔ)償三個(gè)參數(shù)來(lái)計(jì)算矩陣單元值。當(dāng)矩陣中所有的矩陣單元計(jì)算過(guò)以后，矩陣中最右下的矩陣單元值即為要計(jì)算的兩個(gè)字符串的編輯距離。該算法主要適用于尋找局部相似序列對(duì)，其缺點(diǎn)是對(duì)于逆序詞效果不太好。

字符串相似度的Jaro分析方法的主要思想是計(jì)算兩個(gè)字符串σ1和σ2的Jaro距離為：，其中|σ1|，|σ2|分別為兩個(gè)字符長(zhǎng)度，c為兩字符串中的“公共子串”長(zhǎng)度，t為替換總數(shù)，替換總數(shù)計(jì)算方法為：將σ1中的第i個(gè)公共字符與σ2中的第i個(gè)字符做比較，若做比較的兩個(gè)字符不相同則進(jìn)行一次替換。該算法的優(yōu)點(diǎn)是計(jì)算速度較快，對(duì)縮寫詞的識(shí)別準(zhǔn)確率較高。但該算法僅適合縮寫詞普遍存在的場(chǎng)合，對(duì)不是縮寫詞進(jìn)行比較時(shí)常常將兩詞的相似度錯(cuò)誤提高，導(dǎo)致失真。

發(fā)明內(nèi)容

為了解決已有技術(shù)的不足，本發(fā)明提供一種應(yīng)用于Web環(huán)境具有適應(yīng)性的字符串相似度分析方法——Ajusted-edit?distance分析方法，能很好地處理web中經(jīng)常出現(xiàn)的省略、縮寫和字符順序顛倒情況。

本發(fā)明的分析方法步驟如下：

步驟1.定義基本操作代價(jià)，由刪除字符代價(jià)，插入字符代價(jià)，替換字符代價(jià)組成。其中：

刪除字符代價(jià)cost(a—>ε)，表示刪除字符a的代價(jià)；

插入字符代價(jià)cost(ε—>a)，表示插入字符a的代價(jià)；

替換字符代價(jià)cost(a—>a)和cost(a—>b)，分別表示用字符a替換字符a的代價(jià)和用字符a替換字符b的代價(jià)；

步驟2.字符串預(yù)處理，包括識(shí)別詞首字符和去除非實(shí)義字符。其中，詞首字符指字符串中第一個(gè)實(shí)義字符或字符串中非實(shí)義字符后的第一個(gè)實(shí)義字符；非實(shí)義字符是指不具有實(shí)際意義的字符，包括空格、逗號(hào)、括號(hào)。

步驟3.計(jì)算距離矩陣，通過(guò)創(chuàng)建匹配索引實(shí)現(xiàn)字符串中字符位置的交換，進(jìn)而優(yōu)化編輯距離。

其中，匹配索引是指將一個(gè)字符串以最小代價(jià)的編輯操作序列轉(zhuǎn)換成另一個(gè)字符串的過(guò)程中，原本被插入或刪除的字符通過(guò)改變字符順序能夠以更小的代價(jià)進(jìn)行替換的字符的索引。在進(jìn)行實(shí)際交換之前，需要先計(jì)算一下兩個(gè)字符串的距離變化，只有當(dāng)距離變化小于0時(shí)才進(jìn)行位置交換。

創(chuàng)建匹配索引方法的步驟如下：

A.計(jì)算兩個(gè)字符串的距離矩陣；

B.將所有代價(jià)為0的字符對(duì)添加到匹配索引中；

C.通過(guò)距離矩陣選出一個(gè)代價(jià)最小的替換方案；

D.過(guò)濾匹配索引中在轉(zhuǎn)換方案中已經(jīng)采用的代價(jià)為0的替換方案；

E.過(guò)濾匹配索引中包含在其他索引對(duì)中出現(xiàn)的字符的索引對(duì)

F.結(jié)束

優(yōu)化編輯距離的具體公式如下：

ed′(x，y)＝ed(x，y)+distanceChange