Code666 (代码贴、代码片段)

[C#] 字符串相似度算法（编辑距离算法 Levenshtein Distance）原理及C#代码实现 →→→→→进入此内容的聊天室

来自 , 2021-03-19, 写在 C#, 查看 113 次.
URL http://www.code666.cn/view/700fdb2b
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace DeepLeo.Library.String
  7. {
  8. public class LevenshteinSimilarity
  9. {
  10. public class LevenshteinDistance
  11. {
  12.  
  13. /// <summary>
  14. /// 取最小的一位数
  15. /// </summary>
  16. /// <param name="first"></param>
  17. /// <param name="second"></param>
  18. /// <param name="third"></param>
  19. /// <returns></returns>
  20. private int LowerOfThree(int first, int second, int third)
  21. {
  22.  
  23. int min = Math.Min(first, second);
  24.  
  25. return Math.Min(min, third);
  26.  
  27. }
  28.  
  29. private int Levenshtein_Distance(string str1, string str2)
  30. {
  31.  
  32. int[,] Matrix;
  33.  
  34. int n = str1.Length;
  35.  
  36. int m = str2.Length;
  37.  
  38. &nbsp;
  39.  
  40. int temp = 0;
  41.  
  42. char ch1;
  43.  
  44. char ch2;
  45.  
  46. int i = 0;
  47.  
  48. int j = 0;
  49.  
  50. if (n == 0)
  51. {
  52.  
  53. return m;
  54.  
  55. }
  56.  
  57. if (m == 0)
  58. {
  59.  
  60. &nbsp;
  61.  
  62. return n;
  63.  
  64. }
  65.  
  66. Matrix = new int[n + 1, m + 1];
  67.  
  68. &nbsp;
  69.  
  70. for (i = 0; i <= n; i++)
  71. {
  72.  
  73. //初始化第一列
  74.  
  75. Matrix[i, 0] = i;
  76.  
  77. }
  78.  
  79. &nbsp;
  80.  
  81. for (j = 0; j <= m; j++)
  82. {
  83.  
  84. //初始化第一行
  85.  
  86. Matrix[0, j] = j;
  87.  
  88. }
  89.  
  90. &nbsp;
  91.  
  92. for (i = 1; i <= n; i++)
  93. {
  94.  
  95. ch1 = str1[i - 1];
  96.  
  97. for (j = 1; j <= m; j++)
  98. {
  99.  
  100. ch2 = str2[j - 1];
  101.  
  102. if (ch1.Equals(ch2))
  103. {
  104.  
  105. temp = 0;
  106.  
  107. }
  108.  
  109. else
  110. {
  111.  
  112. temp = 1;
  113.  
  114. }
  115.  
  116. Matrix[i, j] = LowerOfThree(Matrix[i - 1, j] + 1, Matrix[i, j - 1] + 1, Matrix[i - 1, j - 1] + temp);
  117.  
  118. }
  119.  
  120. }
  121.  
  122. for (i = 0; i <= n; i++)
  123. {
  124.  
  125. for (j = 0; j <= m; j++)
  126. {
  127.  
  128. Console.Write(" {0} ", Matrix[i, j]);
  129.  
  130. }
  131.  
  132. Console.WriteLine("");
  133.  
  134. }
  135.  
  136. &nbsp;
  137.  
  138. return Matrix[n, m];
  139.  
  140. }
  141. /// <summary>
  142.  
  143. /// 计算字符串相似度
  144.  
  145. /// </summary>
  146.  
  147. /// <param name="str1"></param>
  148.  
  149. /// <param name="str2"></param>
  150.  
  151. /// <returns></returns>
  152.  
  153. public decimal LevenshteinDistancePercent(string str1, string str2)
  154. {
  155.  
  156. //int maxLenth = str1.Length > str2.Length ? str1.Length : str2.Length;
  157.  
  158. int val = Levenshtein_Distance(str1, str2);return 1 - (decimal)val / Math.Max(str1.Length, str2.Length);
  159.  
  160. }
  161. }
  162. }
  163. }
  164. //csharp/7288

回复 "字符串相似度算法（编辑距离算法 Levenshtein Distance）原理及C#代码实现"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666