6

After hearing the latest Stack Overflow podcast, Peter Norvig's compact Python spell-checker intrigued me, so I decided to implement it in Scala if I could express it well in the functional Scala idiom, and also to see how many lines of code it would take.

Here's the whole problem. (Let's not compare lines of code yet.)

(Two notes: You can run this in the Scala interpreter, if you wish. If you need a copy of big.txt, or the whole project, it's on 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}
}

Specifically, I'm wondering if there's anything cleaner I can do with the correct function. In the original Python, the implementation is a bit cleaner:

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

Apparently in Python, an empty set will evaluate to Boolean False, so only the first of the candidates to return a non-empty set will be evaluated, saving potentially expensive calls to edits1 and known_edits2.

The only solution I would come up with is the version you see here, where the Seq of anonymous functions are called until one returns a non-empty Set, which the last one is guaranteed to do.

So experienced Scala-heads, is there a more syntactically concise or better way to do this? Thanks in advance!

4

5 に答える 5

6

knownoxbow_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ため、すべてをサンクにまとめる必要はありません。

しかし、本当に素敵な構文が必要な場合は、これらすべてのコンスに構文糖衣を追加できます。

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の評価が必要な場合にのみ行われるようにします!reduceLeftfoldLeft

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 対応 (暗黙的なパフォーマンスの回避策を含む):

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必要な比較が 2 倍になる可能性があるようです。その行の代替バージョンを次に示します。

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

イテレータも怠け者です (ただし、反復できるのは 1 回だけなのであまり機能的ではありません)。したがって、次のように実行できます。

  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))))

実際のシナリオでは、ダニエルが提案した暗黙の変換を使用します。

于 2009-12-31T14:56:59.827 に答える