J'essaie d'avoir une sorte d'objet de données (je pense à un dictionnaire) de tenir une tonne d'expressions régulières comme des clés, puis je dois prendre une chaîne de texte et faire correspondre contre eux pour obtenir la valeur réelle du dictionnaire. J'ai besoin d'une façon efficace de le faire pour un grand ensemble de données.
Je suis en C # et je ne sais pas où commencer.
6 Réponses :
Je ne sais pas si vous avez besoin d'expressions régulières pour cela - vous pouvez utiliser un Trie . Représenter des dictionnaires est une application commune pour une trie. (Je suppose que vous voulez dire un dictionnaire comme dans une liste de mots, et pas le sens "associatif table").
Voulez-vous faire correspondre une chaîne contre les regextes pour obtenir une correspondance de regex? Ou juste un correspondant de texte? En d'autres termes, la chaîne est-elle la chaîne que vous allez être l'une de ces regexes ou certaines données pour appliquer une regex à?
Si c'est une regex et que vous souhaitez le trouver dans la liste, vous n'avez pas besoin d'un dictionnaire, ce sont des conteneurs 2 parties. Vous pouvez simplement utiliser une liste ou StringCollection et demander à l'indexof (Mytstring), -1 Signification Ce n'est pas là.
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.
Je vais commencer par cette solution, jusqu'à présent, il fonctionne assez vite avec un dictionnaire d'environ 500 articles. Si cela aggrave, je vais regarder d'autres alternatives. Merci!
Si vos refusions ne sont pas triviales monotrings, et que vous vous souciez d'efficacité, vous voudrez les représenter dans un seul NFA (Automaton à l'état fini-État non déterministe , avec des valeurs dans les états finaux. S'il est possible qu'une entrée correspondait à plus d'une réégycle, les états finaux auraient besoin d'un ensemble de valeurs.
À ce stade, vous êtes prêt à envisager d'optimiser l'automate. Si cela peut être pratiquement déterminé (cela vous donne une DFA pouvant être exponentiellement plus grande que la NFA), puis par tous les moyens. Une fois que vous avez une DFA, vous pouvez le minimiser efficacement (et uniquement à la hauteur de l'isomorphisme) (mais depuis que vous avez des valeurs dans vos états finaux, une modification évidente de Algorithme habituel est nécessaire).
Il existe également des techniques pour minimiser directement la NFA. Par exemple, si deux états ont les mêmes ensembles de suffixe ({(reste de chaîne, valeur)}) ils sont équivalents et peuvent être combinés. L'équivalence dans une NFA acyclique peut être effectuée via Consultation de hachage à partir des états finaux.
N'oubliez pas que si vous envisagez d'utiliser une regex plus d'une fois que vous pouvez créer un objet de regex comme compilé et réutilisé pour réduire les frais généraux.
Regex RegexObject = new Regex(Pattern, RegexOptions.Compiled);
Il y a un Le dictionnaire est relativement stable, avec un certain nombre de tests écrites ici: < / P> Si vous souhaitez le coder vous-même, voici un instantané du code source à compter du moment de la rédaction de cette réponse. Remarque: vous devrez peut-être démêler certains aspects de la bibliothèque pour obtenir ce travail: } Ce qui précède Repo est maintenu par moi sur mon site Web personnel GitHub. RegexpatterndictionaryImpl Tapez le repo suivant qui peut être utilisé dans le but de stocker des regextes comme des clés et de ce que vous voulez comme des valeurs. Ce dictionnaire n'est pas optimisé pour la performance. Il fait simplement une analyse linéaire des touches et les correspond à une chaîne donnée pour renvoyer toutes les valeurs correspondantes. Toutefois, pour les petits cas, ce dictionnaire suffira: DIVULGATION
Lorsque vous liez vos propres ressources, vous devez être explicite à ce sujet. Voir Comment ne pas être un spammeur.
Bon point @tripleee, je devrais vraiment inclure les extraits de code, puis reliez ensuite à la bibliothèque Open Source.
Et je devrais aussi expliquer que ces liens ci-dessus sont mon propre repo. Va réparer la réponse maintenant.
Cependant, cette réponse n'est absolument pas du spam et répond valablement la question de l'OP.
Sur la base des réponses jusqu'à présent, vous voudrez peut-être fournir plus de détails dans votre question sur votre application particulière.
À peu près combien d'expressions sont dans une tonne? Quelle est la taille du texte qu'ils correspondent? À quelle fréquence le nouveau texte sera-t-il fréquemment fourni? À quelle vitesse les résultats doivent-ils être retournés?