使用正则表达式查找哈希表/字典/地图

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 中前一项开头节点的反向链接。
• [az] 范围在范围中的每个字符下重复插入相同的后续子节点。小心一点，虽然插入/更新可能有点昂贵，但搜索可以与字符串的大小呈线性关系。通过一些占位符，可以控制常见的组合爆炸情况。
• (foo)|(bar) 节点变成多次插入

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

Perl 有几个类似 Text::Trie 的模块，您可以从中寻找想法。（哎呀，我想我什至在很久以前就写过其中一篇）