1

I have a source of strings (let us say, a text file) and many strings repeat multiple times. I need to get the top X most common strings in the order of decreasing number of occurrences.

The idea that came to mind first was to create a sortable Bag (something like org.apache.commons.collections.bag.TreeBag) and supply a comparator that will sort the entries in the order I need. However, I cannot figure out what is the type of objects I need to compare. It should be some kind of an internal map that combines my object (String) and the number of occurrences, generated internally by TreeBag. Is this possible?

Or would I be better off by simply using a hashmap and sort it by value as described in, for example, Java sort HashMap by value

Community
  • 1
  • 1
AlexR
  • 240
  • 1
  • 11

2 Answers2

0

Why don't you put the strings in a map. Map of string to number of times they appear in text. In step 2, traverse the items in the map and keep on adding them to a minimum heap of size X. Always extract min first if the heap is full before inserting.
Takes nlogx time.

Otherwise after step 1 sort the items by number of occurrences and take first x items. A tree map would come in helpful here :) (I'd add a link to the javadocs, but I'm in a tablet ) Takes nlogn time.

Adrian
  • 5,603
  • 8
  • 53
  • 85
  • 1
    Thank you Adrian. I ended up implementing it as a sortable hashmap, but heap is a nice idea - next time I'll look into something like PriorityQueue with custom comparator. – AlexR Mar 24 '12 at 04:01
0

With Guava's TreeMultiset, just use Multisets.copyHighestCountFirst.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413