{"id":576,"date":"2008-11-01T16:31:32","date_gmt":"2008-11-01T15:31:32","guid":{"rendered":"http:\/\/www.navision-blog.de\/2008\/11\/01\/damerau-levenshtein-distance-in-fsharp-part-iii\/"},"modified":"2008-11-01T16:33:45","modified_gmt":"2008-11-01T15:33:45","slug":"damerau-levenshtein-distance-in-fsharp-part-iii","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2008\/11\/01\/damerau-levenshtein-distance-in-fsharp-part-iii\/","title":{"rendered":"Damerau-Levenshtein-Distance in F# &#8211; part III &#8211; O(m+n) space and functional style"},"content":{"rendered":"<p>In the <a href=\"http:\/\/www.navision-blog.de\/2008\/10\/31\/damerau-levenshtein-distance-in-fsharp-part-i\/\">first part of this series<\/a> I showed a na&#239;ve algorithm for the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Damerau-Levenshtein_distance\">Damerau-Levenshtein distance<\/a> which needs O(m*n) space. In the <a href=\"http:\/\/www.navision-blog.de\/2008\/11\/01\/damerau-levenshtein-distance-in-fsharp-part-ii\/\">last post<\/a> I improved the algorithm to use only O(m+n) space. This time I will show a more functional implementation which uses only immutable F#-Lists and works still in O(m+n) space. This version doesn&#8217;t need any mutable data.   <\/p>\n<pre class=\"code\"><span style=\"color: green\">\/\/\/ Calcs the damerau levenshtein distance.    \n<\/span><span style=\"color: blue\">let <\/span>calcDL (a:'a array) (b: 'a array) =       \n  <span style=\"color: blue\">let <\/span>n = a.Length + 1\n  <span style=\"color: blue\">let <\/span>m = b.Length + 1\n  \n  <span style=\"color: blue\">let <\/span>processCell i j act l1 l2 ll1 =\n    <span style=\"color: blue\">let <\/span>cost = \n      <span style=\"color: blue\">if <\/span>a.[i-1] = b.[j-1] <span style=\"color: blue\">then <\/span>0 <span style=\"color: blue\">else <\/span>1\n    <span style=\"color: blue\">let <\/span>deletion = l2 + 1\n    <span style=\"color: blue\">let <\/span>insertion = act + 1\n    <span style=\"color: blue\">let <\/span>substitution = l1 + cost\n    <span style=\"color: blue\">let <\/span>min1 =  \n      deletion \n      |&gt; min insertion \n      |&gt; min substitution\n\n    <span style=\"color: blue\">if <\/span>i &gt; 1 &amp;&amp; j &gt; 1 &amp;&amp;\n      a.[i-1] = b.[j-2] &amp;&amp; a.[i-2] = b.[j-1] <span style=\"color: blue\">then\n        <\/span>min min1 &lt;| ll1 + cost\n    <span style=\"color: blue\">else\n      <\/span>min1\n  \n  <span style=\"color: blue\">let <\/span>processLine i lastL lastLastL =\n    <span style=\"color: blue\">let <\/span>processNext (actL,lastL,lastLastL) j =\n      <span style=\"color: blue\">match <\/span>actL <span style=\"color: blue\">with \n        <\/span>| act::actRest <span style=\"color: blue\">-&gt; \n          match <\/span>lastL <span style=\"color: blue\">with\n            <\/span>| l1::l2::lastRest <span style=\"color: blue\">-&gt; \n              if <\/span>i &gt; 1 &amp;&amp; j &gt; 1 <span style=\"color: blue\">then\n                match <\/span>lastLastL <span style=\"color: blue\">with\n                  <\/span>| ll1::lastLastRest <span style=\"color: blue\">-&gt; \n                    <\/span>(processCell i j act l1 l2 ll1 :: actL,\n                     l2::lastRest,\n                     lastLastRest)\n                  | _ <span style=\"color: blue\">-&gt; <\/span>failwith <span style=\"color: maroon\">&quot;can't be&quot;\n              <\/span><span style=\"color: blue\">else\n                <\/span>(processCell i j act l1 l2 0 :: actL,\n                 l2::lastRest,\n                 lastLastL)                 \n            | _ <span style=\"color: blue\">-&gt; <\/span>failwith <span style=\"color: maroon\">&quot;can't be&quot;\n        <\/span>| [] <span style=\"color: blue\">-&gt; <\/span>failwith <span style=\"color: maroon\">&quot;can't be&quot;\n      \n    <\/span><span style=\"color: blue\">let <\/span>(act,last,lastLast) =\n      [1..b.Length]\n        |&gt; List.fold_left processNext ([i],lastL,lastLastL)\n    act |&gt; List.rev\n    \n  <span style=\"color: blue\">let <\/span>(lastLine,lastLastLine) =               \n    [1..a.Length]\n      |&gt; List.fold_left\n          (<span style=\"color: blue\">fun <\/span>(lastL,lastLastL) i <span style=\"color: blue\">-&gt; <\/span>\n             (processLine i lastL lastLastL,lastL))\n          ([0..m-1],[])\n              \n  lastLine.[b.Length]    \n \n<span style=\"color: blue\">let <\/span>damerauLevenshtein(a:'a array) (b:'a array) =\n  <span style=\"color: blue\">if <\/span>a.Length &gt; b.Length <span style=\"color: blue\">then\n    <\/span>calcDL a b\n  <span style=\"color: blue\">else\n    <\/span>calcDL b a<\/pre>\n<p>I admit the code is still a little messy but it works fine. Maybe I will find the time to cleanup a bit and post a final version.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In the first part of this series I showed a na&#239;ve algorithm for the Damerau-Levenshtein distance which needs O(m*n) space. In the last post I improved the algorithm to use only O(m+n) space. This time I will show a more functional implementation which uses only immutable F#-Lists and works still in O(m+n) space. This version [&hellip;]<\/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,34],"tags":[53,465,470,86,469,468,664,467,466],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/576"}],"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=576"}],"version-history":[{"count":1,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/576\/revisions"}],"predecessor-version":[{"id":577,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/576\/revisions\/577"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=576"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=576"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=576"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}