Совпадение строки из тонны моделей

Question

Я хочу создать систему для сопоставления URL.Это будет работать следующим образом:

База данных будет содержать много шаблонов.и некоторые метаданные шаблона, например:

pattern1, keyword 
pattern2, keyword
...
...

У меня есть входной URL.например htttp: //example.com/blabla/111/2222/detail.htm

Система получит входные данные и выведет ключевое слово наиболее подходящего шаблона для входного URL.В секунду будет выполняться более 20 000 запросов.

Нам необходимо разработать шаблон и модель базы данных.Я провел более 2 недель в этой системе.

Я думаю о сопоставлении URL-адреса в дереве.

Все узлы в дереве могут выводить 2 вида:Какой узел должен продолжать соответствовать URL-адресу, или же узел знает, какое ключевое слово должно быть применено к URL-адресу.

Каждый узел будет связан с обратным вызовом (скрипт хранится в БД).Таким образом, разные узлы будут вести себя по-разному.

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

Я все еще думаю о генерации дерева.Но должен быть какой-то лучший способ.

Любые идеи будут очень полезны.Спасибо !!!

Answer 1

Вам нужен один из промышленных алгоритмов сопоставления строк: http://en.wikipedia.org/wiki/String_searching_algorithm. Я не думаю, что подход на основе базы данных будет работать так хорошо, потому что, похоже, вам нужно шаблон соответствие,не точное сопоставление префиксов.

Но если вы используете сопоставление префиксов (самое длинное совпадение с самого начала), то вы можете использовать префиксный три, три .На вашем месте я бы использовал базу данных в качестве постоянного хранилища, но сохранял бы свой соответствующий trie в памяти.

Answer 2

Сначала прочитайте эту статью:

Сопоставление регулярных выражений может быть простым и быстрым

В регулярных выражениях у вас есть простое "чередование":

pattern1|pattern2|pattern3|...

... с дополнительным ограничением, которое вы хотите знать , которому соответствует шаблон. Я полагаю, что расширение "NFA Томпсона", чтобы обеспечить эту деталь было бы просто. (Идея: Внутренне, поместите уникальный магический токен в конце каждого шаблона, чтобы однозначно идентифицировать шаблон. Магический токен будет соответствовать пустой строке ... Так что, когда ваш соответствующий механизм встречает один, он сразу же знает, какой шаблон соответствует.)

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

Чтобы повысить скорость, вы можете попробовать использовать оптимизатор регулярных выражений (что-то вроде Regexp :: Optimizer в Perl) перед преобразованием большого регулярного выражения чередования в NFA.

Или, возможно, вы захотите начать с обычного механизма регулярных выражений (например, PCRE) и посмотреть, достаточно ли он быстр.