我有很多字符串（可能大约 50k-1M，所有字符串都不太长，可能 1-20 个字符）。现在我得到任何正则表达式，我需要返回所有匹配字符串的列表/迭代器。这必须尽可能快。
有什么好的索引结构可以做到这一点？
目前，我正在字符串的字符上构建一棵树。我将 RegExp 转换为确定性自动机。然后我计算该自动机与树的交集。这看起来是一种快速的方法，但我想知道其他可能性。
一个额外的挑战是支持 Unicode/UTF8，但我现在不想把这个问题集中在那个位上。
问问题
60 次
1 回答
0
我刚刚找到了似乎已经实现的代码搜索项目。解释在这里：Regular Expression Matching with a Trigram Index。
另一篇相关文章可能是这样的：正则表达式匹配可以简单快速
（我还没有真正进一步调查。我稍后会扩展这个答案。）
于 2014-05-09T11:47:19.183 回答