数据结构重读 - 键树、字典树

键树,又称数字查找树(Digital Search Trees)是一棵度>=2的树,每个结点只含有组成关键字的符号。

键树有两种存储结构:

1、树的孩子-兄弟链表来表示键树。

每个Node有三个域:first指向第一棵子树的根指针;next指向右兄弟;info(可选的)记录附加数据。如下图:

查找过程是,从根结点出发,顺着first查找,如果相等,继续下一个first。否则沿着next查找。直到到了空指针为止。此时若仍未完成key的匹配,查找不成功。

2、以树的多重链表表示键树(Trie树)。

每个结点中含有d个指针域,此时又称Trie树。

Trie树中有两种结点:
(1)分支结点:含有d个指针域,整数n记录非空指针域的个数(可选)。
(2)叶子结点:含有关键字域(完整的关键字、可选)、附加数据域名(可选)。

实际实现的时候,一般都偷懒,只包含那d个指针域。

如下图:

在标准Trie树的基础上,可以压缩:若从键树中某个结点到叶子结点的路径上每个结点都只有一个孩子,则可将该路径上的所有结点压缩成一个叶子结点。如下图所示:

一个标准Trie树的Java实现如下:

import java.util.Arrays;

public class TrieNode {

	public TrieNode() {
		ptr = new TrieNode[BRANCH];
		Arrays.fill(ptr, null);
	}

	public static final int BRANCH = 27;
	public TrieNode[] ptr = null;
	public int nptr = 0;
}
public class Trie {

	public Trie() {
		root = new TrieNode();
	}

	public void Insert(String key) {
		TrieNode p = root;
		for (int i = 0; i < key.length(); i++) {
			int offset = key.charAt(i) - 'a';
			if (p.ptr[offset] == null) {
				p.ptr[offset] = new TrieNode();
				p.nptr++;
			}
			p = p.ptr[offset];
		}
	}

	public boolean Search(String key) {
		TrieNode p = root;
		for (int i = 0; i < key.length(); i++) {
			int offset = key.charAt(i) - 'a';
			if (p.ptr[offset] == null) {
				return false;
			}
			p = p.ptr[offset];
		}
		return true;
	}

	private TrieNode root = null;

	public static void main(String[] args) {
		Trie trie = new Trie();
		trie.Insert("liheyuan");
		trie.Insert("liheyuan");
		System.out.println(trie.Search("liheyuan"));
	}
}

 延伸阅读:中文Trie树

摘抄自:http://hxraid.iteye.com/blog/618962

由于中文的字远比英文的26个字母多的多。因此对于trie树的内部结点,不可能用一个26的数组来存储指针。如果每个结点都开辟几万个中国字的指针空间。估计内存要爆了,就连磁盘也消耗很大。

一般我们采取这样种措施:

(1) 以词语中相同的第一个字为根组成一棵树。这样的话,一个中文词汇的集合就可以构成一片Trie森林。这篇森林都存储在磁盘上。森林的root中的字和root所在磁盘的位置都记录在一张以Unicode码值排序的有序字表中。字表可以存放在内存里。

(2) 内部结点的指针用可变长数组存储。

特点:由于中文词语很少操作4个字的,因此Trie树的高度不长。查找的时间主要耗费在内部结点指针的查找。因此将这项指向字的指针按照字的Unicode码值排序,然后加载进内存以后通过二分查找能够提高效率。

补充:我觉得对于字典这种应用,改动会很小的,真的可以内存中Trie树+二分查找搞定。

 

 

1 thought on “数据结构重读 - 键树、字典树

Leave a Reply

Your email address will not be published. Required fields are marked *