Способ хранения большого словаря с низким объемом памяти + быстрый поиск (на Android)
def to_str(key, value):
if isinstance(key, unicode):
key = str(key)
if isinstance(value, unicode):
value = str(value)
return key, value
передать ключ и значение ему и добавить рекурсию к вашему коду для учета внутреннего словаря.
6 ответов
Вы также можете использовать Android NDK и сделайте структуру на C или C ++.
Вы понадобится какое-то дерево . Возможно, я думаю, было бы хорошо использовать троичное дерево поиска . Они обеспечивают очень быстрый поиск и низкое использование памяти. Эта статья дает дополнительную информацию о TST. Здесь также говорится о сортировке, поэтому не все из этого применимы. Эта статья может быть немного более применимой. Как говорится в статье, TST
объединяют временную эффективность цифровых попыток с пространственной эффективностью деревьев двоичного поиска.
Как показано в этой таблице, время поиска очень сравнимо с использованием хеш-таблицы.
Я предполагаю, что вы хотите проверить, принадлежит ли данное слово словарю.
Взгляните на bloom filter.
Фильтр bloom filter может выполнять запросы типа "принадлежит ли X к предопределенному множеству" с очень небольшими требованиями к хранению. Если ответ на запрос "да", то он с небольшой (и регулируемой) вероятностью может быть неверным, если ответ на запрос "нет", то ответ гарантированно будет верным.
Согласно статье в Википедии, для словаря из 250 000 слов с вероятностью ошибки 1% вам потребуется менее 4 МБ пространства.
Фильтр Блума правильно ответит на вопрос "есть в словаре", если слово действительно содержится в словаре. Если в словаре нет этого слова, фильтр bloom может дать ложный ответ "есть в словаре" с некоторой небольшой вероятностью.
Очень эффективным способом хранения каталога является Направленный ациклический граф слов (DAWG).
Вот несколько ссылок:
Вы можете достичь своих целей и с помощью более скромных подходов... если это игра в слова, то я подозреваю, что вы работаете с алфавитом из 27 букв. Поэтому предположим, что алфавит состоит не более чем из 32 букв, т.е. 5 бит на букву. Тогда 12 букв (12 x 5 = 60 бит) можно запихнуть в один Java long, используя тривиальное кодирование 5 бит на букву.
Это означает, что если у вас нет слов длиннее, чем 12 букв/слово, вы можете просто представить свой словарь в виде набора длинных букв Java. Если у вас есть 250 000 слов, то тривиальное представление этого набора в виде одного сортированного массива длинных слов займет 250 000 слов x 8 байт/слово = 2 000 000 ~ 2MB памяти. Поиск осуществляется путем двоичного поиска, который должен быть очень быстрым, учитывая небольшой размер набора данных (менее 20 сравнений, так как 2^20 - это уже больше миллиона).
ЕСЛИ у вас есть слова длиннее 12 букв, то я буду хранить слова >12 букв в другом массиве, где 1 слово будет представлено двумя конкатенированными длинными словами Java очевидным образом.
ПРИМЕЧАНИЕ: причина, по которой это работает и, вероятно, более эффективно использует пространство, чем trie, и, по крайней мере, очень проста в реализации, заключается в том, что словарь постоянен... деревья поиска хороши, если вам нужно изменять набор данных, но если набор данных постоянен, вы часто можете использовать простой двоичный поиск.
Устройства, с которыми я работал, в основном работали с двоичным сжатым файлом, топология которого напоминала структуру двоичного дерева. В листьях находился сжатый текст Хаффмана. Чтобы найти узел, нужно было перейти к различным местам файла, а затем загрузить только ту часть данных, которая была действительно необходима.