在带有通配符的集合中查找单词的最快方法

Question

我有大约 200,000 个单词需要找到与可以包含任意数量的字母通配符的单词匹配的单词。我还需要在没有任何通配符的情况下查找单词的选项。

我已经按长度将单词分成集合：

static readonly HashSet<string>[] _validWords = { 
    new HashSet<string>(StringComparer.OrdinalIgnoreCase), // 3 letter words
    new HashSet<string>(StringComparer.OrdinalIgnoreCase), // 4 letter words
    new HashSet<string>(StringComparer.OrdinalIgnoreCase), // 5 letter words
    new HashSet<string>(StringComparer.OrdinalIgnoreCase), // 6 letter words
    new HashSet<string>(StringComparer.OrdinalIgnoreCase), // 7 letter words
    new HashSet<string>(StringComparer.OrdinalIgnoreCase), // 8 letter words
    new HashSet<string>(StringComparer.OrdinalIgnoreCase)  // 9 letter words
};

搜索特定单词很简单：

public static bool IsValid(string word) {
    return word.Length >= GameplaySettings.Instance.MinWordLength && _validWords[word.Length - 3].Contains(word);
}

这是我目前使用正则表达式查找通配符的实现（最终我想获得所有匹配的词，但现在只找到一个（或 none) 没问题。):

public static bool IsValidRegex(string pattern, int length) {
    pattern = $"^{pattern}$";

    foreach (string word in _validWords[length - 3]) {
        if (Regex.Matches(word, pattern, RegexOptions.Singleline).Count > 0) { return true; }
    }

    return false;
}

可以有任意数量的通配符（例如所有个字母甚至可以是通配符），目前它的表现不如我希望的那样。

所以我想知道有没有更有效的方法！

感谢任何 help/suggestions！

Answer 1

由于您的通配符只能匹配一个字母，所以问题并不难。如果您需要支持可变长度子字符串，我建议您去阅读一些关于正则表达式如何工作的科学文献。

这是一个相当基础的二年级 comp-sci“数据结构和算法”练习。在每个 Node 中使用 Dictionary 可能不会是最快/内存效率最高的。但我会这样解决问题；

class Node
{
    public bool endWord;
    public Dictionary<char, Node> next;
}

public class Words
{
    private Node root = new Node { endWord = false };
    public const char wildcard = '_';

    public void DefineWord(string word)
    {
        var node = root;
        foreach (var c in word)
        {
            if (node.next == null)
                node.next = new Dictionary<char, Node>();
            if (node.next.TryGetValue(c, out var nextNode))
            {
                node = nextNode;
            }
            else
            {
                node = node.next[c] = new Node { endWord = false };
            }
        }
        node.endWord = true;
    }

    private bool IsValid(ReadOnlySpan<char> word, Node node)
    {
        if (word.IsEmpty && node.endWord)
            return true;
        if (node.next == null)
            return false;

        if (word[0] == wildcard)
        {
            word = word.Slice(1);
            foreach(var n in node.next.Values)
            {
                if (IsValid(word, n))
                    return true;
            }
        } else if (node.next.TryGetValue(word[0], out var nextNode))
            return IsValid(word.Slice(1), nextNode);
        return false;
    }

    public bool IsValid(string word)
        => IsValid(word, root);

    public static void Test1()
    {
        var words = new Words();
        words.DefineWord("APE");
        words.DefineWord("APPLE");
        words.DefineWord("BEAR");
        words.DefineWord("BEER");
        words.DefineWord("PEAR");
        words.DefineWord("PEER");
        words.DefineWord("PEERS");

        Assert.True(words.IsValid("APE"));
        Assert.True(words.IsValid("APPLE"));
        Assert.True(words.IsValid("PEAR"));
        Assert.True(words.IsValid("PEER"));
        Assert.True(words.IsValid("PEERS"));
        Assert.True(!words.IsValid("PLIERS"));
        Assert.True(words.IsValid("PE_R"));
        Assert.True(words.IsValid("_EAR"));
        Assert.True(words.IsValid("_E_R"));
    }
}

在带有通配符的集合中查找单词的最快方法

Fastest method of finding words in a collection with wildcard letters

c#

hashset