• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Жукова Г. Н., Сметанин Ю. Г., Ульянов М. В.

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