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

Для текстовых данных существует великое множество систем полнотекстового поиска, и казалось бы, бери да переводи бинарщину в hex или base64, да пользуйся всеми этими Сфинксами, Эластиками, Мантикорами, или Постгресовским FTS. Однако, помимо неизбежных накладных расходов, есть еще вот какой нюанс: FTS кушают не просто тексты, а желательно тексты на человеческих языках: все эти стемминги, лемматизаторы, нормализаторы как бы намекают, что на "нечеловеческом" материале их производительность неизбежно выродится в линейный поиск.

Существует ли FTS-подомбые движки, заточенные под бинарные данные?

PS. Внутренний голос мне подсказывает, что с этим, скорее всего, на ура справится Постгрес, достаточно лишь правильно его приготовить. Например, индексировать N-грамы, а не корни слов. Если кто-либо из присутствующих занимался чем-то подобным, буду очень благодарен ссылочкам на книги и статьи.

Здравствуйте, zx zpectrum, Вы писали:

ZZ>Дано: антивирусоподобная система, хранящая в себе до хрена и больше бинарных сигнатур.
"До хрена и больше" — сколько именно? Какие длины у этих сигнатур — все одинаковые/сильно разные/более-менее похожие?
Влезут ли все эти сигнатуры в RAM?
ZZ>Требуется: искать сигнатуры по совпадению с бинарной подпоследовательностью за асимптотическое время меньшее, чем O(N).
Что вы тут называете N? Количество сигнатур или длину бинарной последовательности, в которой вы ищете данные?

Что у вас чаще меняется — строка, в которой ищут, или набор сигнатур?
Ну, то есть что нужно "проиндексировать" заранее: набор сигнатур, через который нужно прогнать M документов, или набор документов, через которые потом будете прогонять различные сигнатуры?

В общем, предварительно напрашивается Ахо-Корасик. Он спроектирован ровно для вашей задачи.

ZZ>PS. Внутренний голос мне подсказывает, что с этим, скорее всего, на ура справится Постгрес, достаточно лишь правильно его приготовить. Например, индексировать N-грамы, а не корни слов. Если кто-либо из присутствующих занимался чем-то подобным, буду очень благодарен ссылочкам на книги и статьи.
АФАИК, коробочной версии для постгреса нету. К нему можно прикрутить того же Ахо-Корасика, но стоит ли овчинка выделки?

S>"До хрена и больше" — сколько именно?
S>Какие длины у этих сигнатур — все одинаковые/сильно разные/более-менее похожие?
S>Что вы тут называете N? Количество сигнатур или длину бинарной последовательности, в которой вы ищете данные?
S>Что у вас чаще меняется — строка, в которой ищут, или набор сигнатур?
Приблизительный порядок количества сигнатур — десятки миллионов, с линейным ростом на сотни тысяч в месяц, регулярность пополнения — единицы раз в день. Длины, навскидку, от 6 до 64 байт. На остальные вопросы ответа дать не готов, т.к. всё это пока жуткая экспериментальщина, далекая от реального использования, и сценарии использования могут кардинально поменяться в процессе.

S>В общем, предварительно напрашивается Ахо-Корасик. Он спроектирован ровно для вашей задачи.
Спасибо, да, один из очевидных вариантов. Посмотрю. Однако, бросаться на амбразуру и сразу строить единый граф поиска с таким количеством сигнатур все же, наверное, перебор.
Ради прикола, конечно, попробую Ragel, транслирующий БНФ-нотацию в C-код: он может быть даже всё это хозяйство прожуёт скопом, но в прод такое пускать — жесть Предсказуемость поведения по мере роста корпуса сигнатур под вопросом.

Поэтому тут напрашивается некий упрощенный пре-фильтр. Например, триграммы. Правильной нарезкой на оные, к слову, тривиально реализуется даже индексируемость под поиск по регуляркам, как это было сделано в Google Code Search, хоть это и несколько другая задача:
http://swtch.com/~rsc/regexp/regexp4.html
https://github.com/google/codesearch/

Да и на случай нетекстовых символов оно вполне экстраполируется, т.к. не влечёт никаких допущений о природе документов и сигнатур.

То есть можно попробовать такую двухходовочку: сначала с помощью триграмм получаем сигнатуры-кандидаты, которые "скорее всего" содержатся во входной последовательности.
Затем алгоритмом Ахо-Корасик ищем по этой последовательности за один проход сокращенным множеством сигнатур-кандидатов.

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

Помнится, в прошлый раз я просто строил из всех сигнатур один большой конечный автомат (препроцессинг). Но это работало на отдельном appliance, где памяти было много. В случае работы на клиентских устройствах столько памяти может и не быть.

Здравствуйте, zx zpectrum, Вы писали:

S>>"До хрена и больше" — сколько именно?
S>>Какие длины у этих сигнатур — все одинаковые/сильно разные/более-менее похожие?
S>>Что вы тут называете N? Количество сигнатур или длину бинарной последовательности, в которой вы ищете данные?
S>>Что у вас чаще меняется — строка, в которой ищут, или набор сигнатур?
ZZ>Приблизительный порядок количества сигнатур — десятки миллионов, с линейным ростом на сотни тысяч в месяц, регулярность пополнения — единицы раз в день. Длины, навскидку, от 6 до 64 байт.
Ок, то есть сейчас сырых данных ~ несколько гигабайт. Рост предполагается на ~1Гб в месяц.
Надо посмотреть — скорее всего, граф поиска будет компактнее из-за объединения общих участков.

ZZ>Спасибо, да, один из очевидных вариантов. Посмотрю. Однако, бросаться на амбразуру и сразу строить единый граф поиска с таким количеством сигнатур все же, наверное, перебор.
ZZ>Ради прикола, конечно, попробую Ragel, транслирующий БНФ-нотацию в C-код: он может быть даже всё это хозяйство прожуёт скопом, но в прод такое пускать — жесть
А зачем вам C-код? Нужна структура в памяти, вместе с алгоритмом запихивания в неё новой сигнатуры. Натравливаете генератор на тестовые наборы сигнатур, снимаете метрики перформанса по добавлению сигнатуры, на поиск, на расход памяти.
ZZ>Предсказуемость поведения по мере роста корпуса сигнатур под вопросом.

ZZ>Поэтому тут напрашивается некий упрощенный пре-фильтр. Например, триграммы. Правильной нарезкой на оные, к слову, тривиально реализуется даже индексируемость под поиск по регуляркам, как это было сделано в Google Code Search, хоть это и несколько другая задача:
ZZ>http://swtch.com/~rsc/regexp/regexp4.html
ZZ>https://github.com/google/codesearch/
О, это интересно, почитаю.
ZZ>Да и на случай нетекстовых символов оно вполне экстраполируется, т.к. не влечёт никаких допущений о природе документов и сигнатур.
ZZ>То есть можно попробовать такую двухходовочку: сначала с помощью триграмм получаем сигнатуры-кандидаты, которые "скорее всего" содержатся во входной последовательности.
А вы предполагаете хранить полный обратный индекс по триграммам, найденным в сигнатурах?
ZZ>Затем алгоритмом Ахо-Корасик ищем по этой последовательности за один проход сокращенным множеством сигнатур-кандидатов.
Надо смотреть на скорость построения поискового графа и селективность предварительного фильтра: не окажется ли так, что построение графа для каждого набора сигнатур-кандидатов сожрёт всё время, сэкономленное на использовании неполного графа?
Опять же, исследуемую программу придётся просматривать дважды — один раз триграммным поиском, второй раз Ахо-Корасиком.