如何在Scala中进行快速前缀字符串匹配

Question

我正在使用一些Java代码来执行快速前缀查找,使用java.util.TreeSet,我可以使用scala的TreeSet吗？还是另一种解决方案？

/** A class that uses a TreeSet to do fast prefix matching
 */
class PrefixMatcher {
  private val _set = new java.util.TreeSet[String]

  def add(s: String) = _set.add(s)

  def findMatches(prefix: String): List[String] = {
    val matches = new ListBuffer[String]
    val tailSet = _set.tailSet(prefix)
    for ( tail <- tailSet.toArray ) {
      val tailString = tail.asInstanceOf[String]
      if ( tailString.startsWith(prefix) ) 
        matches += tailString
      else
        return matches.toList    
    }

    matches.toList
  }
}

Answer 1

使用Trie.尽管事实上有些人发布了他们错误命名为试图的有序TreeMap数据结构,但实际上还没有人在这里发布过Trie.这是Java中Trie实现的一个相当有代表性的示例.我不知道任何Scala.另请参阅Wikipedia上的Tries解释.

Answer 2

在从与takeWhile方法:

class PrefixMatcher {
    private val _set = new TreeSet[String]
    def add(s: String) = _set.add(s)
    def findMatches(prefix: String): Iterable[String] =
        _set from prefix takeWhile(_ startsWith prefix)
}

另一种方法是从前缀中选择一个子集来加上前缀++(前缀后面的最小字符串).这仅选择实际以给定前缀开头的树的范围.不必过滤条目.subSet方法将创建基础集的视图.

在增量方法中仍然有一些工作(溢出和空字符串不起作用),但意图应该是清楚的.

class PrefixMatcher {
  private val _set = new java.util.TreeSet[String]

  def add(s: String) = _set.add(s)

  def findMatches(prefix: String) : Set[String] = {
    def inc(x : String) = { //ignores overflow
       assert(x.length > 0) 
       val last = x.length - 1
       (x take last) + (x(last) + 1).asInstanceOf[Char]
    }
   _set.subSet(prefix, inc(prefix))
  }
}

同样适用于scala jcl.TreeSet#range实现.