Соответствие регулярному выражению из словаря в 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

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

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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