silk.text.edit_distance.

When to use#

Use these functions to find the closest spelling to a misspelled name, such as a suggestion for an unknown command-line option, to rank fuzzy search results, or to find near-duplicate keys. damerauLevenshtein is the usual choice for typing errors, because a swap of two neighbouring characters, such as nmae for name, counts as one edit.

Details#

Each function counts four kinds of edit: insert one character, delete one character, replace one character, and swap two neighbouring characters.

• damerauLevenshtein is the true Damerau-Levenshtein distance. An edit can change text that an earlier edit made, so ca to abc is two edits: swap to ac, then insert b.

• optimalStringAlignment does not edit a substring more than once, so ca to abc is three edits. It is a little faster, and it is the variant that many libraries call "Damerau-Levenshtein".

The string forms count Unicode scalar values. The Bytes forms count bytes, which is faster and correct for ASCII text, identifiers, and binary data.

The distances are symmetric, and they are zero only for equal inputs. The text that the two inputs share at the start and at the end is skipped before the main work. Both functions use memory proportional to the shorter length. damerauLevenshtein takes time proportional to the product of the two lengths. optimalStringAlignment processes 64 characters of the shorter input at a time with bit operations, so it is much faster on long inputs. Inputs of at most 64 characters each, after the shared start and end, do not allocate.

Examples#

Suggest the closest known name#

import silk.text.edit_distance
import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }

effect fn suggest() -> i32 ! OutOfMemoryError ? &mut Allocator {
  let known = ["build", "check", "format", "test"]
  let written = "fromat"
  let mut best: usize = 0
  let mut bestDistance = run edit_distance.damerauLevenshtein(written, known[0])
  let mut at: usize = 1
  while at < known.length {
    let distance = run edit_distance.damerauLevenshtein(written, known[at])
    if distance < bestDistance {
      best = at
      bestDistance = distance
    }
    at = at + 1
  }
  if best != 2 || bestDistance != 1 {
    return 1
  }
  return 0
}

effect fn exhausted(error: OutOfMemoryError) -> i32 {
  drop error
  return 2
}

pub fn main() -> i32 {
  let mut allocator = Allocator.systemAllocatorProvider()
  return run Effect.catchAll(suggest(), exhausted) |> Effect.provideMut<Allocator>(&mut allocator)
}

Import as edit_distance with import silk.text.edit_distance as edit_distance.

Public declarations: 4.

damerauLevenshtein#

pub effect fn damerauLevenshtein(left: string, right: string) -> usize
  ! OutOfMemoryError
  ? &mut Allocator

Returns the Damerau-Levenshtein distance between left and right, counted in Unicode scalar values.

When to use#

Use this function to measure how far apart two texts are when people type them, for example to suggest the closest known name for a misspelled one.

Details#

The result is the smallest number of edits that turn left into right. An edit inserts, deletes, or replaces one scalar value, or swaps two neighbouring scalar values. Later edits can change text that earlier edits made, so "ca" to "abc" is 2. The time is proportional to the product of the lengths and the memory to the shorter length.

Errors#

• OutOfMemoryError if the Allocator cannot supply the scratch rows. ASCII inputs of at most 64 bytes each, after the shared start and end, do not allocate.

Gotchas#

A scalar value is not always one visible character: "é" written as e followed by a combining accent is two scalar values. Normalize both texts first if that matters.

Examples#

Count a swap as one edit#

import silk.text.edit_distance
import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }

effect fn check() -> i32 ! OutOfMemoryError ? &mut Allocator {
  let swapped = run edit_distance.damerauLevenshtein("nmae", "name")
  let replaced = run edit_distance.damerauLevenshtein("café", "cafe")
  let rebuilt = run edit_distance.damerauLevenshtein("ca", "abc")
  if swapped != 1 || replaced != 1 || rebuilt != 2 {
    return 1
  }
  return 0
}

effect fn exhausted(error: OutOfMemoryError) -> i32 {
  drop error
  return 2
}

pub fn main() -> i32 {
  let mut allocator = Allocator.systemAllocatorProvider()
  return run Effect.catchAll(check(), exhausted) |> Effect.provideMut<Allocator>(&mut allocator)
}

damerauLevenshteinBytes#

pub effect fn damerauLevenshteinBytes(left: &[u8], right: &[u8]) -> usize
  ! OutOfMemoryError
  ? &mut Allocator

Returns the Damerau-Levenshtein distance between left and right, counted in bytes.

When to use#

Use this function for ASCII text, identifiers, and binary data. For text that can contain other characters, use damerauLevenshtein, which counts Unicode scalar values.

Details#

The result is the smallest number of edits that turn left into right. An edit inserts, deletes, or replaces one byte, or swaps two neighbouring bytes. Later edits can change bytes that earlier edits made, so ca to abc is 2. The time is proportional to the product of the lengths and the memory to the shorter length.

Errors#

• OutOfMemoryError if the Allocator cannot supply the scratch rows. Inputs of at most 64 bytes each, after the shared start and end, do not allocate.

