Регулярное выражение (глобус) дерево поиска

Question

Кто-нибудь знает, как можно адаптировать дерево поиска для обработки ограниченных регулярных выражений? Задача состоит в том, чтобы, учитывая имя файла, найти все узлы, соответствующие этому имени файла. Узлы могут содержать обычные глобусы имен файлов (* и?). Очевидно, что поскольку это дерево поиска, скорость имеет существенное значение.

РЕДАКТИРОВАТЬ: я должен добавить, что наиболее важным случаем для скорости является среднее время, чтобы исключить матч. То есть в большинстве случаев сопоставление не удастся.

Пример: скажем, дерево содержало следующие узлы:

foo, bar, foo *, * bar, foo? Bar

Поиск foo вернул бы узлы 1 и 3. Поиск бара вернул бы узлы 2 и 4. Поиск брелока не вернул бы никаких узлов. Поиск fooxbar вернул бы узел 5. Поиск foobar вернул бы узлы 3 и 4.

Answer 1

Ахорозонное поисковое дерево будет отвечать всем требованиям. Aho-Corasick очень хорошая статья об этом Пытается , и реализация, используемая в Evolution для замены поиска по регулярным выражениям Etrie

Редактировать: Чтобы выполнить сопоставление всей строки, вы можете добавить начальное и конечное состояния привязки, при сканировании многострочных данных вы можете добавить новую строку, чтобы начать и закончить. Вы также можете удалить часть, в которой добавлена ​​перекрестная ссылка для частичного сопоставления, начиная другое совпадение, это также позволяет ускорить исключение.

Другой алгоритм проверки членства в наборе строк: CritBit . Здесь нет Regex, но он прост и тестирует завершенные строки.