Последовательное приближенное сравнение строк: различия между версиями

Первое и наиболее универсальное решение этой задачи [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, -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.

Теорема 1 (Селлерс, 1980 [ ]). Существует решение с временем выполнения O(mn) в наихудшем случае для задачи ASM с использованием взвешенного расстояния редактирования.

Алгоритм требует O(m) памяти, если заметить, что матрицу C можно вычислять по столбцам и что для вычисления столбка j требуется только столбец j – 1. Как было показано, из этого тотчас же следует, что поиск среди расстояний редактирования с единичной стоимостью также может быть выполнен за время O(mn). В этих случаях очень легко вычислить только часть матрицы C, чтобы получить алгоритмы со средним временем O(kn) [14].

Для вычисления взвешенного расстояния редактирования существуют алгоритмы с меньшей сложностью в наихудшем случае. Применяя разбор Лемпеля-Зива к P и T, можно выявить области матрицы C, соответствующие подстрокам P и T, которые могут быть вычислены из предыдущих областей, соответствующиех аналогичным подстрокам P и T [5].

Теорема 2 (Крочмор и др., 2003 [ ]). Существует решение с временем выполнения O(n + mn/\ogcr n) в наихудшем случае для задачи ASM с использованием взвешенного расстояния редактирования. Более того, время составляет O(n + mnh/log n), где 0 < h < logcr – энтропия T.