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

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

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

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

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

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

Теорема 4 (Ким, Амир, Ландау и Парк, 2005 [8]).

Сходство между закодированными длинами серий строками A0 и B0 согласно метрике аффинного штрафа за гэп может быть вычислено за время O(nm0 + n0m).

Для метрики самой длинной общей подпоследовательности существуют более эффективные алгоритмы. Апостолико, Ландау и Скиена [1] предложили алгоритм с временем выполнения O(n0 m0 log(n0 m0)), основанный на отслеживании конкретных оптимальных путей.

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

Митчелл [12] получил алгоритм с временем выполнения O((d + n0 + m0)log(d + n0 + m0)), где d – число совпадений сжатых символов. Этот алгоритм основан на вычислении геометрических кратчайших путей с помощью специальных выпуклых функций расстояния.

Теорема 6 (Митчелл, 1997 [12]). Самая длинная общая подпоследовательность строк A0 и B0, закодированных длинами серий, может быть вычислена за время O((d + n0 + m0) log(d + n0 + m0)), где d– число совпадений сжатых символов.

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

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

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