{"id":555,"date":"2008-10-31T17:12:49","date_gmt":"2008-10-31T16:12:49","guid":{"rendered":"http:\/\/www.navision-blog.de\/2008\/10\/31\/damerau-levenshtein-distance-in-f\/"},"modified":"2008-11-01T14:41:35","modified_gmt":"2008-11-01T13:41:35","slug":"damerau-levenshtein-distance-in-fsharp-part-i","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2008\/10\/31\/damerau-levenshtein-distance-in-fsharp-part-i\/","title":{"rendered":"Damerau-Levenshtein-Distance in F# – part I"},"content":{"rendered":"

Today I am publishing an algorithm for calculating the Damerau-Levenshtein distance<\/a> in F#. The Levenshtein distance<\/a> is a metric that allows to measure the amount of difference between two sequences and shows how many edit operations (insert, delete, substitution) are needed to transform one sequence into the other. The Damerau-Levenshtein distance<\/a> allows the transposition<\/a> of two characters as an operation. It is often used for spelling corrections or to measure the variation (“edit distance”) between DNA sequences.<\/p>\n

\n
let<\/span> damerauLevenshtein(a:'a array) (b:'a array) =       <\/pre>\n
  let<\/span> init i j =<\/pre>\n
    if<\/span> j = 0 then<\/span> i<\/pre>\n
    elif<\/span> i = 0 then<\/span> j else<\/span> 0<\/pre>\n
  let<\/span> n = a.Length + 1<\/pre>\n
  let<\/span> m = b.Length + 1<\/pre>\n
 <\/pre>\n
  let<\/span> d = Array2.init n m init<\/pre>\n
 <\/pre>\n
  for<\/span> i in<\/span> [1..a.Length] do<\/span><\/pre>\n
    for<\/span> j in<\/span> [1..b.Length] do<\/span>          <\/pre>\n
      let<\/span> cost = <\/pre>\n
        if<\/span> a.[i-1] = b.[j-1] then<\/span> 0 else<\/span> 1<\/pre>\n
      let<\/span> deletion = d.[i-1, j] + 1<\/pre>\n
      let<\/span> insertion = d.[i,j-1] + 1<\/pre>\n
      let<\/span> substitution = d.[i-1,j-1] + cost<\/pre>\n
      d.[i, j] <- <\/pre>\n
        deletion <\/pre>\n
        |> min insertion <\/pre>\n
        |> min substitution<\/pre>\n
 <\/pre>\n
      if<\/span> i > 1 && j > 1 && a.[i-1] = b.[j-2] && <\/pre>\n
           a.[i-2] = b.[j-1] then<\/span><\/pre>\n
        let<\/span> transposition = d.[i-2,j-2] + cost  <\/pre>\n
        d.[i, j] <- min d.[i,j] transposition  <\/pre>\n
 <\/pre>\n
  d.[a.Length, b.Length]  <\/pre>\n<\/div>\n
This naïve implementation needs quadratic space (O(m*n)<\/em>). Since the algorithm is used to calculate the edit distance of large DNA sequences this is extremly bad. Next time<\/a> I will show how we can get linear space (O(m+n)<\/em>) for the algorithm.<\/p>\n","protected":false},"excerpt":{"rendered":"
Today I am publishing an algorithm for calculating the Damerau-Levenshtein distance in F#. The Levenshtein distance is a metric that allows to measure the amount of difference between two sequences and shows how many edit operations (insert, delete, substitution) are needed to transform one sequence into the other. The Damerau-Levenshtein distance allows the transposition of […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[9,448,8],"tags":[53,465,86,469,468,664,467,466],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/555"}],"collection":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/comments?post=555"}],"version-history":[{"count":17,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/555\/revisions"}],"predecessor-version":[{"id":573,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/555\/revisions\/573"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=555"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=555"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=555"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}