A Stochastic Model of Noises for Periodic Symbol Sequences
The construction of almost periodic sequences is needed for the analysis of the cycles’ detection methods, identification of symbolic sequences’ features and sensitivity analysis. Two probabilistic models of noise are proposed for constructing almost periodic symbolic sequences. Models provide vario...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
The Fund for Promotion of Internet media, IT education, human development «League Internet Media»
2019-07-01
|
| Series: | Современные информационные технологии и IT-образование |
| Subjects: | |
| Online Access: | http://sitito.cs.msu.ru/index.php/SITITO/article/view/537 |
| _version_ | 1818718243061235712 |
|---|---|
| author | Galina N. Zhukova Yuri G. Smetanin Mikhail V. Ulyanov |
| author_facet | Galina N. Zhukova Yuri G. Smetanin Mikhail V. Ulyanov |
| author_sort | Galina N. Zhukova |
| collection | DOAJ |
| description | The construction of almost periodic sequences is needed for the analysis of the cycles’ detection methods, identification of symbolic sequences’ features and sensitivity analysis. Two probabilistic models of noise are proposed for constructing almost periodic symbolic sequences. Models provide various types of noise in a periodic sequence, such as changing, adding and deleting characters. Thus, on the basis of a periodic symbolic sequence, an almost periodic sequence is constructed.
It is necessary to ensure a given level of noise in the constructed almost periodic sequence. The required level of simulated noise is guaranteed by a two-level model, in which the positions for simulated noise are determined at the first level, based on the discrete random variable, chosen by the researcher. At the second level, the necessary changes are made at the corresponding positions using a random variable that simulates the noise itself. The second model is based on simulated noise with probability (depending on the noise level) in each element of the sequence.
The observed noise level is calculated based on the Levenshtein distance between the original periodic sequence and the almost periodic sequence that we constructed. The observed noise level is always somewhat less than the level of the noise simulated, since when calculating the Levenshtein distance, a shorter way of obtaining a noisy sequence from a periodic one can be found than the one that is used in constructing an almost periodic sequence.
A comparison of the proposed models for the proximity of the noise level they provide to a given noise level is made. The computational experiment showed that the observed noise level is closer to that provided by the two-level model. The software implementation of these models will be used in future to study the algorithms for finding cycles in noisy periodic symbolic sequences. |
| first_indexed | 2024-12-17T19:47:57Z |
| format | Article |
| id | doaj.art-42f69d2bb09748d0a68d7f6f4da5e841 |
| institution | Directory Open Access Journal |
| issn | 2411-1473 |
| language | Russian |
| last_indexed | 2024-12-17T19:47:57Z |
| publishDate | 2019-07-01 |
| publisher | The Fund for Promotion of Internet media, IT education, human development «League Internet Media» |
| record_format | Article |
| series | Современные информационные технологии и IT-образование |
| spelling | doaj.art-42f69d2bb09748d0a68d7f6f4da5e8412022-12-21T21:34:49ZrusThe Fund for Promotion of Internet media, IT education, human development «League Internet Media»Современные информационные технологии и IT-образование2411-14732019-07-0115243144010.25559/SITITO.15.201902.431-440A Stochastic Model of Noises for Periodic Symbol SequencesGalina N. Zhukova0Yuri G. Smetanin1Mikhail V. Ulyanov2National Research University Higher School of Economics, Moscow, RussiaFederal Research Center “Computer Science and Control” of the Russian Academy of Sciences, Moscow, Russia V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, Lomonosov Moscow State University, Moscow, RussiaThe construction of almost periodic sequences is needed for the analysis of the cycles’ detection methods, identification of symbolic sequences’ features and sensitivity analysis. Two probabilistic models of noise are proposed for constructing almost periodic symbolic sequences. Models provide various types of noise in a periodic sequence, such as changing, adding and deleting characters. Thus, on the basis of a periodic symbolic sequence, an almost periodic sequence is constructed. It is necessary to ensure a given level of noise in the constructed almost periodic sequence. The required level of simulated noise is guaranteed by a two-level model, in which the positions for simulated noise are determined at the first level, based on the discrete random variable, chosen by the researcher. At the second level, the necessary changes are made at the corresponding positions using a random variable that simulates the noise itself. The second model is based on simulated noise with probability (depending on the noise level) in each element of the sequence. The observed noise level is calculated based on the Levenshtein distance between the original periodic sequence and the almost periodic sequence that we constructed. The observed noise level is always somewhat less than the level of the noise simulated, since when calculating the Levenshtein distance, a shorter way of obtaining a noisy sequence from a periodic one can be found than the one that is used in constructing an almost periodic sequence. A comparison of the proposed models for the proximity of the noise level they provide to a given noise level is made. The computational experiment showed that the observed noise level is closer to that provided by the two-level model. The software implementation of these models will be used in future to study the algorithms for finding cycles in noisy periodic symbolic sequences.http://sitito.cs.msu.ru/index.php/SITITO/article/view/537symbolic sequenceperiodic sequencesequence with noiseprobabilistic model of noise |
| spellingShingle | Galina N. Zhukova Yuri G. Smetanin Mikhail V. Ulyanov A Stochastic Model of Noises for Periodic Symbol Sequences Современные информационные технологии и IT-образование symbolic sequence periodic sequence sequence with noise probabilistic model of noise |
| title | A Stochastic Model of Noises for Periodic Symbol Sequences |
| title_full | A Stochastic Model of Noises for Periodic Symbol Sequences |
| title_fullStr | A Stochastic Model of Noises for Periodic Symbol Sequences |
| title_full_unstemmed | A Stochastic Model of Noises for Periodic Symbol Sequences |
| title_short | A Stochastic Model of Noises for Periodic Symbol Sequences |
| title_sort | stochastic model of noises for periodic symbol sequences |
| topic | symbolic sequence periodic sequence sequence with noise probabilistic model of noise |
| url | http://sitito.cs.msu.ru/index.php/SITITO/article/view/537 |
| work_keys_str_mv | AT galinanzhukova astochasticmodelofnoisesforperiodicsymbolsequences AT yurigsmetanin astochasticmodelofnoisesforperiodicsymbolsequences AT mikhailvulyanov astochasticmodelofnoisesforperiodicsymbolsequences AT galinanzhukova stochasticmodelofnoisesforperiodicsymbolsequences AT yurigsmetanin stochasticmodelofnoisesforperiodicsymbolsequences AT mikhailvulyanov stochasticmodelofnoisesforperiodicsymbolsequences |