В информационный поиск Introduction to Information Retrieval

Редакционные операции – последовательность действий, необходимых для получения из первой строки второй кратчайшим способом.

Как правило, действия имеют следующие обозначения: D (delete) – удаление символа; I (insert) – добавление символа; R (replace) – замена символа; M (match) – совпадение символа.

В качестве примера редакционной операции рассмотрим преобразование слова «ПРИМЕРЫ» в слово «ПРЕДМЕТ», которое выполняется за четыре действия (добавление, удаление и две замены).

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

ПРИМЕРЫ →ПРЕДМЕТ
Редакционные операции	M	M	I	R	M	M	R	D
Исходный термин	П	Р		И	М	Е	Р	Ы
Результат	П	Р	Е	Д	М	Е	Т

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

Решим пример методом динамического программирования (алгоритм Вагнера).

Построим таблицу.

В ячейках таблицы указаны расстояния редактирования.

Обозначим эти расстояния через d (i,j).

В таблице первой строке соответствует пустое слово.

Любое слово может получиться из пустого, добавлением нужного количества нужных символов, любые другие операции будут только увеличивать оценку. Поэтому значения РР равны значениям индекса i.

d(i,0) = i

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

Аналогично и для первого столбца таблицы.

d(0,j) = j

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

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

Для прочих ячеек

если S1[i] = S2[j], то:

d(i,j) = d(i-1,j-1),

иначе:

d(i,j) = min( d(i-1,j), d(i,j-1), d(i-1,j-1) ) + 1

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

	j	0	1	2	3	4	5	6	7
i			п	р	и	м	е	р	ы
0		0	1	2	3	4	5	6	7
1	п	1	0
2	р	2	1
3	е	3	2
4	д	4	3
5	м	5	4
6	е	6	5
7	т	7	6

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

	j	0	1	2	3	4	5	6	7
i			п	р	и	м	е	р	ы
0		0	1	2	3	4	5	6	7
1	п	1	0	1
2	р	2	1	0
3	е	3	2	1
4	д	4	3	2
5	м	5	4	3
6	е	6	5	4
7	т	7	6	5

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

	j	0	1	2	3	4	5	6	7
i			п	р	и	м	е	р	ы
0		0	1	2	3	4	5	6	7
1	п	1	0	1	2	3	4	5	6
2	р	2	1	0	1	2	3	3	4
3	е	3	2	1	1	2	2	3	4
4	д	4	3	2	2	2	3	3	4
5	м	5	4	3	3	2	3	4	4
6	е	6	5	4	4	3	2	3	4
7	т	7	6	5	5	4	3	3	4