使用正则表达式查找哈希表/字典/映射
我想知道有没有一种比较有效的方法，可以在字典（或者叫哈希表、映射，反正就是你喜欢的编程语言里的那种东西）中查找，键是正则表达式，而字符串是根据这些键来查找的。举个例子（用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)的解决方案。此外，底层的数据结构可以是任何东西，但我想要的基本行为就是：查找一个字符串，并返回与正则表达式键匹配的值。
19 个回答
一般来说，你需要一个词法分析器生成器。它的作用是把一堆正则表达式变成一个可以识别它们的工具。如果你用的是C语言，可以用“lex”。我自己没在Python中用过词法分析器生成器，但似乎有几个可以选择。谷歌搜索显示了PLY、PyGgy和PyLexer。
如果这些正则表达式在某种程度上都很相似，你可能可以走一些捷径。不过，我们需要更多关于你想解决的具体问题的信息，才能给出建议。你能分享一些示例正则表达式和一些示例数据吗？
另外，你这里有多少个正则表达式？你确定简单的方法不能用吗？正如Rob Pike曾经说过，“当n很小的时候，复杂的算法会很慢，而n通常是很小的。”除非你有成千上万的正则表达式和成千上万的匹配对象，而且这是一个需要用户等待的互动应用，否则你可能还是简单地一个个循环处理正则表达式比较好。
这绝对是可能的，只要你使用的是“真正的”正则表达式。教科书上的正则表达式是指那些可以被一种叫做确定性有限状态机识别的东西，这主要意味着你不能在里面使用回溯引用。
正则语言有一个特性，就是“两个正则语言的并集仍然是正则的”，这意味着你可以用一个状态机同时识别任意数量的正则表达式。这个状态机在处理表达式的数量时是O(1)的时间复杂度（在处理输入字符串的长度时是O(n)的时间复杂度，不过哈希表也是如此）。
一旦状态机完成，你就能知道哪些表达式匹配了，从那时起，查找值的时间复杂度也是O(1)。
你想做的事情和xrdb支持的功能很相似。不过，他们只支持一种比较简单的模式匹配方式。
在内部，你可以通过把正则表达式存储为字符树（trie）来实现更复杂的匹配方式。
- 单个字符就变成树的节点。
- 点号（.）可以用来表示通配符，覆盖当前节点的所有子节点。
- 星号（*）则表示回链，指向前一个项目的起始节点。
- [a-z]这样的字符范围会在范围内的每个字符下重复插入相同的子节点。虽然插入和更新可能会比较耗时，但搜索的时间可以和字符串的大小成线性关系。通过一些占位符的处理，可以控制常见的组合爆炸情况。
- (foo)|(bar)这样的节点会变成多个插入。
这种方法不能处理在字符串任意位置出现的正则表达式，但可以通过在正则表达式的两边加上.*来解决。
Perl有一些类似Text::Trie的模块，你可以借鉴一下它们的思路。（我记得我以前也写过其中一个）