algorithm - 有哪些算法可以比较两个字符串的相似程度？

Question

我需要比较字符串以确定它们是否代表同一事物。这与人工输入的案例标题有关，其中缩写和其他小细节可能有所不同。例如，考虑以下两个标题:

std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP";

相对于:

std::string second = "Harper v. The Law Offices of Huey & Luey, LLP";

人类可以快速判断出它们很可能是同一个。我目前采用的方法是通过将所有字母小写并删除所有标点符号和空格来规范化字符串:

std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp";

和:

std::string secondNormalized = "harpervthelawofficesofhueylueyllp";

在这种情况下进行比较，一个是另一个的子序列，但您可以想象其他更复杂的变体，这些变体不一定会发生，但它们具有重要的共同子序列。偶尔也可能出现人为输入错误，例如转置字母和拼写错误。

也许某种字符差异程序可以提供帮助？我见过很好的行差异程序，用于比较要 checkin 的代码的差异，是否有类似的基于字符的东西，也许是在提升中？如果您可以计算共有的连续字符数，并计算出与未共享字符的比率，或许这会是一个很好的启发式方法？

最后，我需要一个 bool 值决定是否认为它们相同。它不一定是完美的，但理想情况下应该很少出错。

我可以使用什么算法来量化这两个字符串彼此之间的相似程度，然后我可以通过一些启发式方法将其转换为是/否答案？

Answer 1

你要找的是String Metric算法。它们的数量数量可观，其中许多具有相似的特征。其中比较受欢迎的是:

• Levenshtein Distance :将一个单词更改为另一个单词所需的最小单字符编辑次数。字符串的长度不必相同
• Hamming Distance : 两个等长字符串中不同字符的个数。
• Smith–Waterman : 一系列用于计算可变子序列相似性的算法。
• Sørensen–Dice Coefficient : 一种计算相邻字符对差异系数的相似度算法。

在 wiki page 上查看这些以及其他内容关于这个话题。