使用正则表达式的Hashtable/dictionary/map查找

Question

我试图找出是否有一种合理有效的方法来执行字典（或哈希，或映射，或任何您喜欢的语言调用它）中的查找，其中键是正则表达式，字符串是根据键集查找的。例如（在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）的东西。此外，底层数据结构可以是任何东西，但我希望的基本行为是上面写的：查找字符串，并返回与正则表达式键匹配的值。

Answer 1

您想要做的与xrdb所支持的非常相似。然而，他们只支持一个相当小的全球化概念。

在内部，通过将正则表达式存储为字符trie，可以实现比它们更大的正则语言家族。

• 单个字符只是trie节点。
• 。成为覆盖当前trie节点的所有子节点的通配符插入。
• *将成为前一项开始处trie to节点中的反向链接。
• [a-z]ranges在范围中的每个字符下重复插入相同的后续子节点。小心，虽然插入/更新可能有点贵，但搜索在字符串大小上可以是线性的。使用一些占位符可以控制常见的组合爆炸情况。
• （foo）|（bar）节点变成多个插入

这不处理出现在字符串中任意点的正则表达式，但可以通过在任意一侧用.*包装正则表达式来建模。

Perl有两个类似于Text：：Trie的模块，您可以对其进行raid以获取想法。（见鬼，我想我甚至在很久以前就写过了）

Answer 2

这与任何语言中的常规哈希表都不可能实现。您要么必须遍历整个键集，尝试将键与正则表达式匹配，要么使用不同的数据结构。

您应该选择一个适合您试图解决的问题的数据结构。如果必须与任意正则表达式匹配，我不知道有什么好的解决方案。如果要使用的正则表达式类的限制性更强，则可以使用数据结构，如trie或suffix tree。

Answer 3

一般来说，你需要的是一个lexer生成器。它需要一堆正则表达式并将它们编译成识别器。”lex“如果你用的是C，它就可以工作了。我从来没有在Python中使用过lexer生成器，但似乎有几个可以选择。谷歌显示PLY、PyGgy和PyLexer。

如果正则表达式在某种程度上彼此相似，则可以使用一些快捷方式。我们需要更多地了解您试图解决的最终问题，以便提出任何建议。可以共享一些示例正则表达式和一些示例数据吗？

另外，这里要处理多少个正则表达式？你确定天真的方法不会奏效吗？正如Rob Pikeonce said，“当n很小，而n通常很小时，花哨的算法很慢。”除非你有成千上万的正则表达式，并且有成千上万的东西可以与它们匹配，而且这是一个用户正在等待你的交互式应用程序，否则你最好用简单的方法并在正则表达式之间循环。