Я пытаюсь выяснить, есть ли достаточно эффективный способ выполнить поиск в словаре (или хэше, или карте, или как там ваш любимый язык называет это), где ключи являются регулярными выражениями, а строки ищутся против набора ключей. Например (в синтаксисе Python):
>>> regex_dict = { re.compile(r'foo.') : 12, re.compile(r'^FileN.*$') : 35 }
>>> regex_dict['food']
12
>>> regex_dict['foot in my mouth']
12
>>> regex_dict['FileNotFoundException: file.x does not exist']
35
(Очевидно, что приведенный выше пример не будет работать так, как написано на Python, но я бы хотел, чтобы это было возможно.)
Я могу придумать наивный способ реализовать это, в котором я перебираю все ключи в словаре и пытаюсь сопоставить переданную строку с ними, но затем я теряю время поиска O (1) хэш-карта и вместо этого есть O (n), где n это количество ключей в моем словаре. Это потенциально большое дело, так как я ожидаю, что этот словарь станет очень большим, и мне нужно будет искать его снова и снова (на самом деле мне нужно будет перебирать его для каждой строки, которую я читаю в текстовом файле, и размер файла может достигать сотен мегабайт).
Есть ли способ сделать это, не прибегая к эффективности O (n)?
В качестве альтернативы, если вы знаете способ выполнения такого поиска в базе данных, это тоже было бы замечательно.
(Подойдет любой язык программирования - я использую Python, но меня больше интересуют структуры данных и алгоритмы здесь.)
Кто-то указал, что возможно более одного совпадения, и это абсолютно правильно. В идеале в этой ситуации я хотел бы вернуть список или кортеж, содержащий все совпадения. Я бы согласился на первый матч.
Я не вижу возможности O (1) в этом сценарии; Я бы согласился на что-то меньшее, чем O (n). Кроме того, базовая структура данных может быть любой, но я хотел бы описать базовое поведение, описанное выше: поиск строки и возврат значений, соответствующих ключам регулярного выражения.