|
|
|
|
|
|
|
|
CTK Exchange
Jon
guest
|
Dec-01-03, 03:05 PM (EST) |
|
|
"Levenshtein Distance"
| |
Hi, I'm taking a look at Levenshtein distance for comparing two strings, and was wondering if (and how!) we can prove that it'satisfies the triangle inequality? Many thanks from a lost computing student! Jon |
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
Vladimir
Member since Jun-22-03
|
Dec-01-03, 08:08 PM (EST) |
   |
1. "RE: Levenstein Distance"
In response to message #0
| |
LAST EDITED ON Dec-01-03 AT 08:24 PM (EST)
Levenstein distance of 2 finite sequences (such as strings, DNA sequences, protein amino acid sequences, etc.) is defined as the minimum number of steps (replacement, deletion, or insertion) required to edit one string into the other.Let A, B, C be 3 arbitrary strings and let D(A,B) be Levenstein distance of strings A and B. 1. D(A,A) = 0
No editing is required. 2. D(A,B) = D(B,A)
Minimum number of steps required to edit'string A into string B is the same as the minimum number of steps reqiured to edit string B into string A in reverse. 3. D(A,C) <= D(A,B) + D(B,C)
String A can be edited to string C directly. Or it can be first edited to some other string B, which is subsequently edited to string C. This cannot take less editing steps than the minimum number of steps required for direct editing. Hence, Levenstein distance is a metric. See Alignment: Definitions and Algorithms. |
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
 |
alexb
Charter Member
1852 posts |
May-29-06, 10:31 AM (EST) |
 |
4. "RE: Levenshtein Distance"
In response to message #3
| |
>Well I am a computer scientist ... which I am not >and planning to work on
>Levenshtein distance and the reversal distances. Good luck. Please keep us informed of any progress. >Do you have
>any idea about the recent work done in this very field? Candidly, no. But googling brought up many links I was unaware of.
|
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.
Copyright © 1996-2018 Alexander Bogomolny
|
|
Printer-friendly copy
Email this topic to a friend