4551
правка
Последовательное приближенное сравнение строк: различия между версиями
Перейти к навигации
Перейти к поиску
Последовательное приближенное сравнение строк (посмотреть исходный код)
Версия от 15:32, 27 марта 2019
, 27 марта 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
== Основные результаты == | == Основные результаты == | ||
Первое и наиболее универсальное решение этой задачи [13] строится на процессе вычисления взвешенного расстояния редактирования. Пусть A = | Первое и наиболее универсальное решение этой задачи [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>. Тогда имеет место C[0, 0] = 0 и | ||
<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>. Вычисление матрицы требует времени O(mn), а d(A, B) = C[m, n]. Для решения задачи приближенного сравнения строк примем A = P и B = T и положим C[0; j] = 0 для всех j, так что вышеприведенная формула будет использоваться только для i > 0. | |||