Модифицированный Бойер-Мур
Я только что откопал какую-то старую реализацию Python Boyer-Moore Я лежал и изменил цикл сопоставления (где текст сравнивается с шаблоном). Вместо разрыва, как только первое несоответствие найдено между двумя строками, просто подсчитайте количество несоответствий, но запомните первое несоответствие :
current_dist = 0
while pattern_pos >= 0:
if pattern[pattern_pos] != text[text_pos]:
if first_mismatch == -1:
first_mismatch = pattern_pos
tp = text_pos
current_dist += 1
if current_dist == smallest_dist:
break
pattern_pos -= 1
text_pos -= 1
smallest_dist = min(current_dist, smallest_dist)
# if the distance is 0, we've had a match and can quit
if current_dist == 0:
return 0
else: # shift
pattern_pos = first_mismatch
text_pos = tp
...
Если строка не полностью совпадает в этой точке, вернитесь к точке первого несоответствия, восстановив значения. Это гарантирует, что наименьшее расстояние действительно найдено.
Вся реализация довольно длинная (~ 150LOC), но я могу опубликовать ее по запросу. Основная идея изложена выше, все остальное - стандартный Бойер-Мур.
Предварительная обработка текста
Еще один способ ускорить процесс - это предварительная обработка текста для получения индекса по позициям символов. Вы хотите начать сравнение только с позиций, где происходит хотя бы одно совпадение между двумя строками, в противном случае расстояние Хэмминга равно | S | тривиально.
import sys
from collections import defaultdict
import bisect
def char_positions(t):
pos = defaultdict(list)
for idx, c in enumerate(t):
pos[c].append(idx)
return dict(pos)
Этот метод просто создает словарь, который отображает каждый символ в тексте в отсортированный список его вхождений.
Цикл сравнения более или менее неизменен по сравнению с наивным O(mn) подходом, за исключением того факта, что мы не увеличиваем позицию, в которой сравнение начинается каждый раз на 1, но на основе позиций символов:
def min_hamming(text, pattern):
best = len(pattern)
pos = char_positions(text)
i = find_next_pos(pattern, pos, 0)
while i < len(text) - len(pattern):
dist = 0
for c in range(len(pattern)):
if text[i+c] != pattern[c]:
dist += 1
if dist == best:
break
c += 1
else:
if dist == 0:
return 0
best = min(dist, best)
i = find_next_pos(pattern, pos, i + 1)
return best
Фактическое улучшение в find_next_pos:
def find_next_pos(pattern, pos, i):
smallest = sys.maxint
for idx, c in enumerate(pattern):
if c in pos:
x = bisect.bisect_left(pos[c], i + idx)
if x < len(pos[c]):
smallest = min(smallest, pos[c][x] - idx)
return smallest
Для каждой новой позиции мы находим наименьший индекс, в котором символ из S встречается в L. Если такого индекса больше нет, алгоритм завершится.
find_next_pos, безусловно, сложно, и можно попытаться улучшить его, используя только первые несколько символов шаблона S, или использовать набор, чтобы убедиться, что символы из шаблона не проверяются дважды.
Обсуждение
Какой метод быстрее, во многом зависит от вашего набора данных. Чем разнообразнее ваш алфавит, тем больше будет скачков. Если у вас очень длинный L, второй метод с предварительной обработкой может быть быстрее. Для очень, очень коротких строк (как в вашем вопросе) наивный подход, безусловно, будет самым быстрым.
ДНК
Если у вас очень маленький алфавит, вы можете попытаться получить положение символов для биграмм (или больше), а не для униграмм.