Nach regulärem Ausdruck aus einem Wörterbuch in C #

Question

Ich versuche, eine Art von Daten-Objekt zu haben (ich bin ein Wörterbuch zu denken) eine TON von regulären Ausdrücken zu halten, wie Tasten, dann muss ich eine Reihe von Text nehmen und Spiel gegen sie den tatsächlichen Wert zu erhalten aus dem Dictionary. Ich brauche eine effiziente Möglichkeit, dies für eine große Menge von Daten zu tun.

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

Answer 1

Warum nicht LINQ 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 für diese benötigen - Sie ein trie . Stellvertretend für Wörterbücher ist eine gemeinsame Anwendung für ein Trie. (Ich nehme an, Sie ein Wörterbuch wie in einer Liste von Worten bedeuten, und nicht das „assoziative Array“ bedeutet).

Answer 3

Meinen Sie damit gegen die reguläre Ausdrücke einen String Match einen Regex zu bekommen? Oder nur ein Text überein? Mit anderen Worten, ist die Zeichenfolge, die Sie einer jener Regexes, oder einige Daten zu haben, gehen einen regulären Ausdruck bewerben?

Wenn es ein regulärer Ausdruck ist, und Sie wollen, dass es in der Liste zu finden, müssen Sie ein Wörterbuch nicht brauchen, sind solche mit 2 Teilbehälter. Sie könnten nur eine Liste oder String verwenden, und fragen Sie nach IndexOf (mytString), -1 bedeutet, da ist es nicht.

Answer 4

Wenn Ihr regexps sind nicht trivial Einzelsaiten, und Sie sorgen für Effizienz, würden Sie sie in einem einzigen darstellen wollen NFA (nichtdeterministischen endlichen Automaten , mit Werten in Endzustände. Wenn es möglich ist, für eine Eingabe mehr als ein regexp übereinstimmen, dann Endzustände würde eine Reihe von Werten müssen.

An diesem Punkt sind Sie bereit, die Optimierung des Automaten zu betrachten. Wenn es praktisch deterministisch sein kann (diese geben Ihnen einen DFA, die exponentiell größer ist als der NFA sein kann), dann mit allen Mitteln tun. Sobald Sie eine DFA haben, können Sie effizient (und eindeutig bis auf Isomorphie) minimiert (aber da Sie Werte in Ihren Endzustände haben, eine offensichtliche Modifikation des üblicher Algorithmus benötigt wird).

Es gibt auch Techniken zur Minimierung direkt NFA. Zum Beispiel, wenn zwei Staaten haben die gleichen Suffix-Sets ({(Rest von string, value)}) sie sind gleichwertig und können kombiniert werden. Equivalence in einem acyclischen NFA über Hash-consing von den Endzuständen Start erfolgen.

Answer 5

Beachten Sie, dass wenn Sie sich mit einem regex planen mehr als einmal Sie ein Regex-Objekt als kompilierte erstellen und wiederverwenden es Aufwand zu verringern.

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

Dieses Modell Verwenden Sie am besten Speichern eines Regex-Objekt sein würde, anstatt die Musterzeichenfolge.