我正在尝试在JS中创建damerau-levenshtein距离函数。

我在WIkipedia上找到了关于该算法的描述，但是他们没有实现它。它说：

要设计适当的算法来计算不受限制的Damerau–Levenshtein距离，请注意，始终存在最佳的编辑操作序列，在此之后，一旦转置的字母就永远不会被修改。因此，我们只需要考虑两种以上修改子串的对称方式：（1）转置字母并在它们之间插入任意数量的字符，或者（2）删除一系列字符并转置在删除后变为相邻的字母。这个想法的直接实现给出了三次复杂度的算法：O
\ left（M \ cdot N \ cdot \ max（M，N）\
right），其中M和N是字符串长度。利用Lowrance和Wagner的思想，[7]在最坏的情况下，可以将这种幼稚算法改进为O \ left（M \
cdot N \ right）。有趣的是，可以修改bitap算法以处理换位。有关此类修改的示例，请参见[1]的信息检索部分。

https://zh.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance

[1]部分指向http://acl.ldc.upenn.edu/P/P00/P00-1037.pdf，这对我来说更加复杂。

如果我正确理解了这一点，那么创建一个实现就不那么容易了。

这是我当前使用的levenshtein实现：

levenshtein=function (s1, s2) {
  //       discuss at: http://phpjs.org/functions/levenshtein/
  //      original by: Carlos R. L. Rodrigues (http://www.jsfromhell.com)
  //      bugfixed by: Onno Marsman
  //       revised by: Andrea Giammarchi (http://webreflection.blogspot.com)
  // reimplemented by: Brett Zamir (http://brett-zamir.me)
  // reimplemented by: Alexander M Beedie
  //        example 1: levenshtein('Kevin van Zonneveld', 'Kevin van Sommeveld');
  //        returns 1: 3

  if (s1 == s2) {
    return 0;
  }

  var s1_len = s1.length;
  var s2_len = s2.length;
  if (s1_len === 0) {
    return s2_len;
  }
  if (s2_len === 0) {
    return s1_len;
  }

  // BEGIN STATIC
  var split = false;
  try {
    split = !('0')[0];
  } catch (e) {
    // Earlier IE may not support access by string index
    split = true;
  }
  // END STATIC
  if (split) {
    s1 = s1.split('');
    s2 = s2.split('');
  }

  var v0 = new Array(s1_len + 1);
  var v1 = new Array(s1_len + 1);

  var s1_idx = 0,
    s2_idx = 0,
    cost = 0;
  for (s1_idx = 0; s1_idx < s1_len + 1; s1_idx++) {
    v0[s1_idx] = s1_idx;
  }
  var char_s1 = '',
    char_s2 = '';
  for (s2_idx = 1; s2_idx <= s2_len; s2_idx++) {
    v1[0] = s2_idx;
    char_s2 = s2[s2_idx - 1];

    for (s1_idx = 0; s1_idx < s1_len; s1_idx++) {
      char_s1 = s1[s1_idx];
      cost = (char_s1 == char_s2) ? 0 : 1;
      var m_min = v0[s1_idx + 1] + 1;
      var b = v1[s1_idx] + 1;
      var c = v0[s1_idx] + cost;
      if (b < m_min) {
        m_min = b;
      }
      if (c < m_min) {
        m_min = c;
      }
      v1[s1_idx + 1] = m_min;
    }
    var v_tmp = v0;
    v0 = v1;
    v1 = v_tmp;
  }
  return v0[s1_len];
}

构建这种算法的想法是什么，如果您认为它太复杂了，那么我该怎么做才能使“ l”（L小写）和“ I”（i大写）之间没有区别。