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

不一致と呼ばれるものは、ハミング距離とも呼ばれます。これは、文字列間で一致しない文字数のカウントです（挿入または削除ではなく、置換のみを許可します）。

したがって、文字列が許可された不一致の数の範囲内にあるかどうかを判断するために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

これにより、処理時間がいくらか追加されます。サブストリングのサイズに関しては線形ですが、残りのデータのサイズを考えると、それほど多くはないかもしれません。その部分についてはあまり考えていませんが、入力文字列に変更を加えて複数回検索するという別のアプローチと比較してテストしたいと思うかもしれません。

たとえば、サブストリングが「GAC」の場合にDNAを操作している場合は、それに加えて「AAC」と「CAC」と「TAC」（および2番目と3番目の位置のヌクレオチドの組み合わせ）を検索します。可能性の数は、メモリに収まるようにそれを十分に小さく保つ必要があります。

反対の-すべての不一致の可能性を接尾辞配列に格納する-は真実ではありません。おそらくすでに大きいので、それ自体を数回乗算すると、大きすぎてメモリにすぐに収まりません。

私は以前にそのアプローチを使用しました-接尾辞配列ではなく、一般的に不一致を保存するだけです。

上記のコードに加えて、すべての一致を取得するための関数を追加するために少し変更しました。それをgithubのリポジトリの1つに投稿しました。

于 2011-03-16T20:02:49.177 に答える
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 に答える