Corrispondenza regolare da un dizionario in C#

Question

Sto cercando di avere una sorta di oggetto dati (sto pensando un dizionario) per contenere un numero di espressioni regolari come chiavi, quindi ho bisogno di prendere una stringa di testo, e combacia con loro per ottenere il valore reale dal Dizionario. Ho bisogno di un modo efficiente per fare questo per un grande insieme di dati.

Sono in C# e non so da dove cominciare.

Answer 1

Perché non utilizzare 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

Non sono sicuro che in questo caso sia effettivamente necessario utilizzare espressioni regolari: è possibile utilizzare uno trie. Rappresentare i dizionari è un'applicazione comune per un trie. (Suppongo tu intenda un dizionario come in una lista di parole, e non il significato di "matrice associativa").

Answer 3

Intendi abbinare una stringa alle espressioni regolari per ottenere una corrispondenza regolare? O solo una corrispondenza testuale? In altre parole, la stringa che hai intenzione di ESSERE una di quelle regex, o alcuni dati per APPLICARE una regex a?

Se si tratta di un'espressione regolare e si desidera trovarla nell'elenco, non è necessario un dizionario, questi sono contenitori in 2 parti. Potresti semplicemente usare una List o StringCollection e chiedere IndexOf (mytString), -1 che significa che non è lì.

Answer 4

Se le espressioni regolari non sono banali singole corde, e la cura per l'efficienza, che ci si vuole rappresentare in un unico NFA (nondeterministic finite-state automaton, con valori in stati finali. Se è possibile che un input corrisponda a più di una regexp, gli stati finali necessitano di un set di valori.

A questo punto, siete pronti a prendere in considerazione l'ottimizzazione dell'automa. Se può essere praticamente determinato (questo ti dà un DFA che può essere esponenzialmente più grande del NFA), allora con tutti i mezzi farlo. Una volta che si dispone di un DFA, è possibile ridurlo in modo efficiente (e in modo univoco fino all'isomorfismo) (ma poiché si hanno valori negli stati finali, è necessaria una modifica evidente di usual algorithm).

Esistono anche tecniche per minimizzare direttamente NFA. Ad esempio, se due stati hanno gli stessi suffissi set ({resto della stringa, valore)}) sono equivalenti e possono essere combinati. L'equivalenza in un NFA aciclico può essere effettuata tramite hash-consing a partire dagli stati finali.

Answer 5

Ricordare che se si prevede di utilizzare un'espressione regolare più di una volta è possibile creare un oggetto di espressioni regolari come compilato e riutilizzarlo per ridurre l'overhead.

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

Utilizzando questo modello si memorizzerebbe meglio un oggetto regex piuttosto che la stringa del modello.