Пару не дель назад игрался с фильтрами Блума для поиска строк в заранее известном наборе. Для того чтобы уменьшить количество кода можно взять только одну хеш-функцию, и для того, чтобы получить i-ый хеш, просто сдвигать значение по кругу, эту хитрость придумал Выссоцкий из Bell Labs в конце 60-х. А что возьмем в качестве хеш-функции?
И тут и у аверов, и у вирмейкеров одинаково травматичный опыт. Во времена модемов первое что приходило в голову по поводу хешей CRC, циклическая контрольная сумма. Если ей пользоваться как хешом, то результат будет так себе, контрольные суммы нужны чтобы ловить пакеты ошибок (burst error), а для некриптографических хешей важно, чтобы значения распределялись равномерно.
Аверы получили пиздюлину по скорости, а вирмейкеры по детектам. Потому довольно быстро, ну лет за десять примерно, антивирусные движки стали считать ROL-XOR хеши, а вирмейкеры (снова привет Z0mbie) стали генерировать случайные ROL-ADD, ROL-SUB хеши, подбирая константы так, чтобы не напороться на коллизию. И CRC куда уж без него, и там очень смешное с выбором п̶о̶л̶и̶н̶о̶м̶а многочлена, я знаю вы любите это слово со школы.
В случае с фильтром, у нас есть набор строк, и все что нас интересует, чтобы у каждой строки был свой уникальный идентификатор. Потому генерировать хеш мы будем случайно, из одной или нескольких операций "подмешивающих" в хеш текущий символ, и битмиксера (используются в качестве финализаторов во взрослых хешах). В качестве "вращающегося" хеша, мы можем взять битмиксер же, не только ROL/ROR.
Остается проверить фильтр (не только хеш) на коллизии и готово. У нас есть случайная функция, массив со случайными значениями случайного размера, с которым что-то происходит в цикле случайное количество раз, а на выходе мы получаем машинку распознающую заранее заданные строки из известного набора строк.
(Если поиграться с параметрами, то можно даже получить компрессию, на картинке 15 строк длиной 91 байт из 36Кб списка прекрасно умещаются в фильтр длиной 32 байта)
А и все. Чего вы еще ждали в воскреченье утром? Пойду чистить и комментировать код, и зашлю его потом на VXUG
