Эффективный способ памяти потребности сохранить тонны строк (был: реализация ШЛЯПЫ-Trie в Java)
Я работаю с большим набором (5-20 миллионов) Строковых ключей (символы средней длины 10), который я должен сохранить в в структуре данных оперативной памяти, которая поддерживает следующую операцию в постоянное время или около постоянного времени:
// Returns true if the input is present in the container, false otherwise
public boolean contains(String input)
Hashmap Java оказывается более, чем удовлетворительным, что касается пропускной способности, но поднимает большую память. Я ищу решение, которое является эффективной памятью и все еще поддерживает пропускную способность, которая достойна (сопоставимый с или почти столь же хороший как хеширующий).
Я не забочусь во времена вставки/удаления. В моем приложении я буду выполнять только вставки (только во время запуска) и буду впоследствии только запрашивать структуру данных с помощью contains метод для срока действия приложения.
Я считал, что структура данных ШЛЯПЫ-Trie является самой близкой для моих потребностей. Я задаюсь вопросом, существует ли библиотека, которая имеет реализацию.
Другие предложения с указателями на приветствующиеся реализации.
Спасибо.
4 ответа
Это дерево кажется очень хорошей идеей для ваших ограничений.
Альтернатива «нестандартного мышления»:
Если вы можете позволить себе некоторую вероятность ответа «присутствует» для строки, которая отсутствует
РЕДАКТИРОВАТЬ: если вы можете позволить себе ложные срабатывания, используйте Bloom filter , как было предложено WizardOfOdds в комментариях.
Для k = 1 фильтр Блума подобен хеш-таблице без ключей: каждое «ведро» - это просто логическое значение, которое сообщает, присутствовал ли хотя бы один вход с таким же хешем. Если приемлемо 1% ложных срабатываний, ваша хеш-таблица может иметь размер примерно 100 * 20 миллионов бит или примерно 200 МБ. На 1 из 1000 ложных срабатываний 2 ГБ.
Использование нескольких хэш-функций вместо одной может улучшить частоту ложных срабатываний для того же количества битов.
Google опубликовал сообщение в блоге о попытках HAT в Java . Но я не вижу, как это решит вашу проблему напрямую: структура представляет собой мелкое дерево по префиксам ключей, а листья - это хэш-таблицы, содержащие суффиксы всех ключей с данным префиксом. Таким образом, у вас есть много хэш-таблиц, в которых хранятся все ключи, которые есть в вашей текущей одной большой хеш-таблице (возможно, экономия нескольких байтов на ключ в целом из-за общих префиксов). В любом случае вам нужна хеш-таблица с более эффективным использованием пространства, чем стандартная Java-таблица, иначе накладные расходы на каждый объект будут сильно ударять по вам. Так почему бы не начать со специализированного класса хэш-таблицы только для строковых ключей, если вы выберете этот маршрут и беспокоитесь о части дерева, только если она все еще кажется полезной?
Для экономии места, поиска O (log (n)) и простого кода попробуйте двоичный поиск по массиву символов. 20 миллионов ключей средней длины 10 составляют 200 миллионов символов: 400 МБ, если вам нужно 2 байта / символ; 200 МБ, если вы можете обойтись с 1. Вдобавок к этому вам нужно как-то представить границы между ключами в массиве. Если вы можете зарезервировать символ-разделитель, это один из способов; в противном случае вы можете использовать параллельный массив смещений типа int.
В простейшем варианте использовался бы массив строк с высокими затратами места из-за накладных расходов на каждый объект. Он должен по-прежнему превосходить хеш-таблицу по эффективности использования пространства, хотя и не так впечатляюще.
Подобно trie, троичное дерево поиска, но тройное дерево поиска имеет то преимущество, что использует меньше памяти. Вы можете прочитать о троичных деревьях поиска здесь , здесь и здесь . Также здесь находится одна из основных статей по этой теме Джона Бентли и Роберта Седжвика. Он также говорит о быстрой сортировке строк, так что не откладывайте это.