Оптимизация генерации

Originally reported on Google Code with ID 345
При генерации тоже можно устроить конкуренцию по типу Вилли, но с другим видом условий.
Завожу чтобы не забыт идею.

Oleg Sychev
допустим брутфорс, а организовать вилли-подобную конкуренцию состояний нельзя?
только по другим критериям состояния конкуренции и другим критериям выбора
Valeriy Streltsov
там есть быстрая генерация с конкуренцией
Oleg Sychev
конкурировать я думаю будут состояния, которые дошли до точки конкатенации на верхнем
уровне
т.е. представим регекс как набор конкатенаций
очевидно, что если мы сгенерируем наименьшее совпадение с каждой, результат будет наименьшим
Valeriy Streltsov
дык конкатенации могут быть переменной длины
Oleg Sychev
так что если два состояния дошли до такой точки, за которой следует конкатенации, которая
наверху - их можно проконкурировать
не
вы не поняли
речь идет об операциях конкатенации которая на самом верхнем уровне
Valeriy Streltsov
сеекунду, пример напишу
Oleg Sychev
как только двумя путями сгенерировался левый операнд такой операции, эти пути можно
конкурировать
понятно что их может и не быть если верхний уровень представлен альтернативой
хотя может и не только верхнего
мы можем выделить состояния, порожденные конкатенациями спец. признаком
Valeriy Streltsov
(a|ver(y)long).(imopossible$to$go$here | equall\1)
когда дойдем до точки, выиграет первый путь, хотя он отбросит единственно возможную
далее ветку
точка это условно где началась конкатенация
Oleg Sychev
там \2 имелось ввиду?
Valeriy Streltsov
ну да
при выключенном мержинге ошибки непроходимых веток не детектятся
Oleg Sychev
ну хорошо, в условия конкуренции запишем наличие одинакового количества совпавших подмасок,
если оно разное - не конкурируют
в смысле не количества а списка подмасок конечно
тогда ваш пример проходит
Valeriy Streltsov
сейчас подумаю
хочется сделать это наподобие вилли-генерации чтобы не отслеживать где конкатенация.
где что
т.е. конкурируют любые два совпадения в одном состоянии
Oleg Sychev
едва ли выйдет
а что, флажок в состоянии это страшно?
другое дело что похоже это любая конкатенация, внутри ветки те же правила действуют
Reported by oasychev on 2015-04-17 23:09:59
Comments (0)
