Какая структура данных наиболее подходит для реализации Словаря?

Question

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

Я рассмотрел использование либо хеш-таблицы , либо trie. Мне предложили кто-то использовать treaps, но пока не смогли их изучить.

В моей базе данных содержится около 100 тыс. Различных слов и их значений. Основные функциональные возможности программы, как ожидается, чтобы обеспечить являются вставки, обновление, удалить и Поиск слово/определение. Если мне удастся сжать автозаполнение и исправление заклинания, это будет дополнительный бонус.

Итак, мой вопрос, учитывая мои требования, какая структура данных лучше всего подходит для моих целей. Когда я говорю «лучше», я прошу структуру данных, которая имеет лучшую сложность во время выполнения и низкую стоимость (требования к памяти).

Кроме того, я хотел иметь алгоритм, который возвращал все слова, начинающиеся с данного префикса. Например, скажем, я вызываю вызов функции dictionary.getWordsStartingWith("fic"), он должен вернуть список всех слов, начинающихся с fic, таких как fiction, fictitious, fickle и т. Д. Я знаю, что могу это сделать, если я реализую свой словарь как trie, я мог бы это сделать , но можно ли это сделать с помощью хеш-таблицы?

Answer 1

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

Treaps - это в основном двоичные деревья поиска, которые используют свойство стохастичности + кучу, чтобы выполнить их балансировку. В общем, интерфейс является стандартным интерфейсом дерева BST; так что это действительно просто деталь реализации, которая приводит только к умеренно различным свойствам, чем к красному черному дереву или дереву AVL.

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

Таким образом, я рекомендую продолжить попытки. Они очень сильно используются для такого рода вещей, и вы можете найти массу ресурсов для их оптимизации (особенно для космоса), поскольку они особенно используются для ввода текста на мобильном телефоне, где пространство/циклы превзойдены.Это также очень интересная структура данных для изучения ИМХО, по сравнению с BST, которые вы a), вероятно, узнали о сильных структурах данных для первокурсников и б) На самом деле это не так интересно в структуре данных; все, кроме схемы балансировки, тривиально, а схемы балансировки более утомительны, чем что-либо еще (у деревьев RB есть что-то вроде 7 действительно отличных случаев для балансировки или чего-то подобного, довольно сложно закодировать дерево RB и получить их все точно).

На странице wikipedia есть некоторая хорошая информация: https://en.wikipedia.org/wiki/Trie. Побитовые попытки выглядят особенно интересными.