Сжатые фильтры Блума

В документе сжатые фильтры Bloom (pdf) объясняется общая идея. . На странице 3 этого документа они говорят:

Предположим, однако, что вместо этого мы выбираем k так, чтобы каждая из записей в m-битовом массиве была равна 1 с вероятностью 1/3. Затем мы можем воспользоваться этим фактом, чтобы сжать m-битовый массив и уменьшить размер передачи.

Таким образом, вместо того, чтобы иметь вектор, спроектированный так, что вероятность установки бита равна 1/2, что создаст «случайный вектор», который плохо сжимается, они возятся с количеством хеш-функций, чтобы повлиять на вероятности. Результирующий массив состоит примерно из одной трети единиц и двух третей нулей, что должно оказаться более сжимаемым.

Фильтр цветения сжимать не нужно.

Не все ваши ключи имеют бит для их представления. Они представлены рядом битов, которые повторно используются для других ключей. Вот почему вы получаете ложные срабатывания. Когда вы добавляете ключи a, b и c, вы устанавливаете количество битов равным 1. Для следующего ключа d может случиться так, что все биты, которые его представляют, уже установлены в 1, поэтому вам не нужно ничего делать ( и вы получите ложное срабатывание, если проверите, был ли он вставлен после вставки a, b и c).

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

Если вам действительно нужно сделать фильтр цветения меньше, установите его размер, какой сможете, а затем проверьте частоту ложных срабатываний. Вы можете сделать это, выбрав набор разных ключей, проверьте, говорит ли фильтр цветения, что они уже вставлены, и вставьте их (в произвольном порядке). Убедитесь, что количество ключей соответствует вашему фактическому варианту использования.

Вы можете передать его через некоторые алгоритмы сжатия, но, как вы сказали, это случайный вектор 0-1, поэтому не ожидайте большого выигрыша.

Как правило, фильтры цветения используются для быстрой проверки существования перед тем, как выполнять дорогостоящие операции поиска / чтения. Вам нужно, чтобы он был в памяти, чтобы быть быстрым (если вас не волнует скорость, вы просто выполняете поиск), и вам нужно, чтобы он был несжатым. Если он достаточно мал для хранения в памяти, обычно нет смысла сжимать его.