Dynamic edit distance table under a general weighted cost function
We discuss the problem of edit distance computation under a dynamic setting, where one of the two compared strings may be modified by single-character edit operations and we wish to keep the edit distance information between the strings up-to-date. A previous algorithm by Kim and Park (2004) [6] solves a more limited problem where modifications can be done only at the ends of the strings (so-called decremental or incremental edits) and the edit operations have (essentially) unit costs. If the lengths of the two strings are m and n , their algorithm requires O(m+n) O ( m + n ) time per modification. We propose a simple and practical algorithm that (1) allows arbitrary non-negative costs for the edit operations and (2) allows the modifications to be done at arbitrary positions. If the latter string is modified at position j? j ? , our algorithm requires O(min?{rc(m+n),mn}) O ( min ? { r c ( m + n ) , m n } ) time, where r=min?{j?,n?j?+1} r = min ? { j ? , n ? j ? + 1 } and c  is the maximum edit operation cost. This equals O(m+n) O ( m + n ) in the simple decremental/incremental unit cost case. Our experiments indicate that the algorithm performs much faster than the theoretical worst-case time limit O(mn) O ( m n ) in the general case with arbitrary edit costs and modification positions. The main practical limitation of the algorithm is its ?(mn) ? ( m n ) memory requirement for storing the edit distance information.
edit distance general cost functions dynamic programming incremental string comparison