Computing the edit distance
The edit distance or Levenshtein distance is the minimum number of simple string operations required to convert one string into another. In this recipe, we will compute the edit distance based on only insertions, deletions, and substitutions of characters.
Getting ready
Review the equation shown in the following figure obtained from the Wikipedia article about the Levenshtein distance (http://en.wikipedia.org/wiki/Levenshtein_distance):
Here, a and b are the two strings, and i and j are numbers representing their lengths.
The Haskell code will be a direct translation of this mathematical formula.
Also, install the data-memocombinators ...
Get Haskell Data Analysis Cookbook now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
