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