Edit distance recomputation

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.

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!