path: root/lib/std/editdistance.nim

#
#
#            Nim's Runtime Library
#        (c) Copyright 2018 Nim contributors
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

## This module implements an algorithm to compute the
## `edit distance`:idx: between two Unicode strings.

import unicode

proc editDistance*(a, b: string): int {.noSideEffect.} =
  ## Returns the unicode-rune edit distance between ``a`` and ``b``.
  ##
  ## This uses the `Levenshtein`:idx: distance algorithm with only a linear
  ## memory overhead.
  if len(a) > len(b):
    # make ``b`` the longer string
    return editDistance(b, a)
  # strip common prefix
  var
    i_start = 0 ## The character starting index of the first rune in both strings ``a`` and ``b``
    i_next_a = 0
    i_next_b = 0
    rune_a, rune_b: Rune
    len_runes_a = 0 ## The number of relevant runes in string ``a``.
    len_runes_b = 0 ## The number of relevant runes in string ``b``.
  block commonPrefix:
    # ``a`` is the shorter string
    while i_start < len(a):
      i_next_a = i_start
      a.fastRuneAt(i_next_a, rune_a, doInc = true)
      i_next_b = i_start
      b.fastRuneAt(i_next_b, rune_b, doInc = true)
      if rune_a != rune_b:
        inc(len_runes_a)
        inc(len_runes_b)
        break
      i_start = i_next_a
  var
    # we know that we are either at the start of the strings
    # or that the current value of rune_a is not equal to rune_b
    # => start search for common suffix after the current rune (``i_next_*``)
    i_end_a = i_next_a ## The exclusive upper index bound of string ``a``.
    i_end_b = i_next_b ## The exclusive upper index bound of string ``b``.
    i_current_a = i_next_a
    i_current_b = i_next_b
  block commonSuffix:
    var
      add_runes_a = 0
      add_runes_b = 0
    while i_current_a < len(a) and i_current_b < len(b):
      i_next_a = i_current_a
      a.fastRuneAt(i_next_a, rune_a)
      i_next_b = i_current_b
      b.fastRuneAt(i_next_b, rune_b)
      inc(add_runes_a)
      inc(add_runes_b)
      if rune_a != rune_b:
        i_end_a = i_next_a
        i_end_b = i_next_b
        inc(len_runes_a, add_runes_a)
        inc(len_runes_b, add_runes_b)
        add_runes_a = 0
        add_runes_b = 0
      i_current_a = i_next_a
      i_current_b = i_next_b
    if i_current_a >= len(a): # ``a`` exhausted
      if i_current_b < len(b): # ``b`` not exhausted
        i_end_a = i_current_a
        i_end_b = i_current_b
        inc(len_runes_a, add_runes_a)
        inc(len_runes_b, add_runes_b)
        while true:
          b.fastRuneAt(i_end_b, rune_b)
          inc(len_runes_b)
          if i_end_b >= len(b): break
    elif i_current_b >= len(b): # ``b`` exhausted and ``a`` not exhausted
      i_end_a = i_current_a
      i_end_b = i_current_b
      inc(len_runes_a, add_runes_a)
      inc(len_runes_b, add_runes_b)
      while true:
        a.fastRuneAt(i_end_a, rune_a)
        inc(len_runes_a)
        if i_end_a >= len(a): break
  block specialCases:
    # trivial cases:
    if len_runes_a == 0: return len_runes_b
    if len_runes_b == 0: return len_runes_a
    # another special case:
    if len_runes_a == 1:
      a.fastRuneAt(i_start, rune_a, doInc = false)
      var i_current_b = i_start
      while i_current_b < i_end_b:
        b.fastRuneAt(i_current_b, rune_b, doInc = true)
        if rune_a == rune_b: return len_runes_b - 1
      return len_runes_b
  # common case:
  var
    len1 = len_runes_a + 1
    len2 = len_runes_b + 1
    row: seq[int]
  let half = len_runes_a div 2
  newSeq(row, len2)
  var e = i_start + len2 - 1 # end marker
  # initialize first row:
  for i in 1 .. (len2 - half - 1): row[i] = i
  row[0] = len1 - half - 1
  i_current_a = i_start
  var
    char2p_i = -1
    char2p_prev: int
  for i in 1 .. (len1 - 1):
    i_next_a = i_current_a
    a.fastRuneAt(i_next_a, rune_a)
    var
      char2p: int
      D, x: int
      p: int
    if i >= (len1 - half):
      # skip the upper triangle:
      let offset = i + half - len1
      if char2p_i == i:
        b.fastRuneAt(char2p_prev, rune_b)
        char2p = char2p_prev
        char2p_i = i + 1
      else:
        char2p = i_start
        for j in 0 ..< offset:
          rune_b = b.runeAt(char2p)
          inc(char2p, rune_b.size)
        char2p_i = i + 1
        char2p_prev = char2p
      p = offset
      rune_b = b.runeAt(char2p)
      var c3 = row[p] + (if rune_a != rune_b: 1 else: 0)
      inc(char2p, rune_b.size)
      inc(p)
      x = row[p] + 1
      D = x
      if x > c3: x = c3
      row[p] = x
      inc(p)
    else:
      p = 1
      char2p = i_start
      D = i
      x = i
    if i <= (half + 1):
      # skip the lower triangle:
      e = len2 + i - half - 2
    # main:
    while p <= e:
      dec(D)
      rune_b = b.runeAt(char2p)
      var c3 = D + (if rune_a != rune_b: 1 else: 0)
      inc(char2p, rune_b.size)
      inc(x)
      if x > c3: x = c3
      D = row[p] + 1
      if x > D: x = D
      row[p] = x
      inc(p)
    # lower triangle sentinel:
    if i <= half:
      dec(D)
      rune_b = b.runeAt(char2p)
      var c3 = D + (if rune_a != rune_b: 1 else: 0)
      inc(x)
      if x > c3: x = c3
      row[p] = x
    i_current_a = i_next_a
  result = row[e]

