4551
правка
Сходство между сжатыми строками: различия между версиями
Перейти к навигации
Перейти к поиску
Сходство между сжатыми строками (посмотреть исходный код)
Версия от 15:11, 24 апреля 2022
, 24 апреля 2022→Постановка задачи
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
Далее будет рассматриваться задача поиска сходства между двумя сжатыми строками. Она связана с эффективным вычислением сходства без декомпрессии двух строк. В литературе рассматривалось решение этой задачи для случаев сжатия методом кодирования на основе длин серий (run-length encoding) и сжатия Лемпеля-Зива (LZ) [14]. | Далее будет рассматриваться задача поиска сходства между двумя сжатыми строками. Она связана с эффективным вычислением сходства без декомпрессии двух строк. В литературе рассматривалось решение этой задачи для случаев сжатия методом кодирования на основе длин серий (run-length encoding) и сжатия Лемпеля-Зива (LZ) [14]. | ||
{| class="wikitable" style="margin:auto" | |||
Совпадение Несовпадение Indel-расстояние Indel-расстояние для k символов | |+ Текст подписи | ||
Самая длинная общая подпоследовательность 1 0 0 0 | |- | ||
Расстояние Левенштейна 0 1 1 k | ! Метрика !! Совпадение !! Несовпадение !! Indel-расстояние !! Indel-расстояние для k символов | ||
Взвешенное расстояние редактирования 0 | |- | ||
Аффинный штраф за гэп 1 - | | Самая длинная общая подпоследовательность || 1 || 0 || 0 || 0 | ||
|- | |||
| Расстояние Левенштейна || 0 || 1 || 1 || k | |||
|- | |||
| Взвешенное расстояние редактирования || 0 || <math>\delta</math> || jX || k/j | |||
|- | |||
| Аффинный штраф за гэп || 1 || <math>- \delta</math> || Текст ячейки | |||
|} | |||
Таблица 1. Различные метрики оценки | Таблица 1. Различные метрики оценки | ||