2

我正在阅读有关在字符串中查找子字符串的后缀数组方法，请参见（http://www.codeodor.com/index.cfm/2007/12/24/The-Suffix-Array/1845），例如

sa = SuffixArray.new("abracadabra")
puts sa.find_substring("aca")

其中 SuffixArray 是后缀数组的一个实现，而 find_substring 是一种搜索子字符串开始位置的方法。

我的问题是如何在允许子字符串中有给定数量的不匹配的同时实现此搜索？例如，

max_mismatches = 2
search_string ="abrazadabra"
substring ="aca"

sa = SuffixArray.new("search_string")
puts sa.find_substring("substring",max_mismatches)

其中不匹配可被视为错误阈值。在这种情况下，它应该能够匹配“aza”并返回“aza”子字符串的起始位置。另请注意，“abr”有 2 个不匹配！所以应该先退货。理想情况下，该方法应该返回所有可能的事件。

有任何想法吗？或解决此类问题的其他方法？谢谢

4

2 回答 2

1 
# checks whether two strings are similar,
# allowing given number of characters of difference
def similar? a, b, mismatches = 1
  a.chars.zip(b.chars).count{|ca, cb| ca != cb} <= mismatches
end

# in haystack, find similar strings to needle
def find_similar haystack, needle, mismatches = 1
  haystack.chars.each_cons(needle.length).map(&:join).select{|s|
    similar?(s, needle, mismatches)
  }
end

find_similar 'abracadabra', 'aca'
# => ["aca", "ada"] 
find_similar 'abracadabra', 'aca', 2
# => ["abr", "bra", "aca", "ada", "abr", "bra"]

随意更改similar?方法以匹配您对相似的定义。

于 2011-03-16T13:36:52.917 回答
1

我们所说的不匹配也称为汉明距离，它只是对字符串之间有多少字符不匹配的计数（只允许替换 - 不允许插入或删除）。

因此，可以在 find_substring 函数中使用 Mladen 的计数代码来确定字符串是否在允许的不匹配数内。

然后，如果是，您可以将其返回（或者如果您想跟踪所有匹配项，则将其添加到匹配项列表中）。在那次检查之后，您进行测试以设置高或低，具体取决于它是大于还是小于比较。

这是我更改代码的方式：

def find_substring(the_substring, n_mismatches)
#uses typical binary search
high = @suffix_array.length - 1
low = 0
while(low <= high)
  mid = (high + low) / 2
  this_suffix = @suffix_array[mid][:suffix]
  compare_len = the_substring.length-1
  comparison = this_suffix[0..compare_len]

  if n_mismatches == 0
    within_n_mismatches = comparison == the_substring
  else
    within_n_mismatches = hamming_distance(the_substring, comparison) <= n_mismatches
  end

  return @suffix_array[mid][:position] if within_n_mismatches

  if comparison > the_substring
    high = mid - 1
  else
    low = mid + 1
  end
end
return nil
end

def hamming_distance(a, b)
# from Mladen Jablanović's answer at http://stackoverflow.com/questions/5322428/finding-a-substring-while-allowing-for-mismatches-with-ruby 
a.chars.zip(b.chars).count{|ca, cb| ca != cb}
end

它会增加一些处理时间 - 与子字符串的大小成线性关系，但我认为考虑到其余数据的大小，这可能不会那么多。我还没有真正考虑过这部分，但也许你想测试它与另一种方法：对你的输入字符串进行更改并多次搜索它。

例如，如果您正在使用 DNA，如果您的子字符串是“GAC”，您将搜索它，加上“AAC”、“CAC”和“TAC”（然后是第 2 位和第 3 位核苷酸的组合。可能性的数量应使其足够小以适合内存。

相反——将所有不匹配的可能性存储在后缀数组中——是不正确的。由于它可能已经很大，将它自身相乘几次会使其太大而无法很快适应内存。

我以前使用过这种方法——不是完全使用后缀数组，而是一般只存储不匹配。

除了上面的代码之外，我还对其进行了一些修改，添加了一个获取所有匹配项的函数。我将它发布到我在 github 的一个存储库中。

于 2011-03-16T20:02:49.177 回答