proc editDistanceAscii*(a, b: string): int {.noSideEffect.} =
  ## Returns the edit distance between `a` and `b`.
  ##
  ## This uses the `Levenshtein`:idx: distance algorithm with only a linear
  ## memory overhead.
  var len1 = a.len
  var len2 = b.len
  if len1 > len2:
    # make `b` the longer string
    return editDistanceAscii(b, a)

  # strip common prefix:
  var s = 0
  while s < len1 and a[s] == b[s]:
    inc(s)
    dec(len1)
    dec(len2)
  # strip common suffix:
  while len1 > 0 and len2 > 0 and a[s+len1-1] == b[s+len2-1]:
    dec(len1)
    dec(len2)
  # trivial cases:
  if len1 == 0: return len2
  if len2 == 0: return len1

  # another special case:
  if len1 == 1:
    for j in s..s+len2-1:
      if a[s] == b[j]: return len2 - 1
    return len2

  inc(len1)
  inc(len2)
  var half = len1 shr 1
  # initalize first row:
  #var row = cast[ptr array[0..high(int) div 8, int]](alloc(len2*sizeof(int)))
  var row: seq[int]
  newSeq(row, len2)
  var e = s + len2 - 1 # end marker
  for i in 1..len2 - half - 1: row[i] = i
  row[0] = len1 - half - 1
  for i in 1 .. len1 - 1:
    var char1 = a[i + s - 1]
    var char2p: int
    var D, x: int
    var p: int
    if i >= len1 - half:
      # skip the upper triangle:
      var offset = i - len1 + half
      char2p = offset
      p = offset
      var c3 = row[p] + ord(char1 != b[s + char2p])
      inc(p)
      inc(char2p)
      x = row[p] + 1
      D = x
      if x > c3: x = c3
      row[p] = x
      inc(p)
    else:
      p = 1
      char2p = 0
      D = i
      x = i
    if i <= half + 1:
      # skip the lower triangle:
      e = len2 + i - half - 2
    # main:
    while p <= e:
      dec(D)
      var c3 = D + ord(char1 != b[char2p + s])
      inc(char2p)
      inc(x)
      if x > c3: x = c3
      D = row[p] + 1
      if x > D: x = D
      row[p] = x
      inc(p)
    # lower triangle sentinel:
    if i <= half:
      dec(D)
      var c3 = D + ord(char1 != b[char2p + s])
      inc(x)
      if x > c3: x = c3
      row[p] = x
  result = row[e]


when isMainModule:
  doAssert editDistance("", "") == 0
  doAssert editDistance("kitten", "sitting") == 3 # from Wikipedia
  doAssert editDistance("flaw", "lawn") == 2 # from Wikipedia

  doAssert editDistance("привет", "превет") == 1
  doAssert editDistance("Åge", "Age") == 1
  # editDistance, one string is longer in bytes, but shorter in rune length
  # first string: 4 bytes, second: 6 bytes, but only 3 runes
  doAssert editDistance("aaaa", "×××") == 4

  block veryLongStringEditDistanceTest:
    const cap = 256
    var
      s1 = newStringOfCap(cap)
      s2 = newStringOfCap(cap)
    while len(s1) < cap:
      s1.add 'a'
    while len(s2) < cap:
      s2.add 'b'
    doAssert editDistance(s1, s2) == cap

  block combiningCodePointsEditDistanceTest:
    const s = "A\xCC\x8Age"
    doAssert editDistance(s, "Age") == 1

  doAssert editDistanceAscii("", "") == 0
  doAssert editDistanceAscii("kitten", "sitting") == 3 # from Wikipedia
  doAssert editDistanceAscii("flaw", "lawn") == 2 # from Wikipedia