我在 Eclipse 中编码，当我CTRL-F查找一些字符串时，我看到除了整个单词的标准化选项、区分大小写之外，还有一个正则表达式搜索选项（它也在 Notepad++ 中）。
我已经尝试过一次或两次，通常结果几乎是瞬时的。但毕竟代码文件并不庞大，最大的不超过 500 行，大多数行不到一半。有什么方法可以优化，使任何用户提供的正则表达式在大段文本上运行得更快，比如 10-15 MB 的大小？
我想不出任何方法，因为这里没有像 Rabin-Karp 或后缀树这样的标准化搜索算法适用！
问问题
242 次
2 回答
1
我不知道如何在 Eclipse 中实现正则表达式以及为什么它这么慢。这里只是一些想法：
首先，您应该了解几个概念：非确定性有限自动机 (NFA)和确定性有限自动机 (DFA)。理论上，正则表达式、NFA 和 DFA 是等价的，这意味着它们具有完全相同的描述语言（字符序列）的能力。这意味着它们中的任何一个都可以转换为另一个（请参阅此站点）。
正则表达式可以通过将其转换为DFA来实现，并且使用DFA匹配文本只需要线性时间（许多字符串匹配算法，例如KMP，实际上是特殊的DFA）。但是，问题在于，大多数现代正则表达式实现都引入了反向引用等功能，因此无法使用 DFA。
因此，如果可以丢弃那些复杂的特征，那么实现一个快速的正则表达式是可行的（在线性时间内进行匹配）。您可能会在本文中找到更多信息。
于 2013-08-05T02:51:32.927 回答
0
是什么让你认为后缀树不是解决这个问题的合适算法？来自http://en.wikipedia.org/wiki/Suffix_tree：
一旦构建了[后缀树]，就可以快速执行几个操作，例如在 S 中定位子字符串，如果允许一定数量的错误，则定位子字符串，定位正则表达式模式的匹配项等。
我认为修改后的 Boyer-Moore 字符串搜索算法也是可能的。
于 2013-08-04T01:42:41.313 回答