1.介绍

在本教程中,我们将了解量化字符串相似性的方法。金宝搏官网188be在大多数情况下,我们将讨论可用于我们应用程序的不同字符串距离类型。我们将概述不同的指标并为每个方法讨论它们的属性和计算复杂性。最后,我们将提出关于特定数据集的技术选择的建议。

2.问题上下文和度量类别

多种应用 - 从记录链接和拼写校正到语音识别和遗传测序 - 依赖于某些定量度量来确定字符串相似度的量度。字符串相似性计算可以帮助我们有任何这些问题,但通常计算昂贵,并且由于所有可能的数据故障的多样化和模糊性质,不会自动产生理想的结果。

鉴于此,我们可能希望从整个可用技术中选择要使用的最佳度量。以下是将最常见的字符串相似距离指标分组为4类的图表:

在本文中,我们将要讨论第一个类别,专注于字符串中的直接字符比较。这个家庭中的所有度量都来自于在字符串上执行的编辑操作的数量,因此通常被称为编辑距离

3.汉明距离

汉明距离是比较字符串中相应符号的位置的数量。这相当于将一个字符串转换为另一个字符串所需的最小替换数。

让我们拿两个字符串,卡罗林和蛋白。我们可能会观察到位置1,3和4(零基)的字符不同,其余的所有其余相当于。

这意味着汉明距离是3在这种情况下:

所有字符串距离度量,汉明距离中最容易应用于相同长度的字符串。计算具有线性时间复杂度的微不足道。

4. Levenshtein距离

Levenshtein距离,如汉明距离,是将一个字符串转换为另一个字符串所需的最小编辑操作数。与汉明距离不同,该组编辑操作还包括插入和删除,从而允许我们比较不同长度的字符串。

给定两个字符串,它们之间的Levenshtein距离是将一个字符串更改为另一个字符串所需的单个字符编辑(插入,删除或替换)的最小数量。

例如,格栅和长颈鹿之间的Levenshtein距离为3:

如果两个字符串具有相同的尺寸,则汉明距离是Levenshtein距离上的上限。例如,由于每个位置的字符不同,谈话的汉明距离也是4,因为每个位置的字符不同。但是,他们的levenshtein距离仅为3:

Levenshtein距离符合公制要求,最重要的是对称并满意三角不等式

dist(a,b)= dist(b,a)

DIST(A,B)\ LEQ DIST(A,C)+ DIST(B,C)

Levenshtein距离计算可以是昂贵的,最糟糕的完整计算\ mathcal {o}(| a | \ times | b |)时间复杂性和\ mathcal {o}(min(| a |,| b |)))空间复杂性。存在许多优化技术以改善摊销复杂性但是一般方法是避免完整的Levenshtein距离计算超过一些预先选择的阈值。

如果我们想使用归一流的指标,我们可能会将Levenshtein距离转换为相似度措施使用公式:

sim_ {ld}(a,b)= 1.0  -  \ dfrac {dist(a,b)} {max(| a |,| b |)}

5. Damerau-Levenshtein距离

已经观察到大多数人拼写错误误差都陷入了这4种类型的误差 - 插入,删除,取代和转置。通过这种经验观察,Damerau-Levenshtein距离延伸了Levenshtein距离允许的编辑操作集换位两个相邻的角色。

例如,礼品和适合之间的Levenshtein距离为3:

在此示例中,我们需要两个步骤来转换为fi。但是,如果我们允许两个相邻字符之间的转换,我们只能使用一步进行转换。因此,礼品和适合之间的Damerau-Levenshtein距离是2:

将换位纳入原始Levenshtein距离计算算法可能是相对挑战的。Straightforward modification of the dynamic programming approach used for Levenshtein distance computation with the entry responsible for transposition unexpectedly calculates not Damerau-Levenshtein distance but “optimal string alignment distance” which is not only different from the expected result but also doesn’t hold triangle inequality property.

高效算法计算Damerau-Levenshtein距离提供相同的复杂性 -\ mathcal {o}(| a | \ times | b |)

6. Jaro距离

字符串之间的Jaro相似性一种B.使用公式定义:

sim_ {j} = \ begin {uis} 0 \ hefil \ mbox {if} m = 0,\\ \ dfrac {1} {3} \ left(\ dfrac {m} {| {a} |} + \ dfrac{m} {| | {b} |} + \ dfrac {m  -  t} {m} \ other)\ hefill \ mbox {否则} \\ \结束{iscus}

在哪里:

