匹配（搜索）C列表中的URL（实施白名单或黑名单）的最佳方法？

问题描述：

我在写代理服务器。它将不同的规则应用于列表中匹配的网站。例如，我们可以阻止列表A和使用其他代理获取的名单B.匹配（搜索）C列表中的URL（实施白名单或黑名单）的最佳方法？

例如内容，列表A：

.google.com 
blogger.com 
sourceforge.net 
ytimg.com 
http://media-cache-*.pinterest.com/* 
images-amazon.com 
*.amazonaws.com 
twitter.com 
fbcdn.net 
google-analytics.com 
staticflickr.com

B组：

ytimg.com 
youtube.com

目前，比赛功能是：

struct proxy_t * 
match_list(char *url) { 
    // 2KB line should be enough 
    char buf[2048]; 
    int pos = 0, size; 

    struct acllist *al = config->acl_h; 
    struct acl *node = al->data; 

    while (node != NULL) { // iterate list 
    pos = 0; // position in list file 

    size = strlen(node->data); // node->data holds a URL list 

    while (1) { // iterate each line in list 

     readline(buf, node->data, &pos, size); 

     if (buf[0] == 0) break; 

     if (strcasestr(url, buf) != NULL 
     || !fnmatch(buf, url, FNM_CASEFOLD)) { 

      return node->proxy; 
     } 
    } 
    node = node->next; 
    } 


    printf("Not Matched\n"); 

    return config->default_proxy; 
}

也就是说，迭代两个列表文件，逐行读取，使用strcasestr和fnmatch匹配一个URL。

它工作正常。但是，如果列表变得越来越大，比如说每个列表和5个列表有10000行，那么我认为它不是一个有效的解决方案，因为它是一个O（N）算法。

我正在考虑为每条比赛线添加一个计数器。通过排序匹配线可以减少平均搜索长度。像这样：

.google.com|150 
blogger.com|76 
sourceforge.net|43 
ytimg.com|22

有没有其他的想法呢？

这不是关于解析URL。这是关于如何有效地匹配URL列表。 – strongwillow 2013-02-12 09:08:46

您可能想要查看哈希表来存储URL或某种搜索树。 – 2013-02-12 09:16:39

谢谢大家。我终于整理出来了。无论使用散列表还是搜索树，都可以使用它的域（xxx.xx）。一旦我们找到节点（也是链表的头部），迭代列表并将其与** fnmatch **和** strstr **进行匹配。 – strongwillow 2013-02-13 06:58:34

答

有两种方法可以提高性能。

第一种方式是为了以某种方式URL列表，因此，你可以优化它搜索。 Quicksort是那里最快的算法。

Bubble sort更容易实现。

然后，您可以使用binary search在列表中进行搜索。二进制搜索具有对数性能，而您的循环具有线性，因此在大型列表中它将显着更快。

如果你的URL列表是静态的，你可以使用一个叫做flex专用工具，它使您通过阅读它来解析字符串。

这也意味着，当你的一些URL列表被更新时，你必须编写新的代码来解析或创建代码生成器。

这是更有效的解析方式，然后是任何类型的排序，因为它只需要N个步骤，当N是您要解析的URL的长度时，因此无论您的列表多长时间，只要你可以写入正确的扫描仪输入。

匹配（搜索）C列表中的URL（实施白名单或黑名单）的最佳方法？

相关推荐