字符串相似度和字符串編輯距離

C#字符串和正則表達(dá)式參考手冊PDF電子書

• 類型：電子教程大�。�9.5M語言：中文 評分：7.5
• 標(biāo)簽：

立即下載

余弦相似度

計(jì)算公式為：

P(A，B) = sqrt(A × B) / (|A| × |B|)

設(shè)有兩個(gè)字符串：

ABCDEFG

ABCHIJK

其中共有11個(gè)字符，為：

A B C D E F G H I J K

如果，不考慮他們之間的關(guān)聯(lián)性以及順序等隱私，那么可以講這兩個(gè)字符串轉(zhuǎn)換成兩個(gè)11維空間中的向量：

{1、1、1、1、1、1、1、0、0、0、0}

{1、1、1、0、0、0、0、1、1、1、1}

那，計(jì)算他們之間的相似度為：

P = sqrt(3) / (sqrt(7) × sqrt(7)) = 0.2474358297

矩陣相似度

給定兩個(gè)長度相等的字符串，在移動(dòng)的過程中比較：

首先有幾個(gè)變量：

n：字符串的長度，此時(shí)為10；

m：相同的字符，此時(shí)為3，包括d、a、c；

r：兩個(gè)字符串重疊部分，此時(shí)為8；

那么給出定義：

重疊率：L = r / n。

匹配率：M = m / n。

相似度：Q = M^2 × L = (m^2 / n^2) × (r / n)。

其實(shí)為什么這樣定義也很好理解，將Q變形一下就可以得到：

　　Q = (m^2 / r^2) × (r / n)

前半部分表示了當(dāng)前相同的比率，后半部分表示了重疊的比率，然后呢，廢話就不多說了。其實(shí)，還有一個(gè)要考慮的地方，舉個(gè)例子：

　　str1：abcabc

　　str2：abcdabc

str1和str2的相似度是很高的，但是，在移位錯(cuò)開的過程中根本沒辦法找到這種匹配。想想其實(shí)原因也是非常簡單的：把所有的字符都死板地粘合在了一起！那么，我們要做的其實(shí)就是將他們打散來匹配。首先，根據(jù)字符串A和字符串B來構(gòu)造矩陣R：

　　Ai和Bi+j相同時(shí)，Rij = 1；否則，Rij = 0。

那么，現(xiàn)在要做的事情就是，在矩陣R中尋找一條路徑，使得這條路徑上的1最多，這個(gè)問題和求兩個(gè)字符串的最大匹配和像的DP問題，這里就不啰嗦了。

字符串編輯距離

還有一種衡量兩個(gè)字符串之間的差異性的方法是，計(jì)算兩個(gè)字符串轉(zhuǎn)換時(shí)候需要的最少操作，需要的操作越少說明這兩個(gè)字符串越相似。

假設(shè)字符串的操作只有三種：

插入一個(gè)字符；

刪除一個(gè)字符；

替換一個(gè)字符；

兩個(gè)字符串之間的編輯距離定義為：從字符串str1到str2的最少的操作次數(shù)。首先，編輯距離是不會(huì)大于str1.length + str2.length的。假設(shè)求字符A、B的編輯距離，考慮下面幾種情況：

如果A[i] = B[j]，那么這時(shí)候還需要操作嗎？

這個(gè)時(shí)候的刪除和替換操作只會(huì)讓情況變得更壞，而且插入操作不會(huì)使情況變得更好，所以此時(shí)F(i, j) = F(i-1, j-1)。

如果A[i] != B[j]，怎么辦呢？

a、從F(i-1, j-1)變過來，這時(shí)候只需要把A[i]替換為B[j]即可；

b、從F(i-1, j)變過來，這時(shí)候只需要將A[i]刪除即可；

c、從F(i, j-1)變過來，這時(shí)候只需要在A[i]后插入字符B[j]即可；

那么此時(shí)，F(i, j) = min{F(i-1，j-1)，F(xiàn)(i-1，j)，F(xiàn)(i，j-1)} + 1。

注：其中F(i, j)表示A[0..i]和B[0..j]之間的編輯距離�？赐赀@種相似度想起了BFS的入門題目：《聰明的打字員》，囧。