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