Нужно запоминать эффективный способ хранения тонны строк (было: реализация HAT-Trie в java)

Я работаю с большим набором (5-20 миллионов) клавиш String (средняя длина 10 символов), которые мне нужно хранить в структуре данных в памяти, которая поддерживает следующую операцию в постоянное время или почти постоянное время:/p >

// Returns true if the input is present in the container, false otherwise
public boolean contains(String input)

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

Мне не нужны времена вставки/удаления. В моем приложении я буду выполнять только вставки (только во время запуска) и впоследствии будет запрашивать структуру данных, используя метод contains для срока службы приложения.

Я прочитал, что структура данных HAT-Trie ближе всего для моих нужд. Мне интересно, есть ли библиотека, которая имеет реализацию.

Другие предложения с указателями на реализацию приветствуются.

Спасибо.

Ответ 1

Трое кажется очень хорошей идеей для ваших ограничений.

Альтернатива "мышление вне коробки":

Если вы можете позволить себе некоторую вероятность ответа на "настоящее" для строки, которая отсутствует

EDIT: если вы можете позволить себе ложные срабатывания, используйте Bloom filter, как это было предложено WizardOfOdds в комментариях.

При k = 1 фильтр Bloom похож на хеш-таблицу без ключей: каждое "ведро" является просто логическим, которое указывает, присутствует ли хотя бы один вход с тем же хэшем. Если допустимо 1% ложных срабатываний, ваша хеш-таблица может быть не меньше 100 * 20 миллионов бит или примерно 200 MiB. Для 1 из 1000 ложных срабатываний, 2GiB.

Использование нескольких хеш-функций вместо одного может улучшить ложную положительную скорость для того же количества бит.

Ответ 2

Google открывает сообщение в блоге HAT пытается в Java. Но я не вижу, как это решит вашу проблему напрямую: структура представляет собой неглубокие префиксы ключей, а листья - hashtables, содержащие суффиксы всех ключей с заданным префиксом. Таким образом, в целом у вас есть много хэш-таблиц, в которых хранятся все ключи, которые находятся в вашей текущей большой хэш-таблице (возможно, сэкономить несколько байтов на каждый ключ из-за общих префиксов). В любом случае вам нужна более эффективная по площади хэш-таблица, чем стандартная Java-версия по умолчанию, или накладные расходы для каждого объекта поражают вас так же плохо. Итак, почему бы не начать со специализированного класса hashtable только для строковых ключей, если вы возьмете этот маршрут и будете беспокоиться о trie-части только в том случае, если это все еще кажется целесообразным?

Ответ 3

Для эффективности пространства, поиска O (log (n)) и простого кода, попробуйте двоичный поиск по массиву символов. 20 миллионов ключей средней длины 10 составляют 200 миллионов символов: 400 МБ, если вам нужно 2 байта / char; 200MB, если вы можете уйти с 1. Вдобавок к этому вам нужно каким-то образом представить границы между ключами в массиве. Если вы можете зарезервировать символ разделителя, то одним способом; в противном случае вы можете использовать параллельный массив смещений int.

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

Ответ 4

Подобно trie, это тройное дерево поиска, но тройное дерево поиска имеет то преимущество, что использует меньше памяти. Вы можете прочитать о троичных деревьях поиска здесь, здесь, и здесь. Также одна из основных работ по теме Джона Бентли и Роберта Седжуика - здесь. В нем также говорится о сортировке строк быстро, поэтому не откладывайте на это.