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
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#.