Regulären Ausdruck aus einem Wörterbuch in C#

Question

Ich versuche, eine Art von Data Object zu haben (ich denke ein Wörterbuch), um eine TON von regulären Ausdrücken als Schlüssel zu halten, dann muss ich eine Zeichenfolge Text nehmen, und Match gegen sie, um den tatsächlichen Wert aus dem Dictionary zu erhalten. Ich brauche einen effizienten Weg, dies für eine große Menge von Daten zu tun.

Ich bin in C# und ich bin mir nicht sicher, wo ich anfangen soll.

Answer 1

Warum LINQ nicht verwenden?

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. 

Answer 2

Ich bin mir nicht sicher, ob Sie tatsächlich reguläre Ausdrücke dafür benötigen - Sie könnten eine trie verwenden. Die Darstellung von Wörterbüchern ist eine gängige Anwendung für einen Trie. (Ich gehe davon aus, dass Sie ein Wörterbuch wie in einer Liste von Wörtern meinen und nicht die Bedeutung "assoziatives Array").

Answer 3

Meinst du, eine Zeichenfolge gegen die Regexe zu finden, um eine Regex-Übereinstimmung zu erhalten? Oder nur ein Text-Match? Mit anderen Worten, ist die Zeichenfolge, die Sie haben werden, einer dieser Regexes, oder einige Daten, um eine Regex auf?

Wenn es ein Regex ist und Sie es in der Liste finden möchten, brauchen Sie kein Dictionary, das sind 2-teilige Container. Sie könnten einfach eine List oder StringCollection verwenden und nach IndexOf (mytString) fragen, -1 was bedeutet, dass es nicht drin ist.

Answer 4

Wenn Ihr regexps sind nicht trivial Einzelsaiten, und Sie sorgen für Effizienz, würden Sie sie in einem einzigen NFA (nondeterministic finite-state automaton, mit Werten in Endzustände darstellen wollen. Wenn es für eine Eingabe möglich ist, mehr als eine Regexp zu finden, benötigen Endzustände eine Reihe von Werten.

An diesem Punkt sind Sie bereit, über die Optimierung des Automaten nachzudenken. Wenn es praktisch determiniert werden kann (dies gibt Ihnen ein DFA, das exponentiell größer sein kann als das NFA), dann tun Sie das auf jeden Fall. Sobald Sie ein DFA haben, können Sie es effizient (und bis zu Isomorphismus) minimieren (aber da Sie Werte in Ihren Endzuständen haben, ist eine offensichtliche Modifikation des usual algorithm erforderlich).

Es gibt auch Techniken zur direkten Minimierung von NFA. Wenn beispielsweise zwei Zustände die gleichen Suffix-Sätze ({(Rest der Zeichenkette, Wert)} haben), sind sie gleichwertig und können kombiniert werden. Äquivalenz in einem azyklischen NFA kann ausgehend von den Endzuständen über hash-consing erfolgen.

Answer 5

Denken Sie daran, dass Sie, wenn Sie eine Regex mehr als einmal verwenden möchten, ein Regex-Objekt als kompiliert erstellen und es erneut verwenden können, um den Overhead zu reduzieren.

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

Mit diesem Modell speichern Sie am besten ein Regex-Objekt und nicht die Musterzeichenfolge.