我正在研究scala/java中一个非常通用的正则表达式案例。我有一组非常大的网址(~20亿(，我想根据它们匹配的正则表达式(~70k(为每个网址分配一个id。单个 url 可以映射到多个正则表达式。问题在于正则表达式集。它们非常通用，因此会导致贪婪的搜索。我尝试使用 [\w\W]？ 代替 .(请参阅下面的示例(。但它仍然非常慢。我正在使用的环境是Spark/scala。任何想法如何优化它？ 下面是一个示例：
网址示例： https://www.amazon.com/dp/B07GC9PL97/ref=sspa_dk_detail_4?psc=1&pd_rd_i=B07GC9PL97&pf_rd_m=ATVPDKIKX0DER&pf_rd_p=a54d13fc-b8a1-4ce8-b285-d77489a09cf6&pf_rd_r=Z6B30TKHBX693HZ53QWP&pd_rd_wg=Z3avy&pf_rd_s=desktop-dp-sims&pf_rd_t=40701&pd_rd_w=k7nGf&pf_rd_i=desktop-dp-sims&pd_rd_r=220cc48e-b142-11e8-ad5d-f9d1f1abea37
正则表达式示例： .*amazon.*desktop-dp.* 将其转换为
[\w\W]*？amazon[\w\W]*？desktop-dp[\w\W]*？否，[wW]匹配所有内容，而.匹配除换行符以外的所有内容。所以我不认为，你可以通过切换它们来获得任何东西。
你可以使用
.*?amazon.*?desktop-dp.*?
对于不情愿的搜索，但我认为不会有所帮助。您可以使用
类似boolean hasTwoSubstringsInOrder(String haystack, String needle1, String needle2) {
int index1 = heystack.indexOf(needle1);
if (index1 == -1) return false;
int index2 = heystack.lastIndexOf(needle2);
if (index2 == -1) return false;
return index1 + needle1.length() <= index2;
}
这很可能更快，尽管增益可能还不够。鉴于 URL 数量巨大，您可以使用一些预处理，例如提取所有相关令牌，可能使用string.split("[^-a-zA-Z0-9]")之类的东西(但使用Pattern.compile(。
显然，只有当 URL 同时包含amazon和desktop-dp时，您的模式才能匹配。如果你的数据集不是那么大，我建议使用类似Multimap<String, String> tokenMap将令牌映射到一组 URL，并使用较小的tokenMap.get("amazon")和tokenMap.get("desktop-dp")进行进一步处理。我对火花一无所知，但我敢打赌，它提供了这样的东西。