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:
“Henry David Thoreau, who never earned much of a living or sustained a relationship with any woman that wasn’t brotherly—who lived mostly under his parents’ roof ... who advocated one day’s work and six days “off” as the weekly round and was considered a bit of a fool in his hometown ... is probably the American writer who tells us best how to live comfortably with our most constant companion, ourselves.”
—Edward Hoagland (b. 1932)
“... the Wall became a magnet for citizens of every generation, class, race, and relationship to the war perhaps because it is the only great public monument that allows the anesthetized holes in the heart to fill with a truly national grief.”
—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)
“A solitary traveler whom we saw perambulating in the distance loomed like a giant. He appeared to walk slouchingly, as if held up from above by straps under his shoulders, as much as supported by the plain below. Men and boys would have appeared alike at a little distance, there being no object by which to measure them. Indeed, to an inlander, the Cape landscape is a constant mirage.”
—Henry David Thoreau (1817–1862)