Ricardo Rocha's Website

Musings on Programming and Programming Languages

Email GitHub Bitbucket Twitter LinkedIn

Spelling Suggestion on the JVM #4: Implementing Norvig's Algo in Scala

This tutorial project implements a basic spelling suggestion service. The motivation is didactic: becoming familiar with “better java” languages around a simple but instructional example. Ease of implementation outranks optimal performance so readers can focus on the JVM languages as such. Examples and new concepts are introduced in Java 10 first so they’re immediately understandable to the experienced Java programmer. Crucially, the Java implementation is accompanied by equivalent (but idiomatic) implementations in today’s most relevant alternative JVM languages: Kotlin, Scala and Xtend. Code is available at Spellbound’s Github repo.

This fourth presents an idiomatic Scala implementation of Norvig’s spelling corrector.

The next post (Implementing Norvig’s Algo in Xtend, in the works) presents an idiomatic Xtend implementation of Norvig’s spelling corrector.

The previous post (Implementing Norvig’s Algo in Kotlin) illustrates how to implement Norvig’s spelling corrector in Kotlin following a functional style.

In the works…

This article is still in the works but complete, tested code is available at the Spellbound Github repository.

The Dictionary

Everything having to do with spelling correction revolves around a curated list of valid words we refer to as the the dictionary.

In our dictionary implementation we associate every word with an integer rank indicating how frequently the word is used in relation to all other words. The higher the rank, the more frequently used the word is. Thus, for instance, the has rank 106295 while triose has rank 1.

The dictionary declaration is:

case class NorvigSpellingCorrector(dictionary: Map[Word, Rank]) {
  def getCorrectionsFor(word: Word): Option[Seq[Word]] =
    NorvigSpellingCorrector.getCorrectionsFor(word, dictionary)
}

Final words about Scala


Next in our plate: Implementing Norvig’s Algo in Xtend

comments powered by Disqus