Trie自动完成字权重（频率）

Question

在最近的一次电话采访中，我被问到这个问题--给出一本词典，上面有一个词和一个词的权重（频率越高越好），就像这样--

            var words = new Dictionary<string,int>();
            words.Add("am",7);
            words.Add("ant", 5);
            words.Add("amazon", 10);
            words.Add("amazing", 8);
            words.Add("an", 4);
            words.Add("as", 11);
            words.Add("be", 8);
            words.Add("bee", 2);
            words.Add("bed", 4);
            words.Add("best", 12);
            words.Add("amuck", 1);
            words.Add("amock", 2);
            words.Add("bestest", 1);

设计一个API方法，给定一个前缀和一个数字k，返回匹配前缀的前k个单词。单词应该根据它们的权重进行排序，越高越好。

• 所以，prefix=“am”，k=5，以特定的顺序返回amazon、amazing、am、amock、amuck。
• 前缀查找的性能至关重要，只要前缀查找速度快，您可以进行预处理并使用尽可能多的空间。

这是一个Trie实现，但我的问题是如何最好地处理单词权重和优化查找。在我看来，选择是-

a.对于Trie中的每个节点，还存储一个以该前缀开头的单词排序列表(sorteddictionary > )--空间更大，但查找更快。

b.对于每个节点，将子节点存储在某种排序列表中，因此您仍然需要对每个子节点执行DFS以获得所需的K个单词--与a相比空间更少，但速度更慢。

我决定选择A。

    public class TrieWithSuggestions
    {
        TrieWithSuggestions _trieRoot;
        public TrieWithSuggestions()
        {
        }

        public char Character { get; set; }
        public int WordCount { get; set; } = 1;
        public TrieWithSuggestions[] ChildNodes { get; set; } = new TrieWithSuggestions[26];
        //Stores all words with this prefix.
        public SortedDictionary<int, HashSet<string>> PrefixWordsDictionary = new SortedDictionary<int, HashSet<string>>();

        public TrieWithSuggestions ConstructTrie(Dictionary<string, int> words)
        {
            if (words.Count > 0)
            {
                _trieRoot = new TrieWithSuggestions() { Character = default(char) };
                foreach (var word in words)
                {
                    var node = _trieRoot;
                    for (int i = 0; i < word.Key.Length; i++)
                    {
                        var c = word.Key[i];
                        if (node.ChildNodes[c - 'a'] != null)
                        {
                            node = node.ChildNodes[c - 'a'];
                            UpdateParentNodeInformation(node, word.Key, words[word.Key]);
                            node.WordCount++;
                        }
                        else
                        {
                            InsertIntoTrie(node, word.Key, i, words);
                            break;
                        }
                    }
                }
            }

            return _trieRoot;
        }

        public List<string> GetMathchingWords(string prefix, int k)
        {
            if (_trieRoot != null)
            {
                var node = _trieRoot;
                foreach (var ch in prefix)
                {
                    if (node.ChildNodes[ch - 'a'] != null)
                    {
                        node = node.ChildNodes[ch - 'a'];
                    }
                    else
                        return null;
                }

                if (node != null)
                    return GetWords(node, k);
                else
                    return null;
            }
            return null;
        }

        List<string> GetWords(TrieWithSuggestions node, int k)
        {
            List<string> output = new List<string>();
            foreach (var dictEntry in node.PrefixWordsDictionary)
            {
                var entries = node.PrefixWordsDictionary[dictEntry.Key];
                var take = Math.Min(entries.Count, k);
                output.AddRange(entries.Take(take).ToList());
                k -= entries.Count;
                if (k == 0)
                    break;
            }
            return output;
        }

        void InsertIntoTrie(TrieWithSuggestions parentNode, string word, int startIndex, Dictionary<string, int> words)
        {
            for (int i = startIndex; i < word.Length; i++)
            {
                var c = word[i];
                var childNode = new TrieWithSuggestions() { Character = c };
                parentNode.ChildNodes[c - 'a'] = childNode;
                UpdateParentNodeInformation(parentNode, word, words[word]);
                parentNode = childNode;

                if (i == word.Length - 1)
                    UpdateParentNodeInformation(parentNode, word, words[word]);
            }
        }

        void UpdateParentNodeInformation(TrieWithSuggestions parentNode, string word, int wordWeight)
        {
            wordWeight *= -1;
            if (parentNode.PrefixWordsDictionary.ContainsKey(wordWeight))
            {
                if (!parentNode.PrefixWordsDictionary[wordWeight].Contains(word))
                    parentNode.PrefixWordsDictionary[wordWeight].Add(word);
            }
            else
                parentNode.PrefixWordsDictionary.Add(wordWeight, new HashSet<string>() { word });
        }
    }

构造trie-运行时O(N*M*logN)，空间-O(N*M*N)，n-#单词，m-avg单词长度。

空间似乎更棘手，但是像以前一样，如果没有sorteddictionary，空间将是O(N*M)，在最坏的情况下，字典可能包含所有N个单词，因此空间复杂性看起来像O(N*M*N)

getmatchingwords-运行时O（len（前缀）+k)

函数调用-

            var trie = new TrieWithSuggestions();
            trie.ConstructTrie(words);
            var list = trie.GetMathchingWords("am", 10); //amazon, amazing, am, amock, amuck

编辑1-

a.在这种设置下，最好按权重对单词进行排序，然后插入trie。在本例中，一个简单的列表 就足够了，因为首先会自动插入频率较高的单词。

b.现在让我们假设，除了用字典 初始化之外，我们还将获得额外的单词频率对。我们仍然需要一个尽可能快的查找，考虑到这个要求，什么是现在最好的数据结构来存储三个字的排序列表，sorteddictionary > 是最好的选择吗？

Answer 1

您可以首先根据权重对输入进行排序。然后，可以在trie节点上使用列表而不是字典。由于单词的权重是按递增（或递减）顺序排列的，检查列表的最后一个元素就足以决定把这个新词放在哪里。这消除了dictionary所占用的O（logN）时间。

输入可以在O(N*logN)中进行比较排序，也可以在O(N+W)中进行计数排序，其中W是最大权重。

建立trie的时间复杂度为O(N*logN+N*M)。这比O(N*M*logN)要好。查询时间不变。

（最后一段假设hashset操作在O(1)中执行，就像问题中一样。对于任意输入和哈希函数，这种假设是错误的。）