适用于将字符串与正则表达式模式匹配的数据库或结构

Question

我有很多正则表达式模式。输入字符串时，我必须找到所有与该字符串匹配的模式。这通常是一个O(n) 操作:

SELECT regex FROM regexes WHERE 'string' RLIKE regex

最快的方法是什么？是否有优化的数据库结构或存储系统来执行此类操作？

Answer 1

简短的回答是“否”。目前在任何 DBMS 平台上都没有索引结构可以像这样索引正则表达式的部分匹配项。

长答案是通配符匹配的前导常量(例如 'foo_')可以用作索引匹配的前缀。许多 DBMS 平台将对此进行优化并使用索引(如果可用)来解析前缀。然而，这并不像一个完整的正则表达式那么聪明，而且索引只能在你有一个常量前缀的情况下使用。

更长的答案是有算法，如RETE这将像这样优化部分匹配。如果您可以将匹配项表示为前向链接生成规则而不是正则表达式，这可能适用。

Rete 的工作原理是计算部分匹配，并且只呈现可以从这个部分匹配达到的规则，所以它比 O(n) 更高效(更像是 O(log n) 但我不确定确切时间complexity)匹配 n 条规则。