4551
правка
Последовательное приближенное сравнение строк: различия между версиями
Перейти к навигации
Перейти к поиску
м
Последовательное приближенное сравнение строк (посмотреть исходный код)
Версия от 14:01, 29 апреля 2019
, 29 апреля 2019→Основные результаты
Irina (обсуждение | вклад) м (→См. также) |
Irina (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
Первое и наиболее универсальное решение этой задачи [13] строится на процессе вычисления взвешенного расстояния редактирования. Пусть <math>A = a_1 a_2 ... a_m</math> и <math>B = b_1 b_2 ... b_n</math> – две строки, а <math>C[0 ... m, 0 ... n]</math> – матрица, такая, что <math>C[i, j] = d(a_1 ... a_i, b_1 ... b_j)</math>. Тогда имеет место <math>C[0, 0] = 0</math> и | Первое и наиболее универсальное решение этой задачи [13] строится на процессе вычисления взвешенного расстояния редактирования. Пусть <math>A = a_1 a_2 ... a_m</math> и <math>B = b_1 b_2 ... b_n</math> – две строки, а <math>C[0 ... m, 0 ... n]</math> – матрица, такая, что <math>C[i, j] = d(a_1 ... a_i, b_1 ... b_j)</math>. Тогда имеет место <math>C[0, 0] = 0</math> и | ||
<math>C[i, j] = min (C[i - 1, j] + w(a_i \to \epsilon | <math>C[i, j] = min (C[i - 1, j] + w(a_i \to \epsilon), C[i, j - 1] + w(\epsilon \to b_j), C[i - 1, j - 1] + w(a_i \to b_j))</math>, | ||
предполагая, что <math>C[i, -1] = C[-1, j] = \infty</math>. Вычисление матрицы требует | предполагая, что <math>C[i, -1] = C[-1, j] = \infty</math>. Вычисление матрицы требует O(mn) времени; d(A, B) = C[m, n]. Для решения задачи приближенного сравнения строк примем A = P и B = T и положим C[0, j] = 0 для всех j, так что вышеприведенная формула будет использоваться только для i > 0. | ||