57888

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

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

Электронная публикация: 

Да

ISBN/ISSN: 

2411-1473

DOI: 

10.25559/SITITO.15.201904.880-891

Наименование источника: 

  • Современные информационные технологии и ИТ-образование

Обозначение и номер тома: 

[S.l.], v. 15, n. 4

Город: 

  • Москва

Издательство: 

  • Фонд содействия развитию интернет-медиа, ИТ-образования, человеческого потенциала «Лига интернет-медиа».

Год издания: 

2019

Страницы: 

880-891
Аннотация
В последние годы разработано множество новых алгоритмов для поиска повторяющихся фрагментов в символьных последовательностях с шумом, а также для определения длины периода. Интерес к этим алгоритмам обусловлен тем, что символьные последовательности, полученные на основе реальных данных, не являются периодическими в обычном смысле, а лишь до какой-то степени похожи на них. Для анализа скрытой периодичности в последовательностях, полученных из реальных данных, используется идея представления последовательности как результата внесения искажений в обычную периодическую последовательность. Наличие искажений замены символа на какой-то другой, вставки или удаления символа не позволяет использовать традиционные алгоритмы поиска длины периода для анализа такой символьной последовательности. Более того, само понятие периодичности последовательности при наличии искажений требует отдельного определения, поскольку обычное понятие периода в этом случае неприменимо. В статье приводятся определения символьной и сегментной периодичности, а также скрытого повторяющегося фрагмента. Кратко описаны алгоритмы CONV, WARP, STNR и алгоритм группы исследователей под руководством Е.Короткова, указана вычислительная сложность алгоритмов CONV, WARP и STNR. Также приведены оценки значимости получаемых в результате работы этих методов значений длины периода. Рассматриваемые алгоритмы сравниваются между собой по устойчивости к шуму разных типов (замена, вставка, удаление символа, а также их комбинация). Все методы позволяют выявить с некоторой долей уверенности скрытый период, если уровень шума менее 0.1. Алгоритм CONV позволяет определять скрытый период и при большем уровне шума, но при условии, что есть только шум замены. Остальные алгоритмы дают хорошие результаты и в случае шумов всех трех типов. Самым устойчивым к шуму алгоритмом оказался STNR.

Библиографическая ссылка: 

Жукова Г.Н., Сметанин Ю.Г., Ульянов М.В. Сравнение основных алгоритмов поиска циклов в символьных последовательностях при наличии искажений // Современные информационные технологии и ИТ-образование. 2019. [S.l.], v. 15, n. 4. С. 880-891 .