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

81

我需要比较字符串以判断它们是否代表相同的事物。这与人类输入的案件标题有关,其中缩写和其他细节可能会有所不同。例如,请考虑以下两个标题:

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中?如果您能计算共同连续字符的数量并将其与未共享的字符的数量比率相结合,或许那将是一个好的启发式方法?
最终,我需要一个布尔决策,判断它们是否相同。它不必完美,但理想情况下应该很少出错。
有什么算法可以给我一些关于两个字符串相似程度的量化指标,我可以通过某些启发式方法将其转换为是/否答案?

7
我之前使用过Levenshtein距离。它易于实现...http://en.wikipedia.org/wiki/Levenshtein_distance - souldzin
Boost库中是否有Levenshtein距离算法? - WilliamKF
1
抱歉,这不是建设性的... 这是您正在寻找的维基页面 - djechlin
@djechlin 为什么?这是一个有趣的问题。 - Stephan Dollberg
@MarkRansom:这就是关键,WhozCraig做了那件事,所以我不会为此负责。 - Daniel Frey
显示剩余9条评论
6个回答

110
您所寻找的是称为字符串度量算法。有很多这样的算法,许多具有相似的特征。其中比较流行的有:
  • Levenshtein距离:将一个单词更改为另一个单词所需的最小单字符编辑次数。字符串长度不必相同。
  • 汉明距离:两个等长字符串中不同字符的数量。
  • Smith-Waterman:用于计算变量子序列相似性的算法族。
  • Sørensen-Dice系数:计算相邻字符对之间差异系数的相似性算法。

还可以在wiki页面上查看这些以及其他算法。


18

Damerau Levenshtein距离是另一种比较两个字符串的算法,它类似于Levenshtein距离算法。两者之间的区别在于,它还可以检查字符之间的置换,因此在纠错方面可能会产生更好的结果。

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


3
请添加参考资料(网站、书籍、论文等)。 - Max Leske

8
您可以使用ngrams来实现。例如,将两个字符串转换为单词三元组(通常是小写),并比较它们之间相等的百分比。
您需要定义相似性的最低百分比。

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


5

您可以考虑的另一个算法是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

1
你可以使用计算最长公共子序列长度的算法来解决这个问题。如果输入字符串的最长公共子序列长度小于任一字符串的长度,则它们不相等。
你可以使用动态规划的方法来解决这个问题,并在不想找出最长公共子序列的情况下优化空间复杂度。

这个答案忽略了OP提到的比较涉及“由人类输入的案件标题,其中缩写和其他小细节可能不同”。然而,它非常明确地回答了OP之前的措辞,询问如何“比较字符串以决定它们是否表示相同的东西”,如果“东西”=“字符串”。 - bballdave025

0
这里提到的字符串相似性指标都可以工作。然而,以非常具体的方式进一步规范化文本可以带来更好的结果。
TL;DR

从我在语音识别和手写识别方面的经验来看,我认为您的问题最好通过使用文本规范化已存档)后跟一个词错误率已存档)来解决。 这个过程的一个很好、快速的概述可以在Amazon AWS机器学习博客上关于评估语音识别的文章已存档)中找到。做这个过程(规范化和评分)的一个很好(有点标准)的工具是NIST的SCTK。首先使用rfilter1进行文本规范化,然后使用sclite得到分数。根据分数确定哪些字符串您认为匹配。

更多细节

我认为有三个研究/应用领域的问题与您的问题非常相似。它们是:1) 语音识别 (已存档) (一个“缩写和其他小细节可能不同”的领域);以及在相关解决方案中的2) 光学字符识别 (已存档) 和3) 手写识别 (已存档) (两个领域“数据由人类输入,其中缩写和其他小细节可能不同”)。

查看自动或人工转录/识别的评分以及在任何这种转录中搜索字符串的问题,非常有用。根据我在这些领域的经验,最好的相似度比较来自于使用单词而不是字符来查找编辑距离的Levenshtein Distance已归档);这被称为单词错误率。对文本进行规范化,包括大小写、标点符号和缩写等内容,可以使比较更好。

一个快速的例子

看起来你正在使用CC ++scliterfilter1大多数是用C编写的。我希望这个示例使用bash+sclite就足够了。

law.glm的内容,是一个非常简单的GLM文件(全局映射文件,即搜索和替换规则对)

