Дерево поиска регулярного выражения (glob)

Question

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

EDIT: Я должен добавить, что самым важным случаем для скорости является среднее время, чтобы исключить совпадение. То есть, в большинстве случаев совпадение не будет выполнено.

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

Foo, Bar, Foo *, * бар, Foo

запретить

Поиск Foo будет возвращать узлы 1 и 3. При поиске бар? вернет узлы 2 и 4. Поиск фоба не возвратит ни одного узла. Поиск fooxbar вернет узел 5. Поиск foobar вернет узлы 3 и 4.

Answer 1

Дерево поиска aho-corasick будет соответствовать счету. Aho-Corasick очень хорошая статья о таком роде вещи Tries, и реализация, используемой в эволюции, чтобы заменить регулярное выражение поиска Etrie

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

Еще один алгоритм проверки членства в наборе строк - CritBit. Это не имеет Regex, но это простое и полное тестирование строк.