Levenshtein edit distance

StringEditDistance.tq

let distance s1 s2 =
  let indexable s =
    let a = Array.ofString s in
    Array.length a, Array.get a in
  let (m, u), (n, v) = indexable s1, indexable s2 in
  let d1 = Array.init n id in
  let d0 = Array.init n [_ → 0] in
  let () = for 1 1 (m-1) () [(), i →
    let () = Array.Unsafe.set d0 0 i in
    let ui = u i in
    let () = for 1 1 (n-1) () [(), j →
      let a = Array.get d1 j in
      let b = Array.get d0 (j-1) in
      let c = Array.get d1 (j-1) + if ui = v j then -1 else 0 in
      1 + min (min a b) c
      @ Array.Unsafe.set d0 j ] in
    Array.blit d0 0 d1 0 n ] in
  Array.get d0 (n-1)