Нахождение ближайшей подстроки по расстоянию Хэмминга - PullRequest
Новая
       46

Нахождение ближайшей подстроки по расстоянию Хэмминга

0 голосов
/ 21 марта 2019

Мне нужно найти подстроку s, ближайшую к строке по расстоянию Хэмминга, и заставить его вернуть кортеж индекса ближайшей подстроки, расстояние Хемминга ближайшей подстроки в p иСамая близкая подстрока.

Пока у меня есть этот код: 

def ham_dist(s1, s2):
    if len(s1) != len(s2):
        raise ValueError("Undefined")
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))

Но я не совсем понимаю, как бы это выяснить:

Ваша функция должна вернуть (1,2,'bcef')поскольку ближайшая подстрока 'bcef', она начинается с индекса 1 в s, а расстояние Хэмминга до p равно 2.

В вашей функции вам следует использовать функцию ham_dist из части(а).Если имеется несколько подстрок с одинаковым минимальным расстоянием до p, верните любую из них.

Ответы [ 2 ]

4 голосов
/ 21 марта 2019

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

source_string = "pGpEusuCSWEaPOJmamlFAnIBgAJGtcJaMPFTLfUfkQKXeymydQsdWCTyEFjFgbSmknAmKYFHopWceEyCSumTyAFwhrLqQXbWnXSn"
search_string = "tyraM"

def ham_dist(s1, s2):
    if len(s1) != len(s2):
        raise ValueError("Undefined")
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))

def search_min_dist(source,search):
    l = len(search)
    index = 0
    min_dist = l
    min_substring = source[:l]    
    for i in range(len(source)-l+1):
        d = ham_dist(search, source[i:i+l])
        if d<min_dist:
            min_dist = d
            index = i
            min_substring = source[i:i+l]  
    return (index,min_dist,min_substring)

print search_min_dist(source_string,search_string)

выход 

(28, 2, 'tcJaM')
1 голос
/ 21 марта 2019

Ответ от Hugo Delahaye - хороший, и он лучше ответит на ваш вопрос напрямую, но другой способ думать о таких проблемах состоит в том, чтобы позволить функции min() Python найти ответ.При этом типе программирования, ориентированного на данные (см. Правило 5), ваша цель - организовать данные, чтобы сделать это возможным. 

s = 'abcefgh'
p = 'cdef'
N = len(p)

substrings = [
    s[i : i + N]
    for i in range(0, len(s) - N + 1)
]

result = min(
    (ham_dist(p, sub), sub, i)
    for i, sub in enumerate(substrings)
)

print(substrings)    # ['abce', 'bcef', 'cefg', 'efgh']
print(result)        # (2, 'bcef', 1)
...