У меня возникли вопросы об использовании Tries / SortedSets для словаря.
Не нужно отвечать на все три, просто ищите хорошие ответы и исходный материал, если он у вас есть. Спасибо.
Поиск в Trie происходит очень быстро, так как он требует просто O(length of key) сравнений и выполняется почти настолько быстро, насколько это возможно. SortedSet обычно реализуется с использованием сбалансированных двоичных деревьев поиска, которые будут выполнять гораздо больше сравнений, в худшем случае O(height of tree) строковых сравнения. Так что Trie здесь явный победитель.
Эффективность виртуальной памяти можно увидеть по тому, насколько быстро структура данных может быть загружена в память. SortedSet занимает место пропорционально количеству элементов. Он реализован с помощью указателей, что может плохо сказаться на эффективности загрузки. Это можно улучшить, сериализовав его и сохранив в массиве, но это увеличивает необходимое пространство. Trie в своей простейшей форме занимает много памяти. Он также реализован с помощью указателей, что опять же плохо сказывается на эффективности загрузки. Даже в случае сериализации требуется большой объем памяти. Но здесь есть интересные альтернативы, которые сжимают дерево и дают такую же производительность. Radix Tries занимают значительно меньше памяти. Более того, DAWG (направленный граф ациклидных слов) перекрывает общие суффиксы и префиксы и сильно сжимает словарь. После сжатия DAWG может занимать меньше места, чем сам ваш словарь. Он реализован с использованием массива, поэтому загружается тоже быстро. В конце концов, если у вас есть статический словарь, лучше всего подойдет DAWG, иначе все зависит от обстоятельств.
Дерево видит ключи как последовательности. Это префиксное дерево. Вы можете очень быстро получить все слова, начинающиеся с префикса. Используя дерево, вы можете эффективно выполнять автозаполнение и автокоррекцию. Некоторые ключи, такие как числа с плавающей запятой, могут привести к длинным цепочкам в дереве, что плохо. SortedSet рассматривает ключи как сопоставимые элементы. Таким образом, можно легко разделить элементы. И SortedSet, и Trie могут предлагать ключи в алфавитном порядке, но я думаю, что SortedSet будет намного быстрее.
