12

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

Предположим, что я делаю поиск по подстрокам "abc", "bc", "bcd" and "abcd".

"bc" это наиболее общая подстрока, результат поиска по "bc" вернет все результаты поиска, что и поиск по "abc", "bcd" и "abcd".

Строки "abc" и "bcd" более общие, чем "abcd".

Но строки "abc" и "bcd" не сравнимы. Поиск по этим строкам вернет подмножества, которые могут не совпадать и не быть вложенными друг в друга.

Этот же пример в регулярных выражениях:

var bcRegex = /bc/;
var abcRegex = /abc/;
var bcdRegex = /bcd/;
var abcdRegex = /abcd/;

function regexComparator(regex1, regex2){...}

regexComparator(bcRegex, abcRegex); // => больше
regexComparator(abcRegex, bcRegex); // => меньше
regexComparator(bcRegex, bcRegex); // => равны
regexComparator(abcRegex, bcdRegex); // => не сравнимы

Возможно ли сделать функцию regexComparator для топологической сортировки регулярных выражений в общем случае для любых регулярных выражений?

8
  • 7
    Теоретически возможно, но очень сложно. Вам придется разбивать регулярные выражения на деревья токенов и сравнивать эти деревья на вхождение друг в друга, учитывая всякие edge cases типа "[a-z][a-z0-9]+ входит в \w*"
    – etki
    26 сен 2016 в 11:31
  • 3
    Добавлю: топологическая сортировка обычно делается не компаратором... 26 сен 2016 в 12:18
  • 1
    Может подойти к задаче с другого конца? какова цель подобных манипуляций? 24 июл 2021 в 23:15
  • 1
    Я голосую за закрытие этого вопроса, потому что автор в комментариях явно указывает о том, что вопрос не актуален 7 янв в 2:43
  • 1
    @hedgehogues, неважно, актуален ли вопрос для автора.
    – Qwertiy
    7 янв в 14:32

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Посмотрите другие вопросы с метками или задайте свой вопрос.