V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
CC11001100
V2EX  ›  Go 编程语言

域名后缀树(Golang)

  •  
  •   CC11001100 ·
    CC11001100 · 2023-03-03 01:31:48 +08:00 · 1498 次点击
    这是一个创建于 618 天前的主题,其中的信息可能已经有所发展或是发生改变。

    项目地址: https://github.com/golang-infrastructure/go-domain-suffix-trie

    域名后缀树( Golang )

    一、什么是域名后缀树

    类似于字典后缀树,不同的是域名后缀树是以.切分域名的各个部分, 对域名中的每个部分作为一个 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 中做后缀匹配,这个工具类就是用来解决这个问题的,尤其是在海量子域名关联到根域名上时效率极高。

    三、Example

    添加此项目作为依赖:

    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
    }
    
    9 条回复    2023-03-05 23:45:41 +08:00
    ruanimal
        1
    ruanimal  
       2023-03-03 09:45:11 +08:00
    这个函数名的长度和 java 有的一拼
    Nazz
        2
    Nazz  
       2023-03-03 13:06:47 +08:00 via Android
    和路由前缀树差不多,Reverse 一下就好了
    777777
        3
    777777  
       2023-03-03 16:15:24 +08:00
    你这个树性能比正则好吗?
    totoro52
        4
    totoro52  
       2023-03-03 17:43:21 +08:00
    好家伙 函数名和 java 一个味道了
    CC11001100
        5
    CC11001100  
    OP
       2023-03-04 01:04:51 +08:00
    @ruanimal @totoro52 哈哈哈,库名字就长点就长点,不过我也一直在头痛限于文化水平取不出言简意赅的方法名啥的...
    CC11001100
        6
    CC11001100  
    OP
       2023-03-04 01:05:17 +08:00
    @Nazz 是的,大佬牛皮
    CC11001100
        7
    CC11001100  
    OP
       2023-03-04 01:07:48 +08:00
    @777777 具体看场景,这个是我从老久之前做过的一个项目里抠出来的,那个场景是短时间内有大量的查询,引入这个后缀树优化之后速度比原来提升了八十多倍好像
    Me7426
        8
    Me7426  
       2023-03-04 01:56:06 +08:00
    跟这个 PAC 脚本异曲同工😁
    https://github.com/ifyour/ipac
    CC11001100
        9
    CC11001100  
    OP
       2023-03-05 23:45:41 +08:00
    @Me7426 哈哈哈看上去是有点像,不过那个库好像是用正则实现的,看场景吧,这个库的定位是底层支撑库,上层各种应用的功能可以基于多个这种库组合而来,想搞搞 infra...
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2636 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 10:45 · PVG 18:45 · LAX 02:45 · JFK 05:45
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.