1. 首页
  2. 文章中心
  3. Other

用C#实现字符串相似度算法（编辑距离算法 Levenshtein Distance）

181 阅读 0 评论
我是靠谱客的博主 忧郁期待，最近开发中收集的这篇文章主要介绍用C#实现字符串相似度算法（编辑距离算法 Levenshtein Distance），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在搞验证码识别的时候需要比较字符代码的相似度用到“编辑距离算法”，关于原理和C#实现做个记录。

据百度百科介绍：

编辑距离，又称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)=1
  • 如果str1="ivan1"，str2="ivan2"，那么经过计算后等于1。str1的"1"转换"2"，转换了一个字符，所以距离是1，相似度=1-1/Math.Max(str1.length,str2.length)=0.8

应用

　　DNA分析

　　拼字检查

　　语音辨识

　　抄袭侦测

算法过程

  1. str1或str2的长度为0返回另一个字符串的长度。 if(str1.length==0) return str2.length; if(str2.length==0) return str1.length;
  2. 初始化(n+1)*(m+1)的矩阵d，并让第一行和列的值从0开始增长。
  3. 扫描两字符串（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三者的最小值。
  4. 扫描完后，返回矩阵的最后一个值d[n][m]即是它们的距离。

计算相似度公式：1-它们的距离/两个字符串长度的最大值。
为了直观表现，我将两个字符串分别写到行和列中，实际计算中不需要。我们用字符串“ivan1”和“ivan2”举例来看看矩阵中值的状况：

1、第一行和第一列的值从0开始增长

    i v a n 1
  0 1 2 3 4 5
i 1          
v 2          
a 3          
n 4          
2 5          
 

2、i列值的产生 Matrix[i - 1, j] + 1 ; Matrix[i, j - 1] + 1   ;    Matrix[i - 1, j - 1] + t

    i v a n 1
  0+t=0 1+1=2 2 3 4 5
i 1+1=2 取三者最小值=0        
v 2 依次类推：1        
a 3 2        
n 4 3        
2 5 4        

 

3、V列值的产生

    i v a n 1
  0 1 2      
i 1 0 1      
v 2 1 0      
a 3 2 1      
n 4 3 2      
2 5 4 3      

 

依次类推直到矩阵全部生成

    i v a n 1
  0 1 2 3 4 5
i 1 0 1 2 3 4
v 2 1 0 1 2 3
a 3 2 1 0 1 2
n 4 3 2 1 0 1
2 5 4 3 2 1 1

 

最后得到它们的距离=1

相似度：1-1/Math.Max(“ivan1”.length,“ivan2”.length) =0.8

算法用C#实现

