Faire correspondre l'expression régulière d'un dictionnaire en C #

Question

J'essaie d'avoir une sorte d'objet de données (je pense un dictionnaire) pour contenir une tonne d'expressions régulières en tant que clés, puis je dois prendre une chaîne de texte et la faire correspondre à celle-ci pour obtenir la valeur réelle. du dictionnaire. J'ai besoin d'un moyen efficace de le faire pour un grand ensemble de données.

Je suis en C # et je ne sais pas par où commencer.

Answer 1

Pourquoi ne pas utiliser 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.

Answer 2

Je ne sais pas si vous avez réellement besoin d'expressions régulières pour cela. Vous pouvez utiliser un trie . La représentation de dictionnaires est une application courante pour un test. (Je suppose que vous entendez un dictionnaire comme une liste de mots et non le sens du terme "tableau associatif").

Answer 3

Voulez-vous dire faire correspondre une chaîne avec les regex pour obtenir un match de regex? Ou juste une correspondance de texte? En d’autres termes, est-ce que la chaîne que vous avez en train d’être BE être l’une de ces regex, ou des données auxquelles appliquer une regex?

S'il s'agit d'une regex et que vous voulez la trouver dans la liste, vous n'avez pas besoin d'un dictionnaire, ce sont des conteneurs en 2 parties. Vous pouvez simplement utiliser une liste ou une StringCollection et demander IndexOf (mytString), -1 signifiant que ce n'est pas là.

Answer 4

Si vos expressions rationnelles ne sont pas des chaînes simples triviales et que vous vous souciez de l'efficacité, vous voudriez les représenter en un seul NFA (automate à états finis non déterministe , avec des valeurs dans les états finaux. S'il est possible qu'une entrée corresponde à plusieurs expressions rationnelles, les états finaux nécessitent alors un ensemble de valeurs.

À ce stade, vous êtes prêt à envisager d’optimiser l’automate. Si cela peut être déterminé de manière pratique (cela vous donne un DFA qui peut être exponentiellement plus grand que le NFA), alors faites-le bien. Une fois que vous avez un DFA, vous pouvez le minimiser de manière efficace (et uniquement jusqu’à l’isomorphisme) (mais puisque vous avez des valeurs dans vos états finaux, une modification évidente du l’algorithme habituel est nécessaire).

Il existe également des techniques permettant de minimiser directement les NFA. Par exemple, si deux états ont les mêmes ensembles de suffixes ({(reste de chaîne, valeur)}), ils sont équivalents et peuvent être combinés. L’équivalence dans une NFA acyclique peut être réalisée via la la gestion du hachage à partir des états finaux.

Answer 5

N'oubliez pas que si vous prévoyez d'utiliser une expression rationnelle plus d'une fois, vous pouvez créer un objet d'expression régulière compilé et le réutiliser pour réduire les frais généraux.

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

En utilisant ce modèle, il serait préférable de stocker un objet regex plutôt que la chaîne de modèle.