Самый быстрый способ найти минимальное Расстояние Хемминга до какой-либо подстроки?

Question

Самый быстрый способ найти минимальное Расстояние Хемминга до какой-либо подстроки?

508 Соответствий - способность к screenreader для понимания разметки.
Ожидание рендеринга - таблицы не представляют в браузере, пока это не добирается до конца </table> элемент.

7

задан dsimcha 18 July 2009 в 01:59

3 ответа

Вы застряли в том, что касается большого-O .. На фундаментальном уровне вам нужно будет проверить, соответствует ли каждая буква в целевой строке каждой подходящей букве в подстроке .

К счастью, это легко распараллелить.

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

-1

ответ дан 6 December 2019 в 12:53

Модифицированный Бойер-Мур

Я только что откопал старую реализацию Python Бойера-Мура , которую я лежал, и модифицировал цикл сопоставления (где текст сравнивается с шаблоном). Вместо того, чтобы выходить из строя, как только обнаруживается первое несовпадение между двумя строками, просто подсчитайте количество несовпадений, но запомните первое несоответствие :

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, второй метод с предварительной обработкой может быть быстрее. Для очень, очень коротких строк (как в вашем вопросе) наивный подход, безусловно, будет самым быстрым.