Сравнение основных алгоритмов поиска циклов в символьных последовательностях при наличии искажений

  • Галина Николаевна Жукова Национальный исследовательский университет «Высшая школа экономики» http://orcid.org/0000-0003-1835-7422
  • Юрий Геннадиевич Сметанин ФИЦ Информатика и управление РАН http://orcid.org/0000-0003-0242-6972
  • Михаил Васильевич Ульянов Институт проблем управления им В.А. Трапезникова РАН; Московский государственный университет им. М.В. Ломоносова http://orcid.org/0000-0002-5784-9836

Аннотация

В последние годы разработано множество новых алгоритмов для поиска повторяющихся фрагментов в символьных последовательностях с шумом, а также для определения длины периода. Интерес к этим алгоритмам обусловлен тем, что символьные последовательности, полученные на основе реальных данных, не являются периодическими в обычном смысле, а лишь до какой-то степени похожи на них. Для анализа скрытой периодичности в последовательностях, полученных из реальных данных, используется идея представления последовательности как результата внесения искажений в обычную периодическую последовательность.


Наличие искажений замены символа на какой-то другой, вставки или удаления символа не позволяет использовать традиционные алгоритмы поиска длины периода для анализа такой символьной последовательности. Более того, само понятие периодичности последовательности при наличии искажений требует отдельного определения, поскольку обычное понятие периода в этом случае неприменимо. В статье приводятся определения символьной и сегментной периодичности, а также скрытого повторяющегося фрагмента. Кратко описаны алгоритмы CONV, WARP, STNR и алгоритм группы исследователей под руководством Е.Короткова, указана вычислительная сложность алгоритмов CONV, WARP и STNR. Также приведены оценки значимости получаемых в результате работы этих методов значений длины периода.


Рассматриваемые алгоритмы сравниваются между собой по устойчивости к шуму разных типов (замена, вставка, удаление символа, а также их комбинация). Все методы позволяют выявить с некоторой долей уверенности скрытый период, если уровень шума менее 0.1. Алгоритм  CONV позволяет определять скрытый период и при большем уровне шума, но при условии, что есть только шум замены. Остальные алгоритмы дают хорошие результаты и в случае шумов всех трех типов. Самым устойчивым к шуму алгоритмом оказался STNR.

Сведения об авторах

Галина Николаевна Жукова, Национальный исследовательский университет «Высшая школа экономики»

кандидат физико-математических наук, доцент

Юрий Геннадиевич Сметанин, ФИЦ Информатика и управление РАН

доктор физико-математических наук, главный научный сотрудник

Михаил Васильевич Ульянов, Институт проблем управления им В.А. Трапезникова РАН; Московский государственный университет им. М.В. Ломоносова

доктор технических наук, профессор, ведущий научный сотрудник, профессор кафедры алгоритмических языков факультета вычислительной математики и кибернетики 

Опубликована
2019-12-23
Как цитировать
ЖУКОВА, Галина Николаевна; СМЕТАНИН, Юрий Геннадиевич; УЛЬЯНОВ, Михаил Васильевич. Сравнение основных алгоритмов поиска циклов в символьных последовательностях при наличии искажений. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 15, n. 4, p. 880-891, dec. 2019. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/596>. Дата доступа: 27 feb. 2020 doi: https://doi.org/10.25559/SITITO.15.201904.880-891.
Раздел
Исследования и разработки в области новых ИТ и их приложений