Структура данных в памяти для компактного отображения миллиардов ключей словаря для значений

Question

У меня есть миллиарды записей (ключей/значений), которые я хочу компактно хранить в памяти, и единственная операция, которую мне нужно поддерживать, - это поиск значения на его ключ. Ключи и значения являются маленькими строками. Самое главное, как сжатый структура данных; он должен использовать внутреннюю структуру ключей более глубоко, чем простой ассоциативный массив. Например, сопоставление клавиш «apple», «apply» и «apron» со значениями «1», «2» и «3» должно каким-то образом сжиматься. Какую структуру данных я ищу?

Answer 1

Похоже, что вы хотите trie - он описывает описанную вами «компрессию», сохраняя каждый префикс только один раз.

Я предполагаю, что у вас достаточно памяти для хранения «миллиардов» ключей, и, конечно же, вам нужно быть в 64-битной системе, чтобы иметь возможность даже адресовать столько предметов в первую очередь.

Answer 2

Вы можете попробовать Trie. Он формирует древовидную структуру из самих ключевых строк. Не было бы пустых мест (как в хэш-карте).

Answer 3

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

Тонкой настройки базы данных может быть достаточно для ваших нужд.