Function: string-distance

string-distance is a function defined in fns.c.

Signature

(string-distance STRING1 STRING2 &optional BYTECOMPARE)

Documentation

Return Levenshtein distance between STRING1 and STRING2.

The distance is the number of deletions, insertions, and substitutions required to transform STRING1 into STRING2. If BYTECOMPARE is nil or omitted, compute distance in terms of characters. If BYTECOMPARE is non-nil, compute distance in terms of bytes. Letter-case is significant, but text properties are ignored.

View in manual

Probably introduced at or before Emacs version 27.1.

Aliases

org-babel-edit-distance (obsolete since 9.5) org-string-distance

Source Code

// Defined in /usr/src/emacs/src/fns.c
{
  CHECK_STRING (string1);
  CHECK_STRING (string2);

  bool use_byte_compare =
    !NILP (bytecompare)
    || (!STRING_MULTIBYTE (string1) && !STRING_MULTIBYTE (string2));
  ptrdiff_t len1 = use_byte_compare ? SBYTES (string1) : SCHARS (string1);
  ptrdiff_t len2 = use_byte_compare ? SBYTES (string2) : SCHARS (string2);
  ptrdiff_t x, y, lastdiag, olddiag;

  USE_SAFE_ALLOCA;
  ptrdiff_t *column = SAFE_ALLOCA ((len1 + 1) * sizeof (ptrdiff_t));
  for (y = 0; y <= len1; y++)
    column[y] = y;

  if (use_byte_compare)
    {
      char *s1 = SSDATA (string1);
      char *s2 = SSDATA (string2);

      for (x = 1; x <= len2; x++)
        {
          column[0] = x;
          for (y = 1, lastdiag = x - 1; y <= len1; y++)
            {
              olddiag = column[y];
              column[y] = min (min (column[y] + 1, column[y-1] + 1),
			       lastdiag + (s1[y-1] == s2[x-1] ? 0 : 1));
              lastdiag = olddiag;
            }
        }
    }
  else
    {
      int c1, c2;
      ptrdiff_t i1, i1_byte, i2 = 0, i2_byte = 0;
      for (x = 1; x <= len2; x++)
        {
          column[0] = x;
          c2 = fetch_string_char_advance (string2, &i2, &i2_byte);
          i1 = i1_byte = 0;
          for (y = 1, lastdiag = x - 1; y <= len1; y++)
            {
              olddiag = column[y];
              c1 = fetch_string_char_advance (string1, &i1, &i1_byte);
              column[y] = min (min (column[y] + 1, column[y-1] + 1),
			       lastdiag + (c1 == c2 ? 0 : 1));
              lastdiag = olddiag;
            }
        }
    }

  SAFE_FREE ();
  return make_fixnum (column[len1]);
}