The OpenD Programming Language

levenshteinDistance

Returns the Levenshtein distance between s and t. The Levenshtein distance computes the minimal amount of edit operations necessary to transform s into t. Performs O(s.length * t.length) evaluations of equals and occupies O(min(s.length, t.length)) storage.

  1. size_t levenshteinDistance(Range1 s, Range2 t)
    size_t
    levenshteinDistance
    (
    alias equals =
    (
    a
    ,
    b
    )
    => a == b
    Range1
    Range2
    )
    (
    Range1 s
    ,
    Range2 t
    )
    if (
    isForwardRange!(Range1) &&
    )
  2. size_t levenshteinDistance(Range1 s, Range2 t)

Parameters

equals

The binary predicate to compare the elements of the two ranges.

s Range1

The original range.

t Range2

The transformation target

Return Value

Type: size_t

The minimal number of edits to transform s into t.

Does not allocate GC memory.

Examples

import std.algorithm.iteration : filter;
import std.uni : toUpper;

assert(levenshteinDistance("cat", "rat") == 1);
assert(levenshteinDistance("parks", "spark") == 2);
assert(levenshteinDistance("abcde", "abcde") == 0);
assert(levenshteinDistance("abcde", "abCde") == 1);
assert(levenshteinDistance("kitten", "sitting") == 3);
assert(levenshteinDistance!((a, b) => toUpper(a) == toUpper(b))
    ("parks", "SPARK") == 2);
assert(levenshteinDistance("parks".filter!"true", "spark".filter!"true") == 2);
assert(levenshteinDistance("ID", "I♥D") == 1);

Meta