(** Distance de Levenshtein *)

let distance a b =
    let m = string_length a
    and n = string_length b in
    let cache = hashtbl__new 128 in
    (* fonction auxiliaire *)
    let rec aux i j =
        if i = 0 then j
        else if j = 0 then i
        else
            try hashtbl__find cache (i,j)
            with Not_found ->
                let d1 = aux (i-1) j + 1
                and d2 = aux i (j-1) + 1
                and d3 = aux (i-1)(j-1)
                    + (if a.[i-1] = b.[j-1] then 0 else 1)
                in
                let d = min d1 (min d2 d3) in
                hashtbl__add cache (i,j) d;
                d
    in
    aux m n ;;

(* version montante *)
let distance_montante a b =
    let m = string_length a
    and n = string_length b in
    let D = make_matrix (m+1) (n+1) 0 in
    (* cas limites *)
    for i = 0 to m do
        D.(i).(0) <- i;
    done;
    for j = 0 to n do
        D.(0).(j) <- j;
    done;
    (* cas recursifs *)
    for i = 1 to m do
        for j = 1 to n do
            let d1 = 1 + D.(i-1).(j)
            and d2 = 1 + D.(i).(j-1)
            and d3 = D.(i-1).(j-1)
                + (if a.[i-1] = b.[j-1] then 0 else 1)
            in
            D.(i).(j) <- min d1 (min d2 d3);
        done
    done;
    D.(m).(n) ;;