有一堆key-value的数据,有人输入一个key的子串,我们希望很容易的得到前面那个key-value中所有key包含该子串的pairs.Trie树是一个不错的解决方案.
如名字所示,Trie树是一个字典树,它的大致方向是构造一个如下图所示的字典树:
它被用来存储to,tea,ted,ten,A,in,inn等若干字符串.
查询是从root开始,foreach查询字符串的每个char,根据char的类型而转换状态,直到状态转换失败或者查询字串完毕.这时候节点的所有子节点内容都是包含查询字串的内容.从这个意义上说,查询就是个有限状态机,到终止状态后求子树这样子.
在你输入't'的时候,你会从root节点跳转到t节点,再输入'e',你就跳转到e节点.
若你的查询字串就是te,那么你将停留在te这个节点.那么它的所有子节点(tea,ted,ten)就是查询结果了.
但是,正如很多地方所提示的,它的是一种prefix-tree,若我们查ea在这个时候并不能得到期望的tea.为了能够查询任意子串,我们需要再加个index,我们在第一步不是从root,而是从index开始,查询然后跳转到所有带第一个字符的节点,这样就很容易实现这一点了.
在树的具体实现上,很多人有各种不同的考虑,因为具体的实施场景不一样,实现自然各有不同.目前我假定的是同一个key也可能有不同的value,然后输入一个子串得到所有的value.在实际使用的时候,我的key-value的pair大约有350k的样子,所以时空权衡方面持保守方向.
我的一个实现贴到了gist上去了,地址在此.简单介绍如下:
首先,对树的每个节点定义如下:
case class TrieNode[V](
base: Option[Char], // current node
check: Option[TrieNode[V]], // previous node , None for the first node
next: TrieMap[Char, TrieNode[V]]) {
var v: MutableSet[V] = MutableSet[V]()
}
这是一个很简单的三元结构,v中存放的是附带的value,其它几个是构造树需要的内容,分别为base,当前节点的状态值,check,父亲节点的地址,next,子节点的map.
顺便一说,本来打算看看scala有没有系统自带trietree的,结果发现了triemap,尝试了下感觉还是蛮好用的.
然后是添加内容代码:
def put(k: String, v: V) = insertMonitor.synchronized {
var p = root
for (c <- k) {
if (!p.next.contains(c)) {
val t = (c -> new TrieNode[V](Some(c), Some(p), TrieMap[Char, TrieNode[V]]()))
index.getOrElseUpdate(c, ArrayBuffer[TrieNode[V]]()) += t._2
p.next += t
}
p = p.next.get(c).get
}
p.v += v
}
root是根节点,定义就是TrieNode,index的定义是TrieMap[Char, ArrayBuffer[TrieNode[V]]],意思就是从root开始将key走一遍状态机并在终止状态留下value.
查询也很方便
def find(k: String, limit: Option[Int] = None): List[V] = {
if (k.length() > 0) {
val tk = k.splitAt(1)
var pSet = index.get(tk._1.charAt(0)) match {
case Some(ps) => ps
case None => ArrayBuffer[TrieNode[V]]()
}
val rpSet = pSet.par.flatMap { p =>
var rp = Option(p)
def checkString {
for (c <- tk._2) {
rp = rp match {
case Some(gp) => gp.next.get(c)
case None => return
}
}
}
checkString
rp
}
//ignored: get results
List[V]()
} else {
List[V]()
}
}
简而言之就是从index查询第一个字符可以跳转到的状态列表,然后逐个跳转状态获得子树下的value(当然篇幅关系省略, 详情参考gist)
Trie树有很多问题,首先是内存占用比较高.为了避免重复存放value,我将value只放在了最后状态,所以当返回值比较多的时候(比如query就一个s,而返回结果可能有数万),将会耗费比较多的时间(一秒多到两秒,我的三十万数据集上),这是个缺憾. 总之就是个或者费空间或者费时间的考虑了.
