60343

Автор(ы): 

Автор(ов): 

4

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

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

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

Название: 

Метод определения периода зашумленной периодической символьной последовательно-сти, основанный на позициях подслов в последовательности

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

Да

ISBN/ISSN: 

2411-1473.

DOI: 

10.25559/SITITO.16.202001.23-32

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

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

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

Т. 16, No 1

Город: 

  • Москва

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

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

Год издания: 

2020

Страницы: 

23-32 http://sitito.cs.msu.ru/index.php/SITITO/article/view/613
Аннотация
Предложен метод определения периода искаженной шумом периодической последовательности. Период почти периодической последовательности — это длина наименьшего периодически повторяющегося фрагмента, образующего соответствующую обычную периодическую последовательность. Метод может быть применен для искаженных периодических последовательностей, полученных из периодических последовательностей, состоящих из, по крайней мере, восьми полных периодически повторяющихся минимальных фрагментов. В соответствующих периодических последовательностях с шумом замены, вставки и удаления некоторые периодические фрагменты могут быть искажены из-за внесения шума. Уровень шума предполагается менее 10%, это предположение позволяет использовать оператор сдвига с окном ширины 16 и наблюдать в этом окне более двух раз каждый неповрежденный фрагмент длины 16, содержащийся в исследуемой последовательности. Метод основан на подсчете числа символов в слове w между первыми символами ближайших одинаковых подслов длины 16. Для вычисления разностей между левыми позициями соседних одинаковых подслов используются только подслова, встретившиеся в рассматриваемом слове более двух раз. Все найденные разности располагаются в порядке возрастания и находятся квантиль 25% и медиана в последовательности разностей. Вычислительный эксперимент показал, что 25% квантиль дает удовлетворительную оценку периода при уровне шума менее 5 %. Иногда метод дает достаточно хороший результат в случае шума от 5 до 10 %. Зависимость доли удовлетворительных оценок периода от уровня шума исследовалась для каждого типа шума отдельно, а также для смеси шумов всех трех типов в одинаковых пропорциях. Вычислительный эксперимент показал, что 25% квантиль дает более точную оценку периода, чем медиана. Предполагается улучшить метод таким образом, чтобы восстанавливать саму периодическую последовательность только по последовательности с шумом.

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

Ульянов М.В., Жукова Г.Н., Жуков А.В., Сметанин Ю.Г. Метод определения периода зашумленной периодической символьной последовательно-сти, основанный на позициях подслов в последовательности // Современные информационные технологии и ИТ-образование. 2020. Т. 16, No 1. С. 23-32 http://sitito.cs.msu.ru/index.php/SITITO/article/view/613.