复制代码
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
<span style= "color: #008080" > 1</span> <span style= "color: #0000ff" > public </span> <span style= "color: #0000ff" > class </span><span style= "color: #000000" > LevenshteinDistance
</span><span style= "color: #008080" > 2</span> <span style= "color: #000000" >    {
</span><span style= "color: #008080" > 3</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><summary></span>
<span style= "color: #008080" > 4</span>         <span style= "color: #808080" > ///</span><span style="color: #008000"> 取最小的一位数
</span><span style= "color: #008080" > 5</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"></summary></span>
<span style= "color: #008080" > 6</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><param name="first"></param></span>
<span style= "color: #008080" > 7</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><param name="second"></param></span>
<span style= "color: #008080" > 8</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><param name="third"></param></span>
<span style= "color: #008080" > 9</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><returns></returns></span>
<span style= "color: #008080" >10</span>         <span style= "color: #0000ff" > private </span> <span style= "color: #0000ff" > int </span> LowerOfThree(<span style= "color: #0000ff" > int </span> first, <span style= "color: #0000ff" > int </span> second, <span style= "color: #0000ff" > int </span><span style= "color: #000000" > third)
</span><span style= "color: #008080" >11</span> <span style= "color: #000000" >        {
</span><span style= "color: #008080" >12</span>             <span style= "color: #0000ff" > int </span> min =<span style= "color: #000000" > Math.Min(first, second);
</span><span style= "color: #008080" >13</span>             <span style= "color: #0000ff" > return </span><span style= "color: #000000" > Math.Min(min, third);
</span><span style= "color: #008080" >14</span> <span style= "color: #000000" >        }
</span><span style= "color: #008080" >15</span>
<span style= "color: #008080" >16</span>         <span style= "color: #0000ff" > private </span> <span style= "color: #0000ff" > int </span> Levenshtein_Distance(<span style= "color: #0000ff" > string </span> str1, <span style= "color: #0000ff" > string </span><span style= "color: #000000" > str2)
</span><span style= "color: #008080" >17</span> <span style= "color: #000000" >        {
</span><span style= "color: #008080" >18</span>             <span style= "color: #0000ff" > int </span><span style= "color: #000000" >[,] Matrix;
</span><span style= "color: #008080" >19</span>             <span style= "color: #0000ff" > int </span> n =<span style= "color: #000000" > str1.Length;
</span><span style= "color: #008080" >20</span>             <span style= "color: #0000ff" > int </span> m =<span style= "color: #000000" > str2.Length;
</span><span style= "color: #008080" >21</span>
<span style= "color: #008080" >22</span>             <span style= "color: #0000ff" > int </span> temp = <span style= "color: #800080" >0</span><span style= "color: #000000" >;
</span><span style= "color: #008080" >23</span>             <span style= "color: #0000ff" > char </span><span style= "color: #000000" > ch1;
</span><span style= "color: #008080" >24</span>             <span style= "color: #0000ff" > char </span><span style= "color: #000000" > ch2;
</span><span style= "color: #008080" >25</span>             <span style= "color: #0000ff" > int </span> i = <span style= "color: #800080" >0</span><span style= "color: #000000" >;
</span><span style= "color: #008080" >26</span>             <span style= "color: #0000ff" > int </span> j = <span style= "color: #800080" >0</span><span style= "color: #000000" >;
</span><span style= "color: #008080" >27</span>             <span style= "color: #0000ff" > if </span> (n == <span style= "color: #800080" >0</span><span style= "color: #000000" >)
</span><span style= "color: #008080" >28</span> <span style= "color: #000000" >            {
</span><span style= "color: #008080" >29</span>                 <span style= "color: #0000ff" > return </span><span style= "color: #000000" > m;
</span><span style= "color: #008080" >30</span> <span style= "color: #000000" >            }
</span><span style= "color: #008080" >31</span>             <span style= "color: #0000ff" > if </span> (m == <span style= "color: #800080" >0</span><span style= "color: #000000" >)
</span><span style= "color: #008080" >32</span> <span style= "color: #000000" >            {
</span><span style= "color: #008080" >33</span>
<span style= "color: #008080" >34</span>                 <span style= "color: #0000ff" > return </span><span style= "color: #000000" > n;
</span><span style= "color: #008080" >35</span> <span style= "color: #000000" >            }
</span><span style= "color: #008080" >36</span>             Matrix = <span style= "color: #0000ff" > new </span> <span style= "color: #0000ff" > int </span>[n + <span style= "color: #800080" >1</span>, m + <span style= "color: #800080" >1</span><span style= "color: #000000" >];
</span><span style= "color: #008080" >37</span>
<span style= "color: #008080" >38</span>             <span style= "color: #0000ff" > for </span> (i = <span style= "color: #800080" >0</span>; i <= n; i++<span style= "color: #000000" >)
</span><span style= "color: #008080" >39</span> <span style= "color: #000000" >            {
</span><span style= "color: #008080" >40</span>                 <span style= "color: #008000" > //</span><span style="color: #008000">初始化第一列</span>
<span style= "color: #008080" >41</span>                 Matrix[i, <span style= "color: #800080" >0</span>] =<span style= "color: #000000" > i;
</span><span style= "color: #008080" >42</span> <span style= "color: #000000" >            }
</span><span style= "color: #008080" >43</span>
<span style= "color: #008080" >44</span>             <span style= "color: #0000ff" > for </span> (j = <span style= "color: #800080" >0</span>; j <= m; j++<span style= "color: #000000" >)
</span><span style= "color: #008080" >45</span> <span style= "color: #000000" >            {
</span><span style= "color: #008080" >46</span>                 <span style= "color: #008000" > //</span><span style="color: #008000">初始化第一行</span>
<span style= "color: #008080" >47</span>                 Matrix[<span style= "color: #800080" >0</span>, j] =<span style= "color: #000000" > j;
</span><span style= "color: #008080" >48</span> <span style= "color: #000000" >            }
</span><span style= "color: #008080" >49</span>
<span style= "color: #008080" >50</span>             <span style= "color: #0000ff" > for </span> (i = <span style= "color: #800080" >1</span>; i <= n; i++<span style= "color: #000000" >)
</span><span style= "color: #008080" >51</span> <span style= "color: #000000" >            {
</span><span style= "color: #008080" >52</span>                 ch1 = str1[i - <span style= "color: #800080" >1</span><span style= "color: #000000" >];
</span><span style= "color: #008080" >53</span>                 <span style= "color: #0000ff" > for </span> (j = <span style= "color: #800080" >1</span>; j <= m; j++<span style= "color: #000000" >)
</span><span style= "color: #008080" >54</span> <span style= "color: #000000" >                {
</span><span style= "color: #008080" >55</span>                     ch2 = str2[j - <span style= "color: #800080" >1</span><span style= "color: #000000" >];
</span><span style= "color: #008080" >56</span>                     <span style= "color: #0000ff" > if </span><span style= "color: #000000" > (ch1.Equals(ch2))
</span><span style= "color: #008080" >57</span> <span style= "color: #000000" >                    {
</span><span style= "color: #008080" >58</span>                         temp = <span style= "color: #800080" >0</span><span style= "color: #000000" >;
</span><span style= "color: #008080" >59</span> <span style= "color: #000000" >                    }
</span><span style= "color: #008080" >60</span>                     <span style= "color: #0000ff" > else </span>
<span style= "color: #008080" >61</span> <span style= "color: #000000" >                    {
</span><span style= "color: #008080" >62</span>                         temp = <span style= "color: #800080" >1</span><span style= "color: #000000" >;
</span><span style= "color: #008080" >63</span> <span style= "color: #000000" >                    }
</span><span style= "color: #008080" >64</span>                     Matrix[i, j] = LowerOfThree(Matrix[i - <span style= "color: #800080" >1</span>, j] + <span style= "color: #800080" >1</span>, Matrix[i, j - <span style= "color: #800080" >1</span>] + <span style= "color: #800080" >1</span>, Matrix[i - <span style= "color: #800080" >1</span>, j - <span style= "color: #800080" >1</span>] +<span style= "color: #000000" > temp);
</span><span style= "color: #008080" >65</span> <span style= "color: #000000" >                }
</span><span style= "color: #008080" >66</span> <span style= "color: #000000" >            }
</span><span style= "color: #008080" >67</span>         <span style= "color: #0000ff" > for </span> (i = <span style= "color: #800080" >0</span>; i <= n; i++<span style= "color: #000000" >)
</span><span style= "color: #008080" >68</span> <span style= "color: #000000" >            {
</span><span style= "color: #008080" >69</span>                 <span style= "color: #0000ff" > for </span> (j = <span style= "color: #800080" >0</span>; j <= m; j++<span style= "color: #000000" >)
</span><span style= "color: #008080" >70</span> <span style= "color: #000000" >                {
</span><span style= "color: #008080" >71</span>                     Console.Write(<span style= "color: #800000" > "</span><span style=" color: #800000 "> {0} </span><span style=" color: #800000 ">" </span><span style= "color: #000000" >, Matrix[i, j]);
</span><span style= "color: #008080" >72</span> <span style= "color: #000000" >                }
</span><span style= "color: #008080" >73</span>                 Console.WriteLine(<span style= "color: #800000" > "" </span><span style= "color: #000000" >);
</span><span style= "color: #008080" >74</span> <span style= "color: #000000" >            }
</span><span style= "color: #008080" >75</span>      
<span style= "color: #008080" >76</span>             <span style= "color: #0000ff" > return </span><span style= "color: #000000" > Matrix[n, m];
</span><span style= "color: #008080" >77</span> <span style= "color: #000000" >        }
</span><span style= "color: #008080" >78</span>
<span style= "color: #008080" >79</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><summary></span>
<span style= "color: #008080" >80</span>         <span style= "color: #808080" > ///</span><span style="color: #008000"> 计算字符串相似度
</span><span style= "color: #008080" >81</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"></summary></span>
<span style= "color: #008080" >82</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><param name="str1"></param></span>
<span style= "color: #008080" >83</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><param name="str2"></param></span>
<span style= "color: #008080" >84</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><returns></returns></span>
<span style= "color: #008080" >85</span>         <span style= "color: #0000ff" > public </span> <span style= "color: #0000ff" > decimal </span> LevenshteinDistancePercent(<span style= "color: #0000ff" > string </span> str1, <span style= "color: #0000ff" > string </span><span style= "color: #000000" > str2)
</span><span style= "color: #008080" >86</span> <span style= "color: #000000" >        {
</span><span style= "color: #008080" >87</span>             <span style= "color: #008000" > //</span><span style="color: #008000">int maxLenth = str1.Length > str2.Length ? str1.Length : str2.Length;</span>
<span style= "color: #008080" >88</span>             <span style= "color: #0000ff" > int </span> val =<span style= "color: #000000" > Levenshtein_Distance(str1, str2);
</span><span style= "color: #008080" >89</span>             <span style= "color: #0000ff" > return </span> <span style= "color: #800080" >1</span> - (<span style= "color: #0000ff" > decimal </span>)val /<span style= "color: #000000" > Math.Max(str1.Length, str2.Length);
</span><span style= "color: #008080" >90</span> <span style= "color: #000000" >        }
</span><span style= "color: #008080" >91</span>     }
复制代码

 调用：

复制代码 
 1 static void Main(string[] args)
 2 
{
 3
string str1 = "ivan1";
 4
string str2 = "ivan2";
 5
Console.WriteLine("字符串1 {0}", str1);
 6
 7
Console.WriteLine("字符串2 {0}", str2);
 8
 9
Console.WriteLine("相似度 {0} %", new LevenshteinDistance().LevenshteinDistancePercent(str1, str2) * 100);
10 
Console.ReadLine();
11
}
复制代码

结果:

拓展与补充：

　小规模的字符串近似搜索，需求类似于搜索引擎中输入关键字，出现类似的结果列表。

    来源：.Net.NewLife。
    需求：假设在某系统存储了许多地址，例如：“北京市海淀区中关村大街1号海龙大厦”。用户输入“北京 海龙大厦”即可查询到这条结果。另外还需要有容错设计，例如输入“广西 京岛风景区”能够搜索到"广西壮族自治区京岛风景名胜区"。最终的需求是：可以根据用户输入，匹配若干条近似结果共用户选择。
    目的：避免用户输入类似地址导致数据出现重复项。例如，已经存在“北京市中关村”，就不应该再允许存在“北京中关村”。

    举例：

    此类技术在搜索引擎中早已广泛使用，例如“查询预测”功能。

    要实现此算法，首先需要明确“字符串近似”的概念。

    计算字符串相似度通常使用的是动态规划(DP)算法。

    常用的算法是 Levenshtein Distance。用这个算法可以直接计算出两个字符串的“编辑距离”。所谓编辑距离，是指一个字符串，每次只能通过插入一个字符、删除一个字符或者修改一个字符的方法，变成另外一个字符串的最少操作次数。这就引出了第一种方法：计算两个字符串之间的编辑距离。稍加思考之后发现，不能用输入的关键字直接与句子做匹配。你必须从句子中选取合适的长度后再做匹配。把结果按照距离升序排序。

复制代码 
 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5
 6 namespace BestString
 7 {
 8
public static class SearchHelper
 9 
{
10
public static string[] Search(string param, string[] datas)
11 
{
12
if (string.IsNullOrWhiteSpace(param))
13
return new string[0];
14
15
string[] words = param.Split(new char[] { ' ', '　' }, StringSplitOptions.RemoveEmptyEntries);
16
17
foreach (string word in words)
18 
{
19
int maxDist = (word.Length - 1) / 2;
20
21
var q = from str in datas
22
where word.Length <= str.Length
23
&& Enumerable.Range(0, maxDist + 1)
24
.Any(dist =>
25 
{
26
return Enumerable.Range(0, Math.Max(str.Length - word.Length - dist + 1, 0))
27
.Any(f =>
28 
{
29
return Distance(word, str.Substring(f, word.Length + dist)) <= maxDist;
30 
});
31 
})
32
orderby str
33
select str;
34
datas = q.ToArray();
35 
}
36
37
return datas;
38 
}
39
40
static int Distance(string str1, string str2)
41 
{
42
int n = str1.Length;
43
int m = str2.Length;
44
int[,] C = new int[n + 1, m + 1];
45
int i, j, x, y, z;
46
for (i = 0; i <= n; i++)
47
C[i, 0] = i;
48
for (i = 1; i <= m; i++)
49
C[0, i] = i;
50
for (i = 0; i < n; i++)
51
for (j = 0; j < m; j++)
52 
{
53
x = C[i, j + 1] + 1;
54
y = C[i + 1, j] + 1;
55
if (str1[i] == str2[j])
56
z = C[i, j];
57
else
58
z = C[i, j] + 1;
59
C[i + 1, j + 1] = Math.Min(Math.Min(x, y), z);
60 
}
61
return C[n, m];
62 
}
63 
}
64 }
复制代码

    分析这个方法后发现，每次对一个句子进行相关度比较的时候，都要把把句子从头到尾扫描一次，每次扫描还需要以最大误差作长度控制。这样一来，对每个句子的计算次数大大增加。达到了二次方的规模（忽略距离计算时间）。

    所以我们需要更高效的计算策略。在纸上写出一个句子，再写出几个关键字。一个一个涂画之后，偶然发现另一种字符串相关的算法完全可以适用。那就是 Longest common subsequence（LCS，最长公共字串）。为什么这个算法可以用来计算两个字符串的相关度？先看一个例子：

关键字：少年时代的神话播下了浪漫注意

句子：就是少年时代大量神话传说在其心田里播下了浪漫主义这颗难以磨灭的种子

    这里用了两个关键字进行搜索。可以看出来两个关键字都有部分匹配了句子中的若干部分。这样可以单独为两个关键字计算 LCS，LCS之和就是简单的相关度。看到这里，你若是已经理解了核心思想，已经可以实现出基本框架了。但是，请看下面这个例子：

关键字：东土大唐，唐三藏

句子：我本是东土大唐钦差御弟唐三藏大徒弟孙悟空行者

    看出来问题了吗？下面还是使用同样的关键字和句子。

关键字：东土大(唐唐)三藏

句子： 我本是东土大唐钦差御弟唐三藏大徒弟孙悟空行者

    举这个例子为了说明，在进行 LCS 计算的过程中，得到的结果并不能保证就是我们期望的结果。为了①保证所匹配的结果中不存在交集，并且②在句子中的匹配结果尽可能的短，需要采取两个补救措施。（为什么需要满足这样的条件，读者自行思考）

    第一：可以在单次计算 LCS 之后，用贪心策略向前（向后）找到最先能够完成匹配的位置，再用相同的策略向后（向前）扫描。这样可以满足第二个条件找到句子中最短的匹配。如果你对 LCS 算法有深入了解，完全可以在计算 LCS 的过程中找到最短匹配的结束位置，然后只需要进行一次向前扫描就可以完成。这样节约了一次扫描过程。

    第二：增加一个标记数组，记录句子中的字符是否被匹配过。

    最后标记数组中标记过的位置就是匹配结果。

    相信你看到这里一定非常头晕，下面用一个例子解释：（句子）

关键字：   ABCD

句子：     XAYABZCBXCDDYZ

句子分解： X Y  Z  X   YZ

           A   B C   D

              A   B C D

    你可能会匹配成 AYABZCBXCDD，AYABZCBXCD，ABZCBXCDD，ABZCBXCD。我们实际需要的只是ABZCBXCD。

    使用LCS匹配之后，得到的很可能是 XAYABZCBXCDDYZ；

    用贪心策略向前处理后，得到结果为 XAYABZCBXCDDYZ；

    用贪心策略向后处理后，得到结果为 XAYABZCBXCDDYZ。

    这样处理的目的是为了避免得到较长的匹配结果（类似正则表达式的贪婪、懒惰模式）。

    以上只是描述了怎么计算两个字符串的相似程度。除此之外还需要：①剔除相似度较低的结果；②对结果进行排序。

    剔除相似度较低的结果，这里设定了一个阈值：差错比例不能超过匹配结果长度的一半。

    对结果进行排序，不能够直接使用相似度进行排序。因为相似度并没有考虑到句子的长度。按照使用习惯，通常会把匹配度高，并且句子长度短的放在前面。这就得到了排序因子：（不匹配度+0.5）/句子长度。

    最后得到我们最终的搜索方法

复制代码 
 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 using System.Diagnostics;
 6
 7 namespace BestString
 8 {
 9
public static class SearchHelper
10 
{
11
public static string[] Search(string param, string[] items)
12 
{
13
if (string.IsNullOrWhiteSpace(param) || items == null || items.Length == 0)
14
return new string[0];
15
16
string[] words = param
17
.Split(new char[] { ' ', 'u3000' }, StringSplitOptions.RemoveEmptyEntries)
18
.OrderBy(s => s.Length)
19 
.ToArray();
20
21
var q = from sentence in items.AsParallel()
22
let MLL = Mul_LnCS_Length(sentence, words)
23
where MLL >= 0
24
orderby (MLL + 0.5) / sentence.Length, sentence
25
select sentence;
26
27
return q.ToArray();
28 
}
29
30
//static int[,] C = new int[100, 100];
31
32
/// <summary>
33
///
34
/// </summary>
35
/// <param name="sentence"></param>
36
/// <param name="words">多个关键字。长度必须大于0，必须按照字符串长度升序排列。</param>
37
/// <returns></returns>
38
static int Mul_LnCS_Length(string sentence, string[] words)
39 
{
40
int sLength = sentence.Length;
41
int result = sLength;
42
bool[] flags = new bool[sLength];
43
int[,] C = new int[sLength + 1, words[words.Length - 1].Length + 1];
44
//int[,] C = new int[sLength + 1, words.Select(s => s.Length).Max() + 1];
45
foreach (string word in words)
46 
{
47
int wLength = word.Length;
48
int first = 0, last = 0;
49
int i = 0, j = 0, LCS_L;
50
//foreach 速度会有所提升，还可以加剪枝
51
for (i = 0; i < sLength; i++)
52
for (j = 0; j < wLength; j++)
53
if (sentence[i] == word[j])
54 
{
55
C[i + 1, j + 1] = C[i, j] + 1;
56
if (first < C[i, j])
57 
{
58
last = i;
59
first = C[i, j];
60 
}
61 
}
62
else
63
C[i + 1, j + 1] = Math.Max(C[i, j + 1], C[i + 1, j]);
64
65
LCS_L = C[i, j];
66
if (LCS_L <= wLength >> 1)
67
return -1;
68
69
while (i > 0 && j > 0)
70 
{
71
if (C[i - 1, j - 1] + 1 == C[i, j])
72 
{
73
i--;
74
j--;
75
if (!flags[i])
76 
{
77
flags[i] = true;
78
result--;
79 
}
80
first = i;
81 
}
82
else if (C[i - 1, j] == C[i, j])
83
i--;
84
else// if (C[i, j - 1] == C[i, j])
85
j--;
86 
}
87
88
if (LCS_L <= (last - first + 1) >> 1)
89
return -1;
90 
}
91
92
return result;
93 
}
94 
}
95 }
复制代码

    对于此类问题，要想得到更快速的实现，必须要用到分词+索引的方案。在此不做探讨。

代码打包下载：http://files.cnblogs.com/Aimeast/BestString.zip

越努力才能越幸运，不让那些为我付出过的人失望。转载请注明：http://www.cnblogs.com/ECJTUACM-873284962/
分类:  language：C#
好文要顶  关注我  收藏该文   
Angel_Kitty
关注 - 35
粉丝 - 187
+加关注
0
0
« 上一篇： x64_dbg破解64位WinSnap4.5.6图文视频教程
posted @  2017-10-13 15:22  Angel_Kitty 阅读( 15) 评论( 0)  编辑  收藏

在搞验证码识别的时候需要比较字符代码的相似度用到“编辑距离算法”，关于原理和C#实现做个记录。

据百度百科介绍：

编辑距离，又称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)=1
  • 如果str1="ivan1"，str2="ivan2"，那么经过计算后等于1。str1的"1"转换"2"，转换了一个字符，所以距离是1，相似度=1-1/Math.Max(str1.length,str2.length)=0.8

