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

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

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

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

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

P.S.: Примеры кода заслуживают высокой оценки.:)

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

UPDATE. Если мы говорим о стандартных реализациях DS в java, верно ли, что HashTable будет лучшим для этой конкретной задачи? Почему не HashMap, TreeMap или LinkedHashMap?

Ответ 1

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

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

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

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

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

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

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

(Есть и другие интересные реализации словарей, например списки пропусков, которые конкурируют с деревьями поиска и вероятностными реализациями, такими как Bloom filter.)

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

Ответ 2

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

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

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

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

Вы хотите, чтобы в ближайшем матче предлагались предложения? Затем вам могут понадобиться такие вещи, как генерация перестановок на то, что вводил пользователь, и для каждой перестановки посмотреть, существует ли она в dico: если это так, вам нужно будет вычислить ее "Levenhstein Edit Distance" и сначала предложить слова, которые имеют самый короткий светодиод.

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

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

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

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

Ответ 3

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

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

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

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