在前缀树中搜索字符串。摘要建议

Question

我正在使用一个前缀树算法。它应该为我提供输入中包含一个单词的所有单词。在向树中添加新单词时，我遇到了一些问题。这是由于Scala知识的空白。你能告诉我怎么修吗？

我的班级：

  class SuggestService(companyNames : Seq[String]) {

  val ternary = Ternary.apply
                       .insert("Googland")   //This word is added.
                       .insert("GoogleMaps") //This word is added.
  ternary.insert("GooglePhone") //This word is not added.
  ternary.insert("Google")      //This word is not added.

  def suggest(input: String, numberOfSuggest : Int) : Seq[String] = {
    val result = ternary.keysWithPrefix("Goog")
    result
  }
}

在启动后，我得到：

result == List(Googland, GoogleMaps)

尽管我希望得到：

result == List(Googland, GoogleMaps, GooglePhone, Google)

树型类：

sealed trait Ternary {
  def insert(key: String): Ternary = Ternary.insert(this, key, 0)

  def keysWithPrefix(prefix: String): List[String] = Ternary.keys(this, prefix)
}

case class Node(value: Option[Int], char: Char, left: Ternary, mid: Ternary, right: Ternary) extends Ternary

case object Leaf extends Ternary

object Ternary {
  def apply: Ternary = Leaf

  private def keys(root: Ternary, prefix: String): List[String] =
    get(root, prefix, 0) match {
      case None => Nil
      case Some(node) =>
        collect(node, prefix.dropRight(1))
    }

  private def collect(node: Ternary, prefix: String): List[String] =
    node match {
      case Leaf => Nil
      case node: Node if node.value.isDefined =>
        (prefix + node.char) +: (collect(node.left, prefix) ++ collect(node.mid, prefix + node.char) ++ collect(node.right, prefix))
      case node: Node =>
        collect(node.left, prefix) ++ collect(node.mid, prefix + node.char) ++ collect(node.right, prefix)
    }

  private def get(root: Ternary, prefix: String, step: Int): Option[Ternary] = root match {
    case Leaf => None
    case node: Node if node.char > prefix.charAt(step) => get(node.left, prefix, step)
    case node: Node if node.char < prefix.charAt(step) => get(node.right, prefix, step)
    case node: Node if step < prefix.length - 1 => get(node.mid, prefix, step + 1)
    case node: Node => Some(node)
  }

  private def insert(root: Ternary, key: String, step: Int): Ternary = root match {
    case Leaf =>
      val node = Node(None, key.charAt(step), Leaf, Leaf, Leaf)
      insert(node, key, step)

    case node: Node if node.char > key.charAt(step) =>
      val left = insert(node.left, key, step)
      node.copy(left = left)

    case node: Node if node.char < key.charAt(step) =>
      val right = insert(node.right, key, step)
      node.copy(right = right)

    case node: Node if step < key.length - 1 =>
      val mid = insert(node.mid, key, step + 1)
      node.copy(mid = mid)

    case node: Node =>
      node.copy(value = Some(0))
  }
}

Answer 1

函数insert返回一个新的Ternary实例。

您可以尝试这样做：

val ternary = Ternary.apply
  .insert("Googland")   //This word is 
  .insert("GoogleMaps") //This word is added.
  .insert("GooglePhone") //This word is not added.
  .insert("Google")
val result = ternary.keysWithPrefix("Goog")
result == List(Googland, GoogleMaps, GooglePhone, Google)

Answer 2

我已经找到了解决我的问题的替代方案。但我感兴趣的是执行the set.range(prefix, succ(prefix))操作的复杂性。我是否可以使用numberOfSuggest变量重写range方法以返回一个有限的集合？

class SuggestService(companyNames : Seq[String]) {

  val tree = new Tree
  companyNames.foreach(tree.add)

  def suggest(input: String, numberOfSuggest : Int) : Seq[String] = {
    val result = tree.findMatches(input, numberOfSuggest)
    result.toSeq
  }
}

树型类：

import scala.collection.immutable._
class Tree {

  private var set = new TreeSet[String]()
  private def succ(s : String) = s.take(s.length - 1) + (s.charAt(s.length - 1) + 1).toChar

  def add(s: String): Unit = set += s

  def findMatches(prefix: String, numberOfSuggest: Int): Set[String] =
    if (prefix.isEmpty)
      set
    else
      set.range(prefix, succ(prefix))
}