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:
“Guilty, guilty, guilty is the chant divorced parents repeat in their heads. This constant reminder remains just below our consciousness. Nevertheless, its presence clouds our judgment, inhibits our actions, and interferes in our relationship with our children. Guilt is a major roadblock to building a new life for yourself and to being an effective parent.”
—Stephanie Marston (20th century)
“Poetry is above all a concentration of the power of language, which is the power of our ultimate relationship to everything in the universe.”
—Adrienne Rich (b. 1929)
“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)
“Morality without religion is only a kind of dead reckoning—an endeavor to find our place on a cloudy sea by measuring the distance we have run, but without any observation of the heavenly bodies.”
—Henry Wadsworth Longfellow (1807–1882)