15.2. Расстояние Левенштейна

Расстояние Левенштейна между $a_{1}, \ldots, a_{n}$ и $b_{1}, \ldots, b_{m}$ можно вычислить алгоритмом, практически полностью совпадающим с алгоритмом поиска НОП: пусть $d[i, j]$ — расстояние Левенштейна между последовательностями $a_{1}, \ldots, a_{i}$ и $b_{1}, \ldots, b_{j}$. Тогда $d[i, 0]=i$, $d[0, j]=j$, а при $i, j>0$ верно

где $\chi(x, y)=0$ при $x=y$, $\chi(x, y)=1$ иначе. Первый случай соответствует удалению $a_{i}$, второй — вставке в последовательность $a$ символа $b_{j}$ после $a_{i}$, третий — замене $a_{i}$ на $b_{j}$ (или бездействию в случае $a_{i}=b_{j}$).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def edit_distance(a: list, b: list) -> list[list[int]]:
    """Возвращает таблицу d[i][j] — расстояние Левенштейна a[:i] и b[:j]."""
    n, m = len(a), len(b)
    d = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        d[i][0] = i
    for j in range(m + 1):
        d[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1)
            cost = 0 if a[i-1] == b[j-1] else 1
            d[i][j] = min(d[i][j], d[i-1][j-1] + cost)
    return d

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <vector>
#include <algorithm>
using namespace std;

// Возвращает таблицу d[i][j] — расстояние Левенштейна a[0..i) и b[0..j)
vector<vector<int>> editDistance(vector<int>& a, vector<int>& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> d(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i <= n; i++) d[i][0] = i;
    for (int j = 0; j <= m; j++) d[0][j] = j;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1);
            int cost = (a[i-1] == b[j-1]) ? 0 : 1;
            d[i][j] = min(d[i][j], d[i-1][j-1] + cost);
        }
    return d;
}

Восстановление ответа делается полностью аналогично восстановлению ответа в алгоритме поиска НОП. Если требуется найти лишь расстояние, но не последовательность действий, то снова достаточно $O(\min(m, n))$ дополнительной памяти.

Значения $d$ для последовательностей $2,1,2,3,1,2$ и $2,3,2,2,1$:

Последовательность операций, соответствующая расстоянию Левенштейна: