Abbina espressione regolare da un dizionario in C #

Question

Sto cercando di avere una sorta di Data Object (sto pensando a un dizionario) per contenere una TONTA di espressioni regolari come chiavi, quindi devo prendere una stringa di testo e confrontarla con loro per ottenere il valore effettivo dal dizionario. Ho bisogno di un modo efficiente per farlo per un ampio set di dati.

Sono in C # e non sono sicuro da dove cominciare.

Answer 1

Perché non usare 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 tu abbia effettivamente bisogno di espressioni regolari per questo - potresti usare un trie . La rappresentazione dei dizionari è un'applicazione comune per un trie. (Suppongo che intendi un dizionario come in un elenco di parole e non il significato di "array associativo").

Answer 3

Vuoi dire abbinare una stringa con le regex per ottenere una corrispondenza regex? O solo una corrispondenza di testo? In altre parole, la stringa che hai intenzione di ESSERE una di quelle regex o alcuni dati a cui applicare una regex?

Se è una regex e vuoi trovarla nell'elenco, non hai bisogno di un dizionario, quelli sono contenitori in 2 parti. Potresti semplicemente usare un List o StringCollection e chiedere IndexOf (mytString), -1 significa che non è lì.

Answer 4

Se le tue regexps non sono banali stringhe singole e ti interessa l'efficienza, vorresti rappresentarle in una singola NFA (automa a stati finiti non deterministico , con valori negli stati finali. Se è possibile che un input corrisponda a più di una regexp, gli stati finali avrebbero bisogno di un insieme di valori.

A questo punto, sei pronto a prendere in considerazione l'ottimizzazione dell'automa. Se può essere praticamente determinato (questo ti dà un DFA che può essere esponenzialmente più grande dell'NFA), allora fallo assolutamente. Una volta che hai un DFA, puoi minimizzare in modo efficiente (e unicamente fino all'isomorfismo) (ma dato che hai valori nei tuoi stati finali, un'ovvia modifica di è necessario il solito algoritmo ).

Esistono anche tecniche per minimizzare direttamente NFA. Ad esempio, se due stati hanno gli stessi set di suffissi ({(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

Ricorda che se stai pensando di utilizzare un regex più di una volta puoi creare un oggetto regex come compilato e riutilizzarlo per ridurre le spese generali.

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

Usando questo modello sarebbe meglio archiviare un oggetto regex piuttosto che la stringa del modello.