レーベンシュタイン距離

gistfile1.fs

let levenshteinDistance (str1 : string) (str2 : string) =
   let d = Array.init (str1.Length+1) (fun _ -> Array.init (str2.Length+1) (fun _ -> 0))
   let mutable cost = 0 
   for i1 = 0 to str1.Length do
       d.[i1].[0] <- i1
   for i2 = 0 to str2.Length do
       d.[0].[i2] <- i2
   for i1 = 1 to str1.Length do
       for i2 = 1 to str2.Length do
           if str1.[i1-1] = str2.[i2-1] then
             cost <- 0
           else
             cost <- 1
           d.[i1].[i2] <- Seq.min [d.[i1 - 1].[i2] + 1; d.[i1].[i2 - 1] + 1; d.[i1 - 1].[i2 - 1] + cost]
   d.[str1.Length].[str2.Length]