C＃の辞書の正規表現に一致

StackOverflow https://stackoverflow.com/questions/1408057

  •  05-07-2019
  •  | 
  •  

質問

キーとして正規表現のトンを保持するために何らかのデータオブジェクト（辞書を考えている）をしようとしています辞書から。大量のデータに対してこれを効率的に行う方法が必要です。

私はC＃を使用しており、どこから始めればよいかわかりません。

役に立ちましたか？

解決

LINQを使用しない理由

Dictionary<string, string> myCollection = new Dictionary<string, string>();

myCollection.Add("(.*)orange(.*)", "Oranges are a fruit.");
myCollection.Add("(.*)apple(.*)", "Apples have pips.");
myCollection.Add("(.*)dog(.*)", "Dogs are mammals.");
// ...

string input = "tell me about apples and oranges";

var results = from result in myCollection
              where Regex.Match(input, result.Key, RegexOptions.Singleline).Success
              select result;

foreach (var result in results)
{
    Console.WriteLine(result.Value);
}

// OUTPUT:
//
// Oranges are a fruit.
// Apples have pips.

他のヒント

実際にこれに正規表現が必要かどうかわかりません-トライ。辞書の表現は、トライの一般的なアプリケーションです。 （「連想配列」の意味ではなく、単語のリストのように辞書を意味すると仮定しています。）

正規表現と一致する文字列を正規表現と照合するということですか？または単にテキストが一致しますか？言い換えれば、これらの正規表現のいずれかになる文字列、または正規表現を適用するデータですか？

正規表現であり、リストで検索する場合、辞書は必要ありません。これらは2つの部分からなるコンテナです。 ListまたはStringCollectionを使用して、IndexOf（mytString）を要求できます。-1は、そこにないことを意味します。

正規表現が単純な単一文字列ではなく、効率を重視する場合は、単一の NFA（非決定的有限状態オートマトン、最終状態の値。入力が複数の正規表現に一致する可能性がある場合、最終状態には値のセットが必要になります。

この時点で、オートマトンの最適化を検討する準備が整いました。実際に決定できる場合（これにより、DFAがNFAよりも指数関数的に大きくなる可能性があります）、どうしてもそれを行います。 DFAを取得したら、効率的に（そして一意的に同型まで）最小化できます（ただし、最終状態に値があるため、通常のアルゴリズムが必要です。

NFAを直接最小化する手法もあります。たとえば、2つの状態に同じ接尾辞セット（{（rest of string、value）}）がある場合、それらは同等であり、組み合わせることができます。非環状NFAでの等価性は、最終状態から開始してハッシュコンシングを介して行うことができます。

正規表現を複数回使用する予定がある場合は、コンパイル済みの正規表現オブジェクトを作成し、再利用してオーバーヘッドを削減できることを思い出してください。

Regex RegexObject = new Regex(Pattern, RegexOptions.Compiled);

このモデルを使用すると、パターン文字列ではなく、正規表現オブジェクトを最適に保存できます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top