Сопоставление шаблонов перестановок в строках

10

Грубо говоря, сопоставление шаблонов перестановок имеет дело с проблемами следующего вида:

При заданных перестановках в S n и в с содержит ли подпоследовательность длины , элементы которой упорядочены по σ ?πSNσSммNπ mτмσ

Например, если и σ = 2 1 3 , то подпоследовательность 3 1 4 матча сгπзнак равно3 1 5 4 2 8 6 7σзнак равно2 1 33 1 4σ . Как вы можете видеть, мы ищем не точное совпадение, а нечто, «похожее» на указанный шаблон.

Кто-нибудь знает, проводилась ли работа по распространению проблем сопоставления шаблонов перестановок на строки? К сожалению, Google не помог, так как хорошо известная проблема сопоставления с образцом в строках не имеет к этому никакого отношения.

Энтони Лабарре
источник
В настоящее время я занимаюсь исследованием аффинных моделей перестановок. Там есть какая-то работа, но большая ее часть доступна только для ученых.
abigail3306

Ответы:

3

Baars, Löh и Swierstra внедрили анализаторы перестановок для Haskell (Журнал функционального программирования / Том 14 / Выпуск 06, с. 635 - 646). Их можно использовать для указания перестановки коллекции синтаксических анализаторов. Если каждый из этих синтаксических анализаторов является необязательным синтаксическим анализатором для одного символа (т. Е. Соответствует ему или ничего), то у вас будут нужные компоненты. Я считаю, что их библиотека доступна с GHC.

Дэйв Кларк
источник
0

Вы должны начать с Revital Eres, Gad M. Landau, Laxmi Parida: Обнаружение модели перестановки в биопоследовательностях . Журнал вычислительной биологии 11 (6): 1050-1060 (2004).

Джанлука Делла Ведова
источник
Это не похоже на одно и то же: они заинтересованы в поиске групп персонажей, которые встречаются вместе, без учета порядка . Та же самая проблема на перестановках упоминается как «идентификация общих интервалов».
Энтони Лабарр
@Labarre Я согласен с вашим комментарием. Должен ли я удалить свой ответ?
Джанлука Делла Ведова
1
Пожалуйста, не удаляйте. Ваш ответ и комментарий Лабарра помогли мне лучше понять вопрос.
Аарон Стерлинг
@ Аарон Стерлинг Тогда мы должны отредактировать вопрос, не так ли?
Джанлука Делла Ведова
2
Я думаю, что вопрос относительно ясен в его нынешнем виде.
Суреш Венкат