如何修改 Damerau-Levenshtein 算法，使其还包括较大子字符串的开始索引和结束索引？

Question

这是我的代码：

#http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
# used for fuzzy matching of two strings
# for indexing, seq2 must be the parent string
  def dameraulevenshtein(seq1, seq2)
      oneago = nil
      min = 100000000000 #index
      max = 0 #index
      thisrow = (1..seq2.size).to_a + [0]
      seq1.size.times do |x|
          twoago, oneago, thisrow = oneago, thisrow, [0] * seq2.size + [x + 1]
          seq2.size.times do |y|
              delcost = oneago[y] + 1
              addcost = thisrow[y - 1] + 1
              subcost = oneago[y - 1] + ((seq1[x] != seq2[y]) ? 1 : 0)
              thisrow[y] = [delcost, addcost, subcost].min
              if (x > 0 and y > 0 and seq1[x] == seq2[y-1] and seq1[x-1] == seq2[y] and seq1[x] != seq2[y])
                  thisrow[y] = [thisrow[y], twoago[y-2] + 1].min
              end
          end
      end
      return thisrow[seq2.size - 1], min, max
  end

必须有某种方法来获取子字符串 seq1 和父字符串 seq2 的起始和结束索引，对吧？

即使在阅读了有关该算法的维基文章之后，我也不完全确定该算法是如何工作的。我的意思是，我理解最高级别的解释，因为它发现插入、删除和转置差异（第二个循环中的行）..但除此之外。我有点失落。

这是我希望能够用这个做的一个例子（^）：

substring = "hello there"
search_string = "uh,\n\thello\n\t there"

索引应该是：

  start: 5
  end:   18 (last char of string)

理想情况下，search_string 永远不会被修改。但是，我想我可以取出所有空白字符（因为只有.. 3？ \n \r 和 \t）存储每个空白字符的索引，获取子字符串的索引，然后重新 -添加空白字符，确保补偿子字符串的索引，因为我首先用最初存在的空白字符偏移它们。 -- 但如果这一切都可以用相同的方法完成，那就太棒了，因为算法已经是 O(n^2).. =(

在某些时候，我只想允许空格字符分割向上子字符串（s1）..但一次只做一件事

Answer 1

我认为这个算法不是你想要做的事情的正确选择。该算法只是根据将一个字符串转换为另一个字符串所需的修改次数来计算两个字符串之间的距离。如果为了简洁起见，我们将函数重命名为 dlmatch 并且仅返回距离，那么我们就得到了：

dlmatch("hello there", "uh, \n\thello\n\t there"
=> 7

这意味着您可以通过 7 个步骤将一个字符串转换为另一个字符串（实际上是从第二个字符串中删除七个字符）。问题是 7 个步骤是一个相当大的差异：

dlmatch("hello there", "panda here"
=> 6

这实际上意味着“hellothere”和“pandahere”比第一个示例更接近匹配。

如果您想要做的是“找到一个最匹配的子字符串”，我认为当您将第一个字符串提供给第二个字符串的一系列子字符串，然后选择时，您会陷入 O(n^3) 算法为您提供最接近匹配的子字符串。

或者，您最好尝试对搜索字符串进行预处理，然后与子字符串进行正则表达式匹配。例如，您可以去掉所有特殊字符，然后构建一个正则表达式来查找子字符串中不区分大小写且之间可以有任意数量空格的单词。