Trie数据结构实现与应用

在二叉树结构中,每个元素的插入通过比较来确定其最终存储的位置,比较操作需要对于整个的元素进行比较 整数的直接比较大小,字符串的可以通过按照字母顺序,其他类型可以通过自定义比较方式来实现。比如下面的存储人员姓名的二叉树结构中,当我们插入一个新的元素”Wendy“的时候:

  • 首先与根元素进行比较,由于Wendy > Karen因此元素需要存储在其右子树中
  • 进入右子树中,由于Wendy > Tom元素继续向下存储在其右子树中。
  • 右边子树已经为空,因此将元素存储在这个位置.

1. Trie结构介绍

trie数据结构也是一个树形结构,不同于二叉树的完整值比较,trie结构在定位查找或者插入的时候仅仅使用部分元素即可确定起所在的位置.比如组成单词”hello“的每一个字母。 为了绘图简单一些,我们使用一个简化版的字母表,这个字母表中仅包含5个字母,分别是ABCDEF,我们使用trie结构来存储下面的一组数据["ABC", “ADD”, “AE”, “EA”, “EAB”, “EBB”, “EDA”],这里存储的长度随意没有限制.我们依次的去存储该数据集合到trie结构.

如果是正常的字母表,则每一个节点包含的子节点数量为26个,而不是上面的5个,因此第一层包含26个节点,第二层则包含26*26个节点,第三层包含26*26*26个节点.对于仅仅存储三个字母的集合我们就需要这么多数据存储,岂不是占用的空间很多? 其实这里在插入的时候,我们构造的并非一个完全的trie结构,而是仅仅包含必要的数据,也就是上面的一组元素中如果都没有被着色 也就是从未被访问过,其实并不存在, 上面的图只是为了展示结构的目的.实际的存储如下面所示:

节点信息的存储,针对上面的实例图中

  • 其中每一个方格代表一个节点
  • 每个节点包含一个值,可以为空,以及一个指针数组分别指向下一级的一组节点(5个节点),且初始化为null空值.
  • 比如根节点初始化为空值"",包含一个5个元素的数组指针分别设置为null

另外使用数组来存储指针可以通过下标来取得指定元素的指针,比如A元素作为第一个值存在数组的索引为0的位置,按照字母顺序依次递增索引值。部分数据存在共享节点的情况,比如数据"EA"和"EAB"的存储路径,因此前缀相同的元素,共享前缀所包含的路径信息. 我们可以使用下面的数据结构来存储每一个节点


type Node struct {
	isLeaf bool
	children [26]*Node
}

// NewNode create a node with default value
func NewNode()*Node{
	node := Node{
		isLeaf:   false,
		children: [26]*Node{},
	}
	return &node
}

2. 如何插入元素

假设我们现在的trie结构为空,我们先来看下如何插入一个元素的流程,这里我们拿"EBB"作为示例,

  1. 初始化一个root节点,节点的值为””, 节点包含一个指针数组,数组大小为5个 , 初始化为null, 开始处理第一个元素.
  2. E代表第五个元素,由于存储的是null, 我们给他初始化一个新的节点,节点值为"",初始化的指针数组同上.此时设置root中第五个数组元素为该节点地址.开始处理第二个元素
  3. B代表了第二个元素, 查询上面E元素包含的指针数组中第二个元素为空,初始化一个新的节点,同上.完成后初开始处理第三个元素.
  4. 同上,只不过这里设置其值不为空,代表其不同于前面创建的节点,该节点为一个叶子节点.上述为空的则代表了路径值.

代码实现如下所示:

// Insert inserts words at a Trie node.
func (n *Node) Insert(s string) {
	curr := n
	s = strings.ToLower(s)
	for _, c := range s {
		// ignore non-alphabet
		if c < 97 || c > 122 {
			continue
		}
		if curr.children[c-97] == nil{
			curr.children[c-97] = NewNode()
		}
		curr = curr.children[c-97]

	}
	curr.isLeaf = true
}

2. 搜索字符串

搜索的流程和插入的流程比较类似,也都是逐层查询元素,比如上面的数据结构总我们查询一个元素为"ABD",

  • 1.首先在根元素中查找A位置的指针是否存在,此时存在该指针
  • 2.追随指针进入第二层,查找B元素所包含的指针是否存在,此时存在该指针
  • 3.追随指针进入第三层,查找D元素位置是否存在节点,此时发现该位置为空.则返回查找失败,该值不存在.

