黑名单查询：前缀树

引入

我现在有一份黑名单数据，里面有10000条域名，现在需要编写一个算法，快速判断一个域名在不在这个黑名单里，怎么设计这个算法？

字典树 or 前缀树

前缀树是N叉树的一种
根节点表示空字符串
重要操作是insert和search

参考

https://blog.csdn.net/qq_41967784/article/details/127648494
这个文章里面只做了26个字母的前缀树，其实把数组长度设为128就可以覆盖所有ASCII字符

代码

import time
class trie():
    def __init__(self):
        self.next = [None]*128
        self.isend = False

    def insert(self, word: str) -> None:
        cur = self
        for c in word:
            od = ord(c)
            if(cur.next[od] is None):
                cur.next[od] = trie()
                cur = cur.next[od]
            else:
                cur = cur.next[od]
        cur.isend = True

    def search(self, word) -> bool:
        cur = self
        for c in word:
            od = ord(c)
            
            if(cur.next[od] is None):
                return False
            else:
                cur = cur.next[od]

        return cur.isend

def main():
    t1 = trie()
    f = open("blacklist.txt", "r")
    line = f.readline()
    while line:
        t1.insert(line)
        line = f.readline()
        # print(line,end="")
    f.close()
    start = time.time()
    for i in range(1000000):
        t1.search("warnerbros.com/web/steppenwolf\n")
    end = time.time()
    print("time usage: %d s"%(end-start))

if __name__ == "__main__":
    main()

前缀树的应用

可以用来做自动补全，即Tab补全
可以用来做敏感词过滤、黑名单过滤等