Найдите подстроки «N грамм», которые находятся на самом маленьком расстоянии от целевой строки. Длина символа N

Question

.

. Я ищу алгоритм, желательно в Python, который поможет мне найти подстроки длиной N символов из существующих строк, наиболее близких к Целевая строка N символа длинная.

Рассмотрим целевую строку, то есть, скажем, длиной 4 символа, чтобы быть:

targetString -> '1111' 

Предположим, что это строка у меня имеется со мной (я сгенерирует подстроки это для «лучшего выравнивания» соответствия):

nonEmptySubStrings -> ['110101'] 

подстроки из перечисленных выше, которые являются 4-х символов длиной:

nGramsSubStrings -> ['0101', '1010', '1101'] 

Я хочу писать/использовать "Magic Function", который будет выбрать строку ближе всего к targetString:

someMagicFunction -> ['1101'] 

еще несколько примеров:

nonEmptySubStrings -> ['101011'] 
nGramsSubStrings -> ['0101', '1010', '1011'] 

someMagicFunction -> ['1011'] 

nonEmptySubStrings -> ['10101'] 
nGramsSubStrings -> ['0101', '1010'] 

someMagicFunction -> ['0101', '1010'] 

Является ли это "Magic Функция" хорошо известная проблема подстроки?

Я действительно хочу найти мин. количество изменений в nonEmptySubStrings, чтобы в качестве подстроки была targetString.

Answer 1

Основание на комментарий OP на вопрос, это то, что желательно

import functools 

def edit_distance(str1, str2): 
    #implement it here 

f = functools.operator(edit_distance, target_string) 
return min(f(s) for s in slices(string_)) # use slices from below 

Это возвращает минимальное расстояние редактирования любой подстроки в целевой строке. Он не укажет, какая строка или какой ее индекс. Его можно было бы легко изменить, чтобы сделать , так что.

---

Наивный способ, который может быть лучшим способом, является

import functools 

def diff(str1, str2): 
    # However you test the distance gets defined here. e.g. Hamming distance, 
    # Levenshtein distance, etc. 


def slices(string_, L): 
    for i in xrange(len(string_) - L + 1)): 
     yield string_[i:i+L] 

best_match = min(slices(string_), key=functools.partial(diff, target_string)) 

Это обыкновение возвращать индекс, при котором происходит подстрока хотя. Конечно, вы не указали, что вам это нужно в вашем вопросе;)

Если вы хотите поправиться, это будет зависеть от того, как вы измеряете расстояние и в основном сворачиваетесь, чтобы избежать проверки некоторых подстрок указав, что вам нужно будет изменить хотя бы х символов, чтобы получить лучшее совпадение, чем у вас уже есть. В этот момент вы можете просто изменить x chars, прыгнув вперед х символов.

Answer 2

Я считаю, что вам нужно Edit Distance. Peter Norvig's spelling corrector - пример реализации в python. Вот implementation of Levenshtein Distance. См. Также this question.

EDIT: Это довольно частое явление в биоинформатике. См. FASTA и BLAST. Биоинформатика имеет много вариантов этого алгоритма. См. Sequence Alignment для исследования методов.

Answer 3

Как часть обсуждения некоторое время назад по сопоставлению генов, я написал this pyparsing example, реализуя класс пиперации CloseMatch.Обычно выражения pyparsing возвращают структуру, содержащую согласованные строки и любые именованные результаты, но CloseMatch возвращает 2-кортеж, содержащий строку соответствия и список мест несоответствия в согласованной строке. Вот как CloseMatch будет использоваться:

searchseq = CloseMatch("TTAAATCTAGAAGAT", 3) 
for g in genedata: 
    print "%s (%d)" % (g.id, g.genelen) 
    print "-"*24 
    for t,startLoc,endLoc in searchseq.scanString(g.gene): 
     matched, mismatches = t[0] 
     print "MATCH:", searchseq.sequence 
     print "FOUND:", matched 
     if mismatches: 
      print "  ", ''.join(' ' if i not in mismatches else '*' 
          for i,c in enumerate(searchseq.sequence)) 
     else: 
      print "<exact match>" 
     print "at location", startLoc 

Вот пример вывода частичного совпадения:

organism=Toxoplasma_gondii_RH (258) 
------------------------ 
MATCH: TTAAATCTAGAAGAT 
FOUND: TTAAATTTAGGAGCT 
      * * * 
at location 195 

Обратите внимание, что этот класс не находит перекрывающихся совпадений. Это может быть достигнуто, но с немного иным подходом с scanString (который я буду включать в следующий выпуск пирамиды).