Форма неохотное регулярное выражение из общих регулярных выражений

Question

Я работаю над очень общим случаем регулярных выражений в scala / java. У меня очень большой набор URL-адресов (~ 2 миллиарда), и я хочу назначить идентификатор для каждого URL-адреса на основе регулярных выражений (~ 70 КБ), которые им соответствуют. Один URL может отображаться более чем в 1 регулярном выражении. Проблема заключается в множестве регулярных выражений. Они очень общие и, следовательно, приводят к жадному поиску. Я пытался использовать [\ w \ W] ? вместо. (см. образец ниже). Но это все еще очень медленно. Среда, с которой я работаю - Spark / scala. Есть идеи, как это оптимизировать? Вот образец:

URL-образец: 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

Regex-образец: . * amazon. * desktop-dp. * преобразовал это в [\ w \ W] *? amazon [\ w \ W] *? desktop-dp [\ w \ W] *?

Answer 1

Нет, [\w\W] соответствует всему, в то время как . соответствует всему, кроме разрыва строки. Поэтому я не думаю, что вы можете получить что-нибудь, переключая их.

Вы можете использовать

.*?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") для дальнейшей обработки. Я ничего не знаю о свечах, но готов поспорить, что это что-то вроде этого.