Недостатки попыток

Question

Я изучаю попытки и проверяю их преимущества и недостатки. Они весьма полезны во многих практических приложениях, таких как словарь, проверки орфографии и т. Д. Из-за их постоянного поиска O (m) (где m - длина строки) и других преимуществ, таких как предоставление упорядоченного извлечения строк и получение общих префиксов. Таким образом, преимущества довольно ясны для меня, но ограничения немного запутанны.

Я по этой ссылке: https://en.wikipedia.org/wiki/Trie

Недостатки, перечисленные здесь:

1. Пытается может быть медленнее, в некоторых случаях, чем хэш-таблицы для поиска данных, особенно если данные доступны непосредственно на жесткий диск или какое-либо другое вторичное запоминающее устройство, где время произвольного доступа является высоким по сравнению с основной памятью.

Следующий вопрос - Почему существует сценарий, связанный с вторичным хранением? Не предполагается, что попытки не будут храниться в основной памяти. Если они хранятся во вторичном хранилище, то использование trie в любом случае бесполезно, поскольку доступ к диску всегда будет приводить к увеличению времени.

2. Для некоторых попыток может потребоваться больше места, чем хеш-таблица, так как память может быть выделена для каждого символа в строке поиска, а не для одного фрагмента памяти для всей записи, так как в большинстве хэш-таблиц.

последующий вопрос: Является ли это из-за того, что пытается будет содержать больше ссылок/указателей для подключения каждого символа к следующему, и что бы потреблять больше байт, чем если бы она хранилась в целом строка? (Я получил эту причину из одного из ответов здесь). Может ли кто-нибудь это уточнить?

Я бы очень признателен за помощь здесь. Благодарю.

Answer 1

Во-первых, «постоянный O (m) look-ups» не имеет смысла. Время поиска в trie равно O (m): это зависит от длины строки, которую вы просматриваете.

Хорошо построенная хеш-таблица (т. Е. Хорошая хеш-функция и разумный коэффициент нагрузки) имеет время поиска O (1).

Предполагая, что компетентная конструкция, поиск строки в хеш-таблице будет намного быстрее, чем поиск в trie.

Простые и хэш-таблицы используются для разных вещей. Если все, что вам нужно, это возможность поиска слова, тогда хэш-таблица будет быстрее. Если вы хотите найти общие префиксы, упорядоченное извлечение или сделать подобные вещи, то вам нужно trie.

Хэш-таблица может очень быстро находить отдельные строки. Это как чистокровная скаковая лошадь. Это все это может сделать. С другой стороны, trie - рабочая лошадка, которая может многое сделать. Это никогда не будет столь же быстрым при поиске, как хэш-таблица, но он может делать много вещей, которые хэш-таблица не может сделать.

Например, поиск всех слов, начинающихся с «pre», займет время O (n) со словарем, потому что вы должны искать все слова. С помощью trie для поиска поддерева, содержащего все эти слова, требуется три зонда, а затем все, что вам нужно сделать, - это пересечь это поддерево. Конечно, худшим случаем является O (n), но это только если все слова в вашем начале начинаются с «pre».

Принимая во внимание, что переход на диск будет медленнее, чем если бы все три были в памяти, неправильно сказать, что диск на основе диска не имеет преимуществ перед альтернативами. Если данные не будут помещаться в память, то независимо от того, какую структуру данных вы используете, вам потребуется некоторое внешнее (то есть не-память) хранилище. Тот факт, что ваш доступ к данным медленнее, когда он находится на диске, принципиально не изменяет преимущества или недостатки таблицы trie vs. hash. Например, диск на основе диска будет по-прежнему быстрее, чем хэш-таблица на основе диска, когда дело доходит до поиска всех слов с определенным префиксом.

Накладные расходы хэш-таблицы обычно являются постоянными, кратными количеству содержащихся в нем слов. То есть в дополнение к памяти, необходимой для хранения строк, накладные расходы для каждой строки сохраняются для хранения отображения хеш-кода и строки.

Память для trie немного больше задействована. В худшем случае есть один узел на символ. Все эти небольшие распределения узлов начинают складываться. Представьте словарь, содержащий 200 000 слов, а средняя длина слова - пять символов. Это миллион узлов накладных расходов.

К счастью, есть способы значительно сжать трюк, не теряя при этом сколько-либо производительности. Результирующая структура данных намного меньше и более удобна для кэширования, чем наивно построенная три.

Answer 2

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

Например, для строки длиной 10 вы можете иметь 10 символов в базовом массиве символов, тогда как для строки длиной 100 вы используете хэш на основе каждого десятого символа.

Итак, чтобы ответить на ваш вопрос, хеширование обычно выполняется в постоянное время, тогда как вставка или извлечение из trie - это время O (n), где n - длина значения, которое нужно вставить или извлечь. Даже если на практике мало различий, константа имеет то преимущество, что она предсказуема. Все операции с хэш-таблицей будут выполняться каждый раз каждый раз, давать или принимать. Но с trie (представляющим словарь по названиям валлийских мест) поиск Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch с одним символом в конце изменился, потребуется гораздо больше времени, чем поиск «a». Система будет питаться через всю строку, прежде чем понимать, что она не находится в словаре. Google и другие технологические компании предпочитают приятное, предсказуемое (но равномерно распределенное) хеширование, чтобы избежать проблем с безопасностью.