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

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

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

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

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

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

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

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

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