Способ хранения большого словаря с низким объемом памяти + быстрый поиск (на Android)

Я разрабатываю приложение для игры в android word, которое нуждается в большом (~ 250 000 слов). Мне нужно:

достаточно быстрый поиск, например. постоянное время предпочтительнее, нужно, может быть, 200 поисковых запросов в секунду, чтобы решить головоломку и, возможно, 20 поисковых запросов в течение 0,2 секунды чаще, чтобы проверять слова, которые только что написаны пользователем.

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

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

Мои первые наивные попытки использовали класс Java HashMap, который вызвал исключение из памяти. Я изучил использование баз данных SQL Lite, доступных на Android, но это похоже на излишний.

Какой хороший способ сделать то, что мне нужно?

Ответ 1

Вы можете достичь своих целей и с более низким подходом... если это словесная игра, то я подозреваю, что вы обрабатываете 27 букв алфавита. Так что предположим, что алфавит не более 32 букв, т.е. 5 бит на букву. Вы можете втиснуть затем 12 букв (12 x 5 = 60 бит) в одну длинную Java, используя трибиальное кодирование 5 бит/букв.

Это означает, что на самом деле, если у вас нет более длинных слов, чем 12 букв/слов, вы можете просто представить свой словарь как набор Java longs. Если у вас есть 250 000 слов, тривиальное представление этого набора как единого, отсортированного массива длин должно принимать 250 000 слов x 8 байт/слово = 2 000 000 ~ 2 МБ памяти. Затем поиск выполняется двоичным поиском, который должен быть очень быстрым, учитывая малый размер набора данных (менее 20 сравнений, как 2 ^ 20, вы получаете более одного миллиона).

Если у вас есть более длинные слова, чем 12 букв, то I будет хранить > 12 буквенных слов в другом массиве, где 1 слово будет представлено двумя конкатенированными Java longs очевидным образом.

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

Ответ 2

Я предполагаю, что вы хотите проверить, принадлежит ли данное слово словарю.

Посмотрите цветной фильтр.

Фильтр цветения может делать "делает X принадлежащим к предопределенному набору" типа запросов с очень небольшими требованиями к хранению. Если ответ на запрос да, он имеет небольшую (и настраиваемую) вероятность ошибиться, если ответ на запрос отсутствует, тогда ответ будет гарантированно правильным.

Согласно статье в Википедии, вам может понадобиться место размером менее 4 МБ для вашего словаря объемом 250 000 слов с вероятностью ошибки 1%.

Фильтр цветения правильно ответит "находится в словаре", если слово действительно содержится в словаре. Если словарь не имеет слова, фильтр цветения может ложно дать ответ "в словаре" с небольшой вероятностью.

Ответ 3

Очень эффективным способом хранения каталога является Directed Acyclic Word Graph (DAWG).

Вот несколько ссылок:

Ответ 4

Вам будет нужен какой-то trie. Возможно, я думаю, что trernary search trie. Они дают очень быстрый поиск и низкое использование памяти. В этой статье дается дополнительная информация о TST. В нем также говорится о сортировке, поэтому не все это будет применяться. Эта статья может быть немного более применимой. Как говорится в статье, TST

объединить эффективность времени цифровых пытается с пространственной эффективностью деревья двоичного поиска.

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

Ответ 5

Вы также можете использовать Android NDK и создать структуру на C или С++.

Ответ 6

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

Ответ 7

Это была крутая идея, предложенная "Antti Huima", пытающейся сохранить словарные слова используя длинный