Восстановление символьной периодической последовательности по последовательности с шумом

Информационные технологии. 2021. Т. 27. С. 531–541.

Жукова Г. Н., Ульянов М. В.

Рассматривается задача построения периодической последовательности, состоящей из не менее чем восьми периодов, на основе заданной последовательности, полученной путем внесения шума удаления, замены и вставки символов из неизвестной периодической последовательности, также содержащей не менее восьми периодов. Для построения периодической последовательности, аппроксимирующей заданную, искаженную шумами, вначале требуется оценить длину повторяющегося фрагмента (период). Далее искаженная исходная последовательность разбивается на последовательные участки равной длины, длина пробегает все целые значения от 80 до 120 % от оценки периода. Каждый полученный участок сравнивается с каждым из оставшихся. Для построения периодической последовательности выбирается участок с минимальным редакционным расстоянием. Минимизация проводится по всем участками фиксированной длины, а затем — по всем длинам от 80 до 120 % от оценки периода. Для корректности сравнения фрагментов разной длины редакционное расстояние делится на длину фрагмента. Длина фрагмента, доставляющего минимум отношения редакционного расстояния, считается периодом аппроксимирующей периодической последовательности, а сам фрагмент, повторяясь необходимое число раз, образует аппроксимирующую последовательность. Построенная последовательность может в конце содержать неполный повторяющийся фрагмент. Качество аппроксимации оценивается отношением редакционного расстояния от исходной искаженной последовательности до построенной периодической последовательности такой же длины к этой длине.

Ключевые слова: символьная последовательность, периодическая последовательность, symbolic sequence, periodic sequence, sequence with noise, noise of insertion, noise of deletion, noise of change, шум вставки, шум удаления, шум замены, зашумленная последовательность