一尘不染

有什么算法可以比较两个字符串的相似程度?

algorithm

我需要比较字符串,以确定它们是否代表相同的东西。这与人类输入的案例名称有关,缩写和其他小细节可能有所不同。例如,考虑以下两个标题:

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";

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

也许某种字符差异程序可能会有所帮助?我见过很好的行差异程序,用于比较要检查的代码中的差异,是否存在基于字符的类似内容,也许是增强功能?如果您可以计算出连续字符的数量,并将其与未共享字符的比例取值,那么这将是一个很好的启发式方法吗?

最后,我需要确定是否将它们视为相同的布尔值决定。它不一定是完美的,但理想情况下应该很少出错。

我可以使用哪种算法对两个字符串彼此之间的相似程度进行某种量化,然后通过启发式方法将其转换为是/否答案?


阅读 255

收藏
2020-07-28

共1个答案

一尘不染

您正在寻找的被称为String Metric算法。有一个
显著 数量的人,许多具有类似特征。其中比较受欢迎的有:

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

在主题的Wiki页面上查看这些以及其他内容。

2020-07-28