Пример: если у меня есть строка «asdf» и набор строк («qwer», «aswr», «asdv»). Расстояние Хэмминга между набором и строкой будет равно 1, поскольку "asdv" и "asdf" имеют расстояние Хэмминга, равное единице.
Легко использовать грубую силу с чем-то вроде этого
def hamming_distance(string, set):
min = len(string)
for element in set:
element_distance = sum(ch1 != ch2 for ch1, ch2 in zip(string, element))
if min > element_distance:
min = element_distance
if min == 0:
break
return min
Я думаю, что это O (n * k), где n = len (строка) и k = len (набор). Однако максимальный размер набора масштабируется с n ^ 2, что означает, что мы, по сути, имеем дело с O (n ^ 3). Наборы довольно статичны, поэтому, если предварительная обработка поможет, это определенно вариант.
Наконец, я должен упомянуть, что приложение здесь предназначено для определения того, какие наборы наиболее близки к рассматриваемой строке, но я уменьшил проблему, потому что длина строки является гораздо более ограничивающим фактором, чем количество наборов. Если есть другой способ приблизиться к этому, глядя на пространство в целом, а не на отдельные подмножества, я был бы внимателен. Когда я впервые применил этот подход, казалось, что пространственная сложность станет совершенно нелепой.
