- Код статьи
- 10.31857/S0132347423050035-1
- DOI
- 10.31857/S0132347423050035
- Тип публикации
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 5
- Страницы
- 3-18
- Аннотация
- В статье рассматриваются различные числовые функции, определяющие степень “похожести” двух заданных конечных последовательностей. Эти меры подобия основаны на определяемом нами понятии вложения в последовательность. Частным случаем такого вложения является обычная подпоследовательность (subsequence). Другие случаи дополнительно требуют равенства расстояний между соседними символами подпоследовательности в обеих последовательностях. Это является обобщением понятия отрезка последовательности (substring), в котором эти расстояния единичны. Дополнительно может требоваться равенство расстояний от начала последовательностей до первого символа вложения или от последнего символа вложения до конца последовательностей. Кроме этих двух последних случаев, вложение может входить в последовательность несколько раз. В литературе используются такие функции как число общих вложений или числа пар вхождений вложений в последовательности. Кроме них, мы вводим еще три функции: сумма длин общих вложений, сумма минимумов числа вхождений общего вложения в обе последовательности и функция подобия на основе наибольшего по числу символов общего вложения. Всего рассматриваются 20 числовых функций, для 17 из которых предложены алгоритмы (в том числе новые) полиномиальной сложности, еще для двух функций алгоритмы имеют экспоненциальную сложность с уменьшенным показателем степени. В Заключении дается краткая сравнительная характеристика этих вложений и функций.
- Ключевые слова
- анализ последовательностей общие подпоследовательности наибольшие и максимальные общие подпоследовательности каноническое вложение соответствующие совместные вложения комбинаторные алгоритмы для подпоследовательностей и вложений аксиомы подобия
- Дата публикации
- 17.09.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 20
Библиография
- 1. Wagner R., Fischer M. The string-to-string correction problem // Journal of the ACM. 1974. V. 21. № 1. P. 168–173. https://dl.acm.org/doi/10.1145/321796.321811
- 2. Wang H. All common subsequences, in: M.M. Veloso (Ed.), IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, 2007. https://www.aaai.org/Papers/IJCAI/2007/IJCAI07-101.pdf
- 3. Cees Elzinga, Sven Rahmann, Hui Wang: Algorithms for Subsequence Combinatorics. Theoretical Computer Science. 2008. V. 409. № 3. P. 394–404. https://doi.org/10.1016/j.tcs.2008.08.035
- 4. Gilbert Ritschard and Matthias Studer (editors). Proceedings of the International Conference on Sequence Analysis and Related Methods (LaCOSA II). Lausanne, Switzerland, June 8–10, 2016. https://www.academia.edu/83294569/Proceedings_of_the_International_Conference_on_Sequence_Analysis_and_Related_Methods_LaCOSA_II_Lausanne_Switzerland_June_8_10_2016
- 5. Знаменский С.В. Модель и аксиомы метрик сходства, Программные системы: теория и приложения. 2017. Т. 8. Вып. 4. С. 347–357. https://doi.org/10.25209/2079-3316-2017-8-4-347-357
- 6. Conte A., Grossi R., Punzi G. et al. Enumeration of Maximal Common Subsequences Between Two Strings // Algorithmica. 2022. V. 84. P. 757–783. https://doi.org/10.1007/s00453-021-00898-5
