Сходство между сжатыми строками
Ключевые слова и синонимы
Приближенное сравнение сжатых строк; выравнивание сжатых строк
Постановка задачи
Задача вычисления сходства между двумя строками заключается в сравнении двух строк с помощью некоторой метрики оценки. Существуют различные метрики оценки; одной из самых популярных является метрика расстояния Левенштейна (или расстояния редактирования). Стандартное решение для метрики расстояния Левенштейна, предложенное Вагнером и Фишером [13], основано на динамическом программировании. Также широко используются такие метрики оценки, как метрика самой длинной общей подпоследовательности, метрика взвешенного расстояния редактирования и метрика аффинного штрафа за гэп (пропуск в последовательности). Последняя имеет наиболее общий характер и является довольно сложной для работы. В таблице 1 показаны различия между этими четырьмя метриками.
Далее будет рассматриваться задача поиска сходства между двумя сжатыми строками. Она связана с эффективным вычислением сходства без декомпрессии двух строк. В литературе рассматривалось решение этой задачи для случаев сжатия методом кодирования на основе длин серий (run-length encoding) и сжатия Лемпеля-Зива (LZ) [14].
Совпадение Несовпадение Indel-расстояние Indel-расстояние для k символов
Самая длинная общая подпоследовательность 1 0 0 0
Расстояние Левенштейна 0 1 1 k
Взвешенное расстояние редактирования 0 S jX k/j,
Аффинный штраф за гэп 1 -S -y -ii -y -kfi
Таблица 1. Различные метрики оценки
Рисунок 1. Таблица динамического программирования для строк arcpbt и asbqcu, разбитая на 9 блоков. Для одного из блоков, например, B, из E и F вычисляются только нижняя строка C и крайний правый столбец D
Кодирование на основе длин серий
Строка S кодируется по длине серии, если она описывается упорядоченной последовательностью пар (a, i), часто обозначаемых как «a'», каждая из которых состоит из символа алфавита, a, и целого числа, i. Каждая пара соответствует длине серии в S, состоящей из i последовательных вхождений a. Например, строка aaabbbbbaccccbb может быть закодирована в виде a3b4a1c4b2 или, что эквивалентно, (a, 3) (b, 4) (a, 1) (c, 4) (b, 2). Пусть A и B – две строки длиной n и m, соответственно, A0 и B0 – закодированные на основе длин серий строки A и B, а n0 и m0 – длины A0 и B0, соответственно.
Задача 1
Дано: две строки A0 aи B0, закодированные на основе длин серий; метрика оценки d.
Требуется: найти сходство между A0 и B0 с использованием метрики d.
Сжатие Лемпеля-Зива (LZ-компрессия)
Пусть X и Y – две строки длиной O(n); X0 и Y0 – сжатые алгоритмом LZ строки X и Y, соответственно. Тогда длины X0 и Y0 равны O(hn/log n), где fc < 1 – энтропия строк X и Y.
Задача 2
Дано: две LZ-сжатые строки X0 и Y0, метрика оценки d.
Требуется: найти сходство между X0 и Y0 с использованием метрики d.
Блочное вычисление
Для эффективного вычисления сходства между сжатыми строками можно использовать метод блочного вычисления. Таблицы динамического программирования делятся на подматрицы, называемые «блоками». Для строк с кодированием на основе длин серий блок представляет собой подматрицу, состоящую из двух элементов – серий по A и серий по B. Для строк с LZ-сжатием блоком является подматрица, состоящая из двух фраз – по одной фразе из каждой строки. Подробнее об этом см. в [5]. Затем блоки вычисляются слева направо и сверху вниз. Для каждого блока вычисляются только нижняя строка и крайний правый столбец. Пример вычисления блоков приведен на рис. 1.
Основные результаты
Задача вычисления сходства двух строк A0 и B0, закодированных на основе длин серий, была изучена для различных метрик оценки. Бунке и Сирик [ ] первыми предложили решение задачи 1, используя метрику самой длинной общей подпоследовательности. Их алгоритм основан на блочном вычислении таблицы динамического программирования.
Теорема 1 (Бунке и Цирик, 1995 [ ]). Самая длинная общая подпоследовательность строк A0 и B0, закодированных на основе длин серий, может быть вычислена за время O(nm0 + n0m).
Для метрики расстояния Левенштейна Арбелл, Ландау и Митчелл [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.
Применение
Кодирование на основе длин серий является популярным методом сжатия изображений, поскольку многие классы изображений (например, двоичные изображения при факсимильной передаче или при использовании в оптическом распознавании символов) обычно содержат большие участки пикселей с одинаковыми значениями. Нахождение приближенного соответствия в изображениях может быть полезным инструментом для работы с искажениями. Даже одномерный алгоритм приближенного сравнения для сжатого текста был бы полезен для ускорения двумерного приближенного сравнения, допускающего несовпадения и даже повороты [3, 7, 9].
Открытые вопросы
Сложность задачи в наихудшем случае не вполне понятна. Для метрики самой длинной общей подпоследовательности найдены некоторые результаты с временной сложностью выше O(nm0 + n0m) при вычислении сходства двух строк, закодированных на основе длин серий [1, 11, 12]. Остается открытым вопрос о распространении этих результатов на метрику расстояния Левенштейна, метрику взвешенного расстояния редактирования и метрику аффинного штрафа за гэп.
Кроме того, для метрики самой длинной общей подпоследовательности не решена задача доказательства гипотезы 1.
См. также
Литература
1. Apostolico, A., Landau, G.M., Skiena, S.: Matching for Run-Length Encoded Strings. J. Complex. 15(1), 4-16 (1999)
2. Arbell, O., Landau, G.M., Mitchell, J.: Edit Distance of Run-Length Encoded Strings. Inf. Proc. Lett. 83(6), 307-314 (2002)
3. Baeza-Yates, R., Navaro, G.: New Models and Algorithms for Multidimensional Approximate Pattern Matching. J. Discret. Algorithms 1(1), 21^9 (2000)
4. Bunke, H., Csirik, H.: An Improved Algorithm for Computing the Edit Distance of Run Length Coded Strings. Inf. Proc. Lett. 54, 93-96(1995)
5. Crochemore, M., Landau, G.M., Schieber, B., Ziv-Ukelson, M.: Re-Use Dynamic Programming for Sequence Alignment: An Algorithmic Toolkit. In: Iliopoulos, C.S., Lecroq, T. (eds.) String Algorithmics, pp. 19-59. King's College London Publications, London (2005)
6. Crochemore, M., Landau, G.M.,Ziv-Ukelson, M.: A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices. SIAM J. Comput. 32(6), 1654-1673 (2003)
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)
8. Kim, J.W., Amir, A., Landau, G.M., Park, K.: Computing Similarity of Run-Length Encoded Strings with Affine Gap Penalty. In: Proc. 12th Symposium on String Processing and Information Retrieval (SPIRE'05). LNCS, vol. 3772, pp. 440-449 (2005)
9. Krithivasan, K., Sitalakshmi, R.: Efficient Two-Dimensional Pattern Matching in The Presence of Errors. Inf. Sci. 43, 169-184 (1987)
10. Makinen, V., Navarro, G., Ukkonen, E.: Approximate Matching of Run-Length Compressed Strings. In: Proc. 12th Symposium on Combinatorial Pattern Matching (CPM'01). LNCS, vol. 2089, pp. 31-49 (2001)
11. Makinen, V., Navarro, G., Ukkonen, E.: Approximate Matching of Run-Length Compressed Strings. Algorithmica 35, 347-369 (2003)
12. Mitchell, J.: A Geometric Shortest Path Problem, with Application to Computing a Longest Common Subsequence in Run-Length Encoded Strings. Technical Report, Dept. of Applied Mathematics, SUNY Stony Brook (1997)
13. Wagner, R.A., Fischer, M.J.: The String-to-String correction Problem. J.ACM 21(1), 168-173(1974)
14. Ziv, J., Lempel, A.: Compression of Individual Sequences via Variable Rate Coding. IEEE Trans. Inf. Theory 24(5), 530-536 (1978)
