Как бы я разработал БД для набора регулярных выражений URL (Python), которые могут быть сопоставлены с входящим URL

Question

Скажем, у меня есть следующий набор URL в БД

url                     data
^(.*)google.com/search   foobar
^(.*)google.com/alerts   barfoo
^(.*)blah.com/foo/(.*)   foofoo
... 100's more

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

Мои вопросы:

1. Как мне создать БД, чтобы сделать это
2. django выполняет urlresolution, просматривая каждое регулярное выражение и проверяя совпадение учитывая, что может быть тысячи URL-адресов, это лучший способ приблизиться к этому?
3. Существуют ли какие-либо реализации, на которые я могу посмотреть?

Answer 1

"2. Django выполняет urlresolution, просматривая каждое регулярное выражение и проверяя совпадение, учитывая, что, возможно, тысячи URL-адресов - это лучший способ приблизиться к этому?"

"3. Могу ли я посмотреть какие-либо существующие реализации?"

Если выполнение большого количества регулярных выражений действительно является проблемой, вы должны проверить esmre , который является модулем расширения Python для ускорения больших коллекций регулярных выражений. Он работает, извлекая фиксированные строки каждого регулярного выражения и помещая их в Aho-Corasick -синхронизированное средство сопоставления с образцами, чтобы быстро устранить почти всю работу.

Answer 2

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

Я использую две таблицы для этого

class Urlregex(db.Model):
    """
    the data field is structured as a newline separated record list
    and each record is a space separated list of regex's and 
    dispatch key. Example of one such record

    domain_tld: google.com
    data:
        ^(.*)google.com/search(.*) google-search

    """
    domain_tld = db.StringProperty()
    data = db.TextProperty()

class Urldispatch(db.Model):
    urlkey = db.StringProperty()
    data = db.TextProperty()

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

Answer 3

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

Answer 4

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

Я в некотором роде согласен с комментарием TokenMacGuy о неразрешимости регулярных выражений, но ситуация может быть не совсем безнадежной в зависимости от истинного масштаба вашей проблемы. Например, чтобы URL соответствовал, его первый символ должен совпадать; так, например, вы можете предварительно отфильтровать свои URL, сказав, какой первый символ на входе будет соответствовать этому URL. Итак, у вас есть вторичная таблица MatchingFirstCharacters, которая представляет собой поиск между начальными символами и URL-адресами, которые соответствуют этому начальному символу. (Это будет работать, только если у вас нет много неоднозначных префиксов, как я упоминал в первом абзаце моего ответа.) Использование этого подхода будет означать, что вам не обязательно загружать все регулярные выражения для полного соответствия - только те, где хотя бы первый символ совпадает. Я полагаю, что эту идею можно обобщить и дальше, но это упражнение для читателя; -)

Answer 5

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

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

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