ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 10. Vol. 27. 2021

DOI: 10.17587/it.27.531-541

G. N. Zhukova, Ph.D., Associate Professor, e-mail: gzhukova@hse.ru, National Research University Higher School of Economics, Moscow, 101000, Moscow, Russian Federation, M. V. Ulyanov, Dr. of Tech. Sc., Professor, e-mail: muljanov@mail.ru, V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, Moscow, 117997, Russian Federation, Lomonosov Moscow State University, Moscow, 119991, Russian Federation

Reconstruction of a Symbolic Periodic Sequence from a Sequence with Noise

The problem of constructing a periodic sequence consisting of at least eight periods is considered, based on a given sequence obtained from an unknown periodic sequence, also containing at least eight periods, by introducing noise of deletion, replacement, and insertion of symbols. To construct a periodic sequence that approximates a given one, distorted by noise, it is first required to estimate the length of the repeating fragment (period). Further, the distorted original sequence is divided into successive sections of equal length; the length takes on integer values from 80 to 120 % of the period estimate. Each obtained section is compared with each of the remaining sections, a section is selected to build a periodic sequence that has the minimum edit distance (Levenshtein distance) to any of the remaining sections, minimization is carried out over all sections of a fixed length, and then along all lengths from 80 to 120 % of period estimates. For correct comparison of fragments of different lengths, we consider the ration between the edit distance and the length of the fragment. The length of a fragment that minimizes the ratio of the edit distance to another fragment of the same length to the fragment length is considered the period of the approximating periodic sequence, and the fragment itself, repeating the required number of times, forms an approximating sequence. The constructed sequence may contain an incomplete repeating fragment at the end. The quality of the approximation is estimated by the ratio of the edit distance from the original distorted sequence to the constructed periodic sequence of the same length and this length.
Keywords: symbolic sequence, periodic sequence, sequence with noise, noise of insertion, noise of deletion, noise of change

P. 531–541

Acknowledgements: This work was supported by the Russian Foundation for Basic Research, projects no. 19-07-00150 and 19-07-00151.

To the contents