f



Edit distance.

I have implmented the Levenshtein algorigthm and it works great for
turning one string into another, but I have discovered that this is
not exactly what I need.  One string will be edited to conform to
merely a substring of another .

So for instance

abbcdefg
abcdefghijklmno

I want a edit distance of 1 where you only have to remove the b.

With Levenshtein the matrix is static.  If you add ijklmno to make the
lengths the same the distance is 2.  Is there an efficient algorithm
that does this?  I have determined that you can use levenshtein
distance to determine which option remove, replace, insert is the best
option and correct the string as you go.  But if there are many
differences the complexity is bad.
0
6/25/2003 9:53:06 PM
comp.theory 5139 articles. 1 followers. marty.musatov (1143) is leader. Post Follow

1 Replies
474 Views

Similar Articles

[PageSpeed] 32

http://www.cogsci.ed.ac.uk/~chrisbr/papers/mt-eval-final/node22.html

for wagner fischer
0
6/26/2003 2:01:41 PM
Reply: