本文參考：字符串相似度算法（編輯距離算法 Levenshtein Distance）
編輯距離，又稱Levenshtein距離（也叫做Edit Distance），是指兩個(gè)字串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)，如果它們的距離越大，說(shuō)明它們?cè)绞遣煌ＴS可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)字符，刪除一個(gè)字符。
例如將kitten一字轉(zhuǎn)成sitting：
sitten （k→s）
sittin （e→i）
sitting （→g）
俄羅斯科學(xué)家Vladimir Levenshtein在1965年提出這個(gè)概念。因此也叫Levenshtein Distance。
例如
- 如果str1="ivan"，str2="ivan"，那么經(jīng)過(guò)計(jì)算后等于 0。沒(méi)有經(jīng)過(guò)轉(zhuǎn)換。相似度=1-0/Math.Max(str1.length,str2.length)
- 如果str1="ivan1"，str2="ivan2"，那么經(jīng)過(guò)計(jì)算后等于1。str1的"1"轉(zhuǎn)換"2"，轉(zhuǎn)換了一個(gè)字符，所以距離是1，相似度=1-1/Math.Max(str1.length,str2.length)
應(yīng)用
DNA分析
拼字檢查
語(yǔ)音辨識(shí)
抄襲偵測(cè)
算法過(guò)程
- str1或str2的長(zhǎng)度為0返回另一個(gè)字符串的長(zhǎng)度。 if(str1.length==0) return str2.length; if(str2.length==0) return str1.length;
- 初始化(n+1)*(m+1)的矩陣d，并讓第一行和列的值從0開(kāi)始增長(zhǎng)。
- 掃描兩字符串（n*m級(jí)的），如果：str1[i] == str2[j]，用temp記錄它，為0。否則temp記為1。然后在矩陣d[i,j]賦于d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp三者的最小值。
- 掃描完后，返回矩陣的最后一個(gè)值d[n][m]即是它們的距離。
計(jì)算相似度公式：1-它們的距離/兩個(gè)字符串長(zhǎng)度的最大值。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace DeepLeo.Library.String { public class LevenshteinSimilarity { public class LevenshteinDistance { /// <summary> /// 取最小的一位數(shù) /// </summary> /// <param name="first"></param> /// <param name="second"></param> /// <param name="third"></param> /// <returns></returns> private int LowerOfThree(int first, int second, int third) { int min = Math.Min(first, second); return Math.Min(min, third); } private int Levenshtein_Distance(string str1, string str2) { int[,] Matrix; int n = str1.Length; int m = str2.Length; int temp = 0; char ch1; char ch2; int i = 0; int j = 0; if (n == 0) { return m; } if (m == 0) { return n; } Matrix = new int[n + 1, m + 1]; for (i = 0; i <= n; i++) { //初始化第一列 Matrix[i, 0] = i; } for (j = 0; j <= m; j++) { //初始化第一行 Matrix[0, j] = j; } for (i = 1; i <= n; i++) { ch1 = str1[i - 1]; for (j = 1; j <= m; j++) { ch2 = str2[j - 1]; if (ch1.Equals(ch2)) { temp = 0; } else { temp = 1; } Matrix[i, j] = LowerOfThree(Matrix[i - 1, j] + 1, Matrix[i, j - 1] + 1, Matrix[i - 1, j - 1] + temp); } } for (i = 0; i <= n; i++) { for (j = 0; j <= m; j++) { Console.Write(" {0} ", Matrix[i, j]); } Console.WriteLine(""); } return Matrix[n, m]; } /// <summary> /// 計(jì)算字符串相似度 /// </summary> /// <param name="str1"></param> /// <param name="str2"></param> /// <returns></returns> public decimal LevenshteinDistancePercent(string str1, string str2) { //int maxLenth = str1.Length > str2.Length ? str1.Length : str2.Length; int val = Levenshtein_Distance(str1, str2);return 1 - (decimal)val / Math.Max(str1.Length, str2.Length); } } } } |
