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

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

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

Требуется: найти сходство между A0 и B0 с использованием метрики d.

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

Дано: две LZ-сжатые строки X0 и Y0, метрика оценки d.

Требуется: найти сходство между X0 и Y0 с использованием метрики d.

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