19.05.2026 18:11
MaxLenPer 22 11000 Источник

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

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

Задача

Есть класс задач, где удобно заранее узнать включение паттерна в потоке. Например, 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

Комментарии (22)


  1. DooKoo2
    19.05.2026 19:23
    #29993494

    Тебя Claude/ChatGPT смог убедить что ты чертов гений?:)


    1. MaxLenPer Автор
      19.05.2026 19:23
      #29993520

      Черт возьми да!) Буду благодарен если найдешь ошибки в алгоритме, тогда сдамся и пойду работать в макдональдс где мне и место?


    1. A-Dobrii
      19.05.2026 19:23
      #29993634

      Ваш комментарий - глупость.


  1. A-Dobrii
    19.05.2026 19:23
    #29993670

    Очень интересно, но размер "скелета" растет с пропущенным через него данными

    С другой стороны выбранный алгоритм сжатия - весьма быстрый гигабайты в минуту перерабатывает.

    Имхо - отличная идея.

    Представим что в редис - есть Блум фильтр размером массива в до 512 мегабайт. И этим пользуются!


    1. MaxLenPer Автор
      19.05.2026 19:23
      #29993692

      Размер ядра можно ограничить увеличив агрессивность сжатия, т. е. Уменьшив размер минимального коллапса, но подрастает число false positives немного

      А скелет в целом напрямую зависит не от количества данных, а от их общей энтропии, так что при линейном росте данных ядро может вообще не расти


  1. A-Dobrii
    19.05.2026 19:23
    #29993772

    Вообще - точно не скажу - но вроде на задачу которую выполняет фильтр Блюма есть несколько разных алгоритмов с разной эффективностью.

    Надо бы покопаться где-то читал, и скорее всего на заборе :)


    1. MaxLenPer Автор
      19.05.2026 19:23
      #29993880

      Я почитал в интернете, да есть BinaryFuse8, завтра сравню, да и пара идей по доработке моего алгоритма появилась - и выложу еще статейку с числами


  1. TimurZhoraev
    19.05.2026 19:23
    #29993842

    Попробуем навайбкодить следующее

    Промпт: дай цифровой фильтр который читает текстовый сигнал 256 значений АЦП байт который выявлять шаблон сигнал не более 16 элементов КИХ БИХ вейвлет или дискретное косинусное вероятность совпадения код Питон. Шаблон в случайную последовательность где-нибудь, длина последовательности случайной 1000, длина шаблона 10 визуализация.

    Цифровая обработка сигналов (зачёркнуто) текста
    import numpy as np


def find_template(signal, template, threshold=0.85):
    """Находит шаблон в сигнале с помощью согласованного КИХ-фильтра.

    signal: массив из 256 байт (0-255)
    template: массив до 16 байт (0-255)
    threshold: порог вероятности/схожести (0.0 до 1.0)
    """
    sig = np.array(signal, dtype=float)
    tmpl = np.array(template, dtype=float)

    # Центрируем сигналы для устойчивости к постоянной составляющей (DC offset)
    sig_centered = sig - np.mean(sig)
    tmpl_centered = tmpl - np.mean(tmpl)

    N = len(tmpl)
    probabilities = np.zeros(len(sig) - N + 1)

    # Энергия шаблона для нормировки
    tmpl_energy = np.sum(tmpl_centered**2)
    if tmpl_energy == 0:
        return []

    # Скользящее окно (КИХ-фильтрация с нормировкой)
    for i in range(len(probabilities)):
        window = sig_centered[i : i + N]
        window_energy = np.sum(window**2)

        if window_energy == 0:
            continue

        # Взаимная корреляция (скалярное произведение)
        cross_corr = np.sum(window * tmpl_centered)

        # Нормированный коэффициент корреляции Пирсона (аналог вероятности совпадения)
        r = cross_corr / np.sqrt(window_energy * tmpl_energy)
        probabilities[i] = max(0.0, r)  # Исключаем отрицательную корреляцию

    # Поиск совпадений выше порога
    matches = [
        {"index": idx, "probability": round(prob, 2)}
        for idx, prob in enumerate(probabilities)
        if prob >= threshold
    ]

    return matches


