Не люблю хэш-таблицы

Не люблю я хэш-таблицы. Какой бы областью я не занимался — они везде просто “достаточно хорошее” решение. Где нужны объёмы — масштабируется линейно. Где нужна точность — даёт вероятность (высокую, но вероятность всё-таки).

Задача

Есть класс задач, где удобно заранее узнать включение паттерна в потоке. Например, 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-фильтра он тоже есть, и я ниже покажу у кого при одинаковом размере их больше :D). А 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. Это вторая статья за сегодня. В первой я показал новый прикольный универсальный код

Ставьте лайки, колокольчик, подписывайтесь на канал! :D