levenshteinAtMost

lib.strings.levenshteinAtMost

Docs pulled from | This Revision | 29 minutes ago

Nixpkgs manual

Returns whether the levenshtein distance between two strings a and b is at most some value k.

Complexity is O(min(n,m)) for k <= 2 and O(n*m) otherwise

Inputs

k: Distance threshold
a: String a
b: String b

Type

levenshteinAtMost :: Int -> String -> String -> Bool

Examples

`lib.strings.levenshteinAtMost` usage example

levenshteinAtMost 0 "foo" "foo"
=> true
levenshteinAtMost 1 "foo" "boa"
=> false
levenshteinAtMost 2 "foo" "boa"
=> true
levenshteinAtMost 2 "This is a sentence" "this is a sentense."
=> false
levenshteinAtMost 3 "This is a sentence" "this is a sentense."
=> true

Noogle detected

Implementation

The following is the current implementation of this function.

k:
    if k <= 0 then
      a: b: a == b
    else
      let
        f =
          a: b:
          let
            alen = stringLength a;
            blen = stringLength b;
            prelen = commonPrefixLength a b;
            suflen = commonSuffixLength a b;
            presuflen = prelen + suflen;
            ainfix = substring prelen (alen - presuflen) a;
            binfix = substring prelen (blen - presuflen) b;
          in
          # Make a be the bigger string
          if alen < blen then
            f b a
          # If a has over k more characters than b, even with k deletes on a, b can't be reached
          else if alen - blen > k then
            false
          else if k == 1 then
            infixDifferAtMost1 ainfix binfix
          else if k == 2 then
            infixDifferAtMost2 ainfix binfix
          else
            levenshtein ainfix binfix <= k;
      in
      f