Wednesday, November 28, 2012

F# on Algorithms - Wagner–Fischer algorithm

You never know when these algorithms can be used. This is the Levenshtein distance between two strings. This sample code also demonstrates how to use Array2D in F#.

 let levenshteinDistance (str0:string) (str1:string) =   
   let s0 = str0.ToCharArray()  
   let s1 = str1.ToCharArray()  
   let result = Array2D.initBased -1 -1 (s0.Length+1) (s1.Length+1)  
           (fun i j ->   
             match i,j with  
             | (-1, -1) -> 0  
             | (_, -1) -> i+1  
             | (-1, _) -> j+1  
             | _ -> 0)  
   let min3 a b c = min a b |> (min c)  
   result   
   |> Array2D.iteri (fun i j v->   
             match i,j with  
             | (-1, -1)   
             | (_, -1)   
             | (-1, _) -> ()  
             | _ when s0.[i] = s1.[j] ->   
               result.[i,j] <- result.[i-1,j-1]  
             | _ ->   
               result.[i,j] <- 1 + min3 result.[i-1,j] result.[i,j-1] result.[i-1,j-1])  
   result  

1 comment:

jackfoxy said...

Hey Tao!

Checkout the BKTree implementation in FSharpx https://github.com/fsharp/fsharpx/blob/master/src/FSharpx.Core/DataStructures/BKTree.fs the Haskell implementation http://hackage.haskell.org/packages/archive/bktrees/0.2.1/doc/html/src/Data-Set-BKTree.html explicitly documents Levenshtein distance. Sadly our F# BKTree is in need of better documentation for those of us in too much of a hurry to do a literature search.