4430
правок
Сходство между сжатыми строками: различия между версиями
Материал из WEGA
Сходство между сжатыми строками (посмотреть исходный код)
Версия от 23:00, 24 апреля 2022
, 24 апреля 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 91: | Строка 91: | ||
Митчелл [12] получил алгоритм с временем выполнения O((d + n' + m')log(d + n' + m')), где d – число совпадений сжатых символов. Этот алгоритм основан на вычислении геометрических кратчайших путей с помощью специальных выпуклых функций расстояния. | Митчелл [12] получил алгоритм с временем выполнения O((d + n' + m') log(d + n' + m')), где d – число совпадений сжатых символов. Этот алгоритм основан на вычислении геометрических кратчайших путей с помощью специальных выпуклых функций расстояния. | ||
| Строка 103: | Строка 103: | ||
Для задачи 2 Крочмор, Ландау и Зив-Укельсон [6] представили решение с использованием метрики аддитивного штрафа за гэп. Метрика аддитивного штрафа за гэп состоит из трех элементов: 1 – для совпадения, </math>- \delta/math> для несовпадения и <math>- \mu</math> для indel (вставки и удаления), что практически совпадает с метрикой взвешенного расстояния редактирования. | Для задачи 2 Крочмор, Ландау и Зив-Укельсон [6] представили решение с использованием метрики аддитивного штрафа за гэп. Метрика аддитивного штрафа за гэп состоит из трех элементов: 1 – для совпадения, </math>- \delta</math> для несовпадения и <math>- \mu</math> для indel (вставки и удаления), что практически совпадает с метрикой взвешенного расстояния редактирования. | ||
