{"id":572,"date":"2008-11-01T14:40:41","date_gmt":"2008-11-01T13:40:41","guid":{"rendered":"http:\/\/www.navision-blog.de\/2008\/11\/01\/damerau-levenshtein-distance-in-fsharp-part-ii\/"},"modified":"2008-11-01T16:37:33","modified_gmt":"2008-11-01T15:37:33","slug":"damerau-levenshtein-distance-in-fsharp-part-ii","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2008\/11\/01\/damerau-levenshtein-distance-in-fsharp-part-ii\/","title":{"rendered":"Damerau-Levenshtein-Distance in F# &#8211; part II &#8211; O(m+n) space"},"content":{"rendered":"<p><a href=\"http:\/\/www.navision-blog.de\/2008\/10\/31\/damerau-levenshtein-distance-in-fsharp-part-i\/\">Last time<\/a> I showed a na&#239;ve implementation of the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Damerau-Levenshtein_distance\">Damerau-Levenshtein-Distance<\/a> in F# that needs O(m*n) space. This is really bad if we want to compute the edit distance of large sequences (e.g. DNA sequences). If we look at the algorithm we can easily see that only the last two lines of the (n*m)-matrix are used. This observation leads to a improvement where we compute the distance with only 3 additional arrays of size <em>min(n,m)<\/em>.<\/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  <span style=\"color: blue\">let <\/span>lastLine = ref (Array.init m (<span style=\"color: blue\">fun <\/span>i <span style=\"color: blue\">-&gt; <\/span>i))\n  <span style=\"color: blue\">let <\/span>lastLastLine = ref (Array.create m 0)\n  <span style=\"color: blue\">let <\/span>actLine = ref (Array.create m 0)\n    \n  <span style=\"color: blue\">for <\/span>i <span style=\"color: blue\">in <\/span>[1..a.Length] <span style=\"color: blue\">do\n    <\/span>(!actLine).[0] &lt;- i      \n    <span style=\"color: blue\">for <\/span>j <span style=\"color: blue\">in <\/span>[1..b.Length] <span style=\"color: blue\">do          \n      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 = (!lastLine).[j] + 1\n      <span style=\"color: blue\">let <\/span>insertion = (!actLine).[j-1] + 1\n      <span style=\"color: blue\">let <\/span>substitution = (!lastLine).[j-1] + cost\n      (!actLine).[j] &lt;- \n        deletion \n        |&gt; min insertion \n        |&gt; min substitution\n\n<span style=\"color: green\">      <\/span><span style=\"color: blue\">if <\/span>i &gt; 1 &amp;&amp; j &gt; 1 <span style=\"color: blue\">then\n        if <\/span>a.[i-1] = b.[j-2] &amp;&amp; a.[i-2] = b.[j-1] <span style=\"color: blue\">then\n          let <\/span>transposition = (!lastLastLine).[j-2] + cost  \n          (!actLine).[j] &lt;- min (!actLine).[j] transposition\n    \n    <span style=\"color: green\">\/\/ swap lines\n    <\/span><span style=\"color: blue\">let <\/span>temp = !lastLastLine\n    lastLastLine := !lastLine\n    lastLine := !actLine\n    actLine := temp\n            \n  (!lastLine).[b.Length]\n\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>This version of the algorithm needs only O(n+m) space but is not really &quot;functional&quot; style. I will show a more &quot;F#-stylish&quot; version in <a href=\"http:\/\/www.navision-blog.de\/2008\/11\/01\/damerau-levenshtein-distance-in-fsharp-part-iii\/\">part III<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Last time I showed a na&#239;ve implementation of the Damerau-Levenshtein-Distance in F# that needs O(m*n) space. This is really bad if we want to compute the edit distance of large sequences (e.g. DNA sequences). If we look at the algorithm we can easily see that only the last two lines of the (n*m)-matrix are used. [&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\/572"}],"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=572"}],"version-history":[{"count":3,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/572\/revisions"}],"predecessor-version":[{"id":578,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/572\/revisions\/578"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=572"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=572"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=572"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}