基数树的应用

1. 电子词典和单词的自动补齐

如百度的搜索引擎，当用户输入内容后，会列出一些可能的候选搜索项。

那么我们接下来看看如何使用基数树来实现电子词典

我们假设词典中保存了key-Value对，key是英文单词或词组，对应的value是解释。

当用户输入“a”的时候，词典不只给出a的意思，而且还提供一列候选单词的列表。

查找算法为：

如果待查找的字符串为空，我们从当前的节点扩展出n个字节点作为候选项

否则递归的在有公共前缀的子分子中查找。

 1  def  patricia_lookup(tree,key,n):
 2      if tree is None:
 3          return None
 4      prefix = ""
 5      while True:
 6          match = False
 7          for k, tr in tree.children.items():
 8              #如果key时k的前缀，则通过expand方法返回以keykey为前缀的单词
 9              if string.find(k,key) == 0:
10                  return expand(prefix+k,tr,n)
11              #如果k是key的前缀，则另prefix += k,在子分支中继续查找key[len(k):]
12              if string.find(key,k) == 0:
13                  match = True
14                  key = key[len[k]:]
15                  tree = tr
16                  prefix += k
17                  break
18          if not match:
19              return None
20  def expand(prefix,t,n):
21      res = []
22      q =[(prefix,t)]
23      while len(res) < n and len(q) >0:
24          (s, p) = q.pop(0)
25          if p.value is not None:
26              res.expand((s,p.value))
27          for k, tr in p.children.items():
28              q.append((s+k, tr))
29      return res

例子2：T9输入法

 1 import string
 2 T9map ={
 3     '2':"abc",'3':"def",'4':"ghi",'5':"jkl",
 4     '6':"mno",'7':"pqrs",'8':"tuv",'9':"wxyz"
 5 }
 6 
 7 def patricia_lookup_t9(t,key):
 8     if t is None or key == "":
 9         return None
10     q = [("",key,t)]
11     res =[]
12     while len(q)>0:
13         (prefix,key,t) = q.pop(0)
14         for k, tr in t.children.items():
15             digits = T9map(k)
16             if string.find(key,digits) == 0:
17                 if key == digits:
18                     res.append((prefix+k,tr.value))
19                 else:
20                     q.append((prefix+k,key[len(k):],tr))
21     return res