如何修改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，withing父串，SEQ2的结束索引，对不对？

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

这里是我婉能够与该做的事的例子（^）：

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个步骤是一个相当大的区别：

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

这实际上“这里的大熊猫”暗示“你好”，比第一个例子更接近的比赛。

如果你想要做的是“找到一个大部分匹配的子字符串”，我认为当你将第一个字符串提供给第二个字符串的一系列子字符串时，你会被卡住O（n^3）算法，然后选择提供最接近匹配的子字符串。

或者，您可能会更好地尝试对搜索字符串执行预处理，然后执行与子字符串匹配的regexp。例如，可以去除所有特殊字符，然后构建一个正则表达式，查找不区分大小写的子字符串中的单词，并在它们之间可以有任意数量的空白。