4551
правка
Сходство между сжатыми строками: различия между версиями
Материал из WEGA
Сходство между сжатыми строками (посмотреть исходный код)
Версия от 11:32, 4 июня 2022
, 4 июня 2022→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
Задача вычисления сходства между двумя строками заключается в сравнении двух строк с помощью некоторой метрики оценки. Существуют различные метрики оценки; одной из самых популярных является метрика расстояния Левенштейна (или расстояния редактирования). Стандартное решение для метрики расстояния Левенштейна, предложенное Вагнером и Фишером [13], основано на динамическом программировании. Также широко используются такие метрики оценки, как метрика самой длинной общей подпоследовательности, метрика взвешенного расстояния редактирования и метрика аффинного штрафа за гэп (пропуск в последовательности). Последняя имеет наиболее общий характер и является довольно сложной для применения. В таблице 1 показаны различия между этими четырьмя метриками. | Задача вычисления сходства между двумя строками заключается в сравнении двух строк с помощью некоторой метрики оценки. Существуют различные метрики оценки; одной из самых популярных является метрика расстояния Левенштейна (или расстояния редактирования). Стандартное решение для метрики расстояния Левенштейна, предложенное Вагнером и Фишером [13], основано на динамическом программировании. Также широко используются такие метрики оценки, как метрика самой длинной общей подпоследовательности, метрика взвешенного расстояния редактирования и метрика аффинного штрафа за гэп (пропуск в последовательности). Последняя имеет наиболее общий характер и является довольно сложной для применения. В таблице 1 показаны различия между этими четырьмя метриками. | ||
{| class="wikitable" style="margin:auto" | {| class="wikitable" style="margin:auto" | ||
|+ | |+ | ||
|- | |- | ||
! Метрика !! Совпадение !! Несовпадение !! Indel-расстояние !! Indel-расстояние для k символов | ! Метрика !! Совпадение !! Несовпадение !! Indel-расстояние !! Indel-расстояние для k символов | ||
| Строка 25: | Строка 23: | ||
[ | Далее будет рассматриваться задача поиска сходства между двумя сжатыми строками. Она связана с эффективным вычислением сходства без декомпрессии двух строк. В литературе рассматривалось решение этой задачи для случаев сжатия методом кодирования длин серий (run-length encoding) и сжатия Лемпеля-Зива (LZ) [14]. | ||
| Строка 44: | Строка 41: | ||
'''Сжатие Лемпеля-Зива (LZ-компрессия)''' | '''Сжатие Лемпеля-Зива (LZ-компрессия)''' | ||
Пусть X и Y – две строки длиной O(n); X' и Y' – сжатые алгоритмом LZ строки X и Y, соответственно. Тогда длины X' и Y' равны O(hn/log n), где < | Пусть X и Y – две строки длиной O(n); X' и Y' – сжатые алгоритмом LZ строки X и Y, соответственно. Тогда длины X' и Y' равны O(hn/log n), где <math>h \le 1</math> – энтропия строк X и Y. | ||
| Строка 55: | Строка 52: | ||
'''Блочное вычисление''' | '''Блочное вычисление''' | ||
Для эффективного вычисления сходства между сжатыми строками можно использовать метод блочного вычисления. Таблицы динамического программирования делятся на подматрицы, называемые ''блоками''. Для строк с кодированием длин серий блок представляет собой подматрицу, состоящую из двух элементов – серий по A и серий по B. Для строк с LZ-сжатием блоком является подматрица, состоящая из двух фраз – по одной фразе из каждой строки. Подробнее об этом см. в [5]. Затем блоки вычисляются слева направо и сверху вниз. Для каждого блока вычисляются только нижняя строка и крайний правый столбец. Пример вычисления блоков приведен на рис. 1. | Для эффективного вычисления сходства между сжатыми строками можно использовать метод блочного вычисления. Таблицы динамического программирования делятся на подматрицы, называемые ''блоками''. Для строк с кодированием длин серий блок представляет собой подматрицу, состоящую из двух элементов – серий по A и серий по B. Для строк с LZ-сжатием блоком является подматрица, состоящая из двух фраз – по одной фразе из каждой строки. Подробнее об этом см. в [5]. Затем блоки вычисляются слева направо и сверху вниз. Для каждого блока вычисляются только нижняя строка и крайний правый столбец. Пример вычисления блоков приведен на рис. 1. | ||
[[Файл:SBCS.png]] | |||
Рисунок 1. Таблица динамического программирования для строк <math>a^r c^p b^t</math> и <math>a^s b^q c^u</math>, разбитая на 9 блоков. Для одного из блоков, например, B, из E и F вычисляются только нижняя строка C и крайний правый столбец D | |||
== Основные результаты == | == Основные результаты == | ||
