Как отсортировать регулярные выражения по степени «специфичности» в отношении конкретной строки?

Question

[nirvimel]

Имеется множество фильтров с регулярками и строка, которая может соответствовать регуляркам из некоторого подмножества этих фильтров. Фильтры должны примеряться к объекту, представленному этой строкой. Порядок применения фильтров имеет значение (последующие фильтры могут перезаписывать результаты работы предыдущих). Требуется выстроить порядок применения фильтров таким образом, чтобы более общие фильтры предшествовали более частным (частные должны иметь возможность переопределять результаты работы более общих). Для этого необходимо отсортировать, соответствующие фильтрам, регулярки в порядке их "специфичности" по отношению к конкретной строке. Например, строке i want to leave соответствуют фильтры 1).*; 2)[\w\s]*; 3)(leave|want|i|to|\s)* именно в таком порядке. Это можно было бы решить зная какому токену шаблона соответствует каждый из символов строки и к какому классу относится этот токен: 1) "любой" символ - .; 2) символ из набора в квадратных скобках; 3) конкретный символ. Тогда можно было бы провести сортировку по множеству полей: 1) количество точно соответствующих символов; 2) количество символов, соответствующих наборам. Или назначить каждому типу соответствия свой "вес" и сортировать по сумме весов. Проблема в том, что мне неизвестна такая regexp-библиотека, которая помимо простой верификации соответствия (да/нет) давала бы еще информацию о соответствии конкретных символов конкретным токенам и типам этих токенов.

Буду благодарен за ваши соображения по сабжу. Интересует или конкретная реализация (релевантная проблеме) на перечисленных языках, или голая идея вообще на любом императивном языке.

Answer 1

[DaneSoul]

А как Вы рассматриваете специфичность фильтров к одной и той же строке?
Для одной строки фильтр или пропускает ее или откидывает.

Соответственно, Ваша задача логична для наборов строк, тогда менее специфичный фильтр будет пропускать больше строк, более специфичный меньше - исходя из этого можно задать фильтрам некие условные веса, по которым их ранжировать.

Если все-таки задача стоит именно так, и оценивается специфичность для одной конкретной строки - можно попробовать мутировать строку разными способами, делая набор строк, прогонять этот набор через фильтры и таким образом свести задачу ранжирования к вышеописанной.

Мутировать строку можно разными способами:
- менять случайные буквы на другие
- менять буквы местами
- убирать\добавлять буквы, слова
- менять слова местами
Таким образом из одной строки можно делать целый тестовый набор.

Соответственно, например мы из строки сделали таким образом 20 тестовых строк, прогнали их фильтрами и посчитали сколько из этих новых строк удовлетворили фильтрам, определив специфичность фильтров в конечном итоге.