Найдите подстроки "N Gram", которые находятся на минимальном расстоянии от целевой строки длиной N символов - PullRequest
Новая
       13

Найдите подстроки "N Gram", которые находятся на минимальном расстоянии от целевой строки длиной N символов

4 голосов
/ 17 ноября 2010

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

Рассмотрим целевую строку, например, длиной 4 символа: 

targetString -> '1111'

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

nonEmptySubStrings -> ['110101']

Подстроки выше, длиной 4 символа: 

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

Я хочу написать / использовать «магическую функцию», которая выберет строку, ближайшую к targetString: 

someMagicFunction -> ['1101']

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

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

someMagicFunction -> ['1011']

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

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

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

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

Ответы [ 3 ]

3 голосов
/ 17 ноября 2010

Я считаю, что вам нужно Редактировать расстояние . Корректор орфографии Питера Норвига является примером реализации в python. Вот реализация расстояния Левенштейна . Смотри также этот вопрос .

EDIT: Это довольно часто встречается в биоинформатике. Смотрите, например FASTA и BLAST . Биоинформатика имеет много разновидностей этого алгоритма. См. Выравнивание последовательности для обзора методов.

2 голосов
/ 17 ноября 2010

Некоторое время назад, в рамках обсуждения соответствия генов, я написал этот пример преобразования , реализующий класс преобразования CloseMatch.Обычно выражения с переносом возвращают структуру, содержащую совпадающие строки и любые именованные результаты, но 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 (который я включу в следующий выпуск pyparsing).

1 голос
/ 17 ноября 2010

Основываясь на комментарии ОП к вопросу, это то, что нужно 

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

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

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

...