Edit distance recomputation

schluehk

Dear participants,

I have a question concerning effective re-computations of an edit distance. What I mean is the following:

suppose we have two strings A, B and a value d = edit_dist(A,B) computed with an algorithm like the Levenshtein algorithm. Now we change A into A' using one edit operation i.e. we insert, delete or change one character in A. Is there a way to avoid a complete recomputation d' = edit_dist(A',B)?

I'd be appreciate a lot if someone can point to an article or book where this problem is treated.

Thx