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

发布时间：2020-12-16 18:27:02 所属栏目：安全来源：网络整理

导读：我正在使用一些 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[St

我正在使用一些 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
  }
}

解决方法

来自&采取的方法：

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实现.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!