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

Задача вычисления сходства двух строк A0 и B0, закодированных при помощи длин серий, была изучена для различных метрик оценки. Бунке и Сирик [ ] первыми предложили решение задачи 1, используя метрику самой длинной общей подпоследовательности. Их алгоритм основан на блочном вычислении таблицы динамического программирования.

Теорема 1 (Бунке и Цирик, 1995 [ ]). Самая длинная общая подпоследовательность строк A0 и B0, закодированных при помощи длин серий, может быть вычислена за время O(nm0 + n0m).

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

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

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

Приведенные выше результаты показывают, что сравнение закодированных при помощи длин серий строк с использованием метрики самой длинной общей подпоследовательности успешно распространяется на метрики оценки более общего плана.

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

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

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