一、先搞懂问题：为啥URL去重这么费资源？
做过爬虫的人都知道，最头疼的问题之一就是“重复爬”——爬了半天，发现某个页面已经爬过N次了，浪费时间不说，还可能触发目标站的反爬规则。所以“URL去重”是每个爬虫系统的基础功能，但做起来没那么简单。
目前大家常用的两种去重方法，各有各的麻烦：第一种是直接存URL字符串，每次来新URL就挨个比字符串，优点是简单，但缺点也很明显——URL越长、数量越多，比字符串的速度就越慢，比如存100万个URL，新URL要和前100万个挨个比，那速度慢得没法用。第二种是用哈希表，比如把URL转成MD5、SHA256这类短指纹，再把指纹存到哈希表里，新URL转成指纹后查哈希表有没有，速度快很多，但问题是：哪怕两个URL只有一个字符不一样，转出来的指纹也完全不同，比如/article/123和/article/124，两个URL差1个字符，转出来的指纹长度都是32位（MD5），相当于每个URL都要占32字节的内存，要是存1亿个URL，光指纹就要占3.2GB内存，成本太高。
有没有办法既像哈希表那样快，又能省内存？答案就是用前缀树做“渐进式指纹”。
二、核心原理：前缀树是什么？渐进式指纹又是什么？
2.1 先搞懂前缀树（Trie）
前缀树是一种专门存字符串的树结构，核心逻辑是“共享前缀”——比如存/article/123和/article/124这两个URL，它们的公共前缀是/article/1，前缀树会把这个公共部分只存一次，不会重复存。
举个简单的例子，我们存三个URL：/a/b、/a/c、/a/b/d，前缀树的结构是这样的：
根节点下面有一个子节点/，/下面有子节点a，a下面有子节点/，/下面有两个子节点b和c，b下面有子节点/，/下面有子节点d。每个URL的终点会打个标记（比如is_end为true），表示这个URL存在。
2.2 渐进式指纹：不是一次性算全指纹，是边走边比
普通的哈希指纹是“一次算完整个URL的指纹”，而渐进式指纹是“沿着前缀树的路径，一步步匹配URL的每个字符，走到终点就算匹配成功”。
比如要判断/article/123有没有存过，我们从根节点开始：
- 第一个字符是
/，找根节点的子节点有没有/——有，就走到这个节点； - 第二个字符是
a，找当前节点的子节点有没有a——有，走到a节点； - 第三个字符是
r，找当前节点的子节点有没有r——有，走到r节点； ... 一直走到最后一个字符3，再看这个节点有没有is_end标记——有，就说明这个URL已经存过；没有的话，就把剩下的路径加进去，再打个is_end标记。
这样做的好处是：两个URL的公共前缀部分，只匹配一次，不用重复计算，而且公共部分只存一次，内存占用比哈希表小很多。
三、具体实现：用Python写一个前缀树去重的例子
我们用Python来写一个简单的前缀树去重系统，为了让大家看懂，代码会加详细注释。
3.1 定义前缀树节点
首先，每个节点需要存两个东西：一个是子节点的集合（用来存下一个字符），一个是是否为URL终点的标记。
# 定义前缀树的节点类
class TrieNode:
def __init__(self):
# 子节点：key是字符，value是对应的TrieNode
self.children = {}
# 是否是URL的终点标记，True表示这个节点是某个URL的最后一个字符
self.is_end = False
3.2 实现前缀树的核心功能：插入URL、判断URL是否存在
接下来，我们实现前缀树的两个核心功能：插入一个URL（把新URL存进去）、判断一个URL是否已经存在（去重判断）。
# 定义前缀树类，用来管理所有URL的存储和判断
class TrieURLDedupe:
def __init__(self):
# 前缀树的根节点，没有任何字符
self.root = TrieNode()
def insert(self, url):
"""插入一个新的URL到前缀树中"""
# 从根节点开始匹配
current_node = self.root
# 遍历URL的每个字符
for char in url:
# 如果当前节点的子节点里没有这个字符，就新建一个节点
if char not in current_node.children:
current_node.children[char] = TrieNode()
# 走到下一个节点
current_node = current_node.children[char]
# 遍历完所有字符后，把当前节点的is_end设为True，表示这是一个完整的URL
current_node.is_end = True
def exists(self, url):
"""判断一个URL是否已经存在于前缀树中"""
# 从根节点开始匹配
current_node = self.root
# 遍历URL的每个字符
for char in url:
# 如果当前节点的子节点里没有这个字符，说明URL不存在
if char not in current_node.children:
return False
# 走到下一个节点
current_node = current_node.children[char]
# 遍历完所有字符后，还要看当前节点是不是URL的终点，避免部分匹配
# 比如前缀树里存了'/article/1234'，要判断'/article/123'，遍历完123后，节点的is_end是False，所以返回False
return current_node.is_end
3.3 测试去重功能
我们来测试一下这个前缀树能不能正确去重，比如存几个URL，然后判断有没有重复。
# 测试代码
if __name__ == "__main__":
# 初始化前缀树去重对象
dedupe = TrieURLDedupe()
# 插入几个测试URL
test_urls = [
"/article/123",
"/article/124",
"/article/1234",
"/blog/2024/05/01",
"/blog/2024/05/02"
]
# 插入URL
for url in test_urls:
dedupe.insert(url)
# 测试判断URL是否存在
print(dedupe.exists("/article/123")) # 输出True，说明这个URL已经存过
print(dedupe.exists("/article/1234")) # 输出True
print(dedupe.exists("/article/125")) # 输出False，说明这个URL没存过
print(dedupe.exists("/blog/2024/05/01")) # 输出True
print(dedupe.exists("/blog/2024/05/03")) # 输出False
print(dedupe.exists("/article/12")) # 输出False，避免部分匹配的问题
四、深入分析：这种方法的优势、问题和适用场景
4.1 优势：省内存、速度快
最核心的优势是省内存，尤其是URL前缀重复率高的场景。比如一个新闻站的URL都是/news/2024/05/01/xxx，所有URL的前缀/news/2024/05/01/都是一样的，前缀树只会存一次这个前缀，而哈希表要给每个URL都存一个32字节的指纹，内存占用差很多。
速度也很快，匹配的时候是按字符一步步走，没有复杂的计算，时间复杂度是O(n)，n是URL的长度，和哈希表的速度差不多，但内存占用低很多。
4.2 问题：有适用限制
前缀树也不是万能的，有两个主要问题：
第一，URL不能太长。如果URL是那种随机的、很长的字符串，比如/api/data?token=abcdefghijklmnopqrstuvwxyz123456，每个URL的前缀都不一样，前缀树的优势就体现不出来了，甚至内存占用比哈希表还高。
第二，不能处理复杂的URL去重逻辑。比如有些URL的参数顺序不同但内容一样，比如/article?id=123&page=1和/article?page=1&id=123，前缀树会把它们当成两个不同的URL，这时候需要先把URL的参数排序、归一化，再用前缀树去重。
4.3 适用场景
前缀树去重最适合的场景是：URL结构固定、前缀重复率高的爬虫系统，比如爬新闻站、博客站、电商站的商品列表，这些网站的URL结构都很规整，前缀重复率很高。
五、优化：让前缀树更省内存
上面的基础实现还有优化空间，比如我们可以把前缀树的节点压缩，比如把连续的相同字符的路径合并，变成“压缩前缀树”（Radix Tree），这样内存占用会更低。
比如存/a/b/c和/a/b/d，基础前缀树的路径是/→a→/→b→/→c，压缩前缀树会把/a/b/合并成一个节点，路径变成/a/b/→c，这样节点数量会少很多，内存占用更低。
不过压缩前缀树的实现会复杂一点，适合对内存要求极高的场景，比如爬取亿级URL的分布式爬虫系统。
六、总结
URL去重是爬虫系统的基础功能，传统的字符串匹配和哈希表各有缺点，而用前缀树做渐进式指纹匹配，能很好地平衡速度和内存占用，尤其是在URL前缀重复率高的场景下，优势非常明显。
当然，前缀树也不是万能的，需要根据自己的爬虫场景选择合适的去重方法：如果URL前缀重复率高，就用前缀树；如果URL是随机的、很长的，还是用哈希表更合适。
评论
围绕“反爬虫系统处理URL去重时字符串匹配与哈希表各有代价，如何利用前缀树做渐进式指纹比较来降低整体内存占用？”参与讨论