c++ - 从输入中导出最小正则表达式

Question

我有一个远程“代理”，它在传递字符串时返回“是”或“否”。与这个代理进行通信是昂贵的，所以我希望找到一个库，它可以让我在给出正面和负面反馈的情况下迭代地构建一个正则表达式，同时对它的构建保持智能。这将允许我在发送端缓存答案。

例如，假设我们用“good”查询代理并收到“yes”。最初派生的正则表达式应该是“好”的。

假设我用“goop”查询并收到“是”。我希望派生的正则表达式是“goo[dp]”，而不是“good|goop”。

等等。

在派生的正则表达式中，我不需要回溯或任何其他花哨的非线性时间操作。据推测，生成的正则表达式将是引擎盖下的 DFA。有人知道任何能够做到这一点的 c/c++ 正则表达式库吗？或者，为什么这是一个愚蠢的想法以及对我的实际问题的更好解决方案的原因也将是有用的。

Answer 1

您可以使用Trie而不是正则表达式。

然后对于每个新字符串，您为每个字符遍历一个节点。我怀疑您还需要一个标记字符作为字符串结尾 - 一旦您到达该字符，如果节点存在，它就会保存是/否的答案。

Answer 2

好吧，除非我在你的情况下遗漏了一些东西，否则我认为内存足够便宜，可以直接实现一个愚蠢的缓存——比如说，一个 unordered_map 的<std::string, bool>. 这不仅会更容易构建，而且可能会更快，因为您正在构建哈希映射。唯一的缺点是，如果您要使用大量不同的键查询远程服务，那么这可能不是最好的方法。