Coincidir con la expresión regular de un diccionario en C #

Question

Estoy tratando de tener algún tipo de Objeto de datos (estoy pensando en un diccionario) para contener una TONELADA de expresiones regulares como claves, luego necesito tomar una cadena de texto y hacer coincidir contra ellas para obtener el valor real del Diccionario. Necesito una forma eficiente de hacer esto para un gran conjunto de datos.

Estoy en C # y no estoy seguro de por dónde empezar.

Answer 1

¿Por qué no usar 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

No estoy seguro de si realmente necesita expresiones regulares para esto, podría usar un trie . Representar diccionarios es una aplicación común para un trie. (Supongo que te refieres a un diccionario como en una lista de palabras, y no al significado de "combinación asociativa").

Answer 3

¿Quiere decir hacer coincidir una cadena con las expresiones regulares para obtener una coincidencia de expresiones regulares? ¿O simplemente una coincidencia de texto? En otras palabras, ¿es la cadena que va a SER una de esas expresiones regulares, o algún dato para APLICAR una expresión regular?

Si ES una expresión regular y desea encontrarla en la lista, no necesita un Diccionario, son contenedores de 2 partes. Simplemente puede usar una lista o StringCollection, y solicitar IndexOf (mytString), -1 significa que no está allí.

Answer 4

Si sus expresiones regulares no son simples cadenas triviales, y le interesa la eficiencia, querría representarlas en una sola NFA (autómata de estado finito no determinista , con valores en estados finales. Si es posible que una entrada coincida con más de una expresión regular, entonces los estados finales necesitarán un conjunto de valores.

En este punto, está preparado para considerar la optimización del autómata. Si puede determinarse en la práctica (esto le da un DFA que puede ser exponencialmente más grande que el NFA), entonces, por supuesto, hágalo. Una vez que tenga un DFA, puede minimizarlo de manera eficiente (y únicamente hasta el isomorfismo) (pero como tiene valores en sus estados finales, una modificación obvia de se necesita el algoritmo habitual ).

También hay técnicas para minimizar NFA directamente. Por ejemplo, si dos estados tienen los mismos conjuntos de sufijos ({(resto de cadena, valor)}) son equivalentes y se pueden combinar. La equivalencia en una NFA acíclica se puede hacer a través de hash-consing a partir de los estados finales.

Answer 5

Recuerde que si planea usar una expresión regular más de una vez, puede crear un objeto de expresión regular como compilado y reutilizarlo para reducir la sobrecarga.

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

Utilizando este modelo, sería mejor que almacenes un objeto de expresión regular en lugar de la cadena de patrón.