Trie 树

有一个记录了数个网站 Web 请求的日志文件,它可能如下:

192.168.56.1 GET www.a.com /index.jsp
192.168.56.2 GET www.b.com /index.asp
...

然后有一个网站列表,列表中只记录了域名的一级域,大概如下:

a.com
b.com
c.com
...

现在需要将这些域名的所有日志提取出来。

最暴力的方法就是将域名列表载入内存,每遍历一行日志,就将这行日志的域名提取出来,然后按域名列表逐个遍历,算法实现如下:

def find(host):
    """
    @Args
    host: 日志行中的主机地址

    @Return:如果域名在列表中,返回 True
    """
    for domain in domain_list:
        if host.endswith(domain):
            return True

    return False

但每一行日志都需要遍历一次列表,效率非常低,尤其是列表非常大的时候。

这个场景可以用 Trie 树来优化:先将要过滤的域名按”.“分割出来,并倒序在内存中建立一棵树。比如 a.com、b.com 和 c.org 的树结构如下:

1.png

最后,对每行日志的域名,只用同样的分割方式,再搜索树即可。

完成实现如下:

tree = dict()


def insert_tree(item_list):
    root = tree

    for i in item_list:
        if not root.get(i):
            root[i] = {}

        root = root[i]


def search_tree(item_list):
    root = tree
    for i in item_list:
        # 这里不能直接写成 if root.get(i)
        # 因为if判断空字典为 False
        if root.get(i) is None:
            return False

        # 到叶节点了,说明找到记录
        if root[i] == {}:
            return True

        root = root[i]

    return False


def insert_domain_to_tree(domain):
    domain_items = domain.split(".")
    domain_items.reverse()
    insert_tree(domain_items)
    return


def search_domain(domain):
    domain_items = domain.split(".")
    domain_items.reverse()
    return search_tree(domain_items)


def init_tree():
    with open("domain_list.txt") as f:
        for line in f:
            domain = line.strip()
            insert_domain_to_tree(domain)


if __name__ == '__main__':
    # self test
    init_tree()
    assert(search_domain("www.a.com") is True)
    assert(search_domain("test.b.com") is True)
    assert(search_domain("test.xx.com") is False)