项目地址: https://github.com/golang-infrastructure/go-domain-suffix-trie
类似于字典后缀树,不同的是域名后缀树是以.切分域名的各个部分, 对域名中的每个部分作为一个 Node 建立后缀树以便高效进行后缀匹配查询。
比如:
www.google.com
会以.分割域名为三个部分,每个部分建立一个节点:
再增加一个:
baidu.com
此时后缀树是这样子的:
比如现在有 n 个域名后缀,称之为集合 A:
google.com
api.baidu.com
007.qq.com
然后有 m 个域名,称之为集合 B:
a.google.com
b.google.com
c.google.com
google.com
google3.com
a.api.baidu.com
b.api.baidu.com
003.qq.com
a.007.qq.com
现在要为这集合 B 中的每个域名从集合 A 中做后缀匹配,这个工具类就是用来解决这个问题的,尤其是在海量子域名关联到根域名上时效率极高。
添加此项目作为依赖:
go get -u github.com/golang-infrastructure/go-domain-suffix-trie
代码示例( DomainSuffixTree 是线程安全的):
package main
import (
"fmt"
domain_suffix_trie "github.com/golang-infrastructure/go-domain-suffix-trie"
)
func main() {
// 调用 #NewDomainSuffixTrie 创建一颗后缀树
tree := domain_suffix_trie.NewDomainSuffixTrie[string]()
// 将需要匹配的域名后缀依次调用 #AddDomainSuffix 添加到树上,添加的时候可以为后缀指定一个 payload (使用集合 A 构建树)
_ = tree.AddDomainSuffix("google.com", "谷歌主站子域名")
_ = tree.AddDomainSuffix("map.google.com", "谷歌地图子域名")
_ = tree.AddDomainSuffix("baidu.com", "百度主站子域名")
_ = tree.AddDomainSuffix("jd.com", "京东子域名")
// 需要查询的时候调用 #FindMatchDomainSuffixPayload 或者 #FindMatchDomainSuffixNode 查询,
// 参数是一个完整的域名,会返回此域名匹配到的后缀在之前指定的 payload (将集合 B 的每个元素依次在树上查询)
fmt.Println(tree.FindMatchDomainSuffixPayload("test.google.com")) // output: 谷歌主站子域名
fmt.Println(tree.FindMatchDomainSuffixPayload("test.map.google.com")) // output: 谷歌地图子域名
fmt.Println(tree.FindMatchDomainSuffixNode("test.baidu.com").GetNodeTriePath()) // output: baidu.com
fmt.Println(tree.FindMatchDomainSuffixNode("test.jd.com").GetNodeTrieValue()) // output: jd
}
1
ruanimal 2023-03-03 09:45:11 +08:00
这个函数名的长度和 java 有的一拼
|
2
Nazz 2023-03-03 13:06:47 +08:00 via Android
和路由前缀树差不多,Reverse 一下就好了
|
3
777777 2023-03-03 16:15:24 +08:00
你这个树性能比正则好吗?
|
4
totoro52 2023-03-03 17:43:21 +08:00
好家伙 函数名和 java 一个味道了
|
5
CC11001100 OP |
6
CC11001100 OP @Nazz 是的,大佬牛皮
|
7
CC11001100 OP @777777 具体看场景,这个是我从老久之前做过的一个项目里抠出来的,那个场景是短时间内有大量的查询,引入这个后缀树优化之后速度比原来提升了八十多倍好像
|
8
Me7426 2023-03-04 01:56:06 +08:00
跟这个 PAC 脚本异曲同工😁
https://github.com/ifyour/ipac |
9
CC11001100 OP @Me7426 哈哈哈看上去是有点像,不过那个库好像是用正则实现的,看场景吧,这个库的定位是底层支撑库,上层各种应用的功能可以基于多个这种库组合而来,想搞搞 infra...
|