有一堆key-value的数据,有人输入一个key的子串,我们希望很容易的得到前面那个key-value中所有key包含该子串的pairs.Trie树是一个不错的解决方案.

如名字所示,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,而返回结果可能有数万),将会耗费比较多的时间(一秒多到两秒,我的三十万数据集上),这是个缺憾. 总之就是个或者费空间或者费时间的考虑了.


Yu

Ideals are like the stars: we never reach them, but like the mariners of the sea, we chart our course by them.

Leave a Reply

Your email address will not be published.