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

我有一些正则表达式模式.输入字符串时,我必须找到与此字符串匹配的所有模式.这通常是O(n)操作:

SELECT regex FROM regexes WHERE 'string' RLIKE regex

最快的方法是什么？是否存在针对此类操作进行优化的数据库结构或存储系统？

最简洁的答案是不.' 目前在任何DBMS平台上都没有索引结构可以索引像这样的正则表达式的部分匹配.

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

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

Rete通过计算部分匹配并且仅显示可以从该部分匹配到达的规则来工作,因此它比O(n)更有效(更像是O(log n)但是我不确定准确的时间复杂度)将n个规则与事实相匹配.