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

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

In recent years, many new algorithms have been developed for detection of periodic patterns in symbolic sequences with noise, as well as for determining the length of a period. The interest in these algorithms is due to the fact that symbolic sequences obtained on the basis of real data are not periodic in the usual sense, but only to some extent similar to them. To analyze latent periodicity in sequences obtained from real data, the idea of representing a sequence as a result of introducing distortions into a regular periodic sequence is used. The presence of distortions of replacing a symbol with some other one, insertion or deletion of a symbol makes it impossible to analyze such a symbolic sequence by the use of traditional algorithms for determining the length of a period. Moreover, the very concept of periodicity of a sequence in the presence of distortions is to be defined, since the usual concept of a period is not applicable in this case. The article provides definitions of symbol and segment periodicity, as well as the definition of an obscure periodic pattern. The CONV, WARP, STNR algorithms and the algorithm of a group of researchers led by E. Korotkov are briefly described; the computational complexity of the CONV, WARP, and STNR algorithms is given. Estimates of the confidence of a period value are also mentioned. The considered algorithms are compared with each other in terms of resistance to noise of different types (replacement, insertion, deletion of a symbol, as well as their combination). All methods detect (with some degree of certainty) the latent period if the noise level is less than 0.1. The CONV algorithm detects the latent period at a higher noise level, but provided that there is only replacement noise. Other algorithms work well in the case of noise of all three types. The most noise resilient algorithm is STNR.