但是你为什么要这样做？

假设，您开发了流行的云服务之一（例如AWS Lambda）。一百万客户正在使用您的服务，该客户创建了数千万件实例。像任何其他云服务一样，您的服务也具有一些结构化配置。配置通常看起来像一堆钥匙值字符串。类似：

...
output_path=s3://my_production_bucket
output_path=s3://my_test_bucket
output_path=s3://blackholepath
...

总共有数十亿美元的关键值字符串。这几乎产生了钥匙值字符串的Terabyte。

这样受欢迎的服务的所有者，维护配置和服务是您的工作：引入新参数，贬低旧参数，监视使用某些功能的频率等。一个使您可以快速执行查询的工具：“显示所有键值对匹配${regular_expression}”。

在这里，我想强调迅速显示的重要性。对于手动维护任务，例如检查所有钥匙值对不变，延迟可能并不重要。主要是因为面对这种延迟的开发人员。当这种延迟暴露于客户时，它变得越来越重要。不难想象这种情况。例如，在配置上验证某些全局不变式（表示为正则表达式匹配数）可能很有用，这些configs需要在客户端将配置提交服务之前需要检查。

好的，开箱即用什么解决方案？

肯定有很多数据库可以允许REGEX匹配搜索：[1]，[2]等

大多数人虽然不这样做快速，并且需要整个数据库扫描。有一些解决方案可以加快速度，例如[3]和[4]。但是最终，在最无约束的正则表达搜索中需要扫描整个数据库。

虽然有一个技巧！

如果您的大多数正则疑问是由人类产生的，那么他们可能具有长期的子弦，没有特殊字符。更重要的是，这些子串可能必须是匹配字符串的一部分。例如：

.*_path=s3.*
.*id=[0-9]{1,4}order

每个与第一个正则匹配的字符串都必须将_path=s3作为子字符串。每个与第二个表达式匹配的字符串都必须同时具有id=和order作为子弦。

这不是一个不好的假设。如果您的开发人员 /客户端正在编写查询以执行常规 /自动化搜索任务，则可能是正确的。同时，它对所有查询都无法使用。希望您可以以明确的方式设计围绕它的UX：如果查询不符合优化要求，延迟将不好。

在任何情况下，如果假设是正确的，则很棒，因为数据库得到了很好的支持。同时，基于n-gram（广泛支持这些索引）的子弦指数可以非常自然地分布（基本上是将N-gram集分开为单独的节点）。

让我们研究一下这将大约减少您的搜索空间。让我们假设您只有一个三个字母的子弦，必须出现在查询结果中，并且3克是均匀分布的（当然，这在实践中不是正确的，但是对于信封计算的背面是可以的）。在这种情况下，它将搜索大约将搜索减少36（字母加上数字的字母）。这是4.5个数量级！

实施技巧

我不会尝试详细解释如何在此处实施。相反，我将链接留给了所有相关信息。

要获取必须在匹配的字符串中发生的所有子串，您需要将正则表达式解析为某些语法树，然后进行分析。此线程[5]对如何做。

在许多数据库中支持构建N-Gram索引。如果您已经有一个数据库，则您可能可以在此处配置它。这是一个[6]的示例。如果您没有一个并且不想依赖另一个数据库，那么仅基于Sstables [7]实现一个数据库。

最后的想法

这里的总体想法是，在您的正则表达式查询的语法树中寻找模式可以帮助您的速度优化很多。

即使您的某些查询没有在所有结果中都必须出现的字符串，也许还有其他一些常见模式。例如，像(one)|(two)这样的查询没有常见的子弦，但同时它们可以通过同一子弦n-gram索引轻松优化它们。

感谢您的阅读，让我知道您在评论中对此有何看法！