Левенштейн — это тот самый алгоритм «расстояния между строками». Да, классика. Вставка, удаление, замена — и вот ты считаешь, насколько две строки похожи. На игрушечных примерах всё выглядит красиво: «hellow» и «hello» → расстояние 1.

Но как только задача становится боевой — например, нужно найти похожие строки в массиве из 10 миллионов записей — вся эта «красота» превращается в ад. Брутфорсить каждую строку? Отличная идея, если у тебя свободных серверов как у Amazon.

На коленке: «и так сойдёт»

Вот базовая реализация на Python (да, все видели её миллион раз, но пусть будет для полноты картины):

def levenshtein_distance(s1, s2):
    if len(s1) < len(s2):
        return levenshtein_distance(s2, s1)

    if len(s2) == 0:
        return len(s1)

    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row
    return previous_row[-1]

Да, оно работает. И даже можно накинуть обёртку, чтобы поискать все строки с расстоянием до трёх:

def find_similar_strings(new_string, array, max_distance=3):
    return [s for s in array if levenshtein_distance(new_string, s) <= max_distance]

В массиве на 100 элементов норм. На 100 тысячах уже будет тормозить. На 10 миллионах — всё, приехали, сервер в гробу.

Оптимизация (а точнее — выживание)

Вот где начинается мясо. Если у тебя реально большие массивы, то:

  • Трай (trie). Да, это дерево префиксов. Оно позволяет отсекать кучу вариантов сразу, а не бегать в лоб. Если слова длинные, прирост заметный.
  • BK-tree. Тоже классика для поиска по расстояниям. Строишь дерево, где каждая вершина хранит строку, а рёбра помечены расстоянием. Запросы на «найди всё в радиусе 3» идут куда быстрее, чем полный перебор.
  • Фильтры. Никто не запрещал сначала отсекать по хэшам/длинам, и только потом дёргать Левенштейна. Потому что сравнивать «hello» и «supercalifragilisticexpialidocious» смысла мало.
  • Фонетика. Иногда тебе вообще не нужен чистый Левенштейн, а надо «похоже звучит». Тут уже подключаются Soundex/Metaphone и прочая старая школа.

Где это реально бьёт по жопе

  • Поиск похожих имён в базе пользователей. Петров/Петрофф/Петрив. Хочешь «умный поиск»? Готовь сервера.
  • Антиплагиат и дубликаты. «Python Tutorial» vs «Python Tutorials». Угадаешь, что 99% систем всё равно гоняют Левенштейна или его клонов?
  • Чистка данных. Когда тебе слили CSV на 10 миллионов строк, а там «Иванов», «Ивановв», «Ивановвв» и прочие радости.

Итог

Левенштейн — штука полезная, но тупо гонять его по массиву в миллионы строк — это не инженерия, это мазохизм. Для маленьких массивов норм. Для серьёзных данных — строй индексированные структуры, иначе ты просто выстрелишь себе в ногу и будешь сидеть с медленным сервисом.

Это как с велосипедом: кататься во дворе можно, но если собрался в Сибирь — не жалуйся, что задница стёрлась.