Какая структура данных наиболее подходит для реализации словаря?
Я должен написать программу-словарь в качестве семестрового проекта для курса бакалавриата по структурам данных и алгоритмам, и я должен найти наиболее подходящее решение (структура данных) для этой проблемы.
Я решил использовать либо хеш-таблица или Trie. Мне предложили использовать treaps кем-то, но пока не смог их разглядеть.
В моей базе данных около 100 тысяч разных слов и их значений. Основные функциональные возможности, которые должна обеспечить программа: вставить, Обновить, Удалить а также поиск слово / определение. Если мне удастся втиснуть автозавершение а также исправление заклинаний, это был бы дополнительный бонус.
Итак, мой вопрос, учитывая мои требования, какая структура данных лучше всего подходит для моих целей. Когда я говорю «лучший», я спрашиваю о структуре данных, которая имеет наилучшую сложность во время выполнения и низкую стоимость (требования к памяти).
Также я хотел иметь алгоритм, который возвращал бы все слова, начиная с заданного префикса. Например, скажем, я делаю вызов функции dictionary.getWordsStartingWith("fic") он должен вернуть список всех слов, которые начинаются с fic такие как fiction, fictitious,fickle и т.д. Я знаю, что могу сделать это, если я реализую свой словарь как три, я мог бы сделать это, но возможно ли это сделать с помощью хеш-таблицы?
Решение
Вам почти наверняка понадобится три, если вы хотите выполнить автоматическое завершение / сопоставление префиксов. Хеш-таблицы на самом деле не делают это возможным; на самом деле хорошие хеш-функции спроектированы так, что даже очень похожие ключи (например, один и тот же префикс) отображаются в совершенно разные части массива. В целях хеширования это считается особенностью.
Treaps — это в основном бинарные деревья поиска, которые используют свойство стохастичности + кучи для балансировки. В целом интерфейс является стандартным интерфейсом дерева BST; так что на самом деле это просто деталь реализации, которая приводит только к умеренно отличным свойствам, чем красное черное дерево или дерево AVL.
BST не так подходят для решения проблем, которые вы, похоже, пытаетесь решить. BST имеют тенденцию следовать неравенствам в нисходящем направлении, тогда как три имеют тенденцию следовать неравенствам в нисходящем направлении. Когда вы имеете дело с числовыми данными, сравнения неравенства — это все, потому что равенство очень редко (так как пространство возможностей огромно). Со строками у каждого символа очень мало возможностей, поэтому имеет больше смысла использовать равенства, что приводит к оптимизации, такой как не хранение ключей в большинстве узлов.
Таким образом, я бы рекомендовал продолжить с попыток. Они очень интенсивно используются именно для такого рода вещей, и вы можете найти массу ресурсов по их оптимизации (особенно для космоса), поскольку они особенно используются для ввода текста на мобильных устройствах, где количество мест / циклов выше. Это также очень интересная структура данных для изучения IMHO, по сравнению с BST, о которой вы а), вероятно, много узнали в структурах данных новичка, и б) Не очень интересна структура данных; все, кроме схемы балансировки, тривиально, а схемы балансировки более утомительны, чем что-либо еще (деревья RB имеют что-то вроде 7 действительно различных случаев для балансировки или что-то в этом роде, довольно сложно кодировать дерево RB и получить их все правильно).
На странице Википедии есть хорошая информация: https://en.wikipedia.org/wiki/Trie. Побитовые попытки выглядят особенно интересно.
Другие решения
Других решений пока нет …