Эффективный алгоритм сопоставления строк с очень большим набором шаблонов

Вот подход, который мы довольно успешно использовали (реализация здесь):

Добавление шаблонов:

Для любого шаблона существует набор подстрок, которые должна содержать строка, чтобы иметь шанс совпасть с ней. Назовите эти метаслова. Например:

dog*fish -> [dog, fish]
[lfd]og  -> [og]
dog?     -> [dog]

Когда вы добавляете шаблон в структуру данных, разбивайте его на метаслова и сохраняйте их в структуре данных, соответствующей строке Ахо-Корасика. Поддерживайте внутреннюю структуру данных, чтобы сопоставлять метаслова со словами-шаблонами.

Выполнение запросов:

Получив входную строку, используйте созданную вами структуру данных Ахо-Корасика, чтобы получить все метаслова, содержащиеся в этой строке. Затем, используя созданную вами карту, проверьте шаблоны, соответствующие этим метасловам.

Это хорошо работает, потому что, хотя сопоставление строк происходит довольно медленно, вы можете очень быстро сузить количество шаблонов, с которыми вам действительно нужно сопоставляться. Наша реализация может выполнять около 200 000 запросов в секунду на обычном ноутбуке по наборам из более чем 150 000 шаблонов. См. режим бенчмаркинга в программе, чтобы проверить это.

Один из подходов, который приходит на ум, заключается в создании древовидных структур шаблонов.

Пример: http://* будет содержать все шаблоны (перечисленные выше). http://*.site1.com/* будет содержать все site1.com. Это может значительно сократить количество шаблонов, которые необходимо проверить.

Кроме того, вы можете определить, какие шаблоны являются взаимоисключающими, чтобы еще больше сократить список, который вы ищете.

Итак, сначала возьмите все шаблоны и создайте из них деревья. Выполните поиск по всем корням, чтобы определить, какие ветви и узлы необходимо проанализировать.

Улучшите алгоритм, определив, какие ветки являются взаимоисключающими, чтобы, обнаружив попадание в данную ветку, вы знали, какие ветки/узлы не нужно посещать.

Для начала вы можете быть ленивым, и ваш первый проход может состоять в том, чтобы отсортировать шаблоны и сделать простой следующий шаблон, содержащий логику этого типа шаблона, чтобы определить, содержится ли «это» в следующем. ПРИМЕР: if( "http://*.site1.com/*".startsWith("http://*") == true )

Вы могли бы стать более изощренной в своей способности определять, действительно ли один шаблон содержит другой, но это поможет вам начать.

Чтобы лучше определить вопрос:

«Этот шаблон содержит этот шаблон?»

Я считаю, что вам нужно будет разобрать регулярное выражение... Эта статья выглядит хорошим местом для начала, чтобы понять, как это сделать: Разбор регулярных выражений с рекурсивным спуском

Если набор URL-адресов не меняется очень быстро, вам действительно следует использовать механизм регулярных выражений, который компилирует его шаблоны. Java предоставляет один из них, но он может быть неудовлетворительным, если вы хотите знать, какой шаблон соответствует.

Широко используемый механизм для выполнения этого и определения совпадения — это различные генераторы лексеров, например, FLEX и подобные инструменты. Они принимают количество регулярных выражений для каждой «лексемы» и создают интегрированный FSA для распознавания любого из них, который чрезвычайно эффективен для выполнения.

Вы можете вызвать Flex, когда ваш набор изменится. Если это слишком медленно, получите версию Flex с открытым исходным кодом и интегрируйте ее в свой движок; он внутри создает FSA, поэтому вы можете использовать его напрямую. (вероятно, потребуется некоторая инженерия). Но если у вас действительно есть проблема сопоставления с высокой производительностью, некоторая работа, чтобы сделать это хорошо, не будет вас беспокоить.

Если набор URL-адресов меняется быстрее, чем FLEX может генерировать FSA (странно), у вас есть реальная проблема. В этом случае вы можете построить онлайн-дерево дискриминации, сканируя «регулярное выражение» слева направо и интегрируя символы/предикаты, которые вы видите, в ваше существующее дерево дискриминации. Затем сопоставление состоит из спуска по дереву различения, выполнения различных тестов; если вы дойдете до листа, у вас есть совпадение, иначе нет. Это может быть так же быстро, как автоматизация, созданная FLEX, если все сделано правильно, но, вероятно, намного, намного больше.