不止是 strcmp()：字符串相似度

• 下载源文件 - 3.31 Kb
• 下载演示项目 - 24.1 Kb

引言

你已经在拼写检查器中看到过这种情况：一个包含正确单词的列表，这些单词与你输入的拼写错误的单词相似。难道不能在你自己的应用程序中加入这种相似单词的概念吗？这有很多可能的用途。

• 最明显的例子是在数据库中搜索姓名。名字不寻常的人总是需要耐心地拼写，并希望它在数据库中被正确记录。现在，想象一下你可以扫描一个数据库，搜索与给定姓名相似（看起来相似）的姓名，并按相似度排序，这样用户就可以选择它们。酷吧？
• 显示一个用户输入错误但未找到的网址列表。或者在你的网站上搜索“近似”关键词时使用它。
• 你还可以利用这个想法来检查书面文本（学术论文、程序源代码等）之间的相似性，例如，以检测抄袭。
• 嘿，比较基因序列，发现基因或蛋白质之间的进化和功能相似性怎么样？实际上，这曾用于线粒体 DNA 来追踪人类所有的民族演化，并创造了线粒体夏娃的概念……好吧，好吧，跑题太远了……

在这里，我提供一个实现此类比较的可能解决方案：一个返回两个字符串有多“像”或相似的函数。但首先，让我们更精确地定义问题。

背景

字符串的相似度可以有多种定义方式。这里，我将使用一种非常简单的方法：最长公共子序列的长度除以第一个字符串的长度。假设你有两个字符串（例如：“consecutivelly”和“successfully”）。现在你会发现有几个子序列出现在两个字符串中，但不一定连续（例如：“c-s-u-l-l-y”、“s-c-u-l-l-y”、“s-e-u-l-l-y”、“s-u-e-l-l-y”等等）。我提出的相似度度量是将最长子序列的长度除以第一个参数字符串的长度（例如，strlen(“suelly”)/strlen(“consecutively”)，大约为 42.85%）。到目前为止，这很简单，对吧？

现在，最困难的部分似乎是如何有效地发现最长子序列。嗯，实际上并不难：我们可以使用一种经典的算法技术，称为动态规划。如果你在任何大学学习过算法，而他们没有教你这个，那就去要回你的钱。粗略地说，你可以将动态规划（或 DP）看作是一种用于优化问题的逆向递归。某些优化问题有递归解。然而，这种递归解可能涉及计算一些可能重复出现的子解。对于这类问题，我们可以使用 DP 来极大地提高性能。在这里详细解释这项技术会太冗长，所以我强烈建议你查阅一本好的算法书籍（我在下面的“兴趣点”部分推荐了一本）。顺便说一下，“动态规划”中的“规划”并不指计算机编程，而是指一般数学意义上的规划；即：一系列导向解决方案的步骤。

使用代码

代码使用起来非常简单。返回相似度的函数在 (string.h) 中具有以下签名：

float simil( char *str1, char *str2);

返回值是 0 到 1 之间的数字。正如我之前提到的，这个值是“最长公共子序列的长度除以 str1 的长度”。0 表示两个字符串没有任何共同之处。1 表示第一个字符串完全包含在第二个字符串中。由你来决定将哪个字符串用作第一个或第二个。但请注意，使用最长字符串作为第一个参数会产生较低的相似度值，而使用最短字符串会产生较高的相似度值（请看上面的图片）。显然，如何调用以及哪个值是可接受的最小值取决于你试图解决的问题。如果你正在扫描数据库中的姓名，你可能希望让用户调整这个值。如果你正在为一个网站的 404 响应页面构建一个脚本，那么你将通过将最常见的错误与你网站上的地址列表进行比较来调整这个值。

我还提供了另一个你可能感兴趣的函数：

char *LCS( char *str1, char *str2);

此函数返回一个指向静态数组的指针，该数组包含最长公共子序列之一，数组类型为 char（最大大小为 MAX_LCS，定义在 string.h 中）。你所要做的就是编译并链接 simil.c 到你的代码中，并将 simil.h 放在你的包含路径文件夹中。

关注点

我写这个代码是为了研究一个更通用的问题，称为编辑距离，它衡量一个字符串（或 DNA 序列，通过进化和基因突变）需要改变多少才能生成另一个字符串。这是一个典型的动态规划问题。你可以在这本书中找到关于动态规划的深入、完整的解释：《算法导论》，第二版；作者 Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 和 Clifford Stein。我对这本书有一种爱恨交加的关系。它是我见过最完整的两本算法书之一（另一本是 Knuth 的）。但它也是我读过的最冗长的书之一。这是一本典型的学术书籍：知识渊博，充满证明，形式化语言复杂。 Robert Sedgewick 的“C 语言算法”也有对 DP 的介绍，但不够全面。如果你有关于动态规划的书籍或网站推荐，请在评论区发表。:-)

历史

• 2004年9月12日：版本 1.0。