前綴樹(shù)算法實(shí)現(xiàn)路由匹配原理解析：Go 實(shí)現(xiàn)

路由功能是 web 框架中一個(gè)很重要的功能，它將不同的請(qǐng)求轉(zhuǎn)發(fā)給不同的函數(shù)(handler)處理，很容易能想到，我們可以用一個(gè)字典保存它們之間的對(duì)應(yīng)關(guān)系，字典的 key 存放 path，value 存放 handler。當(dāng)一個(gè)請(qǐng)求過(guò)來(lái)后，使用 routers.get(path, None) 就可以找到對(duì)應(yīng)的 handler。

利用字典實(shí)現(xiàn)路由可以參考我的這篇文章：動(dòng)手實(shí)現(xiàn) web 框架^[1] 。

使用字典有一個(gè)問(wèn)題，不支持動(dòng)態(tài)路由。如果路由像這樣呢？

/hello/:name/profile

name 前面是通配符:?，表示這是個(gè)動(dòng)態(tài)的值。一個(gè)解決辦法是使用前綴樹(shù) trie。

前綴樹(shù)

leetcode 中有這個(gè)算法，點(diǎn)這里^[2] 查看。

前綴樹(shù)前綴樹(shù)，首先是一棵樹(shù)。不同的是樹(shù)中一個(gè)節(jié)點(diǎn)的所有子孫都有相同的前綴。前綴樹(shù)將單詞中的每個(gè)字母依次插入樹(shù)中，插入前首先確認(rèn)該單詞是否存在，不存在才創(chuàng)建新節(jié)點(diǎn)，如果一個(gè)單詞已經(jīng)全部插入，則將末尾單詞設(shè)置為標(biāo)志位。

type?Node?struct?{
????isWord?bool?//?是否是單詞結(jié)尾
????next???map[string]*Node?//?子節(jié)點(diǎn)
}

type?Trie?struct?{
????root?*Node
}

以單詞 leetcode，leetd 和 code 為例，首先一次插入 leetcode 中的每個(gè)單詞，然后插入 leetd 的時(shí)候，leet 在樹(shù)中已經(jīng)存在，跳過(guò)往下，現(xiàn)在要插入字母 d，不存在，所以新建節(jié)點(diǎn)插入樹(shù)中，并將該節(jié)點(diǎn)的 isWord 置位 true，表明到了單詞末尾。

最終插入結(jié)果為：

func?(this?*Trie)?Insert(word?string)?{
????cur?:=?this.root
????for?_,?w?:=?range?[]rune(word)?{
????????c?:=?string(w)
????????if?cur.next[c]?==?nil?{
????????????cur.next[c]?=?&Node{next:?make(map[string]*Node)}
????????}
????????cur?=?cur.next[c]
????}
????cur.isWord?=?true
}

那么，當(dāng)我們要搜索單詞 leetd 的時(shí)候，從根節(jié)點(diǎn)開(kāi)始查找，如果找到某條路徑是 leetd，并且末尾的 d 是單詞標(biāo)志位，則表示搜索成功。

func?(this?*Trie)?Search(word?string)?bool?{
????cur?:=?this.root
????for?_,?w?:=?range?[]rune(word)?{
????????c?:=?string(w)
????????if?cur.next[c]?==?nil?{
????????????return?false
????????}
????????cur?=?cur.next[c]
????}
????return?cur.isWord
}

明白了前綴樹(shù)的原理，我們來(lái)看看路由匹配是如何利用前綴樹(shù)來(lái)實(shí)現(xiàn)的。

路由前綴樹(shù)

go 語(yǔ)言中 gin 框架的路由實(shí)現(xiàn)就是利用前綴樹(shù)，可以看看它的源代碼是如何實(shí)現(xiàn)的。

考慮一下，路由或者說(shuō)路徑的特點(diǎn)，是以 / 分隔的單詞組成的，那我們將 / 的每一部分掛靠在前綴樹(shù)上就可以了。如下圖所示：

還有一點(diǎn)需要考慮，我們?cè)谟?web 框架定義路由的時(shí)候，常見(jiàn)的做法是根據(jù)不同的 HTTP 方法來(lái)定義。比如：

//?以go語(yǔ)言gin框架為例
g?:=?gin.New()
g.GET("/hello",?Hello)
g.POST("/form",?Form)