应用

　　DNA分析

　　拼字检查

　　语音辨识

　　抄袭侦测

算法过程

  1. str1或str2的长度为0返回另一个字符串的长度。 if(str1.length==0) return str2.length; if(str2.length==0) return str1.length;
  2. 初始化(n+1)*(m+1)的矩阵d，并让第一行和列的值从0开始增长。
  3. 扫描两字符串（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三者的最小值。
  4. 扫描完后，返回矩阵的最后一个值d[n][m]即是它们的距离。

计算相似度公式：1-它们的距离/两个字符串长度的最大值。
为了直观表现，我将两个字符串分别写到行和列中，实际计算中不需要。我们用字符串“ivan1”和“ivan2”举例来看看矩阵中值的状况：

1、第一行和第一列的值从0开始增长

    i v a n 1
  0 1 2 3 4 5
i 1          
v 2          
a 3          
n 4          
2 5          
 

2、i列值的产生 Matrix[i - 1, j] + 1 ; Matrix[i, j - 1] + 1   ;    Matrix[i - 1, j - 1] + t

    i v a n 1
  0+t=0 1+1=2 2 3 4 5
i 1+1=2 取三者最小值=0        
v 2 依次类推：1        
a 3 2        
n 4 3        
2 5 4        

 

3、V列值的产生

    i v a n 1
  0 1 2      
