def _DamerauLevenshtein(a, b):
  """Damerau-Levenshtein edit distance from a to b."""
  memo = {}

  def Distance(x, y):
    """Recursively defined string distance with memoization."""
    if (x, y) in memo:
      return memo[x, y]
    if not x:
      d = len(y)
    elif not y:
      d = len(x)
    else:
      d = min(
          Distance(x[1:], y) + 1,  # correct an insertion error
          Distance(x, y[1:]) + 1,  # correct a deletion error
          Distance(x[1:], y[1:]) + (x[0] != y[0]))  # correct a wrong character
      if len(x) >= 2 and len(y) >= 2 and x[0] == y[1] and x[1] == y[0]:
        # Correct a transposition.
        t = Distance(x[2:], y[2:]) + 1
        if d > t:
          d = t

    memo[x, y] = d
    return d
  return Distance(a, b)
Damerau-Levenshtein edit distance from a to b.