43

我想使用字符串相似度函数在我的数据库中查找损坏的数据。

我遇到了其中几个：

  • 哈罗，
  • 雅罗-温克勒，
  • 莱文斯坦，
  • 欧几里得和
  • Q-克，

我想知道它们之间有什么区别以及它们在什么情况下效果最好？

4

2 回答 2

42

扩展我在勘误表中的 wiki-walk 评论，并注意一些关于适用于类似问题空间的算法可比性的底层文献，让我们在确定它们是否在数值上具有可比性之前探索这些算法的适用性。

来自维基百科，Jaro-Winkler：

在计算机科学和统计学中，Jaro-Winkler 距离 (Winkler, 1990) 是衡量两个字符串之间相似性的指标。它是 Jaro 距离度量 (Jaro, 1989, 1995) 的变体，主要用于记录链接（重复检测）领域。两个弦的 Jaro-Winkler 距离越大，弦越相似。Jaro-Winkler 距离度量是专为短字符串（例如人名）而设计的。分数被归一化，0 表示没有相似性，1 表示完全匹配。

莱文斯坦距离：

在信息论和计算机科学中，Levenshtein 距离是一种字符串度量，用于测量两个序列之间的差异量。术语编辑距离通常用于特指 Levenshtein 距离。

两个字符串之间的 Levenshtein 距离定义为将一个字符串转换为另一个字符串所需的最小编辑次数，允许的编辑操作是插入、删除或替换单个字符。它以弗拉基米尔·列文斯坦 (Vladimir Levenshtein) 的名字命名，他在 1965 年考虑到了这个距离。

欧几里得距离：

在数学中，欧几里得距离或欧几里得度量是用尺子测量的两点之间的“普通”距离，由毕达哥拉斯公式给出。通过使用这个公式作为距离，欧几里得空间（甚至任何内积空间）变成了度量空间。相关的范数称为欧几里得范数。较早的文献将该度量称为毕达哥拉斯度量。

和Q- 或 n-gram 编码：

在计算语言学和概率领域，n-gram 是来自给定文本或语音序列的 n 个项目的连续序列。根据应用，所讨论的项目可以是音素、音节、字母、单词或碱基对。n-gram 是从文本或语音语料库中收集的。

n-gram 模型（以及使用它们的算法）的两个核心优势是相对简单性和扩展能力——通过简单地增加 na 模型可以用于存储更多的上下文，并具有易于理解的时空折衷，实现小型实验以非常有效地扩大规模。

问题是这些算法解决了在所有可能算法的空间内具有不同适用性的不同问题，以解决最长公共子序列问题，在您的数据中或在嫁接其可用度量时。事实上，并非所有这些都是度量，因为其中一些不满足三角不等式。

与其特意定义一个可疑的方案来检测数据损坏，不如正确地做到这一点：对数据使用校验和和奇偶校验位。当一个更简单的解决方案可以解决时，不要试图解决一个更难的问题。

于 2012-03-29T21:48:21.763 回答
4

字符串相似性有很多不同的帮助。例如

  • 谷歌的你的意思是结果是使用字符串相似度计算的。
  • 字符串相似度用于纠正 OCR 错误。
  • 字符串相似性用于纠正键盘输入错误。
  • 字符串相似性用于在生物信息学中寻找两个 DNA 的最匹配序列。

但由于一种尺寸并不适合所有人。每个字符串相似度算法都是为特定用途而设计的，尽管它们中的大多数是相似的。例如Levenshtein_distance是关于您更改多少字符以使两个字符串相等。

kitten → sitten

这里距离是 1 个字符变化。您可以对删除、添加和替换赋予不同的权重。例如，OCR 错误和键盘错误对某些更改的影响较小。OCR（一些字符与其他字符非常相似），键盘一些字符彼此非常接近。生物信息学字符串相似性允许大量插入。

您的第二个示例“ Jaro–Winkler距离度量的设计最适合短字符串，例如人名”

因此，您应该牢记您的问题。

我想使用字符串相似度函数在我的数据库中查找损坏的数据。

您的数据是如何损坏的？是用户错误吗，类似于键盘输入错误？还是类似于 OCR 错误？还是完全不同的东西？

于 2012-03-29T20:36:55.170 回答