Comments 22
Тебя Claude/ChatGPT смог убедить что ты чертов гений?:)
Очень интересно, но размер "скелета" растет с пропущенным через него данными
С другой стороны выбранный алгоритм сжатия - весьма быстрый гигабайты в минуту перерабатывает.
Имхо - отличная идея.
Представим что в редис - есть Блум фильтр размером массива в до 512 мегабайт. И этим пользуются!
Вообще - точно не скажу - но вроде на задачу которую выполняет фильтр Блюма есть несколько разных алгоритмов с разной эффективностью.
Надо бы покопаться где-то читал, и скорее всего на заборе :)
Попробуем навайбкодить следующее
Промпт: дай цифровой фильтр который читает текстовый сигнал 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 буквы) необходимый паттерн.
Сейчас ночь и это не точно, но во-первых, у вас какой-то очень простой bloom-фильтр. Можно же и по-сложнее. Можно не однобитный, а по сложной (и даже динамической) маске, например, биты ставить/проверять.
Но идея интересная. Нужно только качественно подумать, какие у неё практические огрниченая по длинна словаря и блока поика. В том смысле, что на каких задачах это имеет смысл и какое получается быстродействие (манипуляции с со скелетом и данными вовсе не бесплатные же). Может оказаться, что bloom+b-tree и/или какие-то buckets окажется равен по быстродействию вашему алгоритму. В том смысле, что более медленный поиск "второго уровня" после ложно-положительного срабатывания bloom будет равен по быстродействию вашему чудо-алгоритму, что резко ограничивает рельные сценарии его применения. Кроме того у вас время поиска довольно быстро растёт и плохо предсказывается, а объём скелета и вовсе непредсказуем, в общем случае, а bloom он остаётся константой. Есть ощущение, что в какой-то момент (на каких-то задачах) ваш алгоритм начнёт проигрывать фильтру на основе деревьев.
Просто представьте Блум фильтр с массивом в 500 мегабайт.
Там возникает проблема -нелокалность Кеша, то есть процессор вынужден ходить по смешения по всему массива все время по новым адесом - то есть кештпромахи - а все в кеш не влезет.
Описанный алгоритм - пока кажется в основном будет ходить локально,
Но может я и ошибаюсь
Как раз данный алгорим очень быстро вымывает кэш (многократная обработка искомой строки + обращение к условно-большому скелету), а bloom обращается к памяти точечно и расходует одну троку кэша на одно обращение/поиск (ну и ещё один раз прочитать проверяемые данные для полученя хэша, но это в любом алгоритме неизбежно).
Кроме того представьте b-tree в котором не одиночные элементы, а диапазоны хешей (в простейшем случае) - будет относительно быстро и относительно компактно (особено если не через указатели делать, а как линейную структуру). Или b-tree+bloom (в узлах дерева лежат битовые маски для дальнейшего сужения поиска). И ещё вопрос, что там быстрее получится. Хэши-то равномерно распределены и потому балансировка деревьев не нужна, что очень ускоряет процесс и упрощает алгоритмы. А ещё оно совершенно не зависит от длины входного блока данных. А в статье под фиксированный блок получается, либо скорость поиска падает.
В статье алгоритм интересный, но совершенно точно не универсальный и очень неочевидно для чего именно он будет оптимальным.
В общем я понял, что с этим алгоримом не так:
Он имеет непредсказуемую сложность и непредсказуемый расход памяти. В худшем случае он вырождается в хранение полной копии всех данных с просмотром всех данных при каждом поиске. И ничего с этим поделать нельзя, так как трудно придумать данные, которые гарантируют размер скелета и сложность/скорость поиска. О чём автор честно предупредлил, но вот использовать такой алгоритм на практике не получится :)
Кроме того алогоритм жёстко привязан к некоторой фиксированной длине блока данных, используемой при поиске копий/повторов.
А если у нас такие данные, что мы прямо знаем оптимальный/допустимый размер блока и их структуру, то для них можно придумать более эффективный алгоритм поиска.
Кроме того в вашем алгоритме можно хранить не сами данные, а хэши подблоков, что круто ускоряет поиск, но при практически не влияет на точность. У вас там 16-байтные блоки, вроде, были? Ну вот и храните и испольуйте при поисике не сами блоки, а быстрые 4-байтные хэши этих блоков (например через сумму или исключающее-или произведний простого числа на значение байтов и индексов байтов в блоке) - на порядок быстрее будет при том же результате. Но поиск только блочный :)
Хэши поломают поиск подстрок, и оставят только exact мэтчи. Если брать какой то хэш который сохраняет информацию, а не возвращает рандом - тогда еще можно попробовать.
Про размер блока, он привязан к размеру того что вы ищете, если длинный поиск и короткие блоки - будет много false positives просто и все. Размер блоков самих данных не особо важен.
Сегодня поиграюсь с этим, возьму и конкурента пожестче, и свой алгоритм пожестче сделаю
В очень-очень старом номере одного компьютерного журнала была статья, из которой я в принципе узнал про алгоритмы сжатия. И в ней приводился способ, как узнать, что используется именно алгоритм семейства LZ. Берём скрипт, генерирующий данные, в которых принципиально нет ни одного повтора, сжимаем и смотрим: если размер не изменился или изменился слабо, значит используется LZ.
Вопрос: если подавать на вход вашего алгоритма данные, принципиально не имеющие повторов (а такое возможно, даже скрипт есть для их генерации), кто будет эффективнее: фильтр Блума на 1 мегабайт, или ваш алгоритм с хранилищем 1 мегабайт? Объём данных, ну, скажем, 512 мегабайт.
Или я не понял задачу, или тут изобретение велосипеда с костылями вместо колес.
Если вам надо искать вхождение строки в строке - то используйте стандартные методы поиска подстроки в строке. Не надо никаких хеш таблиц и эмулирования их блум фильтрами. Тот же KMP будет быстрее и проще ваших "скелетов".
Ну если устраивает O(N) то в целом можно просто лечь и расслабиться
Если я правильно понял
Формализуйте, пожалуйста, вашу задачу. Ваше построение склета точно не быстрее O(N). Вам же надо как минимум почти все байты хотябы раз просмотреть, иначе вообще ни о какой точности речи быть не может, если вы большую долю входных данных будете игнорировать.
Многоразовая проверка membership
Частая
Т.е. у вас одна фиксированная большая строка и вам надо быстро в ней проверить вхождение кучи мелких строк? Тогда стройте суффиксное дерево, суффиксный массив, или используйте Burrows–Wheeler transform. В последнем никаких ложно-положительных, минимальное количество дополнительной информации, можно хранить результат вместо оригинальной строки, которую потом восстановить. Если допустимы false-positive и фиксированна длина шаблонов, то используйте полиномиальный скользящий хеш.
Мой bloom фильтр побил оригинальный в 200 раз