c# - 匹配 C# 字典中的正则表达式

Question

我正在尝试使用某种数据对象（我正在考虑字典）来保存大量正则表达式作为键，然后我需要获取一串文本，并与它们匹配以从字典中获取实际值. 我需要一种有效的方法来处理大量数据。

我在 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。表示字典是 trie 的常见应用。（我假设您的意思是单词列表中的字典，而不是“关联数组”的含义）。

Answer 3

您是说将字符串与正则表达式匹配以获得正则表达式匹配吗？还是只是文本匹配？换句话说，您将要成为这些正则表达式之一的字符串，还是要应用正则表达式的某些数据？

如果它是正则表达式并且您想在列表中找到它，则不需要字典，它们是 2 部分容器。您可以只使用 List 或 StringCollection，并要求 IndexOf(mytString), -1 表示它不在其中。

Answer 4

如果您的正则表达式不是简单的单字符串，并且您关心效率，那么您希望在单个NFA（非确定性有限状态自动机，具有最终状态的值）中表示它们。如果输入可能匹配更多不是一个正则表达式，那么最终状态将需要一组值。

此时，您已准备好考虑优化自动机。如果它可以实际确定（这给你一个可以比 NFA 大得多的 DFA），那么一定要这样做。一旦你有了一个 DFA，你就可以有效地（并且唯一地达到同构）最小化它（但是由于你在最终状态中有值，因此需要对通常的算法进行明显的修改）。

还有一些技术可以直接最小化 NFA。例如，如果两个状态具有相同的后缀集 ({(rest of string,value)})，它们是等效的并且可以组合。非循环 NFA 中的等价性可以通过从最终状态开始的哈希计算来完成。

Answer 5

请记住，如果您计划多次使用正则表达式，您可以创建一个已编译的正则表达式对象并重新使用它以减少开销。

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

使用此模型，您最好存储正则表达式对象而不是模式字符串。

Answer 6

以下 repo 中有一种RegexPatternDictionaryImpl类型可用于将正则表达式存储为键以及您想要的任何值作为值。不过，这本词典并未针对性能进行优化。它只是对键进行线性扫描并将它们与给定的字符串匹配以返回所有匹配的值。但是，对于小型用例，这本字典就足够了：

https://github.com/ColmBhandal/CsharpExtras/blob/master/CsharpExtras/Dictionary/RegexPatternDictionaryImpl.cs

字典比较稳定，这里写了很多测试：

https://github.com/ColmBhandal/CsharpExtras/blob/master/CsharpExtrasTest/Dictionary/RegexPatternDictionaryTest.cs

如果您想自己编写代码，这里是编写此答案时源代码的快照。注意：您可能必须解开库的某些方面才能使其正常工作：

namespace CsharpExtras.Dictionary
{
    public class RegexPatternDictionaryImpl<TValue> : 
      IRegexPatternDictionary<TValue>
    {
    private readonly IDictionary<string, TValue> _baseDictionary;
    private readonly IDictionary<Regex, string> _regexDictionary;

    public RegexPatternDictionaryImpl()
    {
        _baseDictionary = new Dictionary<string, TValue>();
        _regexDictionary = new Dictionary<Regex, string>();
    }

    public void Add(string pattern, TValue value)
    {
        AddRegexToDictionary(pattern, pattern, value);
    }

    public ICollection<TValue> FindAllValuesThatMatch(string textKey)
    {
        ICollection<TValue> result = new List<TValue>();
        foreach (var item in _regexDictionary.Where(r => r.Key.IsMatch(textKey)))
        {
            result.Add(_baseDictionary[item.Value.ToString()]);
        }
        return result;
    }

    public bool HasMatch(string textKey)
    {
        return _regexDictionary.Any(r => r.Key.IsMatch(textKey));
    }

    public ICollection<(string pattern, TValue values)> FindAllPatternValuePairsThatMatch(string textKey)
    {
        ICollection<(string pattern, TValue values)> result = new List<(string pattern, TValue values)>();
        foreach (KeyValuePair<Regex, string> item in _regexDictionary.Where(r => r.Key.IsMatch(textKey)))
        {
            result.Add((item.Key.ToString(), _baseDictionary[item.Value.ToString()]));
        }
        return result;
    }

    public void AddEscapedFullMatchPattern(string pattern, TValue value)
    {
        string escapedPattern = Regex.Escape(pattern);
        string fullMatchPattern = MakePatternMatchFullString(escapedPattern);
        AddRegexToDictionary(fullMatchPattern, pattern, value);
    }

    public void AddFullMatchPattern(string pattern, TValue value)
    {
        string fullMatchPattern = MakePatternMatchFullString(pattern);
        AddRegexToDictionary(fullMatchPattern, pattern, value);
    }

    #region Base dictionary methods
    public TValue this[string key] { get => _baseDictionary[key]; set => _baseDictionary[key] = value; }

    public ICollection<string> Keys => _baseDictionary.Keys;

    public ICollection<TValue> Values => _baseDictionary.Values;

    public int Count => _baseDictionary.Count;

    public bool IsReadOnly => _baseDictionary.IsReadOnly;

    public void Add(KeyValuePair<string, TValue> item)
    {
        _baseDictionary.Add(item);
    }

    public void Clear()
    {
        _baseDictionary.Clear();
    }

    public bool Contains(KeyValuePair<string, TValue> item)
    {
        return _baseDictionary.Contains(item);
    }

    public bool ContainsKey(string key)
    {
        return _baseDictionary.ContainsKey(key);
    }

    public void CopyTo(KeyValuePair<string, TValue>[] array, int arrayIndex)
    {
        _baseDictionary.CopyTo(array, arrayIndex);
    }

    public IEnumerator<KeyValuePair<string, TValue>> GetEnumerator()
    {
        return _baseDictionary.GetEnumerator();
    }

    public bool Remove(string key)
    {
        return _baseDictionary.Remove(key);
    }

    public bool Remove(KeyValuePair<string, TValue> item)
    {
        return _baseDictionary.Remove(item);
    }

    public bool TryGetValue(string key, out TValue value)
    {
        return _baseDictionary.TryGetValue(key, out value);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return _baseDictionary.GetEnumerator();
    }
    #endregion

    private void AddRegexToDictionary(string actualPattern, string keyPattern, TValue value)
    {
        Regex regex = new Regex(actualPattern, RegexOptions.Compiled);
        _baseDictionary.Add(keyPattern, value);
        _regexDictionary.Add(regex, keyPattern);
    }

    private string MakePatternMatchFullString(string pattern)
    {
        string updatedPattern = pattern;
        if (!pattern.StartsWith("^"))
        {
            updatedPattern = "^" + updatedPattern;
        }
        if (!pattern.EndsWith("$"))
        {
            updatedPattern += "$";
        }
        return updatedPattern;
    }
}

}

披露

上面的 repo 由我在我的个人 GitHub 网站上维护。