Как реализовать словарь (Trie против HashTable и важные вопросы)?

Question

Я столкнулся с несколькими вопросами и статьями, в которых говорилось, что реализация словаря в java лучше всего выполняется с использованием try.Но большинство из них, насколько я видел, не касалось важных вопросов.Итак, следующая задача в реальном мире:

Давайте предположим, что мне нужно реализовать словарь (скажем, что-то вроде Lingvo, но более простой) с использованием Java.Для моей конкретной задачи необходимо сохранить определения слов и выполнить быстрый поиск по словарю.

Пожалуйста, ответьте на следующие вопросы:

• Какую структуру данных мне следует использовать (Trie или HashTable)?
• Как организовать (поиск, структура данных), если мне нужен словарь без учета регистра?
• Что если я хочу, чтобы он (поиск, словарь) был чувствительным к регистру?

PS: примеры кода высоко ценятся.:)

Спасибо за ответы заранее.

ОБНОВЛЕНИЕ : Если мы говорим о стандартных реализациях DS в Java, верно ли, что HashTable будет лучшимдля этой конкретной задачи?Почему не HashMap, TreeMap или LinkedHashMap?

Answer 1

Я хочу обратиться только к одному пункту в вашем вопросе:

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

Все эти реализации основаны на упорядочении элементов словаря, и все они имеют логарифмическое среднее и наихудшее время выполнения для обычных операций.

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

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

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

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

(Существуют и другие интересные реализации словарей, например, , пропускающие списки , которые конкурируют с деревьями поиска и вероятностными реализациями, например фильтр Блума .)

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

Answer 2

РЕДАКТИРОВАТЬ прекратить это голосование: я неправильно понял вопрос.ОП не за словарем проверяет написание слов / предложения / поиск типа вперед / автозаполнение / что угодно (я думал, что он был тем, кем он был).OP - после сопоставления ключ / значение, где для каждого слова есть определение.

Проработав словари, я могу сказать, что вы используете неправильный подход.

Это не такпросто как выбор между хеш-таблицей или деревом.

Вы упомянули Lingvo: это намного больше, чем просто таблица.

Хотите ли вы, чтобы близкое совпадение было предложено?Затем вам могут понадобиться такие вещи, как генерация перестановок на том, что пользователь ввел, и для каждой перестановки посмотрите, существует ли она в Dico: если это произойдет, вам нужно будет вычислить его «Расстояние редактирования Левенштейна» и предложить сначала слова, которыекратчайший светодиод.

Хотите ли вы, чтобы наиболее вероятные совпадения были автоматически завершены / предложены (например, что делает Google)?Тогда вам понадобится очень продвинутая структура данных, такая как BK-дерево (в основном, дерево светодиодов, если я правильно понимаю).

Сколько слов будет в вашем словаре?Вы не сможете использовать словарь, состоящий из 400 000 слов, используя строки и другие тяжелые объекты / структуру данных Java без серьезного снижения производительности (еще раз: словарь - это больше, чем просто одна хеш-таблица,словарь обычно включает несколько структур данных).Это не легко поместится в память компьютера ваших пользователей.Существуют известные способы поиска слов, в которых каждое отдельное слово может быть упаковано менее чем в 15 бит на слово (менее 15 бит на слово, вы правильно прочитали).

В дополнение к этому вы можетехочу сделать предложение, основанное на фонетике: например, с использованием двойного метафона.

Словарь, как в «словаре слов», равен , поэтому гораздо больше, чем просто таблица ключ / значение,Это действительно сложный зверь, из-за каких функций пользователь должен исключить и из-за количества задействованных данных.Просто английский + несколько специализированных терминов по доменам, медицинский, компьютерный, что угодно.даст вам сотни тысяч данных: попробуйте поместить их в Java HashMap и ... Kaboom!

Answer 3

Словарь реализация на Java, определенно лучше всего использовать хэш-коллекции.

Относительно HashMap или HashTable: В основном, если ваш класс используется многопоточным способом, чем вы должны использовать HashTable, в противном случае HashMap - лучший вариант.

HashMap против TreeMap: Если вам нужен порядок вставки в коллекцию, тогда мы должны использовать TreeMap.

Реализация

HashMap против LinkedHashMap: LinkedHashMap отличается от HashMap тем, что она поддерживает двусвязный список, проходящий через все его записи. Этот связанный список определяет порядок итераций, который обычно является порядком, в котором ключи были вставлены в карту (порядок вставки). Обратите внимание, что порядок вставки не изменяется, если ключ повторно вставлен в карту. (Ключ k повторно вставляется в карту m, если m.put(k, v) вызывается, когда m.containsKey(k) возвращает значение true непосредственно перед вызовом.)