levenshtein-distance - 比较相似度算法

Question

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

我遇到了其中几个:

• 贾罗，
• 贾罗-温克勒，
• 编辑，
• 欧几里得和
• Q-gram，

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

Answer 1

扩展我在勘误表中的 wiki-walk 评论和 noting some of the ground-floor literature on the comparability of algorithms that apply to similar problem spaces,在确定这些算法在数值上是否具有可比性之前，让我们先探讨一下它们的适用性。

来自维基百科，Jaro-Winkler :

In computer science and statistics, the Jaro–Winkler distance (Winkler, 1990) is a measure of similarity between two strings. It is a variant of the Jaro distance metric (Jaro, 1989, 1995) and mainly[citation needed] used in the area of record linkage (duplicate detection). The higher the Jaro–Winkler distance for two strings is, the more similar the strings are. The Jaro–Winkler distance metric is designed and best suited for short strings such as person names. The score is normalized such that 0 equates to no similarity and 1 is an exact match.

Levenshtein distance:

In information theory and computer science, the Levenshtein distance is a string metric for measuring the amount of difference between two sequences. The term edit distance is often used to refer specifically to Levenshtein distance.

The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character. It is named after Vladimir Levenshtein, who considered this distance in 1965.

Euclidean distance:

In mathematics, the Euclidean distance or Euclidean metric is the "ordinary" distance between two points that one would measure with a ruler, and is given by the Pythagorean formula. By using this formula as distance, Euclidean space (or even any inner product space) becomes a metric space. The associated norm is called the Euclidean norm. Older literature refers to the metric as Pythagorean metric.

和Q- or n-gram encoding:

In the fields of computational linguistics and probability, an n-gram is a contiguous sequence of n items from a given sequence of text or speech. The items in question can be phonemes, syllables, letters, words or base pairs according to the application. n-grams are collected from a text or speech corpus.

The two core advantages of n-gram models (and algorithms that use them) are relative simplicity and the ability to scale up – by simply increasing n a model can be used to store more context with a well-understood space–time tradeoff, enabling small experiments to scale up very efficiently.

问题是这些算法解决了不同的问题，这些问题在解决longest common subsequence的所有可能算法的空间内具有不同的适用性。问题，在您的数据中或嫁接可用的metric其中。事实上，并非所有这些都是指标，因为其中一些不满足 triangle inequality .

不要特意定义一个可疑的方案来检测数据损坏，正确地执行此操作:使用 checksums和 parity bits当更简单的解决方案可以解决问题时，不要试图解决更困难的问题。