学步园

前几天在CSDN的论坛看到一个需要判断两个字符串之间相差多少个字符的帖子,之前有了解过有相应的算法来计算这个差异,但是没有深入的去了解.刚好趁这个时机了解了一下: Levenshtein Distance (Edit Distance) 编辑距离,字符相似度算法

对于该算法,详细说明可参考wiki: 

摘自维基:

"编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

例如将kitten一字转成sitting：

1. sitten （k→s）
2. sittin （e→i）
3. sitting （→g）

俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。"

中文: http://zh.wikipedia.org/wiki/%E7%B7%A8%E8%BC%AF%E8%B7%9D%E9%9B%A2

英文: http://en.wikipedia.org/wiki/Levenshtein_distance 

然后写了一个Demo来加深了解

这里是维基给的伪代码:

"

动态规划经常被用来作为这个问题的解决手段之一。

整數 Levenshtein距離(字符 str1[1..lenStr1], 字符 str2[1..lenStr2])

   宣告 int d[0..lenStr1, 0..lenStr2]

   宣告 int i, j, cost

   對於 i 等於 由 0 至 lenStr1

       d[i, 0] := i

   對於 j 等於 由 0 至 lenStr2

       d[0, j] := j

   對於 i 等於 由 1 至 lenStr1

       對於 j 等於 由 1 至 lenStr2

           若 str1[i] = str2[j] 則 cost := 0

                                否則 cost := 1

           d[i, j] := 最小值(

                                d[i-1, j  ] + 1,     // 刪除

                                d[i  , j-1] + 1,     // 插入

                                d[i-1, j-1] + cost   // 替換

                            )

   返回 d[lenStr1, lenStr2]

"

Demo如下:

using System;<br /> using System.Collections.Generic;<br /> using System.ComponentModel;<br /> using System.Data;<br /> using System.Drawing;<br /> using System.Linq;<br /> using System.Text;<br /> using System.Windows.Forms;<br /> namespace WindowsFormsApplication1<br /> {<br /> public partial class Form1 : Form<br /> {<br /> public Form1()<br /> {<br /> InitializeComponent();<br /> }<br /> private void button1_Click(object sender, EventArgs e)<br /> {</p> <p> char[] c1 = richTextBox1.Text.Trim().ToCharArray();<br /> char[] c2 = richTextBox2.Text.Trim().ToCharArray();<br /> int[,] result = Calculate(c1, c2);</p> <p> DataTable dt = new DataTable();<br /> for (int i = 0; i < c1.Length + 2; i++)<br /> {<br /> dt.Columns.Add(i.ToString());<br /> }<br /> for (int i = 0; i < c2.Length + 2; i++)<br /> {<br /> DataRow row = dt.NewRow();<br /> dt.Rows.Add(row);<br /> }<br /> for (int i = 0; i < c2.Length + 2; i++)<br /> {<br /> if (i < 2)<br /> {<br /> dt.Rows[i][0] = string.Empty;<br /> }<br /> else<br /> {<br /> dt.Rows[i][0] = c2[i - 2];<br /> }<br /> }<br /> for (int i = 0; i < c1.Length + 2; i++)<br /> {<br /> if (i < 2)<br /> {<br /> dt.Rows[0][i] = string.Empty;<br /> }<br /> else<br /> {<br /> dt.Rows[0][i] = c1[i - 2];<br /> }<br /> }<br /> for (int i = 0; i < result.GetLength(0); i++)<br /> {<br /> for (int j = 0; j < result.GetLength(1); j++)<br /> {<br /> dt.Rows[j + 1][i + 1] = result[i, j];<br /> }<br /> }<br /> if (checkBox1.Checked == true)<br /> {<br /> dataGridView1.DataSource = dt;<br /> dataGridView1.ColumnHeadersVisible = false;<br /> dataGridView1.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells;<br /> }<br /> label1.Text = string.Format("字符相似度:{0}"<br /> , dt.Rows[result.GetLength(1)][result.GetLength(0)].ToString());<br /> }<br /> public static int[,] Calculate(char[] First, char[] Second)<br /> {<br /> int lenFirst = First.Length + 1;<br /> int lenSecond = Second.Length + 1;<br /> int[,] matrixResult = new int[lenFirst, lenSecond];<br /> for (int i = 0; i < lenFirst; i++) matrixResult[i, 0] = i;<br /> for (int j = 0; j < lenSecond; j++) matrixResult[0, j] = j;<br /> for (int i = 1; i < lenFirst; i++)<br /> {<br /> for (int j = 1; j < lenSecond; j++)<br /> {<br /> if (First[i - 1] == Second[j - 1])<br /> {<br /> matrixResult[i, j] = matrixResult[i - 1, j - 1];<br /> }<br /> else<br /> {<br /> matrixResult[i, j] = new int[] {matrixResult[i - 1, j] + 1<br /> , matrixResult[i , j-1] + 1<br /> , matrixResult[i - 1, j-1] + 1<br /> }.Min();<br /> }<br /> }<br /> }<br /> return matrixResult;<br /> }<br /> }<br /> }<br />