Не люблю хэш-таблицы
Не люблю я хэш-таблицы. Какой бы областью я не занимался — они везде просто “достаточно хорошее” решение. Где нужны объёмы — масштабируется линейно. Где нужна точность — даёт вероятность (высокую, но вероятность всё-таки).
Задача
Есть класс задач, где удобно заранее узнать включение паттерна в потоке. Например, AB есть в DDDABEEE. И узнавать надо часто. Наивный подход — линейный скан на каждый запрос. Медленно.
Как работает Bloom-фильтр
Ребята придумали Bloom-фильтр. У вас массив нулей фиксированного размера. Входная строка проходит через K хэш-функций (по сути мясорубку), и по получившимся хэшам вы сыпете единицами в массив:
Вставка "CAT":
hash1("CAT") = 3
hash2("CAT") = 7
hash3("CAT") = 1
Массив: 0 1 0 1 0 0 0 1 0 0
индекс: [0][1][2][3][4][5][6][7][8][9]
↑ ↑ ↑
h3 h1 h2
Проверка: прогоняем запрос через те же K функций. Если все K позиций = 1, ответ “вероятно есть”. Если хоть одна позиция = 0, ответ “точно нет”:
Поиск "DOG":
hash1("DOG") = 3 → массив[3] = 1 ✓
hash2("DOG") = 5 → массив[5] = 0 ✗ → ТОЧНО НЕТ
Поиск "FOX":
hash1("FOX") = 3 → массив[3] = 1 ✓
hash2("FOX") = 7 → массив[7] = 1 ✓
hash3("FOX") = 1 → массив[1] = 1 ✓ → ВЕРОЯТНО ЕСТЬ (но мы FOX не вставляли!)
Работает за константное время, но есть минусы:
- Размер массива надо подбирать эмпирически
- Со временем массив захламляется единицами
- False Positives неизбежны (чем больше данных — тем больше)
Зачем K функций а не одна?
Одна функция ставит 1 бит. Проверка: “этот бит = 1?” — но куча других элементов тоже его поставили. С одной функцией FPR ≈ заполненность массива.
K функций ставят K бит. Проверка: “ВСЕ K бит = 1?” Вероятность что K случайных позиций все заняты чужими элементами = (заполненность)^K:
Массив заполнен на 50%:
K = 1 → FPR ≈ 50% (каждый второй запрос врёт)
K = 3 → FPR ≈ 12.5% (уже терпимо)
K = 7 → FPR ≈ 0.8% (почти идеально)
K = 10 → FPR ≈ 0.1% (но вставка стала в 10 раз дороже)
Моя идея: LZ77 без ссылок
Я подумал: а что будет если взять LZ77 (классический алгоритм сжатия), но вместо ссылок просто удалять дубликат? Тогда у меня останется минимальное ядро — скелет потока без повторов, по которому можно быстро искать вхождение.
Пример
У нас есть поток DDDBBBEEEAAABBB и поисковая строка AAABBB.
Построение скелета: жадно ищем дубликаты с правого конца. BBB уже встречался → удаляем:
Исходный поток: D D D B B B E E E A A A B B B
^^^^^
дубликат BBB — удаляем!
Скелет: D D D B B B E E E A A A
(12 байт вместо 15)
Поиск AAABBB: в скелете DDDBBBEEEAAA такой подстроки целиком нет. Но мы применяем тот же алгоритм коллапса к поисковой строке — ищем в скелете максимальное совпадение:
Запрос: A A A B B B
^^^^^
BBB есть в скелете → удаляем из запроса
Остаток: A A A
^^^
AAA есть в скелете → удаляем
Остаток: пусто → НАЙДЕНО!
Включение доказано! Все куски запроса нашлись в скелете.
При таком алгоритме есть риск False Positives (у Bloom-фильтра он тоже есть, и я ниже покажу у кого при одинаковом размере их больше 
). А False Negatives невозможны — ведь мы не уменьшаем энтропию, а только удаляем точные дубликаты. Оригинал каждого куска всегда остаётся в скелете.
Бенчмарки
Поток: 1MB избыточных данных (100 уникальных блоков по 50 байт, повторённых случайно). Скелет сжал весь мегабайт до 4.88 KB — оставил только уникальные блоки.
Bloom-фильтру выделяем ровно столько же памяти — 4.88 KB. Честное сравнение.
Результат (длина паттерна P = 16 байт)
| Фильтр |
Размер |
False Positive Rate |
False Negative Rate |
| Скелет |
4.88 KB |
0% |
0% |
| Bloom |
4.88 KB |
96.4% |
0% |
При одинаковом бюджете памяти Bloom-фильтр бесполезен (96% ложных срабатываний), а скелет — идеален.
А если памяти мало?
Допустим нам разрешено потратить на фильтр только 2, 5 или 10 KB. Тот же сжимаемый поток (1MB → скелет 4.88KB), ищем паттерны длиной 16 байт. Оба фильтра получают одинаковый бюджет:
| Бюджет памяти |
Скелет FPR |
Bloom FPR |
Скелет FNR |
Bloom FNR |
| 2 KB |
0% |
100% |
0% |
0% |
| 5 KB |
0% |
96% |
0% |
0% |
| 10 KB |
0% |
80% |
0% |
0% |
Скелет влез в 4.88 KB и отвечает без ошибок. Bloom при тех же килобайтах — захлебнулся.
А на случайных данных?
На полном рандоме дубликатов нет при любом уровне агрессивности — скелет не может сжаться и честно говорит: “эти данные несжимаемы, мне нужен весь мегабайт”. Bloom можно запихнуть в любой бюджет, но он предсказуемо ломается — при 50KB на миллион записей даёт 92% FPR. Оба фильтра бесполезны на рандоме при маленьком бюджете, только по разным причинам.
Итог
Bloom-фильтр — универсальный, работает на любых данных, но всегда с ошибками. Скелет — специализированный: на сжимаемых данных (а реальные данные почти всегда сжимаемы) он даёт идеальный результат при в разы меньшей памяти.
|
Bloom |
Скелет |
| FPR |
Есть всегда |
0% на сжимаемых данных |
| FNR |
0% (гарантия) |
0% на сжимаемых данных |
| Сжимаемые данные |
Переполняется |
Идеально |
| Рандом |
Переполняется по-своему |
Честно: “не могу сжать” |
| Сложность |
O(K) хэшей |
O§ поиск подстроки |
Код и бенчмарки на GitHub.-P.S. Это вторая статья за сегодня. В первой я показал новый прикольный универсальный код
Ставьте лайки, колокольчик, подписывайтесь на канал! -Источник
