6

听完最新的 Stack Overflow 播客后，Peter Norvig 的紧凑型 Python 拼写检查器引起了我的兴趣，所以我决定在 Scala 中实现它，如果我能用函数式 Scala 成语很好地表达它，并且看看它需要多少行代码.

这是整个问题。（我们先不要比较代码行。）

（两个注意事项：如果你愿意，你可以在 Scala 解释器中运行它。如果你需要 big.txt 的副本，或者整个项目，它在 GitHub 上。）

import scala.io.Source

val alphabet = "abcdefghijklmnopqrstuvwxyz"

def train(text:String) = {
  "[a-z]+".r.findAllIn(text).foldLeft(Map[String, Int]() withDefaultValue 1)
    {(a, b) => a(b) = a(b) + 1}
}

val NWORDS = train(Source.fromFile("big.txt").getLines.mkString.toLowerCase)

def known(words:Set[String]) =
  {Set.empty ++ (for(w <- words if NWORDS contains w) yield w)}

def edits1(word:String) = {
  Set.empty ++
  (for (i <- 0 until word.length) // Deletes
    yield (word take i) + (word drop (i + 1))) ++ 
  (for (i <- 0 until word.length - 1) // Transposes
    yield (word take i) + word(i + 1) + word(i) + (word drop (i + 2))) ++ 
  (for (i <- 0 until word.length; j <- alphabet) // Replaces
    yield (word take i) + j + (word drop (i+1))) ++ 
  (for (i <- 0 until word.length; j <- alphabet) // Inserts
    yield (word take i) + j + (word drop i))
}

def known_edits2(word:String) = {Set.empty ++ (for (e1 <- edits1(word);
  e2 <- edits1(e1) if NWORDS contains e2) yield e2)}

def correct(word:String) = {
  val options = Seq(() => known(Set(word)), () => known(edits1(word)),
    () => known_edits2(word), () => Set(word))
  val candidates = options.foldLeft(Set[String]())
    {(a, b) => if (a.isEmpty) b() else a}
  candidates.foldLeft("") {(a, b) => if (NWORDS(a) > NWORDS(b)) a else b}
}

具体来说，我想知道我是否可以使用该correct功能做任何更清洁的事情。在原始 Python 中，实现更简洁一些：

def correct(word):
    candidates = known([word]) or known(edits1(word)) or
      known_edits2(word) or [word]
    return max(candidates, key=NWORDS.get)

显然，在 Python 中，一个空集将评估为 Boolean False，因此只有第一个返回非空集的候选者将被评估，从而节省了对edits1and的潜在昂贵调用known_edits2。

我想出的唯一解决方案是您在此处看到的版本，其中Seq调用匿名函数，直到返回一个 non-empty Set，最后一个保证会这样做。

如此有经验的 Scala-heads，有没有更简洁或更好的方法来做到这一点？提前致谢！

4

5 回答 5

6

我不确定您为什么要尝试使用惰性评估，known而不是像 oxbow_lakes 所示的那样简单地使用流。做他所做的更好的方法：

def correct(word: String) = {
  import Stream._

  val str = cons(known(Set(word)), 
            cons(known(edits1(word)),
            cons(known_edits2(word),
            cons(Set(word), empty))))

  str find { !_.isEmpty } match {
    case Some(candidates) =>
      candidates.foldLeft(Set[String]()) { (res, n) =>
        if (NWORDS(res) > NWORDS(n)) res else n
      }

    case None => Set()
  }
}

该漏洞利用了已经很懒惰的事实，Stream.cons因此我们不需要将所有内容都包含在一个 thunk 中。

不过，如果你真的想要好的语法，我们可以在所有这些 conses 中添加一些语法糖：

implicit def streamSyntax[A](tail: =>Stream[A]) = new {
  def #::(hd: A) = Stream.cons(hd, tail)
}

现在我们以前丑陋的str定义如下：

def correct(word: String) = {
  val str = known(Set(word)) #:: known(edits1(word)) #::
            known_edits2(word) #:: Set(word) #:: Stream.empty

  ...
}
于 2009-11-23T02:37:02.193 回答
4

这行得通吗？_语法是部分应用的函数，通过使用 (lazy) ，Stream我确保reduceLeft（我认为比foldLeft这里更合适）中的评估只在需要时发生！

def correct(word:String) = {
  Stream(known(Set(word)) _, 
         known(edits1(word)) _, 
         known_edits2(word) _, 
         Set(word) _
         ).find( !_().isEmpty ) match {
    case Some(candidates) =>
      candidates.reduceLeft {(res, n) => if (NWORDS(res) > NWORDS(n)) res else n}
    case _ => "" //or some other value

}

我可能在这里犯了一些语法错误，但我认为这种Stream方法是有效的

于 2009-11-23T00:12:13.280 回答
3

Scala 2.7-ready（包括隐式性能变通）：

class Or[A](one: Set[A]) {
  def or(other: => Set[A]): Set[A] = if (one.isEmpty) other else one 
}

implicit def toOr[A](one: Set[A]) = new Or(one)

def correct(word: String) = {
  candidates = known(Set(word)) or known(edits1(word)) or known_edits2(word) or Set(word)
  candidates.foldLeft("") {(a, b) => if (NWORDS(a) > NWORDS(b)) a else b}
}

Scala 2.8-善良：

implicit def toOr[A](one: Set[A]) = new AnyRef { 
  def or(other: => Set[A]): Set[A] = if (one.isEmpty) other else one 
}

def correct(word: String) = {
  candidates = known(Set(word)) or known(edits1(word)) or known_edits2(word) or Set(word)
  candidates.max(Ordering.fromLessThan[String](NWORDS(_) < NWORDS(_)))
}

也就是说，我几乎赞成其他所有人的投票。我没有考虑过Stream.

编辑

它似乎Ordering.fromLessThan可以导致两倍的必要比较。这是该行的替代版本：

  candidates.max(new Ordering[String] { def compare(x: String, y: String) = NWORDS(x) - NWORDS(y) })
于 2009-11-23T11:04:01.373 回答
2

迭代器也是惰性的（虽然不是很实用，因为你只能迭代它们一次。）所以，你可以这样做：

  def correct(word: String) = {
    val sets = List[String => Set[String]](
      x => known(Set(x)), x => known(edits1(x)), known_edits2
    ).elements.map(_(word))

    sets find { !_.isEmpty } match {
      case Some(candidates: Set[String]) => candidates.reduceLeft { (res, n) => if (NWORDS(res) > NWORDS(n)) res else n }
      case None => word
    }
  }

作为奖励，Iterator 的 find() 方法不会强制评估下一个元素。

于 2009-11-23T06:41:37.570 回答
0

我试图实现拼写校正器的简短 Scala 实现。这是 15 行没有导入。Python 的 or 的最短替换是简单的按名称参数调用：

def or[T](candidates : Seq[T], other : => Seq[T]) = if(candidates.isEmpty) other else candidates
def candidates(word: String) = or(known(List(word)), or(known(edits1(word)), known(edits2(word))))

在现实世界的场景中，我会使用 Daniel 提出的隐式转换。

于 2009-12-31T14:56:59.827 回答