# --- ПРИМЕР ИСПОЛЬЗОВАНИЯ ---
if __name__ == "__main__":
    # 1. Генерируем случайный сигнал АЦП (256 байт)
    np.random.seed(42)
    mock_signal = np.random.randint(0, 256, size=256)

    # 2. Создаем шаблон (например, импульс из 10 элементов)
    mock_template = np.array([10, 50, 150, 200, 250, 200, 150, 50, 10, 5])

    # 3. Внедряем шаблон в сигнал на позицию 100 для проверки
    mock_signal[100 : 100 + len(mock_template)] = mock_template
    # Добавим немного шума поверх внедренного шаблона (+/- 10 единиц АЦП)
    noise = np.random.randint(-10, 11, size=len(mock_template))
    mock_signal[100 : 100 + len(mock_template)] = np.clip(
        mock_signal[100 : 100 + len(mock_template)] + noise, 0, 255
    )

    # 4. Запуск фильтра
    detected_matches = find_template(
        mock_signal, mock_template, threshold=0.80
    )

    print(f"Найденные совпадения: {detected_matches}")

    В принципе довольно хорошо распознаёт в тексте, который представляется как сигнал от 0 до 255 (можно сократить до 6 бит 32 буквы) необходимый паттерн.



  1. Sap_ru
    19.05.2026 19:23
    #29994110

    Сейчас ночь и это не точно, но во-первых, у вас какой-то очень простой bloom-фильтр. Можно же и по-сложнее. Можно не однобитный, а по сложной (и даже динамической) маске, например, биты ставить/проверять.
    Но идея интересная. Нужно только качественно подумать, какие у неё практические огрниченая по длинна словаря и блока поика. В том смысле, что на каких задачах это имеет смысл и какое получается быстродействие (манипуляции с со скелетом и данными вовсе не бесплатные же). Может оказаться, что bloom+b-tree и/или какие-то buckets окажется равен по быстродействию вашему алгоритму. В том смысле, что более медленный поиск "второго уровня" после ложно-положительного срабатывания bloom будет равен по быстродействию вашему чудо-алгоритму, что резко ограничивает рельные сценарии его применения. Кроме того у вас время поиска довольно быстро растёт и плохо предсказывается, а объём скелета и вовсе непредсказуем, в общем случае, а bloom он остаётся константой. Есть ощущение, что в какой-то момент (на каких-то задачах) ваш алгоритм начнёт проигрывать фильтру на основе деревьев.


    1. A-Dobrii
      19.05.2026 19:23
      #29994162

      Просто представьте Блум фильтр с массивом в 500 мегабайт.

      Там возникает проблема -нелокалность Кеша, то есть процессор вынужден ходить по смешения по всему массива все время по новым адесом - то есть кештпромахи - а все в кеш не влезет.

      Описанный алгоритм - пока кажется в основном будет ходить локально,

      Но может я и ошибаюсь


      1. Sap_ru
        19.05.2026 19:23
        #29994198

        Как раз данный алгорим очень быстро вымывает кэш (многократная обработка искомой строки + обращение к условно-большому скелету), а bloom обращается к памяти точечно и расходует одну троку кэша на одно обращение/поиск (ну и ещё один раз прочитать проверяемые данные для полученя хэша, но это в любом алгоритме неизбежно).


      1. Sap_ru
        19.05.2026 19:23
        #29994206

        Кроме того представьте b-tree в котором не одиночные элементы, а диапазоны хешей (в простейшем случае) - будет относительно быстро и относительно компактно (особено если не через указатели делать, а как линейную структуру). Или b-tree+bloom (в узлах дерева лежат битовые маски для дальнейшего сужения поиска). И ещё вопрос, что там быстрее получится. Хэши-то равномерно распределены и потому балансировка деревьев не нужна, что очень ускоряет процесс и упрощает алгоритмы. А ещё оно совершенно не зависит от длины входного блока данных. А в статье под фиксированный блок получается, либо скорость поиска падает.
        В статье алгоритм интересный, но совершенно точно не универсальный и очень неочевидно для чего именно он будет оптимальным.


  1. Sap_ru
    19.05.2026 19:23
    #29994230

    В общем я понял, что с этим алгоримом не так:
    Он имеет непредсказуемую сложность и непредсказуемый расход памяти. В худшем случае он вырождается в хранение полной копии всех данных с просмотром всех данных при каждом поиске. И ничего с этим поделать нельзя, так как трудно придумать данные, которые гарантируют размер скелета и сложность/скорость поиска. О чём автор честно предупредлил, но вот использовать такой алгоритм на практике не получится :)
    Кроме того алогоритм жёстко привязан к некоторой фиксированной длине блока данных, используемой при поиске копий/повторов.
    А если у нас такие данные, что мы прямо знаем оптимальный/допустимый размер блока и их структуру, то для них можно придумать более эффективный алгоритм поиска.

    Кроме того в вашем алгоритме можно хранить не сами данные, а хэши подблоков, что круто ускоряет поиск, но при практически не влияет на точность. У вас там 16-байтные блоки, вроде, были? Ну вот и храните и испольуйте при поисике не сами блоки, а быстрые 4-байтные хэши этих блоков (например через сумму или исключающее-или произведний простого числа на значение байтов и индексов байтов в блоке) - на порядок быстрее будет при том же результате. Но поиск только блочный :)


    1. MaxLenPer Автор
      19.05.2026 19:23
      #29994646

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

      Про размер блока, он привязан к размеру того что вы ищете, если длинный поиск и короткие блоки - будет много false positives просто и все. Размер блоков самих данных не особо важен.

      Сегодня поиграюсь с этим, возьму и конкурента пожестче, и свой алгоритм пожестче сделаю


  1. Morthan
    19.05.2026 19:23
    #29994648

    В очень-очень старом номере одного компьютерного журнала была статья, из которой я в принципе узнал про алгоритмы сжатия. И в ней приводился способ, как узнать, что используется именно алгоритм семейства LZ. Берём скрипт, генерирующий данные, в которых принципиально нет ни одного повтора, сжимаем и смотрим: если размер не изменился или изменился слабо, значит используется LZ.

    Вопрос: если подавать на вход вашего алгоритма данные, принципиально не имеющие повторов (а такое возможно, даже скрипт есть для их генерации), кто будет эффективнее: фильтр Блума на 1 мегабайт, или ваш алгоритм с хранилищем 1 мегабайт? Объём данных, ну, скажем, 512 мегабайт.


    1. MaxLenPer Автор
      19.05.2026 19:23
      #29994688

      Оба захлебнутся в false positive


  1. wataru
    19.05.2026 19:23
    #29997426

    Или я не понял задачу, или тут изобретение велосипеда с костылями вместо колес.

    Если вам надо искать вхождение строки в строке - то используйте стандартные методы поиска подстроки в строке. Не надо никаких хеш таблиц и эмулирования их блум фильтрами. Тот же KMP будет быстрее и проще ваших "скелетов".


    1. MaxLenPer Автор
      19.05.2026 19:23
      #29997496

      Ну если устраивает O(N) то в целом можно просто лечь и расслабиться

      Если я правильно понял


      1. wataru
        19.05.2026 19:23
        #29997528

        Формализуйте, пожалуйста, вашу задачу. Ваше построение склета точно не быстрее O(N). Вам же надо как минимум почти все байты хотябы раз просмотреть, иначе вообще ни о какой точности речи быть не может, если вы большую долю входных данных будете игнорировать.


        1. MaxLenPer Автор
          19.05.2026 19:23
          #29997544

          Многоразовая проверка membership

          Частая


          1. wataru
            19.05.2026 19:23
            #29997572

            Т.е. у вас одна фиксированная большая строка и вам надо быстро в ней проверить вхождение кучи мелких строк? Тогда стройте суффиксное дерево, суффиксный массив, или используйте Burrows–Wheeler transform. В последнем никаких ложно-положительных, минимальное количество дополнительной информации, можно хранить результат вместо оригинальной строки, которую потом восстановить. Если допустимы false-positive и фиксированна длина шаблонов, то используйте полиномиальный скользящий хеш.


            1. MaxLenPer Автор
              19.05.2026 19:23
              #29997596

              Сегодня-завтра выложу сравнение с ними.

              Суффиксное дерево как минимум весит немало в сравнении. Bwt пока не тестил.

              Но вообще я не для каких то своих задач ищу структуры данных, я просто исследую в свободное время и делюсь наработками.