Алгоритмы

Edit Distance: Расстояние Левенштейна

Цели урока

Понимать три операции: insert, delete, replace
Выводить рекурсивную формулу
Реализовать DP решение O(mn)
Оптимизировать память до O(n)
Восстанавливать последовательность операций

Предварительные знания

LCS
Динамическое программирование

Каждый раз когда телефон исправляет 'teh' на 'the' - работает Edit Distance. Биоинформатики используют его для сравнения генов. Google использует для 'Did you mean?'. Это один из самых практичных алгоритмов.

Autocorrect и spell checking
DNA/protein sequence alignment
Fuzzy search в базах данных
Антиплагиат и детекция копий

История алгоритма

Владимир Левенштейн предложил метрику в 1965 году для исправления ошибок в телеграфных кодах. Независимо Needleman-Wunsch (1970) разработали алгоритм для биоинформатики. Wagner-Fischer (1974) описали DP-алгоритм.

Что такое Edit Distance?

**Edit Distance (расстояние Левенштейна)** - минимальное количество операций для превращения строки A в строку B.

**Вариации:**

**Levenshtein**: insert, delete, replace (все стоят 1)
**LCS distance**: только insert и delete (replace = delete + insert)
**Hamming**: только replace, строки одинаковой длины
**Damerau-Levenshtein**: + транспозиция соседних символов

**Применения:** автокоррекция, DNA alignment, plagiarism detection, fuzzy search.

Edit Distance между "cat" и "cut"?

Рекурсивная формула

**Сравниваем последние символы и выбираем лучшую операцию.**

A="ab", B="a". Какая операция оптимальна?

DP решение

**dp[i][j]** = Edit Distance между A[0..i-1] и B[0..j-1].

**Восстановление операций:**

Откуда берётся значение dp[i][j] при A[i-1] ≠ B[j-1]?

Оптимизация памяти

**dp[i][j] зависит только от dp[i-1][j-1], dp[i-1][j], dp[i][j-1].** Достаточно двух строк.

**Компромисс:** при одной строке теряем возможность восстановить операции. Для полного backtrace нужна вся таблица.

Почему нужна переменная prev_diag при оптимизации до одной строки?

Применения

**Edit Distance используется повсюду!**

**LeetCode задачи:**

#72 Edit Distance: классика
#583 Delete Operation for Two Strings: только delete
#712 Minimum ASCII Delete Sum: weighted delete
#1035 Uncrossed Lines: вариация LCS
#97 Interleaving String: сложная вариация

Почему Edit Distance полезен для spell checking?

Edit Distance

Три операции: insert, delete, replace (стоимость 1)
dp[i][j] = min(match, replace+1, delete+1, insert+1)
База: dp[i][0] = i, dp[0][j] = j
O(mn) время, оптимизация до O(n) памяти
Связь с LCS: edit = m + n - 2*LCS (без replace)

Связанные темы

Edit Distance связан с другими строковыми алгоритмами.

LCS — Edit Distance обобщает LCS
DP основы — Базовая парадигма
Поиск подстроки — Fuzzy matching

Связанные уроки

alg-28-lcs — Расстояние редактирования расширяет DP-таблицу LCS
alg-21-dp — Это классическая 2D-рекуррентность динамического программирования
alg-23-pattern-matching — Нечёткий поиск ранжирует совпадения по расстоянию редактирования
dm-22 — Выравнивание ДНК - взвешенное расстояние редактирования
nlp-01

Цели урока

Понимать три операции: insert, delete, replace

Выводить рекурсивную формулу

Реализовать DP решение O(mn)

Оптимизировать память до O(n)

Восстанавливать последовательность операций

Что такое Edit Distance?

**Edit Distance (расстояние Левенштейна)** - минимальное количество операций для превращения строки A в строку B.

**Вариации:**

**Levenshtein**: insert, delete, replace (все стоят 1)

**LCS distance**: только insert и delete (replace = delete + insert)

**Hamming**: только replace, строки одинаковой длины

**Damerau-Levenshtein**: + транспозиция соседних символов

**Применения:** автокоррекция, DNA alignment, plagiarism detection, fuzzy search.

Edit Distance между "cat" и "cut"?

Оптимизация памяти

**dp[i][j] зависит только от dp[i-1][j-1], dp[i-1][j], dp[i][j-1].** Достаточно двух строк.

Почему нужна переменная prev_diag при оптимизации до одной строки?

Применения

**Edit Distance используется повсюду!**

**LeetCode задачи:**

#72 Edit Distance: классика

#583 Delete Operation for Two Strings: только delete

#712 Minimum ASCII Delete Sum: weighted delete

#1035 Uncrossed Lines: вариация LCS

#97 Interleaving String: сложная вариация

Почему Edit Distance полезен для spell checking?

Связанные уроки

alg-28-lcs — Расстояние редактирования расширяет DP-таблицу LCS

alg-21-dp — Это классическая 2D-рекуррентность динамического программирования

alg-23-pattern-matching — Нечёткий поиск ранжирует совпадения по расстоянию редактирования

dm-22 — Выравнивание ДНК - взвешенное расстояние редактирования

nlp-01