我在 Eclipse 中编写代码，当我执行 CTRL-F 查找一些字符串时，我看到除了整个单词的标准化选项、区分大小写之外，还有一个正则表达式选项也搜索(Notepad++ 中也有)。
我试过一两次，一般来说几乎是立竿见影的效果。但毕竟代码文件并不庞大，最大的也不超过500行，而且大部分行还不到一半。有什么优化方法可以使任何用户提供的正则表达式在大文本(例如 10-15 MB 大小)上运行得更快？
我想不出任何方法，因为这里没有像 Rabin-Karp 或后缀树这样的标准化搜索算法!
最佳答案
我不知道 Eclipse 中的正则表达式是如何实现的，也不知道为什么它这么慢。这里只是一些想法:
首先，有几个概念你应该知道:Nondeterministic finite automaton (NFA)和 Deterministic finite automaton (DFA) .从理论上讲，Regular Expression、NFA、DFA 是等价的，这意味着它们具有完全相同的描述语言(字符序列)的能力。这意味着它们中的任何一个都可以转换为另一个(参见 this site )。
正则表达式可以转化为DFA来实现，使用DFA匹配文本只需要线性时间(很多字符串匹配算法，比如KMP，其实就是特殊的DFA)。然而，问题在于，大多数现代正则表达式实现都引入了反向引用等功能，因此无法使用 DFA。
因此，如果可以丢弃那些复杂的特征，那么实现快速正则表达式将是可行的(在线性时间内进行匹配)。您可以在 this article 中找到更多信息.
关于regex - 有什么方法可以优化通用正则表达式吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18037455/