53948

Автор(ы): 

Автор(ов): 

3

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

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

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

Название: 

Вероятностная модель шумов для периодических символьных последовательностей

DOI: 

10.25559/SITITO.15.201902.431-440

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

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

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

Т. 15, № 2

Город: 

  • Москва

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

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

Год издания: 

2019

Страницы: 

431-440
Аннотация
В целях анализа методов поиска циклов и выявления их особенностей и чувствительности к шумам различных типов необходимо моделирование шумов с заданными характеристиками. Для построения почти периодических символьных последовательностей предложены две вероятностные модели шума. Модели позволяют вносить в периодическую последовательность различные типы шума, такие как изменение, добавление и удаление символов. Таким образом на основе периодической символьной последовательности получается почти периодическая последовательность. Необходимо обеспечить заданный уровень шума в построенной почти периодической последовательности. Требуемый уровень вносимого шума гарантирует двухуровневая модель, в которой на первом уровне на основе выбранной исследователем дискретной случайной величины определяются позиции для внесения шума, а на втором уровне с использованием случайной величины, моделирующей собственно шум, в соответствующие позиции вносится необходимое изменение. Вторая модель основана на внесении шума с вероятностью, зависящей от уровня шума, в каждом элементе последовательности. Наблюдаемый уровень шума рассчитывается на основе расстояния Левенштейна между исходной периодической последовательностью и построенной зашумленной. Наблюдаемый уровень шума всегда несколько меньше уровня вносимого шума, поскольку при вычислении расстояния Левенштейна может быть найден более короткий путь получения зашумленной последовательности из периодической, чем использованный при построении почти периодической последовательности. Проведено сравнение предложенных моделей по близости обеспечиваемого ими уровня шума к заданному уровню шума. Вычислительный эксперимент показал, что наблюдаемый уровень шума ближе к заданному для двухуровневой модели. Программная реализация данных моделей будет использована в дальнейшем для исследования алгоритмов поиска циклов в зашумленных периодических символьных последовательностях.

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

Жукова Г.Н., Сметанин Ю.Г., Ульянов М.В. Вероятностная модель шумов для периодических символьных последовательностей // Современные информационные технологии и ИТ-образование. 2019. Т. 15, № 2. С. 431-440.