Вероятностные структуры данных 1/2.
Иногда бывают задачи, когда вы готовы пожертвовать точностью каких-то значений ради скорости работы/любой другой характеристики. Пробежимся по самым известным.
1. Фильтр Блума решает задачу проверки значения во множестве. Изначально это какой-то битсет размера m и рядом k хеш-функций. При добавлении элемента во множество с помощью хеш-функций определяется k битов, которые устанавливаются в 1. Теперь при необходимости проверить, находится ли элемент во множестве, считаем от него все хеш-функции и проверяем, правда ли, что все интересующие нас биты установлены в 1. Проблемы: иногда могут возникать ложноположительные срабатывания (элемента нет, а мы ответили, что есть); нельзя удалять элементы (один и тот же бит может быть установлен различными элементами). В таком виде два фильтра легко объединять/пересекать (побитовое ИЛИ/И множеств). В отличие от хеш-таблиц (или чего-то подобного) фильтр блума может являться универсальным множеством (все биты == 1).
Есть разные вариации: вместо 0/1 можно хранить числа и при добавлении инкрементить соответствующие значения, а при удалении декрементить (counting bf); вместо одного counting bf можно хранить n независимых (bitwise почему-то); spectral bf — оптимизированный counting; aging bf, который поддерживает операцию удаления и не хранит старые данные; stable bf, в котором мы рандомно декрементим несколько значений, после чего k значениям устанавливаем максимальные значения (утверждается, что рано или поздно получится достичь какого-то константного кол-ва нулей, магия); A^2 bf — теп memory efficient implementation; ну и конечно более менее умеющий в удаление bf (если кратко, разрешается некоторые участки помечаются как collision-unsafe, и удаление из них не происходит).
Тут ещё можно считать конкретные размеры битсета и кол-во хеш-функций исходя из допустимой пропорции ошибок.
Иногда юзается в кешах или как вспомогательная структура для других сд.
Ещё можно строить key-value хранилище на bf. Если вам нужно что-то вроде
k->v \in [0; 10], давайте держать 11 bf, и по значению v решать, в какой bf добавить ключ. При получении значения пройдёмся по всем bf и в котором нашли ключ, такое и значение.Ещё давайте такой пример. Нам нужно на устройстве пользователя (допотопный мобильный телефон == мало памяти) понимать, звонит нам спамер или нет. Давайте все телефоны из базы спамерских закинем в bf. Чтобы избежать false-positive срабатываний, пройдёмся по всему множеству телефонов (для 10циферных вполне реально) и выпишем рядом с bf номера, на которых мы ошибаемся (их не будет много, порядка единиц при хорошем bf). Теперь если bf говорит, что номер спамерский, проверим, есть ли он в отдельно выписаных. И теперь мы умеем точно отвечать при очень маленьких затратах памяти. Тут можно почитать реальные кейсы.
А ещё можно на них bst строить. А ещё можно в борах юзать. Ух короче.
Основной link.
2. Count-min sketch помогает насчитать частотность различных объектов (например у нас есть бесконечный поток данных, и хочется уметь выдавать примерную частоту появления объектов, причём с очень маленькими затратами на время/память).
Структура очень простая: k хеш-таблиц фиксированного размера (можно одного, можно разных). Изначально все они заполнены нулями. Как только нужно добавить объект, инкрементим соответствующую этому объекту ячейку в каждой хеш-таблице. При запросе узнать частоту объекта, берём значения объекта из каждой хеш-таблицы и считаем минимум. Собственно всё. Понятно, что чем больше хеш-табличек вы берёте, тем ближе ответ будет к реальному, иначе из-за коллизий может получится завышенным.
Ещё если знаем, что элемент есть во множестве, можно удалять.
Только пишется это обычно не как несколько хеш-таблиц, а матрицей + хеш-функцию на каждую строку.
Ещё их легко объединять и (если одно множество строго подмножество второго) вычитать.
Тут (осторожно, скачается пдфка) есть про применение в безопасности, базах данных и даже биоинформатике.