изменить строку в соответствии с регулярным выражением

Question

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

т.е. если 1234 - строка, а ^ ([0-9] {6}) $ - регулярное выражение, мне нужно вывести что-то вроде 123412 (выходная строка соответствует регулярному выражению и находится на расстоянии 2 от исходной строки, может быть другая строка, но первый результат будет )

Как это сделать? (без грубой силы ..)

редактировать:

в других случаях, могу ли я получить только расстояние Левенштейна? (без соответствующей строки ...)

или какую другую информацию кроме логического (совпадать или не сопоставить) может дать регулярное выражение?

Answer 1

Если вы знаете о конечном автомате , вы можете сконструировать тот, который представляет ваше регулярное выражение (для этого есть библиотеки). Затем вы запускаете его со своей строкой (1234), и вы окажетесь в каком-то состоянии. Из этого состояния вы выполняете поиск в выдохе , пока не достигнете состояния принятия. Во время поиска вы отслеживаете, какие переходы (символы) вы перебрали. И символы дадут вам самую короткую (или одну из них) строку, которая соответствует вашему регулярному выражению.

Добавлена ​​ссылка: вы можете взглянуть на http://www.brics.dk/automaton/, которая является библиотекой автоматов, реализованной в Орхусском университете (лицензия BSD)

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

package dk.brics.automaton;

public class ExtendedOperations {
    //Taken from Automaton.run and modified to just return state instead of accept (bool)
    static State endState(String s, Automaton a)
    {
        if (!a.deterministic) a.determinize();

        State p = a.initial;
        for (int i = 0; i < s.length(); i++) {
            p = p.step(s.charAt(i));
            if (q == null) return null;
        }
        return p;
    }

    public static String getShortestCompletion(Automaton a, String partlyInput)
    {
        State e = endState(partlyInput, a);

        if (e == null) return null;

        return BasicOperations.getShortestExample(e, true);
    }
}

Во-вторых, небольшой тестовый образец:

package subsetautomaton;

import dk.brics.automaton.*;

public class Main {
    public static void main(String[] args) {
        RegExp re = new RegExp("[a-zA-Z0-9._%+-]+\\@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,6}");
        Automaton a = re.toAutomaton();

        System.out.println(ExtendedOperations.getShortestCompletion(a, "a"));
    }
}

Примером является наивный адрес электронной почты рег. эксп. Обратите внимание, что ^ подразумевается в рег. эксп. и то же самое с $. Во-вторых, @ экранируется с \, потому что это означает «любая строка» в этой реализации.

Результат примера выше: @-.AA