Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой
Проблема распознавания последовательности, включающей повторяющийся фрагмент
Структура последовательности:
M' Í M = {1,...,M}, |M'| = M';
Y = X + E;
U = (u0,..., uq-1) Î A, – соответствует искомому информационному фрагменту, A – множество допустимых информационных фрагментов (алфавит), ||A|| = K.
Vm Î B, m Î M\M', – фрагменту-вставке (вектору-вставке), B – множество допустимых вставок.
Имеем следующие варианты задач
|
вставок нет M=M' |
имеются вставки M' Ì M |
|||||||
|
задан алфавит вставок B |
множество вставок не ограничено |
|||||||
|
число вставок M – M' |
=0 |
изв.
|
неизв.
|
изв.
|
неизв.
|
|||
| по-теря дан-ных |
нет | число фраг- ментов M
|
изв. |
+ |
? |
? |
? |
? |
| неизв. | + | ? | ? | ? | ? | |||
| есть | изв. | + | ? | ? | ? | ? | ||
| неизв. | + | ? | ? | ? | ? | |||
|
Здесь используются следующие обозначения: |
|
|
+ |
– обоснован точный полиномиальный алгоритм; |
|
? |
– статус сложности не выяснен, какие либо алгоритмы неизвестны. |
В варианте наличия потери данных рассматривается частный случай потерь, когда начальная и конечная части фрагмента оказываются обнулены, то есть исходная последовательность сформирована из обрывков эталонных фрагментов.
