Регулярные выражения - вес для совпадений

«Интуитивно» понятно

Этим человек и отличается от бездушной машины. Задача решается, но критерии интуитивности должны быть сформированы ТОБОЙ в жёсткой логике.

Чем тебя не устраивает перечисление всех вариантов в группах? ((Вариант A)|(Вариант B)|(Вариант С))

Мне непонятно, почему последнее «дальше», чем предпоследнее.

Была у меня задача, в которой можно было бы применить решение из этой темы: Поиск в множестве шаблонов по конкретному образцу

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

Последнее матчит 4 символа диапазоном, предпоследнее только 2. Если не было бы звёздочек по бокам, то близость можно было бы оценить суммой log(Wk), Wk длина диапазона маски для k-го символа строки.

Можно попробовать строить дерево: abc -> { {X}bc, a{X}c, ab{X}, и {X}abc, a{X}bc .. } и смотреть какую ссумарную глубину допистит каждый регэксп. Это навскидку, надо смотреть.

// ссумарную глубину - ну понятно, предел в общем случае какой-то придется вводить

Ах да, лучше не просто количество, а нормировать каждый узел по длине левенштайна.

Зато в предпоследнем сам диапазон в несколько раз шире.

Точно, не заметил. Ну тогда да, не понятна логика ТСа.

Еще не решал, но предположу навскидку.

1. Весовой функции, вычисляемой за O(length(regexp+string)) не существует.

2. Без поиска в пространстве некоторых «состояний» не обойтись.

3. Существует такое понятие, как эвристический поиск.

Обещаю подумать. Самому стало интересно. Задача сложной не выглядит.

Даже не знаю, что значит интуитивно.

Регулярное выражение описывает язык. Во всех случаях кроме первого языки бесконечны и... что значит «ближе» в таком случае - не ясно.

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

Такое вот имхо.

потому что в последнем больше компонентов неограниченной длины

AGREP, an approximate GREP (см. секцию Algorithms).

А зчем тебе это нужно? Уже несколько человек за последние дни встречаю с такими вопросами.

Критерий «наиболее близкое» неопределен.

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

Нужно ли для этого реализация самого движка регэкспов, вопрос открытый. :)

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

Это тоже реализационно зависимо, т.е. неопределено.

«Интуитивно» понятно

Тут две проблемы.
Во-первых, не совсем. У тебя почему-то строки, различающиеся в начале, более схожи, чем строки, различающиеся концом. Иногда доходит до спорных моментов. Вот, например:

.*abcdef$
.*abcdef.*

А почему не наоборот?

.*ab[bc]def.*
.*ab[a-z]def.*

То есть abddef менее похоже, чем abbdef?

.*ab[a-zA-Z]def.*

Э... а как тут сформулировать общее правило? Ну, допустим, когда вся строка из строчных букв, заглавные могут отличаться. А если иходный запрос был AbCdEf?

.*ab[c-f]+.*

Почему? А если искали abcxyz?

А во-вторых, с математической точки зрения, решулярные выражения описывают довольно простой класс языков, обрабатываемый довольно простыми алгоритмами. ОК, конечно, на практике в программировании гораздо более широкий класс формальных языков называют «регулярными», но тем не менее, не любые формальные языки. Такие «подобия» могут сильно усложнить работу программ.

Для решения конкретной задачи можно посоветовать взять последнее выражение из списка, потом список результатов отфильтровать через предпоследнее, потом через предпредпоследнее и так далее, получится несколько списков результатов с разной степенью совпадений.

выражения будут «ближе» к строке в порядке убывания

, если мощность множества строк, удовлетворяющих данному выражению будет меньше. В таком смысле?

AGREP, an approximate GREP (см. секцию Algorithms).

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

А ТСу надо каким-то образом на основании заданного регулярного выражения для языка L₁ составить языки L₂ ⊃ L₃ ⊃ L₄ и т.д. и найти вхождения даже для самого всеобъемлющего языка в цепочке, причём чётких критериев он не указал.

Да в этой задаче много чего не указано. Оно так часто и бывает - надо самим придумать адекватное определение терминам «близко», «похожи», «эквивалентны» и т.п.

Предлагаю формализацию, как я ее понял.

Пусть S - множество существующих строк ограниченной длины, m(r,s) - матчится ли строчка s к выражению r, NS(r) - количество существующих строк s из S, удовлетворяющих условию m(r,s) - натуральное число, далее вводим отношение порядка на множестве регулярок: r1 < r2 <=> NS(r1) < NS(r2), и называть это будем «r1 более узкое выражение, чем r2». Тогда для любой строки s1 и любого набора регулярок (r1...rn) можно извлечь подмножество (r[i1]...r[ik]) таких, что для любого i от 1 до k m(r,s1) и далее в этом подмножестве найти минимум NS(r[j]), и эта регулярка r[j] объявляется наиболее близкой к строке s1.

А по-хорошему надо обрабатывать бесконечные строки, но я не придумал, как.