我有很多字符串(可能大约 50k-1M，都不会太长，可能 1-20 个字符)。现在我得到任何 RegExp，我需要返回所有匹配字符串的列表/迭代器。这必须尽可能快。
什么是好的索引结构来做到这一点？
目前，我正在根据字符串的字符构建一棵树。然后我将 RegExp 转换为确定性自动机。然后我计算该自动机与树的交集。这看起来是一种快速的方法，但我想知道其他可能性。
另一个挑战是支持 Unicode/UTF8，但我现在不想把这个问题集中在这一点上。
最佳答案
我刚找到 codesearch project似乎已经实现了这一点。解释在这里:Regular Expression Matching with a Trigram Index .
另一篇相关文章可能是这样的:Regular Expression Matching Can Be Simple And Fast
(我还没有真正深入研究它。我稍后会扩展这个答案。)
关于regex - 在大量字符串上测试 RegExp，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23559919/