1

假设我在数据库中有以下一组 url

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

给定任意 url，我想检查该 url 是否属于现有的一组 url 并获取相应的数据字段。

我的问题是：

  1. 我将如何设计数据库来做到这一点
  2. 鉴于可能有 1000 个 url，django 通过循环遍历每个正则表达式并检查匹配项来执行 urlresolution，这是解决此问题的最佳方法吗？
  3. 我可以查看任何现有的实现吗？
4

5 回答 5

1

“2. django 通过循环遍历每个正则表达式并检查匹配项来进行 urlresolution，因为可能有 1000 个 url，这是解决这个问题的最佳方法吗？”

“3. 有没有我可以查看的现有实现？”

如果运行大量正则表达式确实是个问题，您应该查看esmre，这是一个 Python 扩展模块，用于加速大量正则表达式集合。它的工作原理是提取每个正则表达式的固定字符串并将它们放入受Aho-Corasick启发的模式匹配器中，以快速消除几乎所有的工作。

于 2009-07-19T04:01:23.207 回答
0

Django 的优势在于它的 URL 通常是分层的。虽然整个 Django 项目可能有 100 个或更多 URL，但它一次可能只处理十几个或更少的模式。您的 URL 中是否有任何可以通过这种方式利用的结构？

除此之外，您可以尝试创建某种启发式方法。例如，找到模式的“固定”部分，然后消除其中的一些，然后（通过简单的子字符串搜索），然后才切换到正则表达式匹配。

在极端情况下，您可以创建产品自动机。那将是超快的，但内存要求可能是不切实际的（并且可能在接下来的几个世纪里仍然如此）。

于 2009-07-17T22:40:58.340 回答
0

在确定 django 方法不可能工作之前，请尝试实施它并应用典型的工作负载。对于一个真正彻底的方法，您实际上可以计算每个正则表达式的成本，这可以指导您改进最昂贵和最常用的正则表达式。特别是，您可以将最常用、最便宜的正则表达式安排在列表的前面。这可能是比发明一种新技术来解决您甚至不知道的问题更好的选择。

于 2009-07-17T22:59:39.550 回答
0

您在设计正则表达式时肯定需要更加小心。例如，前缀^(.*)将匹配任何输入 - 虽然您可能出于各种原因需要前缀来捕获组，但拥有它意味着您无法真正轻松地消除数据库中的任何 URL。

我有点同意 TokenMacGuy 关于正则表达式难以处理的评论，但根据您问题的真实规模，情况可能并非完全没有希望。例如，要匹配一个 URL，那么它的第一个字符应该匹配；因此，例如，您可以通过说明输入中的哪个第一个字符将匹配该 URL 来预先过滤您的 URL。所以，你有一个辅助表MatchingFirstCharacters这是初始字符和与该初始字符匹配的 URL 之间的查找。（这仅在您没有很多不明确的前缀时才有效，正如我在答案的第一段中提到的那样。）使用这种方法意味着您不必加载所有正则表达式以进行完全匹配 - 只需至少第一个字符匹配的那些。我想这个想法可以进一步推广，但这是读者的练习;-)

于 2009-07-18T12:04:34.267 回答
0

我倾向于的计划是从 url 中选择域名 + tld，将其用作查找所有正则表达式的键，然后遍历每个正则表达式子集以查找匹配项。

我为此使用了两个表

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 db 读取和循环通过特定于域的 url 子集的成本，任何传入的 url 都应该能够与大型 db 的 url 匹配。

于 2009-07-18T15:02:42.473 回答