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

Задача вычисления сходства между двумя строками заключается в сравнении двух строк с помощью некоторой метрики оценки. Существуют различные метрики оценки; одной из самых популярных является метрика расстояния Левенштейна (или расстояния редактирования). Стандартное решение для метрики расстояния Левенштейна, предложенное Вагнером и Фишером [13], основано на динамическом программировании. Также широко используются такие метрики оценки, как метрика самой длинной общей подпоследовательности, метрика взвешенного расстояния редактирования и метрика аффинного штрафа за гэп (пропуск в последовательности). Последняя имеет наиболее общий характер и является довольно сложной для работы. В таблице 1 показаны различия между этими четырьмя метриками.

|+ Текст подписи

[[Файл:SBCS.png]]

Строка S кодируется по длине серии, если она описывается упорядоченной последовательностью пар <math>(\sigma, i)</math>, часто обозначаемых как <math>\sigma^i</math>, каждая из которых состоит из символа алфавита, <math>\sigma</math>, и целого числа, i. Каждая пара соответствует ''длине серии'' в S, состоящей из i последовательных вхождений a. Например, строка ''aaabbbbbaccccbb'' может быть закодирована в виде <math>a^3 b^4 a^1 c^4 b^2</math> или, что эквивалентно, (a, 3) (b, 4) (a, 1) (c, 4) (b, 2). Пусть A и B – две строки длиной n и m, соответственно, A' и B' – закодированные при помощи длин серий строки A и B, а n' и m' – строк длины A' и B', соответственно.

Пусть X и Y – две строки длиной O(n); X' и Y' – сжатые алгоритмом LZ строки X и Y, соответственно. Тогда длины X' и Y' равны O(hn/log n), где </math>h \le 1</math> – энтропия строк X и Y.

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

Для задачи 2 Крочмор, Ландау и Зив-Укельсон [6] представили решение с использованием метрики аддитивного штрафа за гэп. Метрика аддитивного штрафа за гэп состоит из 1 для совпадения, -S для несовпадения и -fi для indel (вставки и удаления), что практически совпадает с метрикой взвешенного расстояния редактирования.

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

Сложность задачи в наихудшем случае не вполне понятна. Для метрики самой длинной общей подпоследовательности найдены некоторые результаты с временной сложностью выше O(nm0 + n0m) при вычислении сходства двух строк, закодированных при помощи длин серий [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)