Examples#

Measure two byte strings#

import silk.text.edit_distance
import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }

effect fn check() -> i32 ! OutOfMemoryError ? &mut Allocator {
  let swapped = run edit_distance.damerauLevenshteinBytes(b"--relaese", b"--release")
  let plural = run edit_distance.damerauLevenshteinBytes(b"dependency", b"dependencies")
  let empty = run edit_distance.damerauLevenshteinBytes(b"", b"abc")
  if swapped != 1 || plural != 3 || empty != 3 {
    return 1
  }
  return 0
}

effect fn exhausted(error: OutOfMemoryError) -> i32 {
  drop error
  return 2
}

pub fn main() -> i32 {
  let mut allocator = Allocator.systemAllocatorProvider()
  return run Effect.catchAll(check(), exhausted) |> Effect.provideMut<Allocator>(&mut allocator)
}

optimalStringAlignment#

pub effect fn optimalStringAlignment(left: string, right: string) -> usize
  ! OutOfMemoryError
  ? &mut Allocator

Returns the optimal string alignment distance between left and right, counted in Unicode scalar values.

When to use#

Use this function when the variant of Damerau-Levenshtein distance that many other libraries compute is needed, or when speed matters more than the exact distance. For the true Damerau-Levenshtein distance, use damerauLevenshtein.

Details#

The result is the smallest number of edits that turn left into right, when no substring is edited more than once. An edit inserts, deletes, or replaces one scalar value, or swaps two neighbouring scalar values. Because no substring is edited twice, "ca" to "abc" is 3. The result is never less than damerauLevenshtein's. The shorter text is processed 64 scalar values at a time with bit operations, so the time is proportional to the longer length times the shorter length divided by 64.

Errors#

• OutOfMemoryError if the Allocator cannot supply the scratch rows. ASCII inputs of at most 64 bytes each, after the shared start and end, do not allocate.

Gotchas#

The distance does not obey the triangle inequality: "ca" to "ac" is 1 and "ac" to "abc" is 1, but "ca" to "abc" is 3.

Examples#

Compare the two variants#

import silk.text.edit_distance
import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }

effect fn check() -> i32 ! OutOfMemoryError ? &mut Allocator {
  let aligned = run edit_distance.optimalStringAlignment("ca", "abc")
  let exact = run edit_distance.damerauLevenshtein("ca", "abc")
  let swapped = run edit_distance.optimalStringAlignment("naïve", "nalve")
  if aligned != 3 || exact != 2 || swapped != 1 {
    return 1
  }
  return 0
}

effect fn exhausted(error: OutOfMemoryError) -> i32 {
  drop error
  return 2
}

pub fn main() -> i32 {
  let mut allocator = Allocator.systemAllocatorProvider()
  return run Effect.catchAll(check(), exhausted) |> Effect.provideMut<Allocator>(&mut allocator)
}

optimalStringAlignmentBytes#

pub effect fn optimalStringAlignmentBytes(left: &[u8], right: &[u8]) -> usize
  ! OutOfMemoryError
  ? &mut Allocator

Returns the optimal string alignment distance between left and right, counted in bytes.

When to use#

Use this function for ASCII text, identifiers, and binary data when the variant of Damerau-Levenshtein distance that many other libraries compute is needed. For the true distance, use damerauLevenshteinBytes.

Details#

The result is the smallest number of edits that turn left into right, when no substring is edited more than once. An edit inserts, deletes, or replaces one byte, or swaps two neighbouring bytes. Because no substring is edited twice, ca to abc is 3. The shorter input is processed 64 bytes at a time with bit operations, so the time is proportional to the longer length times the shorter length divided by 64.

Errors#

• OutOfMemoryError if the Allocator cannot supply the scratch rows. Inputs of at most 64 bytes each, after the shared start and end, do not allocate.

Examples#

Measure two byte strings#

import silk.text.edit_distance
import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }

effect fn check() -> i32 ! OutOfMemoryError ? &mut Allocator {
  let swapped = run edit_distance.optimalStringAlignmentBytes(b"pakcage", b"package")
  let rebuilt = run edit_distance.optimalStringAlignmentBytes(b"ca", b"abc")
  if swapped != 1 || rebuilt != 3 {
    return 1
  }
  return 0
}

effect fn exhausted(error: OutOfMemoryError) -> i32 {
  drop error
  return 2
}

pub fn main() -> i32 {
  let mut allocator = Allocator.systemAllocatorProvider()
  return run Effect.catchAll(check(), exhausted) |> Effect.provideMut<Allocator>(&mut allocator)
}

Category: Text.

Profiles: aarch64-apple-darwin, aarch64-unknown-linux-gnu, aarch64-unknown-linux-gnu-no-libc, x86_64-unknown-linux-gnu, x86_64-unknown-linux-gnu-no-libc, wasm32-unknown-unknown, wasm32-wasip1, wasm32-wasip2, x86_64-pc-windows-msvc, wasm64-unknown-unknown.