Лучше, чем O (N) Glob Matcher?

Question

Проблема: Учитывая список globs , мне нужно найти (и вернуть) глобус из списка, которому соответствует данная строка или окончательно определить, что ни один не соответствует.Исключая время установки, производительность должна быть лучше, чем линейный поиск всех глобусов:

foreach glob in list:
  if glob.matches(string):
    return glob
return None

Вопрос: Есть ли для этого доступные библиотеки (предпочтительно C ++)?

---

Редактировать: Подумав еще немного, я думаю, что могу утверждать, что это можно сделать.Учитывая, что глобусы являются более или менее регулярным выражением с другим синтаксисом, версия lex, которая использует синтаксис глобуса, будет соответствовать всем требованиям.

Учитывая, что проблема может быть просто сведена к известной,все еще заинтересованы в реализованных решениях.

Answer 1

Преобразуйте ваши глобусы в регулярные выражения (это может быть достигнуто с помощью ряда простых операций со строками - * становится .* и т. Д.). Объедините их в одно регулярное выражение, используя | и назначив результаты в разные группы захвата для каждого глобуса, чтобы вы могли определить, какой глобус совпадал, если было совпадение. Положитесь на свою любимую библиотеку регулярных выражений, чтобы скомпилировать регулярное выражение в DFA, который, как мы надеемся, более оптимален для обработки, чем линейный обход составных частей, где это возможно - однако в самом общем случае это не будет быстрее.

Answer 2

Глобусы - это подмножество регулярных выражений (относительно выразительной силы, а не точного синтаксиса). Поэтому глобусы могут быть преобразованы в детерминированные конечные автоматы (DFA), и они могут быть объединены в единый DFA, который распознает объединение отдельных DFA. DFA имеют сложность O (n), где n - длина строки. От того, из каких глобусов сконструирован автомат, зависит только время установки (т.е. создание автомата), а не время выполнения.

Answer 3

Я бы посмотрел, подходит ли ваше приложение для анализатора сдвига , например bison .Они используют таблицы поиска, которые являются трудной для настройки или изменения и используют больше памяти, но очень быстры.Технически, физически невозможно сделать лучше, чем O (n) наихудший случай , но в зависимости от ваших глобусов, строк и вашего токенизатора, использование такой техники может сделать ваше среднее случай намного лучше, чем этот, потому что он устраняет шаблоны, которые не совпадают без необходимости проверять каждый из них каждый раз.

Answer 4

Вероятно, только в некоторых частных случаях. Если вы можете как-то предсказать, что некоторые глобусы не будут соответствовать вашей строке.

Answer 5

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

РЕДАКТИРОВАТЬ: В общем случае это невозможно с использованием шаров. Как отмечается в комментарии, возможно комбинирование некоторых комбинаций глобусов (на первый взгляд может быть полезно три дерева, где каждый узел указывает следующую букву для сопоставления и глобусы, которые вам еще нужно проверить), что вызывает меньший объем работы поиск.

В общем случае также возможно преобразовать набор глобусов в соответствующее регулярное выражение.

Является ли производительность этого соответствия такой проблемой, что вам нужно ее улучшить? Рассматривали ли вы, если более фундаментальное алгоритмическое переписывание может быть лучше?