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

Далее будет рассматриваться задача поиска сходства между двумя сжатыми строками. Она связана с эффективным вычислением сходства без декомпрессии двух строк. В литературе рассматривалось решение этой задачи для случаев сжатия методом кодирования на основе длин серий (run-length encoding) и сжатия Лемпеля-Зива (LZ) [14].

'''Кодирование на основе длин серий'''

Строка 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, соответственно.

Дано: две строки A0 aи B0, закодированные на основе длин серий; метрика оценки d.

Для эффективного вычисления сходства между сжатыми строками можно использовать метод блочного вычисления. Таблицы динамического программирования делятся на подматрицы, называемые «блоками». Для строк с кодированием на основе длин серий блок представляет собой подматрицу, состоящую из двух элементов – серий по A и серий по B. Для строк с LZ-сжатием блоком является подматрица, состоящая из двух фраз – по одной фразе из каждой строки. Подробнее об этом см. в [5]. Затем блоки вычисляются слева направо и сверху вниз. Для каждого блока вычисляются только нижняя строка и крайний правый столбец. Пример вычисления блоков приведен на рис. 1.

Задача вычисления сходства двух строк 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).

Кодирование на основе длин серий является популярным методом сжатия изображений, поскольку многие классы изображений (например, двоичные изображения при факсимильной передаче или при использовании в оптическом распознавании символов) обычно содержат большие участки пикселей с одинаковыми значениями. Нахождение приближенного соответствия в изображениях может быть полезным инструментом для работы с искажениями. Даже одномерный алгоритм приближенного сравнения для сжатого текста был бы полезен для ускорения двумерного приближенного сравнения, допускающего несовпадения и даже повороты [3, 7, 9].

Сложность задачи в наихудшем случае не вполне понятна. Для метрики самой длинной общей подпоследовательности найдены некоторые результаты с временной сложностью выше O(nm0 + n0m) при вычислении сходства двух строк, закодированных на основе длин серий [1, 11, 12]. Остается открытым вопрос о распространении этих результатов на метрику расстояния Левенштейна, метрику взвешенного расстояния редактирования и метрику аффинного штрафа за гэп.