Здравствуйте, 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>Затем алгоритмом Ахо-Корасик ищем по этой последовательности за один проход сокращенным множеством сигнатур-кандидатов.
Надо смотреть на скорость построения поискового графа и селективность предварительного фильтра: не окажется ли так, что построение графа для каждого набора сигнатур-кандидатов сожрёт всё время, сэкономленное на использовании неполного графа?
Опять же, исследуемую программу придётся просматривать дважды — один раз триграммным поиском, второй раз Ахо-Корасиком.