m是匹配字符的数量。我们考虑两个角色一种B.与匹配相匹配,如果它们相同,而不是比{\ left \ lfloor {\ frac {\ max(| {a} |,| {b} |)} {2}} \ \ \ rfloor -1字符分开。

T.是匹配数(但不同的序列顺序)字符的一半。

Jaro相似性值范围为0到1包。如果两个字符串完全相同,那么| {a} |= | {B} |= M.t = 0.。因此,他们的Jaro相似性是基于第二个条件的1。在另一边,如果两个字符串完全不同,那么m = 0.。他们的Jaro相似性将是0的第一个条件。

Jaro距离是Jaro相似性的反演:1-sim_ {j}。因此,较大的Jaro距离值意味着两个字符串之间的更多差异。

例如,比较卡特尔与跟踪,我们可能看到只有“A”,'R'和'E'是匹配的字符:

匹配距离阈值是{\ left \ lfloor {\ frac {\ max(6,5)} {2}} \ rick \ rfloor -1 = 2。虽然角色'C'出现在两个字符串中,但它们分开了3个字符。因此,我们不会认为'C'作为匹配字符。同样,角色't'也不是匹配的字符。总的来说,匹配字符的总数是m = 3.

匹配序列是和rae。匹配数(但不同的序列顺序)字符为2,这意味着t = 1。因此,两个字符串的Jaro相似值是\ dfrac {1} {3} \ left(\ dfrac {3} {6} + \ dfrac {3} {5} + \ dfrac {3  -  1} {3}右)= \ dfrac {53} {90\ \约0.5889。然后,Jaro距离是1  -  \ DFRAC {53} {90} \约0.4111

算法计算Jaro距离的时间和空间复杂性是\ Mathcal {O}(| A | + | B |)

7. Jaro-Winkler距离

Winkler通过基于经验观察应用思路来改进Jaro算法,这发现通常在拼写错误人名的开头时出现更少的错误。

因此,Winkler算法增加了同等初始字符的Jaro相似度测量:

sim_ {jw}(a,b)= sim_ {j}(a,b)+ l * p *(1  -  sim_ {j}(a,b))

在哪里:

L.是两个字符串开始时共同前缀的长度,最多可为4。

P.是缩放因素。缩放因子不应超过0.25。否则,相似性可能变得大于1,因为所考虑的前缀的最大长度为4.原始Winkler的工作使用值0.1。

类似于Jaro距离,我们可以将Jaro-Winkler距离定义为d_ {jw} = 1-sim_ {jw}

例如,当我们比较两个字符串处理和跟踪时,匹配序列是tra:

因此,这两个字符串之间的Jaro相似性是\ dfrac {1} {3} \ left(\ dfrac {3} {5} + \ dfrac {3} {5} + \ dfrac {3  -  0} {3}右)= \ dfrac {11} {15\ \约0.7333。两个字符串的共同前缀是TR,其长度为2.如果我们使用0.1作为缩放因子,则Jaro-Winkler的相似性将是\ DFRAC {11} {15} + 2 * 0.1 *(1  -  \ DFRAC {11} {15})= \ DFRAC {59} {75} \ \约0.7867。然后,Jaro-Winkler距离是1  -  \ DFRAC {59} {75} \约0.2133

Jaro-Winkler距离并不遵守三角不等式,因此不是一个公制适合建造公制空间

Winkler还考虑了比较具有两个或多个单词的字符串的主题,可能有不同的订购。为此,他介绍了变种排序闪光灯允许的洪克勒。前算法在计算相似度之前按字母顺序排列字符串,而后者在所有可能的置换上计算相似性并返回最大值。

8.评估和建议

鉴于所有可用算法的各种可用算法,在相关数据集中评估匹配质量变得重要。任何匹配的最终结果应基于基于所选择的相似度测量阈值 - 字符串对被分类为匹配/非匹配,其中相似度值阈值是分类的匹配,以及与不匹配的相似值的对对。

为了提供有形估计,常见做法是使用标记的培训数据。

对于每个匹配对,我们定义了真实阳性的数量TP.- 已知匹配字符串对被归类为匹配项,真正的否定TN.- 已知的未匹配对被归类为非匹配,假阳性FP.- 无与伦比的对被归类为匹配项,以及错误的否定FN.- 已知匹配对被归类为非匹配项。

使用这些值,我们估计精确记起

p = \ dfrac {tp} {tp + fp}

r = \ dfrac {tp} {tp + fn}

精确反映了所有发现匹配中的实际对应关系的份额。具有高值的溶液意味着它不会返回许多误报。

调用指定实际对应关系的份额。给定答案的高值召回意味着它不会返回许多错误的否定。

最后,为了估算整体效率,我们可以使用F测量F测量是精确和召回的谐波均值

r = \ dfrac {2 \ times p \ times r} {p + r}

选择最佳阈值以实现最高的F措施可能被证明是具有挑战性的。一些算法和数据集之间的相似度测量阈值与结果为低耦合,而其他算法均表明甚至小的阈值变化可能导致匹配质量的戏剧性下降。

除匹配质量外,性能对于处理大数据集是至关重要的。

如果速度很重要,则必须在字符串长度中使用时间复杂性线性的技术。如果已知手的名称数据包含大量昵称,别名和类似的变化,则应在执行匹配之前应用基于字典的名称标准化。

通常,我们可能希望使用提供更好的质量 - 如Levenshtein距离 - 用于更短的琴弦,以及基于令牌的Q-Gram或袋距离 - 更长的琴弦。

除了字符串的相似之处,句法本质上,我们可能需要解决在不同句子或整个文档中找到语义相似性的相关问题。基于的各种语义指标路径长度信息内容词典, 和更多。在他们之上,建立了几种统计方法,包括潜在语义分析点相互信息, 还有很多。

在上面概述的类别之外还有一些其他的常见度量,就像NCD.-归一化压缩距离,您可能想要在您的申请中雇用。

9.结论

在本教程中,我们已经讨论了多个算法和度量标准来评估字符串相似度。

我们发现我们可以使用多种不同的方法来解决这个问题,每个都具有自己的复杂性,就实现和执行而言。

最后,我们已经看到了我们如何评估这些指标,以找到最适合我们的应用程序。

评论在本文上关闭!