iPhone:RegexKit 与 RegexKit lite - 遍历数组需要很长时间

Question

对于我的应用程序，我需要查看 url 是否与正则表达式字符串匹配。所以我创建了一个包含所有正则表达式字符串(大约 1000 多个字符串)的数组，并使用 RegexKit lite 检查它们:

for (NSString * aString in mainDelegate.whiteListArray) {

if (![urlString isMatchedByRegex:aString]) {

它可以工作，但遗憾的是这个操作需要很长时间。对于像 google.com 这样的网页，至少需要 20 秒

我尝试过使用“普通”RegexKit.framework，因为它有一个名为 (BOOL)isMatchedByAnyRegexInArrayNSArray *)regexArray 的方法，该方法要快得多。我可以构建应用程序，但每当我尝试启动它时，它就会崩溃并出现以下错误:

dyld: Library not loaded: @executable_path/../Frameworks/RegexKit.framework/Versions/A/RegexKit Referenced from: /Users/Reilly/Library/Application Support/iPhone Simulator/User/Applications/7E057EA8-5CD1-465B-8102-38A53A9B5F5B/Drowser.app/Drowser Reason: image not found

我想这是因为 RegexKit 不适用于 ARM ？ (包括我遵循文档中提供的方法的 RegexKit)

所以我的问题是:

如果字符串被 1000 个正则表达式中的任何一个匹配，您是否知道任何更快的方法来检查字符串。

或者你知道如何在 iPhone 或任何其他正则表达式框架上使用“普通”RegexKit，它可以在一秒钟内完成我需要的操作吗？

提前致谢

Answer 1

注意:我是 RegexKit 等人的作者。

这是一个相当复杂的答案.. :)

首先，将一千个正则表达式与任何常用的正则表达式引擎实现匹配会相当慢，可能除了 TCL 和 TRE 正则表达式引擎。 RegexKit.framework 在这个任务中的性能大大优于 RegexKitLite 的原因是 RegexKit.framework 有相当多的非平凡的优化代码来完成这个任务。这样做的原因是因为它用于 Safari AdBlock，它需要对 URL 执行正则表达式的批量匹配。它根据它们成功匹配的次数保持正则表达式列表按排序顺序排列。这是基于观察到 Safari AdBlock 中使用的一些正则表达式模式比其他模式匹配得更频繁，并且首先尝试这些模式大大减少了需要尝试确定是否存在“命中”的正则表达式的数量。还有一个小的负命中缓存，以及许多并行执行匹配的多线程代码。这些都不会出现在 Lite 版本中，因为它绝对不是一个轻量级的功能——可能有 60-70KB 的代码只是为了实现这个功能，更不用说保持一千个编译的巨大内存占用了正则表达式。

使用 RegexKitLite 做这种模式匹配肯定会非常非常慢。第一个问题是它只保留了最近使用的编译正则表达式的小缓存。默认情况下，缓存设置为仅 23 ，因此向其扔一千个正则表达式将导致每次使用每个正则表达式时都会对其进行编译。

正如其他人指出的那样，RegexKit.framework 并没有真正设置为在 iPhone 上使用。即使您绕过“链接到外部框架”规定，RegexKit.framework 的默认构建也不在其胖二进制文件中包含 arm 架构(它包括 ppc 、 ppc64 、 i386 和 x86_64 )。你真正需要做的是设置一个新的构建目标来创建一个静态库。做起来并不难，真的。

恐怕如果这种模式匹配是您需要做的事情，您可能不得不推出自己的正则表达式引擎。您需要的是一个正则表达式引擎，它可以将您的数千个正则表达式连接在一起，例如“r1|r2|r3|r4”。大多数正则表达式引擎，特别是 pcre 和 ICU (分别由 RegexKit.framework 和 RegexKitLite 使用的引擎)以几乎从左到右的方式评估这样的正则表达式。需要的是一个几乎类似于 DFA 的引擎，它可以同时评估所有可能的状态。有关详细信息，请参阅 this link。我已经构建了这样一个正则表达式引擎，它甚至可以在 ~ O(M*log2(N))(M 是要匹配的文本的大小，N 是正则表达式的大小)时间内处理反向引用(比每个人都说的容易得多)，但是它还没有完成。如果是这样，它将像等 ionic 炬穿过黄油一样解决这类问题。

不过，我知道至少有一个人将 RegexKit.framework 移植到 iPhone: Mobile Safari AdBlock 。 AFAIK，它也是桌面版 Safari AdBlock 的一个端口。我不知道很多细节，但我认为它需要安装越狱的 iPhone。

总之，我认为没有任何可用于 iPhone 开发的交 key 解决方案可以满足您的需求。除了创建自己的正则表达式引擎之外，最好的选择是查看 TRE regex engine 并尝试使用串联的正则表达式进行一些实验。不过，要做好卷起袖子的准备，因为你将不得不弄脏你的手并处理 Cocoa 的字符串、Unicode 编码和各种其他令人不快的东西——RegexKitLite 需要的那种东西在幕后为您照顾。