c++ - 入力から最小限の正規表現を導出する

Question

文字列を渡されたときに「はい」または「いいえ」を返すリモート「エージェント」があります。このエージェントとの通信にはコストがかかるため、正と負のフィードバックを与えられた正規表現を反復的に構築できるライブラリを見つけたいと思っています。これにより、送信側で回答をキャッシュできます。

たとえば、エージェントに「良い」と問い合わせて、「はい」を受け取ったとします。最初に派生した正規表現は「良い」はずです。

次に「goop」でクエリを実行し、「yes」を受け取ったとします。派生した正規表現は、「good|goop」ではなく「goo[dp]」になると思います。

などなど。

派生した正規表現では、バックトラッキングやその他の派手な非線形時間操作は必要ありません。おそらく、生成された正規表現は内部の DFA になります。これを実行できる c/c++ 正規表現ライブラリを知っている人はいますか? あるいは、これがばかげた考えである理由と、実際の問題に対するより良い解決策も役立ちます。

Answer 1

正規表現ではなく、Trieを使用できます。

次に、新しい文字列ごとに、文字ごとに 1 つのノードを試行します。文字列の末尾にマーカー文字も必要になると思います-この文字に到達すると、ノードが存在する場合、はい/いいえの答えが保持されます。

Answer 2

まあ、あなたの状況で何かが欠けていない限り、メモリは単純にダムキャッシュを実装するのに十分安いと思います-たとえば、の unordered_map <std::string, bool>. ハッシュ マップを作成しているので、これは作成がはるかに簡単になるだけでなく、おそらく高速になります。これの唯一の欠点は、膨大な数の異なるキーを使用してリモート サービスにクエリを実行する場合、これは最善の方法ではない可能性があることです。