對(duì)于同一個(gè)路徑，可能有多個(gè)方法支持。所以我們要以不同 HTTP 方法為樹(shù)根創(chuàng)建前綴樹(shù)。當(dāng)一個(gè) GET 請(qǐng)求過(guò)來(lái)的時(shí)候，就從 GET 樹(shù)上搜索，POST 請(qǐng)求就從 POST 樹(shù)上搜索。

除了為不同的 HTTP 方法定義樹(shù)之外，還要給那些是通配符的節(jié)點(diǎn)增加一個(gè)標(biāo)志位。所以，我們的路由前綴樹(shù)結(jié)構(gòu)看起來(lái)像這樣：

type?node?struct?{
????path?????string???????????//?路由路徑
????part?????string???????????//?路由中由'/'分隔的部分
????children?map[string]*node?//?子節(jié)點(diǎn)
????isWild???bool?????????????//?是否是通配符節(jié)點(diǎn)
}

type?router?struct?{
????root??map[string]*node???????//?路由樹(shù)根節(jié)點(diǎn)
????route?map[string]HandlerFunc?//?路由處理handler
}

依照上面的前綴樹(shù)算法的實(shí)現(xiàn)，照葫蘆畫(huà)瓢，我們可以寫(xiě)出插入路由和搜索路由的方法：

//?addRoute?綁定路由到handler
func?(r?*router)?addRoute(method,?path?string,?handler?HandlerFunc)?{
????parts?:=?parsePath(path)
????if?_,?ok?:=?r.root[method];?!ok?{
????????r.root[method]?=?&node{children:?make(map[string]*node)}
????}
????root?:=?r.root[method]
????key?:=?method?+?"-"?+?path
????//?將parts插入到路由樹(shù)
????for?_,?part?:=?range?parts?{
????????if?root.children[part]?==?nil?{
????????????root.children[part]?=?&node{
????????????????part:?????part,
????????????????children:?make(map[string]*node),
????????????????isWild:???part[0]?==?':'?||?part[0]?==?'*'}
????????}
????????root?=?root.children[part]
????}
????root.path?=?path
????//?綁定路由和handler
????r.route[key]?=?handler
}

//?getRoute?獲取路由樹(shù)節(jié)點(diǎn)以及路由變量
func?(r?*router)?getRoute(method,?path?string)?(node?*node,?params?map[string]string)?{
????params?=?map[string]string{}
????searchParts?:=?parsePath(path)

????//?get?method?trie
????var?ok?bool
????if?node,?ok?=?r.root[method];?!ok?{
????????return?nil,?nil
????}

????//?在該方法的路由樹(shù)上查找該路徑
????for?i,?part?:=?range?searchParts?{
????????var?temp?string
????????//?查找child是否等于part
????????for?_,?child?:=?range?node.children?{
????????????if?child.part?==?part?||?child.isWild?{
????????????????//?添加參數(shù)
????????????????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

}

上面的代碼是我自己實(shí)現(xiàn)的一個(gè) web 框架 **gaga**^[3] 中路由前綴樹(shù)相關(guān)的代碼，有需要的可以去看看源代碼。另外，歡迎star 呀。

其中的 addRoute 用來(lái)將路由插入到對(duì)應(yīng) method 的路由樹(shù)中，如果節(jié)點(diǎn)是通配符，將其設(shè)置為 isWild ， 同時(shí)綁定路由和 handler 方法。

getRoute 方法首先查找路由方法對(duì)應(yīng)的路由前綴樹(shù)，然后在樹(shù)中查找是否存在該路徑。

總結(jié)

前綴樹(shù) trie 算法不光可以用在路由的實(shí)現(xiàn)上，搜索引擎中自動(dòng)補(bǔ)全的實(shí)現(xiàn)，拼寫(xiě)檢查等等都是用 trie 實(shí)現(xiàn)的。trie 樹(shù)查找的時(shí)間和空間復(fù)雜度都是線(xiàn)性的，效率很高，很適合路由這種場(chǎng)景使用。

路由的實(shí)現(xiàn)上，go 語(yǔ)言中 httpRouter 這個(gè)庫(kù)除了使用前綴樹(shù)之外，還加入了優(yōu)先級(jí)，有興趣的可以看看它的源碼了解下。

作者：鳥(niǎo)石

原文鏈接：https://segmentfault.com/a/1190000021657573

參考資料