入力から最小正規表現を派生させる

文字列を渡すときに "yes"または "no"を返すリモートの "エージェント"があります。このエージェントとのやりとりは高価なので、正のフィードバックと負のフィードバックを与えられた反復的な正規表現を構築し、その構築について知的であるライブラリを見つけることを望んでいます。これにより、送信側で回答をキャッシュすることができます。入力から最小正規表現を派生させる

たとえば、エージェントを「good」でクエリし、「yes」を受信したとします。最初に派生した正規表現は「良い」ものでなければなりません。

私は "goop"で質問し、 "yes"を受け取るとします。私は、得られた正規表現が "良い| goop"ではなく "goo [dp]"であると期待します。

など。

派生正規表現でバックトラッキングなどの非線形時間演算を行う必要はありません。おそらく、生成された正規表現はDFAの下にあるでしょう。誰もがこれを行うことができる任意のc/c + +の正規表現ライブラリを認識していますか？代わりに、これが愚かなアイデアであり、私の本当の問題に対するより良い解決策である理由もまた有用であろう。

出典

2011-09-28 tgoodhart

この質問を単純化できますか？「与えられた文字列のセットに一致する最小正規表現を見つける方法」 –

@Kerrek：私はおおよそだと思いますが、新しい文字列を追加して段階的に構築するのが効率的であることが望ましいと思われます。 –

@Rこれは正しいです。バッチモデルの代わりに新しい文字列を追加することが重要です。 – tgoodhart

あなたの状況に何か不足している場合を除き、私はメモリがちょうど真っ暗なキャッシュを実装するのに十分安価だと思います。たとえば、unordered_map <std::string, bool>です。これはビルドがはるかに簡単であるばかりでなく、ハッシュマップを作成しているので、おそらく高速になるでしょう。これに対する唯一の欠点は、リモート・サービスにbazillion異なる鍵を照会しようとしている場合、これが最良の方法ではない可能性があるということです。

出典

2011-09-28 23:54:04 Matt

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

次に、新しい文字列ごとに、各文字ごとに1つのノードを表示します。私は文字列の終わりにもマーカー文字が必要だと思っています。この文字に達すると、ノードが存在すればyes/noの答えを保持します。

出典

2011-09-29 00:01:49 Trejkaz

これは表の1つのオプションです。しかし、反復を除外するのは良いことです。 – tgoodhart

@tgoodhart繰り返しを除外することによって、同じ文字の連続するノードを持つのではなく、カウントが付けられたノードまたはトライの全体の部分だけを持つことを意味します。 – pmr

@ pmr全部品。理想的には、生成される正規表現は、 "abcabc（？：abc）"の代わりに "abc {2,3}"のようなものになります。 – tgoodhart

入力から最小正規表現を派生させる

答えて

関連する問題