Подскажите, пожалуйста, хороший (т.е. эффективный в плане скорости) алгоритм для следующей задачи.
На вход функции подается текстовая строка. Нужно проверить, совпадает ли она по маске с
хотя бы одной строкой из списка правил. Каждое правило — это текстовая строка, которая может
содержать wildcard-символ *. Приведу пример:
(здесь будут совпадения по *.txt и по *path*/*ello*)
Предполагаем, что такие проверки выполняются много-много раз в секунду, а сам список правил
содержит тысячи и даже миллионы элементов. Хотелось бы не проходить по всему списку, а
использовать что-то вроде двоичного поиска.
Список правил формируется динамически, во время работы программы, поэтому строить из него
какую-то предкомпилированную модель нельзя. Также нельзя использовать средства с динамической
генерацией кода (JIT и т.п.) — такие ограничения среды.
Хочется найти не столько реализацию (C/C++), сколько описание самого алгоритма.
Здравствуйте, okman, Вы писали:
O>Список правил формируется динамически, во время работы программы, поэтому строить из него O>какую-то предкомпилированную модель нельзя. Также нельзя использовать средства с динамической O>генерацией кода (JIT и т.п.) — такие ограничения среды.
При таких ограничениях быстро не будет ИМХО.
Можно поддерживать три структуры: префиксное дерево, суффиксное дерево и список шаблонов вида *someapp*. Проверяем сначала по префиксам/суффиксам, затем по остальной части шаблона.
Здравствуйте, okman, Вы писали:
O>(здесь будут совпадения по *.txt и по *path*/*ello*)
Из теории БД известно, что выражение like '%что-то%' сразу делает индексы неэффективными и приводит к полному скану таблицы
Если бы можно было упростить задачу запретив использовать паттерны в начале и/или конце строки, тогда какое-то готовое эффективное алгоритмическое решение можно будет прикрутить
Здравствуйте, α, Вы писали:
α>Из теории БД известно, что выражение like '%что-то%' сразу делает индексы неэффективными и приводит к полному скану таблицы
Здравствуйте, okman, Вы писали:
O>Подскажите, пожалуйста, хороший (т.е. эффективный в плане скорости) алгоритм для следующей задачи.
O>На вход функции подается текстовая строка. Нужно проверить, совпадает ли она по маске с O>хотя бы одной строкой из списка правил. Каждое правило — это текстовая строка, которая может O>содержать wildcard-символ *. Приведу пример:
O>Ввод: /path/hello.txt O>Правила: *.pdf;*.txt;*someapp*;*path*/*ello*
O>(здесь будут совпадения по *.txt и по *path*/*ello*)
O>Предполагаем, что такие проверки выполняются много-много раз в секунду, а сам список правил O>содержит тысячи и даже миллионы элементов. Хотелось бы не проходить по всему списку, а O>использовать что-то вроде двоичного поиска.
Никогда не пробовал этого сам и тем более не знаю, как это будет работать на миллионах правил. Но поскольку, судя по задаче, тебе всё равно, какое именно срабатывает, важно только сработало или нет, то из них из всех можно сделать большой-большой конечный автомат, и он обработает строку за линейное время и скажет, подошла или не подошла. Линейное относительно длины строки, а не количества правил, сколько там правил вообще не важно.
O> Хотелось бы не проходить по всему списку, а использовать что-то вроде двоичного поиска.
O>Список правил формируется динамически, во время работы программы, поэтому строить из него O>какую-то предкомпилированную модель нельзя.
Посчитать частоту константных символов в каждом правиле, на основе этой частоты простроить дерево поиска — так ты будешь уменьшать количество правил, а там уже перебором проверять.
Этот способ, конечно, работает для не очень длинных строк — чем длиннее и разнообразнее строка, тем больше правил будут подходить по частоте константных символов. Зато к обновлению правил очень дружественый.
Здравствуйте, okman, Вы писали:
O>На вход функции подается текстовая строка. Нужно проверить, совпадает ли она по маске с O>хотя бы одной строкой из списка правил. Каждое правило — это текстовая строка, которая может O>содержать wildcard-символ *. Приведу пример:
O>Предполагаем, что такие проверки выполняются много-много раз в секунду, а сам список правил O>содержит тысячи и даже миллионы элементов. Хотелось бы не проходить по всему списку, а O>использовать что-то вроде двоичного поиска.
Делал почти такое недавно, там надо наиболее подходящее одно правило выбрать и списка подходящих, и само правило уже задано регуляркой. Нагрузка- десятки правил, проверка ну скажем 10 в секунду. Сделал с модифицированной регуляркой и перебором.
Тебе действительно нужен мега- FSA один на все правила, а у меня было сделано по отдельному автомату на правило. Если разберешься- выложи здесь. Мне тоже интересно.
В принципе, wildcard- это существенное упрощение задачи. Сделать типа суффиксного дерева, в узлах прицепить ключик и хранить в каком-то виде данные мемоизации (как копия массива на поток исполнения, а ее представление описано твоим суффиксным деревом).
Здравствуйте, okman, Вы писали:
O>Список правил формируется динамически, во время работы программы, поэтому строить из него O>какую-то предкомпилированную модель нельзя.
А почему нельзя? Можно же при модификации/добавлении правила сразу модифицировать вспомогательную структуру данных, разве нет?
Если могут быть только джокеры ('*'), а не полноценная регулярка, то может сработать такой вариант: каждое правило вида *Строка1*Строка2*Строка3* представляем в виде массива [Строка1, Строка2, Строка3]. Т.е. разбиваем по джокерам. Отдельно рядом с массивом храним признак наличия джокера в начале и в конце шаблона. Все такие фрагменты (строки без джокеров) из всех шаблонов складываем в одну структуру типа суффиксного дерева (сохраняя при этом информацию, в какие шаблоны входит каждая строка). Далее: Входную строку прогоняем по суффиксному дереву и определяем, какие фрагменты каких шаблонов там есть.
Отбираем шаблоны, для которых в строке присутствуют все фрагменты
Смотрим, есть ли шаблон(ы), для которых строки присутствуют в нужном порядке.
Шаги 2 и 3 уже работают с небольшим объёмом данных, по идее.
