江苏龙网

  1. 首页 > 人文 > >

树袋熊|前缀树算法实现路由匹配原理解析：Go 实现

路由功能是 web 框架中一个很重要的功能 ， 它将不同的请求转发给不同的函数(handler)处理 ， 很容易能想到 ， 我们可以用一个字典保存它们之间的对应关系 ， 字典的 key 存放 path ， value 存放 handler 。 当一个请求过来后 ， 使用routers.get(path, None) 就可以找到对应的 handler 。
利用字典实现路由可以参考我的这篇文章：动手实现 web 框架[1]。
使用字典有一个问题 ， 不支持动态路由 。 如果路由像这样呢？
/hello/:name/profilename 前面是通配符:， 表示这是个动态的值 。 一个解决办法是使用前缀树 trie 。
前缀树leetcode 中有这个算法 ， 点这里[2] 查看 。
前缀树前缀树 ， 首先是一棵树 。 不同的是树中一个节点的所有子孙都有相同的前缀 。 前缀树将单词中的每个字母依次插入树中 ， 插入前首先确认该单词是否存在 ， 不存在才创建新节点 ， 如果一个单词已经全部插入 ， 则将末尾单词设置为标志位 。
type Node struct {isWord bool // 是否是单词结尾nextmap[string]*Node // 子节点}type Trie struct {root *Node}以单词 leetcode ， leetd 和 code 为例 ， 首先一次插入 leetcode 中的每个单词 ， 然后插入 leetd 的时候 ， leet 在树中已经存在 ， 跳过往下 ， 现在要插入字母 d ， 不存在 ， 所以新建节点插入树中 ， 并将该节点的 isWord 置位 true ， 表明到了单词末尾 。
【树袋熊|前缀树算法实现路由匹配原理解析：Go 实现】最终插入结果为：
树袋熊|前缀树算法实现路由匹配原理解析：Go 实现前缀树
func (this *Trie) Insert(word string) {cur := this.rootfor _, w := range []rune(word) {c := string(w)if cur.next[c] == nil {cur.next[c] =!ok {r.root[method] =!ok {return nil, nil}// 在该方法的路由树上查找该路径for i, part := range searchParts {var temp string// 查找child是否等于partfor _, child := range node.children {if child.part == part || child.isWild {// 添加参数if child.part[0] == '*' {params[child.part[1:]] = strings.Join(searchParts[i:], "/")}if child.part[0] == ':' {params[child.part[1:]] = part}temp = child.part}}// 遇到通配符* ， 直接返回if temp[0] == '*' {return node.children[temp], params}node = node.children[temp]}return}上面的代码是我自己实现的一个 web 框架 **gaga**[3] 中路由前缀树相关的代码 ， 有需要的可以去看看源代码 。 另外 ， 欢迎star 呀 。
其中的 addRoute 用来将路由插入到对应 method 的路由树中 ， 如果节点是通配符 ， 将其设置为 isWild，同时绑定路由和 handler 方法 。
getRoute 方法首先查找路由方法对应的路由前缀树 ， 然后在树中查找是否存在该路径 。
总结前缀树 trie 算法不光可以用在路由的实现上 ， 搜索引擎中自动补全的实现 ， 拼写检查等等都是用 trie 实现的 。 trie 树查找的时间和空间复杂度都是线性的 ， 效率很高 ， 很适合路由这种场景使用 。
路由的实现上 ， go 语言中 httpRouter 这个库除了使用前缀树之外 ， 还加入了优先级 ， 有兴趣的可以看看它的源码了解下 。
作者：鸟石
原文链接：
参考资料[1]
动手实现 web 框架: 动手实现web框架/
[2]
点这里:
[3]
gaga:


    推荐阅读


    上一篇：安理会|仅获2票支持！美延长对伊武器禁运草案还遭遇了哪些尴尬

    下一篇：乌鲁木齐|浙江新增3例无症状感染者，均为新加坡输入