图片来自维基百科
介绍
trie，又称前缀树/字典树/单词查找树，是一种有序树
Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的
上图图示说明
图示中，键标注在节点中，值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie可以看作是一个确定有限状态自动机。键不需要被显式地保存在节点中。图示中标注出完整的单词，只是为了演示trie的原理
读音
trie的发明者Edward Fredkin把它读作英语发音：“tree”。但是，其他作者把它读作英语发音：“try”。
基本特性
- 根结点不包含字符，除根节点意外每个结点只包含一个字符
- 从根结点到某个结点，经过的字符连接起来，为该结点对应的字符串
- 每个节点的所有子节点包含的字符都不相同
基本操作
基本操作有：查找、插入和删除,当然删除操作比较少见
应用
典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）
trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能
在我们做NLP中命名实体识别（NER），采用字典法时，可能会用到trie-tree作为快速搜索算法
可视化
C语言实现
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
|
#define MAX 26//字符集大小
typedef struct TrieNode
{
int nCount;//记录该字符出现次数
struct TrieNode* next[MAX];
}TrieNode;
TrieNode Memory[1000000];
int allocp=0;
/*初始化*/
void InitTrieRoot(TrieNode* *pRoot)
{
*pRoot=NULL;
}
/*创建新结点*/
TrieNode* CreateTrieNode()
{
int i;
TrieNode *p;
p=&Memory[allocp++];
p->nCount=1;
for(i=0;i<MAX;i++)
{
p->next[i]=NULL;
}
return p;
}
/*插入*/
void InsertTrie(TrieNode* *pRoot,char *s)
{
inti,k;
TrieNode*p;
if(!(p=*pRoot))
{
p=*pRoot=CreateTrieNode();
}
i=0;
while(s[i])
{
k=s[i++]-'a';//确定branch
if(!p->next[k])
p->next[k]=CreateTrieNode();
p->next[k]->nCount++;
p=p->next[k];
}
}
//查找
int SearchTrie(TrieNode* *pRoot,char *s)
{
TrieNode *p;
int i,k;
if(!(p=*pRoot))
{
return0;
}
i=0;
while(s[i])
{
k=s[i++]-'a';
if(p->next[k]==NULL) return 0;
p=p->next[k];
}
return p->nCount;
}
|
python描述
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
|
""" Tries in python
Methods - insert_key(k, v)
has_key(k)
retrie_val(k)
start_with_prefix(prefix)
"""
def _get_child_branches(trie):
"""
Helper method for getting branches
"""
return trie[1:]
def _get_child_branch(trie, c):
"""
Get branch matching the character
"""
for branch in _get_child_branches(trie):
if branch[0] == c:
return branch
return None
def _retrive_branch(k, trie):
"""
Get branch matching the key word
"""
if not k:
return None
for c in k:
child_branch = _get_child_branch(trie, c)
if not child_branch:
return None
trie = child_branch
return trie
def _is_trie_bucket(bucket):
if len(bucket) != 2:
return False
return type(bucket[1]) is tuple
def _get_bucket_key(bucket):
if not _is_trie_bucket(bucket):
return None
return bucket[1][0]
def has_key(k, trie):
"""
Check if trie contain the key word
"""
return _retrive_branch(k, trie) is not None
def retrie_val(k, trie):
key_tuple = _retrive_branch(k, trie)
if not key_tuple:
return None
return key_tuple[1]
def insert_key(key, v, trie):
"""
Insert a (key, value) pair into trie
"""
if not key or has_key(key, trie):
return
for char in key:
branch = _get_child_branch(trie, char)
if not branch:
new_branch = [char]
trie.append(new_branch)
trie = new_branch
else:
trie = branch
trie.append((key, v))
def start_with_prefix(prefix, trie):
"""
Find words start with prefix
"""
branch = _retrive_branch(prefix, trie)
if not branch:
return []
prefix_list = []
q = branch[1:]
while q:
curr_branch = q.pop(0)
if _is_trie_bucket(curr_branch):
prefix_list.append(_get_bucket_key(curr_branch))
else:
q.extend(curr_branch[1:])
return prefix_list
|
使用
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
|
trie = [[]]
states = """
Alabama
Alaska
Arizona
Arkansas
California
Colorado
Connecticu
Hawaii
Idaho
Illinois
Indiana
Maine
Maryland
Massachusetts
Michigan
Minnesota
Mississippi
Missouri
Montana
"""
states_list = [w.strip().lower() for w in states.splitlines() if w]
for state in states_list:
insert_key(state, True, trie)
print start_with_prefix("new", trie)
|
参考