Алгоритм быстрого сопоставления строк с поддержкой простых подстановочных знаков

Question

Мне нужно сопоставить входные строки (URL-адреса) с большим набором (от 1 до 250 тысяч) строковых правил с простой поддержкой подстановочных знаков.

Требования для поддержки подстановочных знаков следующие:

Подстановочный знак (*) может заменять только «часть» URL-адреса.Это фрагменты домена, пути и параметров.Например, «*.part.part/*/part?part=part&part=*».Единственное исключение из этого правила — область пути, где «/*» должно соответствовать всему, что находится после косой черты.

Примеры:

• *.site.com/* — должно соответствовать sub.site.com/home.html, sub2.site.com/path/home.html.
• sub.site.*/path/* – должно соответствовать sub.site.com/path/home.html, sub.site.net/path/home.html, но не соответствовать sub.site.com/home.html.

Дополнительные требования:

• Быстрый поиск (я понимаю, что «быстрый» — понятие относительное.Учитывая максимальное количество правил в 250 тысяч, время все равно находится в пределах < 1,5 с. если возможно.)
• Работайте в рамках современного рабочего стола (например.не серверная реализация)
• Возможность возвращать совпадения 0:n для заданной входной строки.
• К матчам будут прикреплены данные правил.

Какая система/алгоритм лучше всего подходит для такой задачи?Я буду разрабатывать решение на C++, а сами правила будут храниться в базе данных SQLite.

Answer 1

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

Пример

Rule: *.site.com/*
    domain => *.site.com
    path   => /*
    query  => [empty]

URL: sub.site.com/path/home.html
    domain => sub.site.com
    path   => /path/home.html
    query  => [empty]

Matching process:
    domain => *.site.com matches sub.site.com?     YES
    path   => /*         matches /path/home.html?  YES
    query  => [empty]    matches [empty]           YES

Result: MATCH

Поскольку вы храните правила в базе данных, я бы хранил их уже разбитыми на эти три части.А если вам нужна сверхскорость, вы можете конвертировать *это к %, а затем использовать собственный код базы данных LIKE операцию, чтобы выполнить сопоставление за вас.Тогда у вас просто будет запрос типа

SELECT *
FROM   ruleTable
WHERE  @urlDomain LIKE ruleDomain
   AND @urlPath   LIKE rulePath
   AND @urlQuery  LIKE ruleQuery

где @urlDomain, @urlPath, и @urlQuery являются переменными в подготовленном операторе.Запрос вернет правила, соответствующие URL-адресу, или пустой набор результатов, если ничего не соответствует.

Answer 2

Прежде всего, один из худших результатов поиска — использование подстановочных знаков на обоих концах строки ".domain.com/путь"... и я думаю, что ты очень сильно пострадаешь в этом деле.Итак, моя первая рекомендация — изменить порядок доменов, хранящихся в вашей БД:com.domain.example/path1/path2/page.html.Это позволит вам сохранить порядок и использовать подстановочные знаки только в «одном направлении» в строке, что обеспечит НАМНОГО более быстрый поиск.

Я думаю, Джон упоминает несколько хороших моментов о том, как сделать все это в вашей БД.Если это не сработает, я бы использовал для списка библиотеку регулярных выражений на C++.Могу поспорить, что таким образом вы получите лучшую производительность и наиболее общий синтаксис регулярных выражений.