Аудит алгоритмов: как реализация Boyer-Moore с 190K звёзд на GitHub оказалась brute-force

Значимый прорыв формирует отрасль ИИ: StudyQA 1 час назад Аудит алгоритмов: как реализация Boyer-Moore с 190K звёзд на GitHub оказалась brute-force Средний 3 мин 3K Python * Open source * Алгоритмы * Программирование * Кейс Recovery Mode В 2015 году группа исследователей (Flouri et al. ) решила проверить реализации классического алгоритма Готоха (1982) для выравнивания биологических последовательностей. Из 10 проверенных реализаций только 2 давали правильный результат.

8 из 31 учебных материалов содержали математическую ошибку. Я решил проверить, насколько это типично для других классических алгоритмов. Начал с Boyer-Moore (1977), одного из самых известных алгоритмов поиска подстроки.

Технические детали

МетодологияНаписал тестовый фреймворк, который проверяет любую реализацию поиска подстроки против brute-force эталона:35 статических тестов: пустые строки, перекрывающиеся совпадения, периодические строки, pattern == textProperty-based случайные тесты (8000+ на реализацию): полнота (все совпадения найдены), корректность (нет ложных срабатываний), порядок, количествоРазные распределения: маленький/большой алфавит, бинарные строки, длинные паттерныНаходка 1: TheAlgorithms/Python (190K+ звёзд)Самый популярный образовательный репозиторий алгоритмов на GitHub. Файл strings/boyer_moore_search. Метод bad_character_heuristic() пытается использовать правило плохого символа для пропуска позиций.

Но сдвиг записывается в переменную цикла for:for i in range(self. patLen + 1): mismatch_index = self. mismatch_in_text(i) if mismatch_index == -1: positions.

append(i) else: match_index = self. match_in_pattern(self. text) i = (mismatch_index - match_index) # мёртвый код В Python переприсвоение переменной for-цикла не влияет на следующую итерацию.

Отраслевые последствия

for i in range(N) всегда берёт следующее значение из range(), игнорируя любые изменения i внутри тела цикла. Я добавил счётчик итераций:Текст: 32 символа, Паттерн: 4 символа Итераций выполнено: 29 (= brute-force) Рабочий Boyer-Moore: ~8 итераций Алгоритм выдаёт правильные результаты, поэтому все тесты проходят. Но работает за O(nm) вместо O(n/m).

Каждый, кто скопировал этот код, думает что у него Boyer-Moore, а на самом деле имеет наивный поиск с лишними вычислениями. Исправление тривиальное: заменить for на while. Находка 2: бесконечный цикл при pattern == textТипичная реализация полного Boyer-Moore (с обоими правилами: bad character + good suffix) зависает на тривиальном входе search("abc", "abc .

Причина: при полном совпадении индекс i декрементируется на m позиций (с m-1 до -1). Затем good_suffix сдвигает i ровно на m назад. i возвращается на исходную позицию.

Событие, по словам экспертов, усилит конкуренцию в сфере ИИ.