Комментарии 8
Фильтр из 38,340,233 бит (~4,79 МБ) с 6 хэш-функциями может проверять присутствие элементов в датасете размером 4,000,000, давая всего ~1% ложноположительных. Впечатляет.
Каждое сотое - ложноположительное? Не очень впечатляет. В битовой карте того же размера не будет вообще ложных срабатываний (ключи, понятно, будут более ограниченными).
Вроде бы можно использовать сразу несколько фильтров Блума каскадно и уменьшить ошибку.
В битовой карте того же размера
Если у нас есть 4e8 бит для хранения датасета из 4e7 элементов то получается что у нас есть ~10 бит на каждый элемент, то есть элементы могут иметь числовое значение от 0 до 1024. Чтобы что-то в этой битовой карте найти, понадобится воспользоваться одним из двух способов:
Проитерировать битовую карту целиком и получить 100% уверенности и отсутствия и присутствия, но долго.
Сортировка коллекции из 10-битных значений?
Лично меня впечатляет то что можно хранить sparce-массив на поле размером допустим в 2^256 элементов каждый из которых имеет случайное значение в 256 бит энтропии имея смешное требование по памяти. Ложноположительность в этой вероятностной структуре данных просто разменивается на возможность напихать в небольшое храниище так много данных как способны генерировать хоть все компьютеры планеты.
Это прекрасно подходит для хранения мусорных данных таких как гарантированно невыигрышные лотерейные билеты что может помочь в подборе приватного ключа, или в распределённом поиске новых материалов, таких как белки для молекулярной биологии. Если мы сгенерировали случайно или брутфорсом число от 0 до 2^256 (перебрать невозможно, ведь это больше чем гугол) - можно перед тем, как подвергнуть это число проверке на выигрышность, спросить структуру данных Блума - проверялось ли это число до меня? Если проверялось - то это довольно редкое явление, с учётом пространства возможностей, - в зависимости от сценария использования можно: либо проверить в особом порядке, либо просто потратить меньше сил на запись.
Интересно, что соответствие условным требованиям условного белка который мы ищем есть смысл искать по другой таблице Блума, при условии что каждое одно из "условных требований" получится привести в одно целочисленное значение определённой битности. При этом организаторы децентрализованного поиска вносят "условные требования" в количестве миллионов-миллиардов числовых значений, настраивая адекватное количество ложно-положительных выводов, а рядовые участники будут не только писать проверенно-мусорные данные в общее хранилище Блума, но и сверять свои результаты с другим хранилищем Блума, маленьким и доступным только на чтение. Одна структура данных для двух совершенно разных задач!
Сильнее впечатлить может hashmap, например Object в языке JS, в котором для адресации элементов используется похожая математика, только доведённая до идеала и с другими компромисами по мере достижения большого количества элементов.
В битовой карте того же размера
Предположим, что у нас размер элемента около килобайта - на битовую карту понадобится в районе 2^1024 бит...
рано или поздно практически любое ПО достигает определённой степени недетерминированности
Ага, когда не знаешь, что тебе выдаст калькулятор в ответ на "2*2=" - "4", "4.00000000002" или "Error 0x089237894".
Вы наверняка уже поняли, что удалять биты из фильтра нельзя, так как один и тот же бит может быть занят несколькими элементами. Как нам тогда представлять удалённые элементы, используя такой фильтр?
Представить второй фильтр удаленных элементов и проверять вхождение перед основным. Но, как минимум, вероятностная структура для этого не подходит - достаточно примитивного Set
Элегантная математика фильтров Блума