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

'''Теорема 3 (Крочмор, Ландау и Зив-Укельсон 2003 [6]; Мякинен, Наварро и Укконен [11]). Взвешенное расстояние редактирования между строками A' и B', закодированными длинами серий, может быть вычислена за время O(nm' + n'm).'''

Для метрики аффинного штрафа за гэп Ким, Амир, Ландау и Парк [8] предложили алгоритм с временем выполнения O(nm' + n'm). Для эффективного вычисления сходства в этой метрике задача преобразуется в задачу поиска пути в ориентированном ациклическом графе, и используются некоторые свойства максимальных путей в этом графе. Нет необходимости строить граф в явном виде, так как авторы предложили новые рекуррентности, использующие свойства графа.  

'''Теорема 5 (Апостолико, Ландау и Скиена, 1999 [ ]). Самая длинная общая подпоследовательность строк A' и B', закодированных длинами серий, может быть вычислена за время O(n' m' log(n' + m')).'''

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