Можно ли рассчитать расстояние редактирования между регулярным выражением и строкой?

Question

Если да, объясните, пожалуйста, как.

Re: что такое расстояние - "Расстояние между двумя строками определяется как минимальное количество правок, необходимых для преобразования одной в другую. "

Например, xyz в XYZ займет 3 редактирования, поэтому строка xYZ ближе к XYZ и xyz.

Если шаблон [0-9] {3} илиэкземпляр 123, тогда a23 будет ближе к шаблону, чем ab3.

Как найти кратчайшее расстояние между регулярным выражением и несоответствующей строкой?

Выше приведен алгоритм расстояния Дамерау – Левенштейна .

Answer 1

Вы можете использовать конечные автоматы, чтобы сделать это эффективно (то есть, линейно по времени). Если вы используете преобразователь, вы даже можете написать спецификацию преобразования довольно компактно и выполнять гораздо больше нюансов преобразований, чем просто вставлять или удалять - см. Википедию для Преобразователь конечного состояния в качестве отправной точки и программное обеспечение, такое как инструментарий FSA или FSA6 (который имеет не совсем стабильную web-demo ) тоже. Есть много библиотек для манипуляции FSA; Я не хочу предполагать, что два предыдущих варианта - ваш единственный или лучший вариант, только два, о которых я слышал.

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

Answer 2

Если вы имеете в виду строку с наименьшим левенштейновым расстоянием между самой близкой совпадающей строкой и образцом, то я почти уверен, что это можно сделать, но вам придется конвертировать Regex в DFA самостоятельно, затем попытайтесьсопоставлять и всякий раз, когда что-то не получается, недетерминировано продолжать, как если бы оно прошло, и отслеживать разницу в числах.Вы можете использовать поиск A * или что-то подобное для этого, хотя это будет весьма неэффективно (O (2 ^ n) в худшем случае)