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.