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

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

Для задачи 2 Крочмор, Ландау и Зив-Укельсон [6] представили решение с использованием метрики аддитивного штрафа за гэп. Метрика аддитивного штрафа за гэп состоит из трех элементов: 1 – для совпадения, </math>- \delta/math> для несовпадения и <math>- \mu</math> для indel (вставки и удаления), что практически совпадает с метрикой взвешенного расстояния редактирования.

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