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

В 2015 году группа исследователей (Flouri et al. ^[1]) решила проверить реализации классического алгоритма Готоха ^[2] (1982) для выравнивания биологических последовательностей. Из 10 проверенных реализаций только 2 давали правильный результат. 8 из 31 учебных материалов содержали математическую ошибку.

Я решил проверить, насколько это типично для других классических алгоритмов. Начал с Boyer-Moore ^[3] (1977), одного из самых известных алгоритмов поиска подстроки.

Методология

Написал тестовый фреймворк, который проверяет любую реализацию поиска подстроки против brute-force эталона:

• 35 статических тестов: пустые строки, перекрывающиеся совпадения, периодические строки, pattern == text

• Property-based случайные тесты (8000+ на реализацию): полнота (все совпадения найдены), корректность (нет ложных срабатываний), порядок, количество

• Разные распределения: маленький/большой алфавит, бинарные строки, длинные паттерны

Находка 1: TheAlgorithms/Python (190K+ звёзд)

Самый популярный образовательный репозиторий алгоритмов на GitHub. Файл strings/boyer_moore_search.py.

Метод bad_character_heuristic() пытается использовать правило плохого символа для пропуска позиций. Но сдвиг записывается в переменную цикла for:

for i in range(self.textLen - 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[mismatch_index])
        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[0] сдвигает i ровно на m назад. i возвращается на исходную позицию. Цикл бесконечен.

Находка 3: оригинальная статья 1977 года содержала ошибку

Boyer и Moore опубликовали алгоритм в 1977 году, но не включили корректный алгоритм вычисления таблицы good suffix (delta2). Первый правильный алгоритм дал Войцех Ритер (Rytter ^[4]) в 1980 году, через 3 года.

Эта ошибка продолжает распространяться. В 2019 году Microsoft исправляла баги в std::boyer_moore_searcher (C++17 STL), связанные именно с отсутствием Rytter correction.

Масштаб проблемы

Это не уникальная ситуация. Классические алгоритмы копируются между учебниками, лекциями и GitHub-репозиториями без верификации. Ошибки в оригинальных статьях распространяются десятилетиями.

Я составил список из 35 алгоритмов в 6 категориях (биоинформатика, численные методы, графы, сортировки, строки, вычислительная геометрия) для систематического аудита. Следующая цель: BLAST (1990), самый используемый инструмент биоинформатики. Формального аудита его корректности не существует, несмотря на 35 лет использования.

Код

Тестовый фреймворк и все результаты: https://github.com/devladpopov/algorithm-autopsy ^[5]

Issue в TheAlgorithms/Python: https://github.com/TheAlgorithms/Python/issues/14844 ^[6]

Если знаете о подобных багах в классических алгоритмах, буду рад обсудить.