i 1 0 1      
v 2 1 0      
a 3 2 1      
n 4 3 2      
2 5 4 3      

 

依次类推直到矩阵全部生成

    i v a n 1
  0 1 2 3 4 5
i 1 0 1 2 3 4
v 2 1 0 1 2 3
a 3 2 1 0 1 2
n 4 3 2 1 0 1
2 5 4 3 2 1 1

 

最后得到它们的距离=1

相似度：1-1/Math.Max(“ivan1”.length,“ivan2”.length) =0.8

算法用C#实现

复制代码
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
<span style= "color: #008080" > 1</span> <span style= "color: #0000ff" > public </span> <span style= "color: #0000ff" > class </span><span style= "color: #000000" > LevenshteinDistance
</span><span style= "color: #008080" > 2</span> <span style= "color: #000000" >    {
</span><span style= "color: #008080" > 3</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><summary></span>
<span style= "color: #008080" > 4</span>         <span style= "color: #808080" > ///</span><span style="color: #008000"> 取最小的一位数
</span><span style= "color: #008080" > 5</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"></summary></span>
<span style= "color: #008080" > 6</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><param name="first"></param></span>
<span style= "color: #008080" > 7</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><param name="second"></param></span>
<span style= "color: #008080" > 8</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><param name="third"></param></span>
<span style= "color: #008080" > 9</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><returns></returns></span>
<span style= "color: #008080" >10</span>         <span style= "color: #0000ff" > private </span> <span style= "color: #0000ff" > int </span> LowerOfThree(<span style= "color: #0000ff" > int </span> first, <span style= "color: #0000ff" > int </span> second, <span style= "color: #0000ff" > int </span><span style= "color: #000000" > third)
</span><span style= "color: #008080" >11</span> <span style= "color: #000000" >        {
</span><span style= "color: #008080" >12</span>             <span style= "color: #0000ff" > int </span> min =<span style= "color: #000000" > Math.Min(first, second);
</span><span style= "color: #008080" >13</span>             <span style= "color: #0000ff" > return </span><span style= "color: #000000" > Math.Min(min, third);
</span><span style= "color: #008080" >14</span> <span style= "color: #000000" >        }
</span><span style= "color: #008080" >15</span>
<span style= "color: #008080" >16</span>         <span style= "color: #0000ff" > private </span> <span style= "color: #0000ff" > int </span> Levenshtein_Distance(<span style= "color: #0000ff" > string </span> str1, <span style= "color: #0000ff" > string </span><span style= "color: #000000" > str2)
</span><span style= "color: #008080" >17</span> <span style= "color: #000000" >        {
</span><span style= "color: #008080" >18</span>             <span style= "color: #0000ff" > int </span><span style= "color: #000000" >[,] Matrix;
</span><span style= "color: #008080" >19</span>             <span style= "color: #0000ff" > int </span> n =<span style= "color: #000000" > str1.Length;
</span><span style= "color: #008080" >20</span>             <span style= "color: #0000ff" > int </span> m =<span style= "color: #000000" > str2.Length;
</span><span style= "color: #008080" >21</span>
<span style= "color: #008080" >22</span>             <span style= "color: #0000ff" > int </span> temp = <span style= "color: #800080" >0</span><span style= "color: #000000" >;
</span><span style= "color: #008080" >23</span>             <span style= "color: #0000ff" > char </span><span style= "color: #000000" > ch1;
</span><span style= "color: #008080" >24</span>             <span style= "color: #0000ff" > char </span><span style= "color: #000000" > ch2;
</span><span style= "color: #008080" >25</span>             <span style= "color: #0000ff" > int </span> i = <span style= "color: #800080" >0</span><span style= "color: #000000" >;
</span><span style= "color: #008080" >26</span>             <span style= "color: #0000ff" > int </span> j = <span style= "color: #800080" >0</span><span style= "color: #000000" >;
</span><span style= "color: #008080" >27</span>             <span style= "color: #0000ff" > if </span> (n == <span style= "color: #800080" >0</span><span style= "color: #000000" >)
</span><span style= "color: #008080" >28</span> <span style= "color: #000000" >            {
</span><span style= "color: #008080" >29</span>                 <span style= "color: #0000ff" > return </span><span style= "color: #000000" > m;
</span><span style= "color: #008080" >30</span> <span style= "color: #000000" >            }
</span><span style= "color: #008080" >31</span>             <span style= "color: #0000ff" > if </span> (m == <span style= "color: #800080" >0</span><span style= "color: #000000" >)
</span><span style= "color: #008080" >32</span> <span style= "color: #000000" >            {
</span><span style= "color: #008080" >33</span>
<span style= "color: #008080" >34</span>                 <span style= "color: #0000ff" > return </span><span style= "color: #000000" > n;
</span><span style= "color: #008080" >35</span> <span style= "color: #000000" >            }
</span><span style= "color: #008080" >36</span>             Matrix = <span style= "color: #0000ff" > new </span> <span style= "color: #0000ff" > int </span>[n + <span style= "color: #800080" >1</span>, m + <span style= "color: #800080" >1</span><span style= "color: #000000" >];
</span><span style= "color: #008080" >37</span>
<span style= "color: #008080" >38</span>             <span style= "color: #0000ff" > for </span> (i = <span style= "color: #800080" >0</span>; i <= n; i++<span style= "color: #000000" >)
</span><span style= "color: #008080" >39</span> <span style= "color: #000000" >            {
</span><span style= "color: #008080" >40</span>                 <span style= "color: #008000" > //</span><span style="color: #008000">初始化第一列</span>
<span style= "color: #008080" >41</span>                 Matrix[i, <span style= "color: #800080" >0</span>] =<span style= "color: #000000" > i;
</span><span style= "color: #008080" >42</span> <span style= "color: #000000" >            }
</span><span style= "color: #008080" >43</span>
<span style= "color: #008080" >44</span>             <span style= "color: #0000ff" > for </span> (j = <span style= "color: #800080" >0</span>; j <= m; j++<span style= "color: #000000" >)
</span><span style= "color: #008080" >45</span> <span style= "color: #000000" >            {
</span><span style= "color: #008080" >46</span>                 <span style= "color: #008000" > //</span><span style="color: #008000">初始化第一行</span>
<span style= "color: #008080" >47</span>                 Matrix[<span style= "color: #800080" >0</span>, j] =<span style= "color: #000000" > j;
</span><span style= "color: #008080" >48</span> <span style= "color: #000000" >            }
</span><span style= "color: #008080" >49</span>
<span style= "color: #008080" >50</span>             <span style= "color: #0000ff" > for </span> (i = <span style= "color: #800080" >1</span>; i <= n; i++<span style= "color: #000000" >)
</span><span style= "color: #008080" >51</span> <span style= "color: #000000" >            {
</span><span style= "color: #008080" >52</span>                 ch1 = str1[i - <span style= "color: #800080" >1</span><span style= "color: #000000" >];
</span><span style= "color: #008080" >53</span>                 <span style= "color: #0000ff" > for </span> (j = <span style= "color: #800080" >1</span>; j <= m; j++<span style= "color: #000000" >)
</span><span style= "color: #008080" >54</span> <span style= "color: #000000" >                {
</span><span style= "color: #008080" >55</span>                     ch2 = str2[j - <span style= "color: #800080" >1</span><span style= "color: #000000" >];
</span><span style= "color: #008080" >56</span>                     <span style= "color: #0000ff" > if </span><span style= "color: #000000" > (ch1.Equals(ch2))
</span><span style= "color: #008080" >57</span> <span style= "color: #000000" >                    {
</span><span style= "color: #008080" >58</span>                         temp = <span style= "color: #800080" >0</span><span style= "color: #000000" >;
</span><span style= "color: #008080" >59</span> <span style= "color: #000000" >                    }
</span><span style= "color: #008080" >60</span>                     <span style= "color: #0000ff" > else </span>
<span style= "color: #008080" >61</span> <span style= "color: #000000" >                    {
</span><span style= "color: #008080" >62</span>                         temp = <span style= "color: #800080" >1</span><span style= "color: #000000" >;
</span><span style= "color: #008080" >63</span> <span style= "color: #000000" >                    }
</span><span style= "color: #008080" >64</span>                     Matrix[i, j] = LowerOfThree(Matrix[i - <span style= "color: #800080" >1</span>, j] + <span style= "color: #800080" >1</span>, Matrix[i, j - <span style= "color: #800080" >1</span>] + <span style= "color: #800080" >1</span>, Matrix[i - <span style= "color: #800080" >1</span>, j - <span style= "color: #800080" >1</span>] +<span style= "color: #000000" > temp);
</span><span style= "color: #008080" >65</span> <span style= "color: #000000" >                }
</span><span style= "color: #008080" >66</span> <span style= "color: #000000" >            }
</span><span style= "color: #008080" >67</span>         <span style= "color: #0000ff" > for </span> (i = <span style= "color: #800080" >0</span>; i <= n; i++<span style= "color: #000000" >)
</span><span style= "color: #008080" >68</span> <span style= "color: #000000" >            {
</span><span style= "color: #008080" >69</span>                 <span style= "color: #0000ff" > for </span> (j = <span style= "color: #800080" >0</span>; j <= m; j++<span style= "color: #000000" >)
</span><span style= "color: #008080" >70</span> <span style= "color: #000000" >                {
</span><span style= "color: #008080" >71</span>                     Console.Write(<span style= "color: #800000" > "</span><span style=" color: #800000 "> {0} </span><span style=" color: #800000 ">" </span><span style= "color: #000000" >, Matrix[i, j]);
</span><span style= "color: #008080" >72</span> <span style= "color: #000000" >                }
</span><span style= "color: #008080" >73</span>                 Console.WriteLine(<span style= "color: #800000" > "" </span><span style= "color: #000000" >);
</span><span style= "color: #008080" >74</span> <span style= "color: #000000" >            }
</span><span style= "color: #008080" >75</span>      
<span style= "color: #008080" >76</span>             <span style= "color: #0000ff" > return </span><span style= "color: #000000" > Matrix[n, m];
</span><span style= "color: #008080" >77</span> <span style= "color: #000000" >        }
</span><span style= "color: #008080" >78</span>
<span style= "color: #008080" >79</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><summary></span>
<span style= "color: #008080" >80</span>         <span style= "color: #808080" > ///</span><span style="color: #008000"> 计算字符串相似度
</span><span style= "color: #008080" >81</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"></summary></span>
<span style= "color: #008080" >82</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><param name="str1"></param></span>
<span style= "color: #008080" >83</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><param name="str2"></param></span>
<span style= "color: #008080" >84</span>         <span style= "color: #808080" > ///</span> <span style="color: #808080"><returns></returns></span>
<span style= "color: #008080" >85</span>         <span style= "color: #0000ff" > public </span> <span style= "color: #0000ff" > decimal </span> LevenshteinDistancePercent(<span style= "color: #0000ff" > string </span> str1, <span style= "color: #0000ff" > string </span><span style= "color: #000000" > str2)
</span><span style= "color: #008080" >86</span> <span style= "color: #000000" >        {
</span><span style= "color: #008080" >87</span>             <span style= "color: #008000" > //</span><span style="color: #008000">int maxLenth = str1.Length > str2.Length ? str1.Length : str2.Length;</span>
<span style= "color: #008080" >88</span>             <span style= "color: #0000ff" > int </span> val =<span style= "color: #000000" > Levenshtein_Distance(str1, str2);
</span><span style= "color: #008080" >89</span>             <span style= "color: #0000ff" > return </span> <span style= "color: #800080" >1</span> - (<span style= "color: #0000ff" > decimal </span>)val /<span style= "color: #000000" > Math.Max(str1.Length, str2.Length);
</span><span style= "color: #008080" >90</span> <span style= "color: #000000" >        }
</span><span style= "color: #008080" >91</span>     }
复制代码

 调用：

复制代码 
 1 static void Main(string[] args)
 2 
{
 3
string str1 = "ivan1";
 4
string str2 = "ivan2";
 5
Console.WriteLine("字符串1 {0}", str1);
 6
 7
Console.WriteLine("字符串2 {0}", str2);
 8
 9
Console.WriteLine("相似度 {0} %", new LevenshteinDistance().LevenshteinDistancePercent(str1, str2) * 100);
10 
Console.ReadLine();
11
}
复制代码

结果:

拓展与补充：

　小规模的字符串近似搜索，需求类似于搜索引擎中输入关键字，出现类似的结果列表。

    来源：.Net.NewLife。
    需求：假设在某系统存储了许多地址，例如：“北京市海淀区中关村大街1号海龙大厦”。用户输入“北京 海龙大厦”即可查询到这条结果。另外还需要有容错设计，例如输入“广西 京岛风景区”能够搜索到"广西壮族自治区京岛风景名胜区"。最终的需求是：可以根据用户输入，匹配若干条近似结果共用户选择。
    目的：避免用户输入类似地址导致数据出现重复项。例如，已经存在“北京市中关村”，就不应该再允许存在“北京中关村”。

    举例：

    此类技术在搜索引擎中早已广泛使用，例如“查询预测”功能。

    要实现此算法，首先需要明确“字符串近似”的概念。

    计算字符串相似度通常使用的是动态规划(DP)算法。

    常用的算法是 Levenshtein Distance。用这个算法可以直接计算出两个字符串的“编辑距离”。所谓编辑距离，是指一个字符串，每次只能通过插入一个字符、删除一个字符或者修改一个字符的方法，变成另外一个字符串的最少操作次数。这就引出了第一种方法：计算两个字符串之间的编辑距离。稍加思考之后发现，不能用输入的关键字直接与句子做匹配。你必须从句子中选取合适的长度后再做匹配。把结果按照距离升序排序。

复制代码 
 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5
 6 namespace BestString
 7 {
 8
public static class SearchHelper
 9 
{
10
public static string[] Search(string param, string[] datas)
11 
{
12
if (string.IsNullOrWhiteSpace(param))
13
return new string[0];
14
15
string[] words = param.Split(new char[] { ' ', '　' }, StringSplitOptions.RemoveEmptyEntries);
16
17
foreach (string word in words)
18 
{
19
int maxDist = (word.Length - 1) / 2;
20
21
var q = from str in datas
22
where word.Length <= str.Length
23
&& Enumerable.Range(0, maxDist + 1)
24
.Any(dist =>
25 
{
26
return Enumerable.Range(0, Math.Max(str.Length - word.Length - dist + 1, 0))
27
.Any(f =>
28 
{
29
return Distance(word, str.Substring(f, word.Length + dist)) <= maxDist;
30 
});
31 
})
32
orderby str
33
select str;
34
datas = q.ToArray();
35 
}
36
37
return datas;
38 
}
39
40
static int Distance(string str1, string str2)
41 
{
42
int n = str1.Length;
43
int m = str2.Length;
44
int[,] C = new int[n + 1, m + 1];
45
int i, j, x, y, z;
46
for (i = 0; i <= n; i++)
47
C[i, 0] = i;
48
for (i = 1; i <= m; i++)
49
C[0, i] = i;
50
for (i = 0; i < n; i++)
51
for (j = 0; j < m; j++)
52 
{
53
x = C[i, j + 1] + 1;
54
y = C[i + 1, j] + 1;
55
if (str1[i] == str2[j])
56
z = C[i, j];
57
else
58
z = C[i, j] + 1;
59
C[i + 1, j + 1] = Math.Min(Math.Min(x, y), z);
60 
}
61
return C[n, m];
62 
}
63 
}
64 }
复制代码

    分析这个方法后发现，每次对一个句子进行相关度比较的时候，都要把把句子从头到尾扫描一次，每次扫描还需要以最大误差作长度控制。这样一来，对每个句子的计算次数大大增加。达到了二次方的规模（忽略距离计算时间）。

    所以我们需要更高效的计算策略。在纸上写出一个句子，再写出几个关键字。一个一个涂画之后，偶然发现另一种字符串相关的算法完全可以适用。那就是 Longest common subsequence（LCS，最长公共字串）。为什么这个算法可以用来计算两个字符串的相关度？先看一个例子：

关键字：少年时代的神话播下了浪漫注意

句子：就是少年时代大量神话传说在其心田里播下了浪漫主义这颗难以磨灭的种子

    这里用了两个关键字进行搜索。可以看出来两个关键字都有部分匹配了句子中的若干部分。这样可以单独为两个关键字计算 LCS，LCS之和就是简单的相关度。看到这里，你若是已经理解了核心思想，已经可以实现出基本框架了。但是，请看下面这个例子：

关键字：东土大唐，唐三藏

句子：我本是东土大唐钦差御弟唐三藏大徒弟孙悟空行者

    看出来问题了吗？下面还是使用同样的关键字和句子。

关键字：东土大(唐唐)三藏

句子： 我本是东土大唐钦差御弟唐三藏大徒弟孙悟空行者

    举这个例子为了说明，在进行 LCS 计算的过程中，得到的结果并不能保证就是我们期望的结果。为了①保证所匹配的结果中不存在交集，并且②在句子中的匹配结果尽可能的短，需要采取两个补救措施。（为什么需要满足这样的条件，读者自行思考）

    第一：可以在单次计算 LCS 之后，用贪心策略向前（向后）找到最先能够完成匹配的位置，再用相同的策略向后（向前）扫描。这样可以满足第二个条件找到句子中最短的匹配。如果你对 LCS 算法有深入了解，完全可以在计算 LCS 的过程中找到最短匹配的结束位置，然后只需要进行一次向前扫描就可以完成。这样节约了一次扫描过程。

    第二：增加一个标记数组，记录句子中的字符是否被匹配过。

    最后标记数组中标记过的位置就是匹配结果。

    相信你看到这里一定非常头晕，下面用一个例子解释：（句子）

关键字：   ABCD

句子：     XAYABZCBXCDDYZ

句子分解： X Y  Z  X   YZ

           A   B C   D

              A   B C D

    你可能会匹配成 AYABZCBXCDD，AYABZCBXCD，ABZCBXCDD，ABZCBXCD。我们实际需要的只是ABZCBXCD。

    使用LCS匹配之后，得到的很可能是 XAYABZCBXCDDYZ；

    用贪心策略向前处理后，得到结果为 XAYABZCBXCDDYZ；

    用贪心策略向后处理后，得到结果为 XAYABZCBXCDDYZ。

    这样处理的目的是为了避免得到较长的匹配结果（类似正则表达式的贪婪、懒惰模式）。

    以上只是描述了怎么计算两个字符串的相似程度。除此之外还需要：①剔除相似度较低的结果；②对结果进行排序。

    剔除相似度较低的结果，这里设定了一个阈值：差错比例不能超过匹配结果长度的一半。

    对结果进行排序，不能够直接使用相似度进行排序。因为相似度并没有考虑到句子的长度。按照使用习惯，通常会把匹配度高，并且句子长度短的放在前面。这就得到了排序因子：（不匹配度+0.5）/句子长度。

    最后得到我们最终的搜索方法

复制代码 
 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 using System.Diagnostics;
 6
 7 namespace BestString
 8 {
 9
public static class SearchHelper
10 
{
11
public static string[] Search(string param, string[] items)
12 
{
13
if (string.IsNullOrWhiteSpace(param) || items == null || items.Length == 0)
14
return new string[0];
15
16
string[] words = param
17
.Split(new char[] { ' ', 'u3000' }, StringSplitOptions.RemoveEmptyEntries)
18
.OrderBy(s => s.Length)
19 
.ToArray();
20
21
var q = from sentence in items.AsParallel()
22
let MLL = Mul_LnCS_Length(sentence, words)
23
where MLL >= 0
24
orderby (MLL + 0.5) / sentence.Length, sentence
25
select sentence;
26
27
return q.ToArray();
28 
}
29
30
//static int[,] C = new int[100, 100];
31
32
/// <summary>
33
///
34
/// </summary>
35
/// <param name="sentence"></param>
36
/// <param name="words">多个关键字。长度必须大于0，必须按照字符串长度升序排列。</param>
37
/// <returns></returns>
38
static int Mul_LnCS_Length(string sentence, string[] words)
39 
{
40
int sLength = sentence.Length;
41
int result = sLength;
42
bool[] flags = new bool[sLength];
43
int[,] C = new int[sLength + 1, words[words.Length - 1].Length + 1];
44
//int[,] C = new int[sLength + 1, words.Select(s => s.Length).Max() + 1];
45
foreach (string word in words)
46 
{
47
int wLength = word.Length;
48
int first = 0, last = 0;
49
int i = 0, j = 0, LCS_L;
50
//foreach 速度会有所提升，还可以加剪枝
51
for (i = 0; i < sLength; i++)
52
for (j = 0; j < wLength; j++)
53
if (sentence[i] == word[j])
54 
{
55
C[i + 1, j + 1] = C[i, j] + 1;
56
if (first < C[i, j])
57 
{
58
last = i;
59
first = C[i, j];
60 
}
61 
}
62
else
63
C[i + 1, j + 1] = Math.Max(C[i, j + 1], C[i + 1, j]);
64
65
LCS_L = C[i, j];
66
if (LCS_L <= wLength >> 1)
67
return -1;
68
69
while (i > 0 && j > 0)
70 
{
71
if (C[i - 1, j - 1] + 1 == C[i, j])
72 
{
73
i--;
74
j--;
75
if (!flags[i])
76 
{
77
flags[i] = true;
78
result--;
79 
}
80
first = i;
81 
}
82
else if (C[i - 1, j] == C[i, j])
83
i--;
84
else// if (C[i, j - 1] == C[i, j])
85
j--;
86 
}
87
88
if (LCS_L <= (last - first + 1) >> 1)
89
return -1;
90 
}
91
92
return result;
93 
}
94 
}
95 }
复制代码

    对于此类问题，要想得到更快速的实现，必须要用到分词+索引的方案。在此不做探讨。

代码打包下载：http://files.cnblogs.com/Aimeast/BestString.zip

越努力才能越幸运，不让那些为我付出过的人失望。转载请注明：http://www.cnblogs.com/ECJTUACM-873284962/
分类:  language：C#
好文要顶  关注我  收藏该文   
Angel_Kitty
关注 - 35
粉丝 - 187
+加关注
0
0
« 上一篇： x64_dbg破解64位WinSnap4.5.6图文视频教程
posted @  2017-10-13 15:22  Angel_Kitty 阅读( 15) 评论( 0)  编辑  收藏

最后

以上就是忧郁期待为你收集整理的用C#实现字符串相似度算法（编辑距离算法 Levenshtein Distance）的全部内容，希望文章能够帮你解决用C#实现字符串相似度算法（编辑距离算法 Levenshtein Distance）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(120)

相关文章

编辑距离——莱文斯坦距离1.编辑距离2.莱文斯坦距离
编辑距离——莱文斯坦距离1.编辑距离2.莱文斯坦距离
【字符串】字符串相似度（大小写敏感问题）（有起点的部分片段遍历）
【字符串】字符串相似度（大小写敏感问题）（有起点的部分片段遍历）
文本相似度Levenshtein算法原理(转载)
文本相似度Levenshtein算法原理(转载)
Levenshtein Distance Levenshtein 编辑距离——一种相似度的计算方法
Levenshtein Distance Levenshtein 编辑距离——一种相似度的计算方法
用C#实现字符串相似度算法（编辑距离算法 Levenshtein Distance）
用C#实现字符串相似度算法（编辑距离算法 Levenshtein Distance）
计算字符串的相似度/华为机试(C/C++)
计算字符串的相似度/华为机试(C/C++)
编程之美3.3 计算两个字符串的相似度
编程之美3.3 计算两个字符串的相似度
字符串相似度算法(编辑距离)
字符串相似度算法(编辑距离)

评论列表共有 0 条评论

立即
投稿
返回
顶部