Получите минимальное регулярное выражение из ввода

Question

У меня есть удаленный «агент», который возвращает «да» или «нет» при передаче строки. Общение с этим агентом стоит дорого, поэтому я надеюсь найти библиотеку, которая позволит мне итеративно строить регулярные выражения с учетом положительных и отрицательных отзывов, при этом не забывая о его построении. Это позволило бы мне кэшировать ответы на отправляющей стороне.

Например, предположим, что мы запрашиваем агента «хорошо» и получаем «да». Исходное производное регулярное выражение должно быть «хорошим».

Предположим, я запрашиваю "goop" и получаю "yes". Я ожидаю, что производное регулярное выражение будет «goo [dp]», а не «good | goop».

И так далее.

Мне не нужно возвращаться назад или выполнять какие-либо необычные нелинейные операции с временем в моем производном регулярном выражении. Предположительно, сгенерированное регулярное выражение будет DFA под капотом. Кто-нибудь знает какие-либо библиотеки регулярных выражений c / c ++, способные сделать это? В качестве альтернативы, причины, почему это глупая идея и лучшие решения моей настоящей проблемы, также были бы полезны.

Answer 1

Вместо регулярного выражения вы можете использовать Trie .

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

Answer 2

Ну, если я не упустил что-то в вашей ситуации, я думаю, что память достаточно дешевая, чтобы просто реализовать тупой кеш - скажем, unordered_map <std::string, bool>. Мало того, что это будет намного легче построить, но, вероятно, будет быстрее, так как вы строите хэш-карту. Единственным недостатком этого является то, что если вы собирались запросить удаленную службу с помощью нескольких разных ключей, то это может быть не лучшим подходом.