c# - 使用.NET StringDictionary 通过列表/字典进行前缀搜索？

Question

我想知道.NET 是否提供任何标准功能来通过列表或字典对象进行前缀搜索。我遇到了StringDictionary，但不知道它是否可以为我做到这一点。

如果它可以进行前缀搜索，它还可以进行子字符串搜索还是让我使用正则表达式之类的东西进行搜索？

提前致谢。

Answer 1

StringDictionary只是一个哈希表，其中键和值都是strings。这在泛型之前存在（当Dictionary<string, string>不可能时）。

您在这里想要的数据结构是trie。CodeProject上有实现：

1. 使用 TRIE 实现电话目录
2. 在 C# 2.0 中使用泛型的可重用前缀树

或者，如果你是那种人，那就自己动手吧（参见CLRS）。

Answer 2

我不相信 StringDictionary 支持前缀搜索，但是如果您使用 a SortedList<,>，则可以对键范围进行二分搜索，直到找到前缀前后的第一个条目。

Answer 3

我认为这StringDictionary是老派（pre-generics）。您可能应该使用 aDictionary(Of String, String)代替，因为它实现了 IEnumerable（想想 LINQ）。关于 StringDictionary的一件极其蹩脚的事情是它不区分大小写。

Answer 4

我在这里做了一个通用的实现。

由于stringimplements IEnumerable<char>，您可以将其与charas 参数一起使用TKeyElement。

Answer 5

下面是一组可以通过前缀有效搜索的字符串的基本实现。

想法是将集合中的所有单词保存在一个 trie 中，当查询以某个前缀开头的所有单词时，我们找到与前缀中最后一个字符对应的节点，然后在 DFS 中从那里收集并返回它的所有后代。

public class PrefixSearchableSet
{
    private readonly Dictionary<char, TrieNode> _letterToNode = new Dictionary<char, TrieNode>();
    private bool _isEmptyWordIncluded;

    public PrefixSearchableSet(IEnumerable<string> words = null)
    {
        if (words is null) return;
        foreach (string word in words)
        {
            AddWord(word);
        }
    }

    public void AddWord(string word)
    {
        if (word is null) return;

        if (word is "") _isEmptyWordIncluded = true;

        else
        {
            TrieNode node = FindOrAdd(_letterToNode, word[0]);
            foreach (char c in word.Skip(1))
            {
                node = FindOrAdd(node.Children, c);
            }

            node.Word = word;
        }
    }

    public List<string> GetWords(string prefix)
    {
        List<string> words = new List<string>();

        if (prefix is null) return words;

        if (prefix is "")
        {
            if (_isEmptyWordIncluded) words.Add("");
            foreach (TrieNode trieNode in _letterToNode.Values)
            {
                trieNode.CollectWords(words);
            }
            return words;
        }

        _letterToNode.TryGetValue(prefix[0], out TrieNode node);
        foreach (char c in prefix.Skip(1))
        {
            if (node is null) break;
            node.Children.TryGetValue(c, out node);
        }
        node?.CollectWords(words);

        return words;
    }

    private static TrieNode FindOrAdd(Dictionary<char, TrieNode> letterToNode, char key)
    {
        if (letterToNode.TryGetValue(key, out TrieNode node)) return node;
        return letterToNode[key] = new TrieNode();
    }

    private class TrieNode
    {
        public Dictionary<char, TrieNode> Children { get; } = new Dictionary<char, TrieNode>();

        public string Word { get; set; }

        public void CollectWords(List<string> words)
        {
            if (Word != null) words.Add(Word);
            foreach (TrieNode child in Children.Values)
            {
                child.CollectWords(words);
            }
        }
    }
}