不使用宏，能否在Excel中进行Levenshtein距离计算？

Question

让我解释一下。

我需要为一家公司进行一些模糊匹配，目前我使用的是莱文斯坦距离计算器，然后计算两个术语之间的相似度百分比。如果这些术语超过80％相似，则Fuzzymatch返回“TRUE”。

我的问题是，我正在实习，很快就要离开了。将继续进行此操作的人不知道如何使用带宏的Excel，并希望我尽力实现我的工作。

因此，我的问题是：无论函数效率有多低，是否有任何方法可以在Excel中创建一个标准函数来计算我以前所做的事情，而不必诉诸于宏？

谢谢。

- user1504088

Answer 1

如果你是通过搜索“levenshtein distance google sheets”之类的关键词找到这篇文章的，那么我为你准备了下面的内容，其中包括了milot-midia在https://gist.github.com/andrei-m/982927上发布的代码注释（该代码使用MIT许可证）。

以下是操作步骤：

1. 在表格中选择 “工具” 菜单，进入“脚本编辑器”。

2. 给项目命名

- 函数名称（而不是项目名称）将允许您使用该函数。

3. 粘贴以下代码。

function Levenshtein(a, b) {
  if(a.length == 0) return b.length; 
  if(b.length == 0) return a.length;

  // swap to save some memory O(min(a,b)) instead of O(a)
  if(a.length > b.length) {
    var tmp = a;
    a = b;
    b = tmp;
  }

  var row = [];
  // init the row
  for(var i = 0; i <= a.length; i++){
    row[i] = i;
  }

  // fill in the rest
  for(var i = 1; i <= b.length; i++){
    var prev = i;
    for(var j = 1; j <= a.length; j++){
      var val;
      if(b.charAt(i-1) == a.charAt(j-1)){
        val = row[j-1]; // match
      } else {
        val = Math.min(row[j-1] + 1, // substitution
                       prev + 1,     // insertion
                       row[j] + 1);  // deletion
      }
      row[j - 1] = prev;
      prev = val;
    }
    row[a.length] = prev;
  }

  return row[a.length];
}

您应该能够从电子表格中运行它，使用

=Levenshtein(cell_1,cell_2)

- duality

Answer 2

虽然对于任何合理大小的字符串来说，不能使用单个公式完成它，但您可以仅通过使用工作表中的公式来计算字符串之间的Levenshtein距离。

以下是一个示例，可处理长度为15个字符的字符串，它可以轻松扩展以处理更多字符：

https://docs.google.com/spreadsheet/ccc?key=0AkZy12yffb5YdFNybkNJaE5hTG9VYkNpdW5ZOWowSFE&usp=sharing

这对于除了临时比较之外的任何事情都不实用，但它确实做了一个不错的工作来展示算法的工作原理。

- richardtallent

Answer 3

其实，我想我刚刚找到了一个解决方法。我是在代码的错误部分添加它...

添加这行代码

  } else if(b.charAt(i-1)==a.charAt(j) && b.charAt(i)==a.charAt(j-1)){
    val = row[j-1]-0.33;  //transposition

现在它已经被读取

  if(b.charAt(i-1) == a.charAt(j-1)){
    val = row[j-1]; // match
  } else if(b.charAt(i-1)==a.charAt(j) && b.charAt(i)==a.charAt(j-1)){
    val = row[j-1]-0.33;  //transposition
  } else {
    val = Math.min(row[j-1] + 1, // substitution
                   prev + 1,     // insertion
                   row[j] + 1);  // deletion 
  } 

看起来问题已经解决了。现在，“biulding”的准确率为92%，而“bilding”的准确率为88%。（原始公式中，“biulding”仅为75%……尽管更接近正确的拼写“building”）

- Ewan Hume

Answer 4

看了一下之前计算Levenshtein距离的答案，我认为不可能将其创建为公式。

在这里查看代码。

- SeanC

---

我已经有代码了，谢谢。实际上我有多个，因为我编写了一个，找到了你链接的一个，还在MrExcel论坛上找到了一个，并从FuzzyVlookup中提取了一个。我只是希望它可以用作公式...如果不行，那么我就得另想办法了。 - user1504088