Sunday, 9 August 2009

Dynamic programming: Levenshtein edit distance

The OCaml Journal just published an article about dynamic programming and memoization:

"Levenshtein distance is a metric used to measure the amount of difference between a pair of sequences in terms of the number of insertions, deletions and substitutions required to get from one sequence to the other. Computing the Levenshtein distance is an interesting problem in dynamic programming with many practical applications including spell checkers and the study of DNA in bioinformatics. This article describes how the basic algorithm may be implemented and then optimized, including the use of both generic and specialized memoization..."

To read this article and more, subscribe to The OCaml Journal today!