Levenshtein Distance - Relationship With Other Edit Distance Metrics

Relationship With Other Edit Distance Metrics

Levenshtein distance is not the only popular notion of edit distance. Variations can be obtained by changing the set of allowable edit operations: for instance,

  • length of the longest common subsequence is the metric obtained by allowing only addition and deletion, not substitution;
  • the Damerau–Levenshtein distance allows addition, deletion, substitution, and the transposition of two adjacent characters;
  • the Hamming distance only allows substitution (and hence, only applies to strings of the same length).

Edit distance in general is usually defined as a parametrizable metric in which a repertoire of edit operations is available, and each operation is assigned a cost (possibly infinite). This is further generalized by DNA sequence alignment algorithms such as the Smith–Waterman algorithm, which make an operation's cost depend on where it is applied.

Read more about this topic:  Levenshtein Distance

Famous quotes containing the words relationship with, relationship, edit and/or distance:

    “Christianity as an organized religion has not always had a harmonious relationship with the family. Unlike Judaism, it kept almost no rituals that took place in private homes. The esteem that monasticism and priestly celibacy enjoyed implied a denigration of marriage and parenthood.”
    —Beatrice Gottlieb, U.S. historian. The Family in the Western World from the Black Death to the Industrial Age, ch. 12, Oxford University Press (1993)

    “But the relationship of morality and power is a very subtle one. Because ultimately power without morality is no longer power.”
    —James Baldwin (1924–1987)

    “To a philosopher all news, as it is called, is gossip, and they who edit it and read it are old women over their tea.”
    —Henry David Thoreau (1817–1862)

    “Midway the lake we took on board two manly-looking middle-aged men.... I talked with one of them, telling him that I had come all this distance partly to see where the white pine, the Eastern stuff of which our houses are built, grew, but that on this and a previous excursion into another part of Maine I had found it a scarce tree; and I asked him where I must look for it. With a smile, he answered that he could hardly tell me.”
    —Henry David Thoreau (1817–1862)