Поиск подстроки с учетом несоответствий с Ruby - PullRequest
Новая
       22

Поиск подстроки с учетом несоответствий с Ruby

2 голосов
/ 16 марта 2011

Я читал о подходе с массивом суффиксов для поиска подстрок в строках, см. (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 несоответствия! Поэтому он должен быть возвращен первым. В идеалеподход должен возвращать все возможные случаи.

Есть идеи? Или есть другие подходы для решения такой проблемы? Спасибо

Ответы [ 2 ]

1 голос
/ 16 марта 2011

То, что мы называем несоответствиями, иначе известно как Расстояние Хэмминга , которое является просто подсчетом того, сколько символов не совпадает между строками (допускается только подстановка, а не вставка или удаление).

Следовательно, код Младена для подсчета, который можно использовать в функции find_substring, чтобы определить, находится ли строка в пределах допустимого числа несовпадений.

Затем, если это так, вы можете вернуть его (или добавить его в список совпадений, если хотите отслеживать их все).После этой проверки вы делаете тест, чтобы установить высокий или низкий уровень в зависимости от того, больше или меньше, чем сравнение.

Вот как я изменил код: 

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 /5068004/poisk-podstroki-s-uchetom-nesootvetstvii-s-ruby 
a.chars.zip(b.chars).count{|ca, cb| ca != cb}
end

Это добавит некоторое время обработки - линейное по отношению к размеру подстроки, но я думаю, что это может быть не таксильно учитывая размер остальных данных.Я на самом деле не продумал эту часть так сильно, как мог бы, но, возможно, вы хотите проверить ее по сравнению с другим подходом: внесение изменений во входную строку и поиск по ней несколько раз.

Например, если выработают с ДНК, если ваша подстрока была «GAC», вы бы искали это, плюс «AAC» и «CAC» и «TAC» (а затем комбинации для нуклеотидов во 2-й и 3-й позициях. Количество возможностей должно сохранятьсяон достаточно мал, чтобы поместиться в памяти.

Противоположность - сохранение всех возможностей несоответствия в массиве суффиксов - не будет правдой. Поскольку он, вероятно, уже большой, его умножение на несколько раз приведет к его получению.слишком большой, чтобы поместиться в память довольно быстро.

Я уже использовал этот подход - не совсем с массивом суффиксов, а просто для хранения несоответствий в целом.

В дополнение к приведенному выше кодуЯ также немного изменил это, чтобы добавить функцию для получения всех совпадений. Я разместил это в одном из моих репозиториев.es at github .

1 голос
/ 16 марта 2011 
# 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? метод в соответствии с вашим определением аналога.

...