Задачи поиска ближайшей строки и ближайшей подстроки: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
'''Более общая задача''' | '''Более общая задача''' | ||
Задача выбора различающей подстроки получает на входе два множества строк, B и G. Требуется найти подстроку неуказанной длины (обозначаемой L), такую, что она оказывается близкой к подстрокам каждой строки из B и далекой от любой подстроки длины L строк из G. Впрочем, мы можем пройти все возможные значения L и предположить, что каждая строка в G имеет одну и ту же длину L, поскольку множество G может быть реконструировано с тем, чтобы содержать все подстроки длины L в каждой из хороших строк. | Задача ''выбора различающей подстроки'' получает на входе два множества строк, B и G. Требуется найти подстроку неуказанной длины (обозначаемой L), такую, что она оказывается близкой к подстрокам каждой строки из B и далекой от любой подстроки длины L строк из G. Впрочем, мы можем пройти все возможные значения L и предположить, что каждая строка в G имеет одну и ту же длину L, поскольку множество G может быть реконструировано с тем, чтобы содержать все подстроки длины L в каждой из хороших строк. | ||
Формальное определение задачи выглядит следующим образом. Пусть даны множество | Формальное определение задачи выглядит следующим образом. Пусть даны множество <math>B = \{ s_1, s_2, ..., s_{n_1} \}</math> из <math>n_1</math> (плохих) строк длиной не менее L и множество <math>G = \{ g_1, g_2, ..., g_{n_2} \}</math> из <math>n_2</math> (хороших) строк, длина которых в точности равна, а также два целых числа <math>d_b</math> и <math>d_g</math> <math>(d_b \le d_g)</math>. Задача выбора различающей подстроки (distinguishing substring selection problem, DSSP) заключается в нахождении строки s, такой, что для каждой строки si 2 B существует имеющая длину L подстрока ti строки si с d(s; ti) < db, и для каждой строки gi 2 G имеет место d(s;gi) > dg. Здесь d(;) обозначает расстояние Хэмминга между двумя строками. Если все строки в множестве B также имеют длину L, задача называется задачей поиска различающей строки (distinguishing string problem, DSP). | ||