Corresponde à expressão regular de um dicionário em C #

Question

Eu estou tentando ter algum tipo de objecto de dados (estou pensando um dicionário) para manter uma tonelada de expressões regulares como chaves, então eu preciso tomar uma seqüência de texto, e jogo contra eles para obter o valor real do dicionário. Eu preciso de uma maneira eficiente de fazer isso por um grande conjunto de dados.

Eu estou em C # e eu não tenho certeza por onde começar.

Answer 1

Por que não 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

Eu não tenho certeza se você realmente precisa de expressões regulares para isso - você poderia usar um trie . Representando dicionários é uma aplicação comum para um trie. (Eu estou supondo que você quer dizer um dicionário como em uma lista de palavras, e não a "matriz associativa" significado).

Answer 3

Você quer dizer encontrar uma string contra as expressões regulares para obter um jogo regex? Ou apenas um texto combinar? Em outras palavras, é a string que você vai ser uma daquelas expressões regulares, ou alguns dados para aplicar um regex para?

Se é um regex e você quer encontrá-lo na lista, você não precisa de um dicionário, esses são 2 recipientes de peças. Você poderia usar apenas uma lista ou StringCollection, e pedir IndexOf (mytString), -1 que significa que não está lá.

Answer 4

Se seus regexps não são triviais single-cordas, e você se importa com eficiência, você gostaria de representá-los em um único NFA (de estado finito não determinístico autômato , com valores em estados finais. Se é possível para uma entrada para corresponder mais do que uma expressão regular, então estados finais seria necessário um conjunto de valores.

Neste ponto, você está preparado para considerar otimizar o autômato. Se ele pode ser praticamente determinized (isto dará um DFA que podem ser exponencialmente maior do que o NFA), em seguida, por todos os meios fazê-lo. Depois de ter um DFA, você pode eficientemente (e exclusivamente a menos de isomorfismo) minimizá-lo (mas desde que você tem valores em seus estados finais, uma modificação óbvia do algoritmo de costume é necessária).

Existem também técnicas para minimizar NFA diretamente. Por exemplo, se dois estados têm os mesmos conjuntos de sufixos ({(resto da string, value)}) eles são equivalentes e podem ser combinados. Equivalência em um AFN acíclico pode ser feito através de mistura-consing a partir dos estados finais.

Answer 5

Lembre-se que se você estiver planejando usar um regex mais de uma vez, você pode criar um objeto de regex como compilado e reutilizá-lo para reduzir a sobrecarga.

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

Usando este modelo você seria melhor guardar um objeto regex em vez da cadeia padrão.