Сходство между сжатыми строками: различия между версиями

Для метрики расстояния Левенштейна Арбелл, Ландау и Митчелл [2] и Макинен, Наварро и Укконен [10] независимо друг от друга представили алгоритмы с временем выполнения O(nm' + n'm). Эти алгоритмы являются расширениями алгоритма Бунке и Цирика.

'''Теорема 2 (Арбелл, Ландау и Митчелл [2]; Макинен, Наварро и Укконен [10]). Расстояние Левенштейна между строками A' и B', закодированными длинами серий, может быть вычислена за время O(nm' + n'm).'''

Для метрики взвешенного расстояния редактирования Крочмор, Ландау и Зив-Укельсон [6] и Макинен, Наварро и Укконен [11] предложили алгоритмы с временем выполнения O(nm' + n'm), используя совершенно отличные друг от друга методы. Алгоритм Крочмора, Ландау и Зив-Укельсона [6] основывается на технике, которая используется в алгоритме сравнения с шаблоном для текста с LZ-сжатием [6], тогда как алгоритм Макинена, Наварро и Укконена [11] является расширением алгоритма для метрики расстояния Левенштейна.

'''Теорема 3 (Крочмор, Ландау и Зив-Укельсон 2003 [6]; Макинен, Наварро и Укконен [11]). Взвешенное расстояние редактирования между строками A' и B', закодированными длинами серий, может быть вычислена за время O(nm' + n'm).'''

Макинен, Наварро и Укконен [11] пришли к выводу, что среднее время работы алгоритма составляет O(n'm') в предположении, что распределение длин серий одинаково в обеих строках.

'''Гипотеза 1 (Макинен, Наварро и Укконен, 2003 [11]). Самая длинная подпоследовательность строк A' и B', закодированных длинами серий, в среднем может быть вычислена за время O(n'm').'''