;;
* name "law.glm"
* desc "Showing extra normalization"
* format = "NIST1"     ;; other option is NIST2
* max_nrules = "1000"  ;; allocating space (I can update this if necessary)
* copy_no_hit = "T"    ;; don't ignore the line if there isn't a match
* case_sensitive = "F"

. => / __ [ ] ;; changes only if there's a space after it
, => / __ [ ]
? => / __ [ ]
! => / __ [ ]
versus => v / [ ] __ [ ] ;; changes only if there's a space before & after
vs => v / [ ] __ [ ]
& => and / [ ] __ [ ]
llp => limited liability partnership / [ ] __ [ ]
llc => limited liability company / [ ] __ [ ]
it's => it is / [ ] __ [ ]
shoppe => shop / [ ] __ [ ]
mister => Mr / [ ] __ [ ]

现在,在 bash 中。
$ first="Henry C. Harper v. The Law Offices of Huey & Luey, LLP (spk1_1)" 
$ second="Harper v. The Law Offices of Huey & Luey, LLP (spk1_1)"
#
# sclite requires actual files.
# It also requires something after the string (an ID, which has been
#+ put in as '(spk1_1)', don't worry about the details.)
#
$ echo "${first}" > first.txt
$ echo "${second}" > second.txt
#
# normalization
$ rfilter1 law.glm < first.txt > first_glm_normalized.txt
$ tr [A-Z] [a-z] < first_glm_normalized.txt > first_normalized.txt
$ rfilter1 law.glm < second.txt > second_glm_normalized.txt
$ tr [A-Z] [a-z] < second_glm_normalized.txt > second_normalized.txt
#
# Run the scorer (similarity finder)
$ sclite -r first_normalized.txt -h second_normalized.txt -i rm -o snt stdout
===============================================================================

                     SENTENCE LEVEL REPORT FOR THE SYSTEM:
    Name: second_normalized.txt

===============================================================================


SPEAKER spk1
id: (spk1_1)
Scores: (#C #S #D #I) 12 0 2 0
REF:  HENRY C harper v the law offices of huey and luey limited liability partnership
HYP:  ***** * harper v the law offices of huey and luey limited liability partnership
Eval: D     D                                                                   

Correct               =   85.7%   12   ( 12)
Substitutions         =    0.0%    0   (  0)
Deletions             =   14.3%    2   (  2)
Insertions            =    0.0%    0   (  0)

Errors                =   14.3%    2   (  2)

Ref. words            =           14   ( 14)
Hyp. words            =           12   ( 12)
Aligned words         =           14   ( 14)

-------------------------------------------------------------------------------


$ # That `-i rm' has to do with that ID we talked about

所以,这是一个14.3%的词错误率。
现在,让我们来看一个不应该匹配的法律案例名称。
$ third="Larry Viola versus The Law Office of Mister Scrooge McDuck, Limited Liability Corporation (spk1_1)"
$ echo "${third}" > third.txt
$ rfilter1 law.glm < third.txt > third_glm_normalized.txt
$ tr [A-Z] [a-z] < third_glm_normalized.txt > third_normalized.txt
#
$ sclite -r first_normalized.txt -h third_normalized.txt -i rm -o snt stdout
$ sclite -r first_normalized.txt -h third_normalized.txt -i rm -o snt stdout    ===============================================================================

                     SENTENCE LEVEL REPORT FOR THE SYSTEM:
    Name: third_normalized.txt

===============================================================================


SPEAKER spk1
id: (spk1_1)
Scores: (#C #S #D #I) 6 7 1 0
REF:  HENRY C     HARPER v the law OFFICES of HUEY AND     LUEY   limited liability PARTNERSHIP
HYP:  ***** LARRY VIOLA  v the law OFFICE  of MR   SCROOGE MCDUCK limited liability CORPORATION
Eval: D     S     S                S          S    S       S                        S

Correct               =   42.9%    6   (  6)
Substitutions         =   50.0%    7   (  7)
Deletions             =    7.1%    1   (  1)
Insertions            =    0.0%    0   (  0)

Errors                =   57.1%    8   (  8)

Ref. words            =           14   ( 14)
Hyp. words            =           13   ( 13)
Aligned words         =           14   ( 14)

-------------------------------------------------------------------------------


$ # This one has a 57.1% Word Error Rate

您可能需要将一些字符串通过评分(比较)过程,以得出在哪里将TrueFalse分开的启发式。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接