diff lists

[Steven D. Majewski]

On 29 Mar 2001, Michael Hudson wrote:

> 
> Tangentially, does anyone know of any good algorithms for "edit
> distance" between two sequences?  E.g. if I have 
> 
> "abcdef"
> 
> and want to get to
> 
> "abQUACKcde"
> 
> I want to get the answer back "insert 'QUACK' at position 3 and delete
> a character at position 11".
> 
> "Good" means "pretty quick", here.
> 

I used to have a Levenshtein string edit distance done in Icon, and
I think I may have translated it to python once, but I can't find 
a copy. 

If you do a google search on that, you'll find a lot of stuff:

http://www-apparitions.ucsd.edu/~rmckinle/string/
http://www-igm.univ-mlv.fr/~lecroq/lec_en.html
http://www.ling.ohio-state.edu/~cbrew/795M/string-distance.html

However, the algorithm for the distance does not give location, but
maybe this info can be extracted from the intermediate matrix. 


-- Steve Majewski