Представление очень большого массива битов в маленькой памяти

Question

Я хотел бы представить структуру, содержащую 250 М состояний (по 1 биту каждое), как можно меньше памяти (максимум 100 Кб) Операции над ним установлены / получены. Я не говорю, что он плотный или разреженный, он может варьироваться. Я хочу использовать язык C.

Я посмотрел другие темы здесь, чтобы найти что-то подходящее. Вероятностная структура, такая как, например, фильтр Блума, не подходит из-за возможных ложных ответов.

Есть предложения, пожалуйста?

Answer 1

Если вы знаете, что ваши данные могут быть редкими, то вы можете использовать кодирование длины пробега . Но в противном случае вы не сможете сжать его.

Answer 2

возможны ли файлы в вашей среде?если это так, вы можете поменять местами, например, сегментированный битовый буфер размером 4 КБ.Ваше решение должно иметь последовательный доступ к этим битам, чтобы минимизировать загрузку / сохранение диска.

Answer 3

Максимальное количество бит, которое вы можете сохранить в 100 Кбайт памяти, составляет 819 200 бит.Предполагается, что 1 К = 1024 байта и 1 байт = 8 бит.

Answer 4

Размер структуры зависит от энтропии информации.Вы не можете сжать информацию чем-то меньше заданного размера, если у вас нет повторяющегося шаблона.В худшем случае все равно будет около 32 Мб памяти в вашем случае.Если вы знаете что-то об отношении между битами, тогда это возможно ...

Answer 5

250M бит займет 31,25 мегабайта для хранения (конечно, при условии 8 бит / байт), намного больше, чем ваша цель в 100k.

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

Answer 6

Я не думаю, что возможно сделать то, что вы просите. Если вам нужно покрыть 250 миллионов состояний по 1 биту в каждом, вам понадобится 250 Мбит / 8 = 31,25 МБ. Очень далеко от 100 Кбайт.

Обычно вы создаете большой массив байтов и используете функции для определения байта (index >> 3) и позиции бита (index & 0x07) для установки / очистки / получения.