Соответствие регулярному выражению из словаря в C #

Question

Я пытаюсь создать какой-то объект данных (я думаю, словарь) для хранения TON регулярных выражений в качестве ключей, затем мне нужно взять строку текста и сопоставить ее, чтобы получить фактическое значение из словаря. Мне нужен эффективный способ сделать это для большого набора данных.

Я нахожусь в C # и не знаю, с чего начать.

Answer 1

Почему бы не использовать 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

Я не уверен, что вам действительно нужны регулярные выражения для этого - вы можете использовать trie . Представление словарей является распространенным приложением для дерева. (Я предполагаю, что вы имеете в виду словарь в виде списка слов, а не «ассоциативный массив», означающий).

Answer 3

Вы имеете в виду сопоставление строки с регулярными выражениями, чтобы получить соответствие регулярному выражению? Или просто текстовое совпадение? Другими словами, является ли строка, в которой вы собираетесь быть, одним из этих регулярных выражений, или какие-либо данные, чтобы ПРИМЕНИТЬ регулярное выражение?

Если это регулярное выражение и вы хотите найти его в списке, вам не нужен словарь, это 2 контейнера для частей. Вы можете просто использовать List или StringCollection и запросить IndexOf (mytString), -1, что означает, что его там нет.

Answer 4

Если ваши регулярные выражения не являются тривиальными однострочными и вам нужна эффективность, вам нужно представить их в одной NFA (недетерминированный автомат конечных состояний , со значениями в конечных состояниях. Если вход может соответствовать нескольким регулярным выражениям, тогда конечным состояниям потребуется набор значений.

На данный момент вы готовы рассмотреть вопрос об оптимизации автомата. Если это может быть практически определено (это даст вам DFA, который может быть экспоненциально больше, чем NFA), то непременно сделайте это. Получив DFA, вы можете эффективно (и однозначно с точностью до изоморфизма) минимизировать его (но поскольку у вас есть значения в ваших конечных состояниях, очевидное изменение необходим обычный алгоритм ).

Существуют также методы минимизации NFA напрямую. Например, если два состояния имеют одинаковые наборы суффиксов ({(остаток строки, значение)}), они эквивалентны и могут быть объединены. Эквивалентность в ациклическом NFA можно сделать с помощью хеш-консинга , начиная с конечных состояний.

Answer 5

Помните, что если вы планируете использовать регулярное выражение более одного раза, вы можете создать его как скомпилированный и использовать повторно, чтобы уменьшить накладные расходы.

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

Используя эту модель, лучше всего хранить объект регулярного выражения, а не строку шаблона.