Levenshtein 编辑距离算法

• 下载 源代码 - 121.3 KB

引言

这段源代码旨在帮助大家更容易地理解 Levenshtein 编辑距离算法。当我开始研究这个算法时，我非常害怕实现它。我阅读了所有关于这个算法的文章，但真的什么也没理解。随着研究的深入，我试图弄清楚这个常用算法的秘密。当我完成实现后，我决定在 CodeProject.com 上写一篇文章。我希望我的实现对那些努力理解 Levenshtein 编辑距离算法的人有所帮助。

背景

这个算法常用于 Microsoft Outlook 或 Microsoft Word 的拼写检查系统以及 Google。所以感谢 Vladimir Levenshtein 为我们提供了这个算法。我不会尝试向你解释算法的细节。这篇文章的目的是让你能够轻松地按照步骤操作，并查看算法的流程图。

关于该算法

两个字符串之间的编辑距离定义为将一个字符串转换为另一个字符串所需的最小编辑操作数。假设第一个字符串命名为目标字符串，第二个字符串命名为源字符串。我们希望将源字符串转换为目标字符串。编辑操作包括三种：删除（从源字符串中删除一个字符）、插入（从目标字符串中插入一个字符）和替换（用目标字符串中的一个字符替换源字符串中的一个字符）。还有第四种操作，称为匹配，它不计为编辑操作。考虑两个输入字符串“activate”和“caveat”。下面你可以看到一种可能的转换。在示例中，转换由一个字符串表示，该字符串由字符 M 表示匹配，S 表示替换，D 表示删除，I 表示插入。

D M D S M I M M D

a  c   t  i   v    a  t   e   

    c      a  v e a  t   

使用代码

我将在这里分享一些我的实现代码片段

在我们的实现中

• 删除成本 = 0.7
• 插入成本 = 0.7
• 替换成本 = 1.0

匹配没有成本。

Reference = Ref_text_box.Text;
Hypotheses = Hyp_text_box.Text;

distance_table = new double[Reference.Length + 1, Hypotheses.Length + 1];
for (int i = 0; i <= Reference.Length; i++)
    distance_table[i, 0] = i * 0.7;

for (int j = 0; j <= Hypotheses.Length; j++)
    distance_table[0, j] = j * 0.7;

for (int i = 1; i <= Reference.Length; i++)
{
    for (int j = 1; j <= Hypotheses.Length; j++)
    {
        if (Reference[i - 1] == Hypotheses[j - 1])//if the letters are same 
            distance_table[i, j] = distance_table[i - 1, j - 1];
        else //if not add 1 to its neighborhoods and assign minumun of its neighborhoods 
        {
            distance_table[i, j] = Math.Min(Math.Min(distance_table[i - 1, j - 1] + 1, 
              distance_table[i - 1, j] + 0.7), distance_table[i, j - 1] + 0.7);
        }
    }

}
//create table
//Compute Distance
String distance_string = " ";
String distance_result;
int i = Reference.Length, j = Hypotheses.Length;

while (true)
{
    this.dataGridView1.Rows[i].Cells[j+1].Style.BackColor = Color.LightGreen;

    if (i == 0 && j == 0)
    {
        this.dataGridView1.Rows[i].Cells[j].Style.BackColor = Color.LightGreen;

        distance_string_textbox.Text = distance_string;
        char[] a = distance_string.ToCharArray();
        Array.Reverse(a);
        distance_result = new string(a);
        distance_string_textbox.Text = distance_result;
        break;
    }
    else if (i == 0 && j > 0)
    {
        this.dataGridView1.Rows[i].Cells[j+1].Style.BackColor = Color.LightGreen;
        distance_string += "d";//delete
        j--;
    }
    else if (i > 0 && j == 0)
    {
        this.dataGridView1.Rows[i].Cells[j+1].Style.BackColor = Color.LightGreen;
        distance_string += "i";//insert
        i--;
    }
    else
    {
        if (distance_table[i - 1, j - 1] <= distance_table[i - 1, j] && 
                distance_table[i - 1, j - 1] <= distance_table[i, j - 1])
        {
            this.dataGridView1.Rows[i].Cells[j+1].Style.BackColor = Color.LightGreen;
            if (distance_table[i - 1, j - 1] == distance_table[i, j])
                distance_string += "m"; //match
            else
                distance_string += "s"; //substitue

            i--;
            j--;
        }

        else if (distance_table[i - 1, j] < distance_table[i, j - 1])
        {
            this.dataGridView1.Rows[i ].Cells[j+1].Style.BackColor = Color.LightGreen;
            distance_string += "i"; //insert
            i--;

        }
        else if (distance_table[i, j - 1] < distance_table[i - 1, j])
        {
            this.dataGridView1.Rows[i].Cells[j +1].Style.BackColor = Color.LightGreen;
            distance_string += "d"; //delete
            j--;
        }
    }
}

关注点

这段代码片段将帮助你轻松理解 Levenshtein 编辑距离算法。你可以尝试一些单词和句子来相互比较，并可以跟踪距离表来了解如何计算字符串的距离。