Skip to content

Instantly share code, notes, and snippets.

@games

games/gist:2b0b86d1ee332bed5c47

Last active August 29, 2015 14:23
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save games/2b0b86d1ee332bed5c47 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save games/2b0b86d1ee332bed5c47 to your computer and use it in GitHub Desktop.
Download ZIP
levenshtein distance
Raw
gistfile1.fs
module test
open NUnit.Framework
open FsUnit
open System
let min (a: int) (b: int) (c: int) =
Math.Min(a, Math.Min(b, c))
let rec lev' (s: string) (sl: int) (t: string) (tl: int) =
match sl, tl with
| 0, _ -> tl
| _, 0 -> sl
| _ ->
let cost = if s.Chars (sl - 1) = t.Chars (tl - 1) then 0 else 1
min (lev s (sl - 1) t tl + 1)
(lev s sl t (tl - 1) + 1)
(lev s (sl - 1) t (tl - 1) + cost)
let distance' (s: string) (t: string) =
lev' s s.Length t t.Length
[<Test>]
let ``levenshtein distance`` () =
distance' "kitten" "sitting" |> should equal 3
Raw
gistfile2.fs
module test
open NUnit.Framework
open FsUnit
open System
let min (a: int) (b: int) (c: int) =
Math.Min(a, Math.Min(b, c))
let rec lev (s: string) (sl: int) (t: string) (tl: int) =
if sl = 0 then tl
else if tl = 0 then sl
else
let cost = if s.Chars (sl - 1) = t.Chars (tl - 1) then 0 else 1
min (lev s (sl - 1) t tl + 1)
(lev s sl t (tl - 1) + 1)
(lev s (sl - 1) t (tl - 1) + cost)
let distance (s: string) (t: string) =
lev s s.Length t t.Length
[<Test>]
let ``levenshtein distance`` () =
distance "kitten" "sitting" |> should equal 3
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment