Top K words with MaxHeap

top-k-words-stream.sc

val input2 =
  """
    |Lorem ipsum dolor sit amet, consectetur adipiscing elit. Vestibulum viverra sit amet ligula id imperdiet. Proin vestibulum eget tellus in viverra. Mauris eleifend malesuada nunc, non porta quam placerat non. Nunc viverra, quam ac varius posuere, sapien tortor elementum nibh, a pulvinar mi nulla vitae lorem. Duis diam dolor, luctus ut suscipit eu, sodales in est. Maecenas egestas at velit eleifend laoreet. Aliquam imperdiet lorem et dolor finibus laoreet vel et lectus. Duis finibus felis eu tempus consectetur. Quisque vestibulum metus sed pretium consequat. Sed non quam faucibus, fringilla mi vel, porttitor metus.
    |
    |Nulla tortor est, dignissim nec orci sit amet, vulputate commodo libero. Integer gravida non turpis malesuada fermentum. Pellentesque sollicitudin sem sed lobortis elementum. Phasellus nec est metus. Integer id vehicula velit, sit amet scelerisque tortor. Nullam fermentum ultricies sodales. Duis vitae elementum diam, sit amet dictum nulla. Cras eu velit aliquam, venenatis neque posuere, sollicitudin eros. Phasellus nec enim quis dolor varius placerat sed id leo. Nam a leo volutpat, facilisis quam ac, consectetur neque. Morbi sagittis tincidunt urna sed ultricies. Nulla sollicitudin vitae augue ac ullamcorper. Phasellus fringilla tellus nisl, in mattis lorem sagittis at. Mauris sed turpis sed libero lobortis sollicitudin.
    |
    |Fusce non imperdiet ex. Integer nec risus quis magna maximus condimentum. Pellentesque facilisis fermentum massa eget aliquet. Etiam quis urna velit. Interdum et malesuada fames ac ante ipsum primis in faucibus. Donec commodo nibh ante, vitae ullamcorper quam facilisis vitae. Vestibulum mattis sed augue nec vulputate. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Integer non purus ut ligula semper aliquet. Nam varius id erat eu aliquam. Integer volutpat mattis mauris, nec ultrices metus vehicula sit amet. Cras vel risus et elit tempor pharetra. Fusce ac tortor cursus, ultrices mauris non, porta mauris. Pellentesque nisi diam, ullamcorper eget tincidunt eu, laoreet sit amet eros. Etiam ut tristique turpis. Vestibulum malesuada orci non feugiat blandit.
    |
    |Aliquam hendrerit laoreet odio, at laoreet arcu sollicitudin eget. Aliquam massa tortor, tempor eu pretium vel, sagittis bibendum libero. Ut feugiat justo vulputate velit ornare, sed volutpat ex sagittis. Donec semper, dui at tempus semper, lectus dolor iaculis enim, non bibendum odio ex at massa. Suspendisse sollicitudin aliquet ante, sed porta massa dictum ac. Curabitur fermentum fermentum lorem eget vehicula. In vulputate massa sed nulla efficitur interdum. Maecenas ac fermentum neque. Duis sed consectetur erat, ut venenatis nibh. Integer scelerisque leo at mollis consectetur.
    |
    |Morbi pretium, diam convallis commodo ullamcorper, sapien dui tempus dolor, non vehicula nisl diam vel tortor. Cras ac libero augue. Donec scelerisque purus et lectus egestas, quis molestie massa auctor. Donec vel commodo arcu. Donec non volutpat erat. Maecenas aliquam ex ut leo volutpat, tincidunt posuere magna consequat. Nullam in feugiat eros. Sed iaculis tristique sem nec imperdiet. Donec erat libero, aliquam id euismod vitae, rutrum sit amet diam. Proin ac lacinia lacus, id aliquet metus. Proin ultricies aliquet nulla, quis blandit diam sagittis sit amet. Morbi facilisis libero dolor, aliquam consectetur nisi consectetur et.
  """.stripMargin


val lines: Stream[String] = input2.split("[\\r\\n]+").toStream

/**
  * 
  * @param lines input String Stream
  * @param k     most top words 
  * @param n     process at max n lines
  * @return
  */
def topKWords(lines: Stream[String], k: Int, n: Int): List[(String, Int)] = {
  val tokenFreq: Map[String, Int] = lines
    .take(n)
    .flatMap(s => s.toLowerCase.split("\\W+"))
    .groupBy(w => w)
    .mapValues(_.length)
  
  val maxHeap: mutable.PriorityQueue[(String, Int)] = mutable.PriorityQueue[(String, Int)]()(Ordering.by(_._2)) ++ tokenFreq
  
  val lb = ListBuffer[(String, Int)]()
  
  (1 to Math.min(k, maxHeap.size)).foreach(_ => lb += maxHeap.dequeue())
  lb.toList
}

// note that input2 is "interlaced", 1 line empty and 1 with words
topKWords(lines, 5, 2) // List((non,3), (viverra,3), (dolor,3), (lorem,3), (quam,3))
topKWords(lines, 5, 20) // List((sed,13), (non,11), (ac,10), (sit,9), (amet,9))

top-k-words.sc

import scala.collection.mutable
import scala.collection.mutable.ListBuffer

val input = "One Ring to rule them all, One Ring to find them,\n" +
  "One Ring to bring them all and in the darkness bind them"

def topKwords(line: String, k: Int): List[(String, Int)] = {
  val tokenFreq = line.trim.toLowerCase.split("\\W+").groupBy(w => w).mapValues(_.length)
  val maxHeap = mutable.PriorityQueue[(String, Int)]()(Ordering.by(_._2)) ++ tokenFreq
  val lb = ListBuffer[(String, Int)]()

  (1 to Math.min(k, maxHeap.size)).foreach(_ => lb += maxHeap.dequeue())

  lb.toList
}

topKwords(input, 5) // List((them,4), (to,3), (one,3), (ring,3), (all,2))