Метод определения периода зашумленной периодической символьной последовательности, основанный на позициях подслов в последовательности
Authors: Жукова Г.Н. , Жуков А.В. , Сметанин Ю.Г. , Ульянов М.В. 
Published: December 2024

Предложен метод определения периода искаженной шумом периодической последовательности. Период почти периодической последовательности — это длина наименьшего периодически повторяющегося фрагмента, образующего соответствующую обычную периодическую последовательность. Метод может быть применен для искаженных периодических последовательностей, полученных из периодических последовательностей, состоящих из, по крайней мере, восьми полных периодически повторяющихся минимальных фрагментов. В соответствующих периодических последовательностях с шумом замены, вставки и удаления некоторые периодические фрагменты могут быть искажены из-за внесения шума. Уровень шума предполагается менее 10%, это предположение позволяет использовать оператор сдвига с окном ширины 16 и наблюдать в этом окне более двух раз каждый неповрежденный фрагмент длины 16, содержащийся в исследуемой последовательности. Метод основан на подсчете числа символов в слове w между первыми символами ближайших одинаковых подслов длины 16. Для вычисления разностей между левыми позициями соседних одинаковых подслов используются только подслова, встретившиеся в рассматриваемом слове более двух раз. Все найденные разности располагаются в порядке возрастания и находятся квантиль 25% и медиана в последовательности разностей. Вычислительный эксперимент показал, что 25% квантиль дает удовлетворительную оценку периода при уровне шума менее 5 %. Иногда метод дает достаточно хороший результат в случае шума от 5 до 10 %. Зависимость доли удовлетворительных оценок периода от уровня шума исследовалась для каждого типа шума отдельно, а также для смеси шумов всех трех типов в одинаковых пропорциях. Вычислительный эксперимент показал, что 25% квантиль дает более точную оценку периода, чем медиана. Предполагается улучшить метод таким образом, чтобы восстанавливать саму периодическую последовательность только по последовательности с шумом.

The method of estimating the period of an almost periodic sequence is proposed. The period of an almost periodic sequence is the length of the smallest periodic pattern that composes the corresponding completely periodic sequence by repetition. The method can be applied to corrupted periodic sequences that originated from a periodic sequence that consists of no less than eight complete periodic patterns. In the corresponding periodic sequence with noise of insertion, deletion or change, some periodic patterns might be corrupted by noise intrusion. The level of noise is supposed to be less than 10%, this assumption allows us to use a shift operator with the window of width 16 so that we can observe at least more than twice every uncorrupted pattern of length 16 that the sequence under consideration contains. The method is based on the counting of the number of symbols in the word w between the two first symbols of the closest equal patterns of length 16. Only patterns that were encountered in word more than twice are used for counting the differences between the left positions of the neighbor equal patterns in the sequence under consideration. All the differences counted are arranged in the ascending order and the 25% quantile and the median of the sequence of the differences are calculated. The computational experiment shows that in most cases the 25% quantile is an appropriate estimation of the length of the periodic pattern when the noise level is no more than 5%. Sometimes the method provides a sufficient result in case of noise level between 5 and 10%. The dependence of the percentage of sufficient estimations of periodic pattern length on the noise level was studied in cases of only one type of noise and the noise of all three types in equal proportions. The computational experiment showed that in all situations 25% quantile provides more sufficient estimations than the median. The method is supposed to be improved, in order to restore the whole corresponding periodic sequence using only the sequence with noise.