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

Для метрики расстояния Левенштейна Арбелл, Ландау и Митчелл [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).'''

Для метрики аффинного штрафа за гэп Ким, Амир, Ландау и Парк [8] предложили алгоритм с временем выполнения O(nm' + n'm). Для эффективного вычисления сходства в этой метрике задача преобразуется в задачу поиска пути в ориентированном ациклическом графе, и используются некоторые свойства максимальных путей в этом графе. Нет необходимости строить граф в явном виде, так как авторы предложили новые рекуррентности, использующие свойства графа.  

'''Теорема 5 (Апостолико, Ландау и Скиена, 1999 [ ]). Самая длинная общая подпоследовательность строк A' и B', закодированных длинами серий, может быть вычислена за время O(n' m' log(n' + m')).'''

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

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

'''Теорема 7 (Крочмор, Ландау и Зив-Укельсон, 1993 [6]). Сходство между LZ-сжатыми строками X' и Y' в метрике аддитивного штрафа за гэп может быть вычислено за время O(hn2 / log n), где <math>h \le 1</math> – энтропия строк X и Y.'''

Сложность задачи в наихудшем случае не вполне понятна. Для метрики самой длинной общей подпоследовательности найдены некоторые результаты с временной сложностью выше O(nm' + n'm) при вычислении сходства двух строк, закодированных при помощи длин серий [1, 11, 12]. Остается открытым вопрос о распространении этих результатов на метрику расстояния Левенштейна, метрику взвешенного расстояния редактирования и метрику аффинного штрафа за гэп.

7. Fredriksson, K., Navarro, G., Ukkonen, E.: Sequential and Indexed Two-Dimensional Combinatorial Template Matching Allowing Rotations. Theor. Comput. Sci. 347(1-2), 239-275

(2005)