使用 Levenshtein 算法进行容错字符串匹配

• 下载源代码 - 11.6 Kb

引言

有时，有一个容错的字符串匹配函数来查找几乎完全相同的字符串会很方便。我在我们的德国收据数据库 RkSuite 中需要它来管理有时拼写错误或属于其他类别变体的类别。

存在不同的算法来解决这个问题，Unix 下一个非常常见的程序是 soundex，但它只在你坚持使用一种语言时才有用。如果你有英语、德语、法语等单词，soundex 算法将无法有效地工作，因此需要更通用的方法。在使用 Google 进行一些搜索后，我听说了 Levenshtein。

背景

该代码基于 Michael Gillel 的原始工作，请访问他的 主页 并阅读他关于 Levenshtein 算法的精彩文章。回来加入我，我将向你展示如何在自己的应用程序中使用你的新知识。

使用代码

类 Levenshtein (levenshtein.cpp, levenshtein.h) 包含计算 2 个单词之间编辑距离的代码。编辑距离描述了将一个字符串转换成另一个字符串需要多少编辑操作（插入、删除、更改）。该代码没有使用复杂的技巧，任何 C++ 编译器都应该能够处理它。

方法 Get 返回编辑距离。对于你来说，原始值可能有趣也可能不有趣，在我的例子中，我使用公式 编辑距离 * 100 / 字符串长度 来容忍更长字符串中的更多错误。

有两种不同的 Get 方法可用，第一种方法处理最大长度为 MAXLINE （默认：128）的字符串。我使用静态数组进行计算，这稍微提高了算法的速度。你可以更改常量以节省内存。请注意，将创建一个二维数组，该数组需要 MAXLINE * MAXLINE * sizeof(int) 字节。

如果你不确定字符串的长度，你可以使用方法 Get2，它动态分配内存，并且可以处理（几乎）任何字符串长度。如果一个字符串对于上面的算法来说太长，则会自动使用第二个算法。

用法非常简单

// calculate Levenshtein distance
Levenshtein lev;
int nError = lev.Get(string1, string2);

// recalculate value
int nNormalizedError = 100 * nError / strlen(string1);

示例中的代码使用来自文件 liste.txt 的一个小列表。你可以尝试使用tolerance 设置，看看哪些字符串被识别为相似。该演示项目使用 MFC，并已使用 Visual Studio .NET 2003 编译。应该可以轻松创建一个 VC6 项目，只需将所有 .h、.cpp 和 .rc 文件添加到项目中即可。

最终结论

该算法对于小型数据集（几千个）效果很好。我尝试将其用于拼写检查，但将字符串与通常大小的字典进行比较效率不高。无论如何，从完美匹配切换到容错匹配是令人难以置信的，并且你的用户会很高兴你的程序让你有机会犯错误。

历史

• 2005-05-02 修复下载链接
• 2005-04-29 CodeProject 的第一个版本