Блог

Меня спросили об этом во время недавнего телефонного интервью — дали словарь со словом и весом слова (частота, чем выше, тем лучше), вот так —

             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 — в этом конкретном порядке.
• Производительность при поиске по префиксу имеет первостепенное значение, вы можете предварительно обработать и использовать столько места, сколько захотите, если поиск по префиксу выполняется быстро.

Это простая реализация, но мой вопрос заключается в том, как лучше всего обрабатывать вес слова и оптимизировать поиск. На мой взгляд, возможны следующие варианты —

a. Для каждого узла в дереве также сохраните отсортированный список слов ( SortedDictionary<int,List<string>> ), которые начинаются с этого префикса — больше места, но быстрее поиск.

б. Для каждого узла сохраните дочерние узлы в каком-то отсортированном списке, поэтому вам все равно нужно будет выполнить DFS для каждого дочернего узла, чтобы получить необходимые K слов — меньше места по сравнению с 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 });
        }
    }

 

Construct Trie — Время выполнения O (N * M * logN), пробел — O (N * M * N), N — количество слов, M — средняя длина слова.

Обоснование — Если бы не было словаря, это было бы O (N * M), вставка в a SortedDictionary равна O (logN), поэтому время выполнения в наихудшем случае должно быть O (N * M * logN)

Пробел кажется более сложным, но, как и раньше, если бы его не 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 . В этом случае List<string> достаточно простого, поскольку слова с более высокой частотой были бы вставлены первыми автоматически.

b. Теперь предположим, что в дополнение к инициализации с помощью a Dictionary<string,int> мы также получим дополнительные пары word, frequency . Мы все равно хотели бы, чтобы поиск выполнялся как можно быстрее, учитывая это требование. какая сейчас лучшая структура данных для хранения отсортированного списка слов в триноде, является SortedDictionary<int,HashSet<string>> лучшим вариантом?

Сначала вы могли бы отсортировать входные данные по весам. Затем вы могли бы использовать Lists вместо Dictionaries на узлах trie . Поскольку слова идут в порядке возрастания (или уменьшения) веса, проверки последнего элемента списка достаточно, чтобы решить, куда поместить это новое слово. Это избавляет от времени, затраченного O (logN) Dictionary .

Входные данные могут быть отсортированы в O (N * logN) с сортировкой сравнения или в O (N W) с сортировкой подсчета, где W — максимальный вес.

Временная сложность настройки дерева становится O (N * logN N * M). Это лучше, чем O (N * M * logN). Время запроса не меняется.

(В последнем абзаце предполагается HashSet , что операции выполняются в O (1), как и в вопросе. Неверно делать это предположение для произвольных входных данных и хэш-функций.)