Обнаружение гибких шаблонов?

#regex #algorithm #artificial-intelligence #decision-tree

#регулярное выражение #алгоритм #искусственный интеллект #дерево решений

Вопрос:

Мне нужно обнаружить гибкий шаблон в наборе данных. Например, шаблон, подобный:

 0{1},1{*},0{1}
(the number between { and } is how many times a number may occur)

Это будет соответствовать:

 0,1,0
0,1,1,1,1,1,0

Выше один по-прежнему прост, здесь более сложный:

 0{1},( 1{*} | 1{*},2{1},1{*} ),0{1}
(the | pipe character is a "or")

Это будет соответствовать:

 0,1,0
0,1,1,1,1,1,0
0,1,2,1,0
0,1,1,1,1,1,2,1,0

Мне трудно понять, как я могу обнаружить эти гибкие шаблоны.

Моей первой мыслью было сгенерировать какое-то дерево решений, но это становится довольно сложной задачей, когда шаблоны становятся еще более сложными, особенно потому, что вам нужно вернуться назад в таком дереве и пометить пути как «не работающие» и попробовать альтернативный маршрут.

Может быть, есть лучшее решение для такого рода проблем?

[редактировать] Упс, возможно, я слишком упростил свой вопрос, маленькие числа 0,1,2 в моем случае не числа, а объект со многими свойствами. Мое определение шаблона будет соответствовать одному или комбинации этих свойств объекта.

1. Разве вы не можете просто переписать свои шаблоны в обычные регулярные выражения?

2. @svick , я думаю, что, возможно, я слишком упростил вещи, шаблоны содержат такие вещи, как (i> x amp;amp; i

Ответ №1:

Похоже, вы говорите о создании средства сопоставления регулярных выражений. Каждое регулярное выражение может быть сформулировано как DFA. Вот ссылка, объясняющая, как это сделать.