搜索过程中可能出现的结果包括:路径节点不存在, 最终位置节点值为空(只是作为其他元素存储的路径使用),比如我们搜索”AB”, 以及最终位置节点存在且值不为空


// Find finds words at a Trie node.
func (n *Node) Find(s string) bool {
	curr := n
	s = strings.ToLower(s)
	for _, c := range s {
		if c < 97 || c > 122 {
			continue
		}
		next := curr.children[c-97]
		if next == nil{
			return false
		}
		curr = next
	}
	return curr.isLeaf == true
}

3. 删除元素

删除元素相对于其他的操作不是那么直接,因为我们的删除操作,可能会对其他的节点产生影响.具体的删除元素的流程如下面所示:

  • 1.检查元素EBB是否存在, 发现存在
  • 2.设置最终位置的B节点内数据为空,
    • 2.1 并检查是否存在指针列表不为空的位置(代表有路径经过该元素)
    • 2.2 如果发现有其他指针不为空,则删除流程结束,完成数据的删除
    • 2.3 如果发现数组指针全部为null, 返回上一层,将指针位置(B)指针设置为null.

重复2.1-2.3 步骤.直到发现存在不为null的指针或者到达根的位置.

这里处理的逻辑包含一个向下的查询,和向上的清理操作流程,假如我们不去执行向上的清理操作,会导致随着路径元素越来越多,节点没有得到有效清理,会导致后续查询中很多的无效路径验证.

// BackTrace trace the path from root to founded node
type BackTrace struct{
	index int32
	node *Node
}

func (n *Node) Delete(s string) bool{
	curr := n
	s = strings.ToLower(s)
	// insert root node with index -1 for stop condition check
	path:=[]*BackTrace{
		{
			index: -1,
			node:  n,
		},
	}
	for _, c := range s {
		if c < 97 || c > 122 {
			continue
		}
		next := curr.children[c-97]
		if next == nil{
			return false
		}
		path = append(path, &BackTrace{
			index: c-97,
			node:  next,
		})
		curr = next
	}
	if curr.isLeaf == false{
		return false
	}
	curr.isLeaf = false
	for i := len(path)-1; i==0 ;i--{
		backTrace := path[i]
		if backTrace.index == -1 {
			return true
		}
		for j := 0; j<26 ;j++  {
			if backTrace.node.children[j] != nil{
				return true
			}
		}
		path[i-1].node.children[backTrace.index] = nil
	}
	return true
}

3.trie的性能与资源占用

根据trie的结构以及常用操作流程,我们可以对比一下Trie和哈希表结构,两者都同样可以用来存储kv数据,也同样具有唯一性限制,因此功能上是可以相互替换使用的,并且相对哈希表还省略了计算key的hash值流程.直接通过key的名称来进行逐层操作, 效率上通常也要比hash算法也更快一些(尽管hash操作为O(1),但是计算hash值以及处理碰撞等开销也较大).我们不要忘了算法中任何的选择都是有代价的!!! trie结构中存储需要占用的内存相对要更多一些.而且随着元素长度越长,其占用的无效的数据也就越多.存储效率方面则同时和字母空间成正比,存储效率为O(n*N*M),其中M为存储的元素数量,N代表字母表空间,默认为26 trie结构在插入,删除和搜索上的执行效率还是可以的,与待搜索的单词长度n成正比,整体的执行效率为O(n).
比如我们初始化一个trie,只存在了一个单词"Hippopotomonstrosesquippedaliophobia"(中文翻译 长单词恐惧症)那我们就需要为每一个字母都初始化一个26个元素的指针数组.35*26*4字节

4.trie结构的用途

自动补全:这个可能是最为熟知的trie结构的应用,我们首先将允许的单词集合写入trie结构中,每当我们输入一个单词的时候,我们就可以通过在构造的trie中进行查询,不仅可以知道是否该元素存在字典中,同时还可以知道是否存在路径前缀相同的单词存在,返回该节点后面的所有指针以及包含的元素即可.

url补全,浏览器中仅需要输入前缀,则返回所有相同前缀的历史访问记录的,但是现在也有一些浏览器支持更多的模糊匹配规则,支持随机位置的匹配,实现则与前缀匹配不同

树形结构数据存储: 另外在一些DNS软件中,数据存储层实现除了使用常见的红黑树以外,也可以使用trie结构来存储。比如开源DNS软件Knot的实现, 其内部使用了一个qp trie结构(一种trie结构的变种实现)

发表评论

电子邮件地址不会被公开。 必填项已用*标注