Computing the Levenshtein distance using dynamic programming

LevenshteinDistance.fsx

/// compute the minimum of 3 elements
let min3 a b c = if a < b then min a c else min b c 

/// compute the levenstein distance between two strings given the substitution/deletion/insertion cost
let levenstein sub del ins (s1:string) (s2:string) =
    // arrays to store the previous results
    let cost = Array.init (s1.Length+1) id 
    let mutable costPrev = 0 // contains the content of cost.[i1-1] during the previous iteration
    // main loop on all pairs of characters
    for i2 = 1 to s2.Length do 
        costPrev <- cost.[0]
        cost.[0] <- cost.[0]+del 
        for i1 = 1 to s1.Length do 
            let cDel = cost.[i1]+del
            let cIns = cost.[i1-1]+ins
            let cSub = if s1.[i1-1] = s2.[i2-1]
                        then costPrev
                        else costPrev+sub
            costPrev <- cost.[i1]         
            cost.[i1] <- min3 cDel cIns cSub 
    // final result
    cost.[s1.Length]

/// number of edition needed to transform s1 into s2
let edit s1 s2 = levenstein 1 1 1 s1 s2