golang实现前缀数实现匹配路由和获取路由参数

---

前言

golang实现前缀数实现匹配路由和获取路由参数：

---

一、前缀树是什么？

前缀树:
又称单词查找树，字典树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

二、需求定义

使用前缀树 匹配路由
提取路由上的参数规则: 定义路由/v1/{a},其中a就是参数名,请求路由/v1/123,那么a=123
可以定义多个参数, 如: 定义路由/v1/{a}/{b}/{c},其中就有 a,b,c 3个路由参数
必须匹配完,如: 定义路由/v1/{a}/{b}则/v1/123/456能匹配上，/v1/123不能匹配上
不允许的规则,如: /v1/* /v1/{a} 两个都不能用，相互冲突

代码如下（示例）：

package main

import (
	"log"
	"strings"
)

// 前缀树结构
type Trie struct {
	next map[string]*Trie
	isWord bool
}

func NewTrie() Trie {
	root := new(Trie)
	root.next = make(map[string]*Trie)
	root.isWord = false
	return *root
}

// 插入数据， 路由根据 "/" 进行拆分
func (t *Trie) Insert(word string) {
	for _, v := range strings.Split(word, "/") {
		if t.next[v] == nil {
			node := new(Trie)
			node.next = make(map[string]*Trie)
			node.isWord = false
			t.next[v] = node
		}
		// * 匹配所有
		// {X}  匹配路由参数 X
		if v == "*" || strings.Index(v, "{") != -1 {
			t.isWord = true
		}
		t = t.next[v]
	}
	t.isWord = true
}

// 匹配路由
func (t *Trie) Search(word string) (isHave bool, arg map[string]string) {
	arg = make(map[string]string)
	isHave = false
	for _, v := range strings.Split(word, "/") {
		if t.isWord {
			for k,_ := range t.next {
				if strings.Index(k, "{") != -1 {
					key := strings.Replace(k, "{", "", -1)
					key = strings.Replace(key, "}", "", -1)
					arg[key] = v
				}
				v = k
			}
			//log.Println("v = ", v)
		}
		if t.next[v] == nil {
			log.Println("找不到了, 匹配不上")
			return
		}
		t = t.next[v]
	}
	//log.Println(t.next, len(t.next))
	// 必须匹配全  比如: /v1/{b}/{a}  /v1/123匹配不到， /v1/123/456才可匹配
	if len(t.next) == 0 {
		isHave = t.isWord
		return
	}
	return
}

// 打印树
func (t *Trie) Show(){
Loop:
	if t == nil {
		log.Println("end")
		return
	}
	log.Println(t)
	for _, v :=range t.next {
		t = v
		goto Loop
	}

}

func main(){

	// 1. 使用前缀树 匹配路由
	// 2. 提取路由上的参数规则:  定义路由/v1/{a},其中a就是参数名,请求路由/v1/123,那么a=123
	// 3. 可以定义多个参数, 如: 定义路由/v1/{a}/{b}/{c},其中就有 a,b,c 3个路由参数
	// 4. 必须匹配完,如: 定义路由/v1/{a}/{b}则/v1/123/456能匹配上，/v1/123不能匹配上
	// 5. 不允许的规则,如:  /v1/*  /v1/{a}  两个都不能用，相互冲突

	t := NewTrie()
	t.Insert("/")
	t.Insert("H/e/c/{b}/{a}")
	t.Insert("a/e/c/l/o")
	t.Insert("e/c/c/*")// 任意的 无法取 *的值
	t.Insert("e/c/c/{a}/{a}") // 只取后一个a
	t.Insert("/v1/*")
	t.Insert("/v1/{a}")
	t.Show()
	//isok, cs := t.Search("H/e/c/asdasd/asdasd")
	//isok, cs := t.Search("/v1/123")
	isok, cs := t.Search("/")
	log.Println(isok, cs)

	//fmt.Print(t.Search("H/e/l/l/aaa"),"\n")

}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112