有哪些算法用于比较两个字符串的相似程度？

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

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

也许某种角色差异程序可以帮助？我已经看到用于比较要检入的代码差异的良好行差异程序,在字符的基础上有类似的东西,也许在提升？如果你可以统计连续字符的数量并将比率与未共享的字符进行比较,那么这可能是一个很好的启发式算法？

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

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

Answer 1

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

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

在主题的维基页面上查看这些以及其他人.

Answer 2

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

例如:间的Levenshtein距离night和nigth是2,但之间Damerau Levenshtein距离night和nigth将是1,因为它仅仅是一个一对字符的交换.

Answer 3

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

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

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

Answer 4

您可以考虑的另一个算法是 Simon White 相似度：

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