本文参考：字符串相似度算法（编辑距离算法 Levenshtein Distance）
编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
例如将kitten一字转成sitting：
sitten （k→s）
sittin （e→i）
sitting （→g）
俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。因此也叫Levenshtein Distance。
例如
- 如果str1="ivan"，str2="ivan"，那么经过计算后等于 0。没有经过转换。相似度=1-0/Math.Max(str1.length,str2.length)
- 如果str1="ivan1"，str2="ivan2"，那么经过计算后等于1。str1的"1"转换"2"，转换了一个字符，所以距离是1，相似度=1-1/Math.Max(str1.length,str2.length)
应用
DNA分析
拼字检查
语音辨识
抄袭侦测
算法过程
- str1或str2的长度为0返回另一个字符串的长度。 if(str1.length==0) return str2.length; if(str2.length==0) return str1.length;
- 初始化(n+1)*(m+1)的矩阵d，并让第一行和列的值从0开始增长。
- 扫描两字符串（n*m级的），如果：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三者的最小值。
- 扫描完后，返回矩阵的最后一个值d[n][m]即是它们的距离。
计算相似度公式：1-它们的距离/两个字符串长度的最大值。
|
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> /// 取最小的一位数 /// </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> /// 计算字符串相似度 /// </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); } } } } |
