How do I compare strings for fuzzy or approximate matching in EK9?

← Common String Operations · Ref: Q179

EK9 has a built-in fuzzy-match operator for strings. The <~> operator returns a weighted, Levenshtein-style match COST as an Integer: lower means closer, 0 means identical. It is not the plain edit count.

FUZZY MATCH COST (<~>)

  cost <- str1 <~> str2

The weights: a change of case only costs 1; a substitution, an insertion or a deletion usually costs 2. When the two strings share too few characters to be a plausible match (including comparing with ""), the result is the Integer maximum, 2147483647, meaning 'no viable match'.

IDENTICAL STRINGS

Comparing "hello" with "hello" gives 0.

ONE SUBSTITUTION

Comparing "kitten" with "sitten" gives 2.

SEVERAL EDITS

Comparing "kitten" with "sitting" gives 6 (the classic edit count is 3).

PRACTICAL USE: TYPO DETECTION

Pick a threshold in COST units, not edits. A transposed pair ("funciton" for "function") costs 4:

  if (input <~> expected) <= 4
    stdout.println("Close enough")

PRACTICAL USE: CLOSEST MATCH

Compare the input with each candidate and keep the lowest cost: "colr" scores 2 against "color", 4 against "collar", and the Integer maximum against "column".

REGEX FOR PATTERN MATCHING

For pattern-based matching rather than distance:

  if myString matches /pattern/

See Q37 for string basics. See Q33 for regular expressions.

See Q37 for strings. See Q33 for regular expressions. See Q239 for the <~> fuzzy comparison operator used in ordering and matching.

Example

defines module qa.stringops.fuzzymatch

  defines program
    FuzzyMatchDemo()
      stdout <- Stdout()

      // === FUZZY MATCH COST (<~>) ===

      // Identical strings — cost 0
      greeting <- "hello"
      sameGreeting <- "hello"
      dist0 <- greeting <~> sameGreeting
      stdout.println(`hello <~> hello = ${dist0}`)

      // One substitution — cost 2
      original <- "kitten"
      dist1 <- original <~> "sitten"
      stdout.println(`kitten <~> sitten = ${dist1}`)

      // Several edits — cost 6 (the classic edit count would be 3)
      dist3 <- original <~> "sitting"
      stdout.println(`kitten <~> sitting = ${dist3}`)

      // Too few shared characters — Integer maximum (no viable match)
      planet <- "world"
      distEmpty <- planet <~> ""
      stdout.println(`world <~> empty = ${distEmpty}`)

      // === PRACTICAL: TYPO DETECTION ===

      expected <- "function"
      typo <- "funciton"
      typoDistance <- expected <~> typo
      stdout.println(`Typo distance: ${typoDistance}`)

      // A transposition costs 4, so the threshold is in cost units
      typoThreshold <- 4
      if typoDistance <= typoThreshold
        stdout.println("Close enough - likely a typo")

      // === PRACTICAL: FIND CLOSEST MATCH ===

      input <- "colr"
      target1 <- "color"
      target2 <- "collar"
      target3 <- "column"

      d1 <- input <~> target1
      d2 <- input <~> target2
      d3 <- input <~> target3
      stdout.println(`colr <~> color = ${d1}`)
      stdout.println(`colr <~> collar = ${d2}`)
      stdout.println(`colr <~> column = ${d3}`)

      // The lowest cost is the closest match
      if d1 < d2 and d1 < d3
        stdout.println(`Closest to colr: ${target1}`)

      // === REGEX FOR PATTERN MATCHING ===

      testPhrase <- "Hello World"
      if testPhrase matches /.*World$/
        stdout.println("Pattern match: ends with World")

Common mistakes

E50060 — String has no levenshtein() method. Use the <~> operator, which returns a weighted fuzzy-match cost. See ek9 -h E50060 for details.

Incorrect:

dist1 <- original.levenshtein("sitten")

Correct:

dist1 <- original <~> "sitten"

Coming from another language?

Java: no built-in Levenshtein, requires Apache Commons or custom implementation. Python: no built-in, requires python-Levenshtein or difflib.SequenceMatcher. Rust: no built-in, requires strsim crate. Go: no built-in, requires third-party packages. JavaScript: no built-in, requires libraries. Kotlin: no built-in. EK9: built-in <~> operator returns a weighted Levenshtein-style match cost as an Integer (case change 1, other edits 2, Integer max for no viable match), no libraries needed.

Keywords: levenshtein, similar, compare, typo, string, approximate, match, text, distance, regex, fuzzy