URL的最长前缀匹配

Question

我需要有关任何标准python包的信息,这些包可用于URL上的"最长前缀匹配".我已经通过两个标准包不见了http://packages.python.org/PyTrie/#pytrie.StringTrie&"http://pypi.python.org/pypi/trie/0.1.1",但他们似乎并没有对URL的最长前缀匹配任务有用.

例如,如果我的设置包含以下网址1-> http://www.google.com/mail,2-> http://www.google.com/document,3-> http://www.facebook.com等等..

现在,如果我搜索"http://www.google.com/doc",则应返回2并搜索"http://www.face"应返回3.

我想确认是否有任何标准的python包可以帮助我这样做,或者我应该实现Trie的前缀匹配.

我不是在寻找一种正则表达式的解决方案,因为随着URL数量的增加它不可扩展.

非常感谢.

Answer 1

性能比较

suffixtreevs. pytrievs. trievs. datrievs.- startswithfunctions

建立

记录的时间是3次重复1000次搜索中的最小时间.包括建筑时间并在所有搜索中传播.搜索是在1到1000000个项目的主机名集合上执行的.

三种类型的搜索字符串:

• non_existent_key - 字符串没有匹配项
• rare_key - 大约20万分之一
• frequent_key - 出现次数与集合大小相当

结果

百万网址的最大内存消耗:

| function    | memory, | ratio |
|             |     GiB |       |
|-------------+---------+-------|
| suffix_tree |   0.853 |   1.0 |
| pytrie      |   3.383 |   4.0 |
| trie        |   3.803 |   4.5 |
| datrie      |   0.194 |   0.2 |
| startswith  |   0.069 |   0.1 |
#+TBLFM: $3=$2/@3$2;%.1f

要重现结果,请运行trie基准代码.

• rare_key/nonexistent_key案例

  如果网址数小于10000,那么datrie是最快的,因为N> 10000 - suffixtree更快,startwith平均来说显着更慢.

• 轴:

  • 垂直(时间)刻度约为1秒(2**20微秒)
  • 横轴表示每种情况下的网址总数:N = 1,10,100,1000,10000,100000和1000000(百万).

• frequent_key

  高达N = 100000 datrie是最快的(对于一百万个网址,时间由特里施工时间决定).

  通过找到找到的匹配项中最长的匹配来获取最多时间.所以所有函数的行为都与预期的相似.

startswith - 时间表现与密钥类型无关.

trie并且pytrie表现得彼此相似.

没有施工时间的性能

• datrie - 最快,最体面的内存消耗

• startswith 在这里处于劣势甚至更加不利,因为其他方法不会因建立一个trie而受到惩罚.

• datrie,pytrie,trie-几乎O(1)(时间常数)为稀有/ non_existent键

拟合(近似)已知函数的多项用于比较(与图中相同的对数/对数刻度):

| Fitting polynom              | Function          |
|------------------------------+-------------------|
| 0.15  log2(N)   +      1.583 | log2(N)           |
| 0.30  log2(N)   +      3.167 | log2(N)*log2(N)   |
| 0.50  log2(N)   +  1.111e-15 | sqrt(N)           |
| 0.80  log2(N)   +  7.943e-16 | N**0.8            |
| 1.00  log2(N)   +  2.223e-15 | N                 |
| 2.00  log2(N)   +  4.446e-15 | N*N               |

Answer 2

此示例适用于小网址列表但不能很好地扩展.

def longest_prefix_match(search, urllist):
    matches = [url for url in urllist if url.startswith(search)]
    if matches:
        return max(matches, key=len)
    else:
        raise Exception("Not found")

使用trie模块的实现.

import trie


def longest_prefix_match(prefix_trie, search):
    # There may well be a more elegant way to do this without using
    # "hidden" method _getnode.
    try:
        return list(node.value for node in prefix_trie._getnode(search).walk())
    except KeyError:
        return list()

url_list = [ 
    'http://www.google.com/mail',
    'http://www.google.com/document',
    'http://www.facebook.com',
]

url_trie = trie.Trie()

for url in url_list:
    url_trie[url] = url 

searches = ("http", "http://www.go", "http://www.fa", "http://fail")

for search in searches:
    print "'%s' ->" % search, longest_prefix_match(url_trie, search)

结果:

'http' -> ['http://www.facebook.com', 'http://www.google.com/document', 'http://www.google.com/mail']
'http://www.go' -> ['http://www.google.com/document', 'http://www.google.com/mail']
'http://www.fa' -> ['http://www.facebook.com']
'http://fail' -> []

或使用PyTrie,它给出了相同的结果,但列表的排序方式不同.

from pytrie import StringTrie


url_list = [ 
    'http://www.google.com/mail',
    'http://www.google.com/document',
    'http://www.facebook.com',
]

url_trie = StringTrie()

for url in url_list:
    url_trie[url] = url 

searches = ("http", "http://www.go", "http://www.fa", "http://fail")

for search in searches:
    print "'%s' ->" % search, url_trie.values(prefix=search)

从内存使用的角度来看,我开始认为基数树/帕特里夏树会更好.这就是基数树的样子:

而trie看起来更像: