我有很多字符串(大约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
(我还没有进行进一步的调查。稍后我将扩展这个答案。)