75

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

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

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

也许某种字符差异程序可以提供帮助？我已经看到了用于比较要签入的代码差异的良好行差异程序，是否有类似的基于字符的东西，也许是在 boost 中？如果您可以计算公共连续字符的数量并取非共享字符的比率，也许这将是一个很好的启发式方法？

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

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

4

5 回答 5

99

您正在寻找的是所谓的字符串度量算法。其中有很多，其中许多具有相似的特征。其中比较流行：

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

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

于 2013-03-08T21:31:30.560 回答
15

Damerau Levenshtein distance是另一种比较两个字符串的算法，它类似于 Levenshtein 距离算法。两者之间的区别在于它还可以检查字符之间的转置，因此可以为纠错提供更好的结果。

例如：nightand之间的 Levenshtein 距离为 2，但和nigth之间的 Damerau Levenshtein 距离将为 1，因为它只是一对字符的交换。nightnigth

于 2013-11-10T13:53:31.567 回答
7

您可以为此使用 ngrams。例如，将两个字符串转换为单词三元组（通常为小写），并比较它们彼此相等的百分比。

您的挑战是定义相似度的最小百分比。

http://en.wikipedia.org/wiki/N-gram

于 2015-02-03T19:06:18.240 回答
2

您可以考虑的另一种算法是 Simon White Similarity：

def get_bigrams(string):
    """
    Take a string and return a list of bigrams.
    """
    if string is None:
        return ""

    s = string.lower()
    return [s[i : i + 2] for i in list(range(len(s) - 1))]

def simon_similarity(str1, str2):
    """
    Perform bigram comparison between two strings
    and return a percentage match in decimal form.
    """
    pairs1 = get_bigrams(str1)
    pairs2 = get_bigrams(str2)
    union = len(pairs1) + len(pairs2)

    if union == 0 or union is None:
        return 0

    hit_count = 0
    for x in pairs1:
        for y in pairs2:
            if x == y:
                hit_count += 1
                break
    return (2.0 * hit_count) / union
于 2019-05-08T17:30:56.330 回答
0

您可以使用计算最长公共子序列长度的算法来解决这个问题。如果两个输入字符串的最长公共子序列的长度小于任何一个字符串的长度，则它们不相等。

您可以使用动态规划的方法来解决问题并优化空间复杂度，以防您不希望找出最长的公共子序列。

于 2019-07-27T14:03:54.263 回答