Easiest Way to Sort a List of Words by Occurance

Question

What is the best/easiest way to sort a large list of words (10,000-20,000) by the number of times they occur in the list, in Java. I tried a basic implementation but I get an out of memory runtime error, so I need a more efficient way. What would you suggest?

ArrayList<String> occuringWords = new ArrayList<String>();
    ArrayList<Integer> numberOccur = new ArrayList<Integer>();
    String temp;
    int count;
    for(int i = 0; i < finalWords.size(); i++){
        temp = finalWords.get(i);
        count = 0;
        for(int j = 0; j < finalWords.size(); j++){
            if(temp.equals(finalWords.get(j))){
            count++;
            finalWords.remove(j);
            j--;
            }
        }
        if(numberOccur.size() == 0){
            numberOccur.add(count);
            occuringWords.add(temp);
        }else{
            for(int j = 0; j < numberOccur.size(); j++){
            if(count>numberOccur.get(j)){
                numberOccur.add(j, count);
                occuringWords.add(j, temp);
            }
        }
    }
}

Where finalWords is the list of all of the Strings. I had to store the number of times each word occured in a separate arraylist because I couldn't think of a better way to keep them paired without making each word a separate object.

Answer 1

Build a HashMap<String, Integer> mapping words to the number of occurrences. The first time you see a word add it to the map and set the count to 1. Every time thereafter if the word already exists in the map increment the count.

This will be much faster since you will only have to iterate over the list of words once. It's the difference between O(n) and O(n²), which for a large dictionary will be a tremendous difference.

At the end you can then take the list of words and sort them by count. You'll have to take them out of the map and add them to a separate data structure to do this. (Hint: you could use a TreeSet with a custom Comparator which compares words based on their frequency. Or, less elegantly, add them to a List and then sort that list, again with a custom Comparator.)

Answer 2

The Multiset is what you are looking from google collections. That data structure is exactly built to support your use cases. All you need to do is populate it with your words. It will maintain the frequency for you

Answer 3

Why all so complicated? You need basically the following:

1. Sort the words in-place. The same words will be grouped now.
2. Go through the array, counting duplicates and store the resulting pairs (word, number of occurrences) in other array
3. Sort the other array by number of occurrences.

The complexity is O(n log n).

Answer 4

Have you considered using String interning in addition to a hashmap? String interning means all same Strings use the same memory location in order to save memory. Based on an answer Sort a Map<Key, Value> by values (Java) please see below:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.TreeMap;
public class WordOccurSortExample {

public static void main(String[] args) {
        new  WordOccurSortExample();        
}

public WordOccurSortExample()
{
    ArrayList<String> occuringWords = new ArrayList<String>();
    occuringWords.add("Menios".intern());
    occuringWords.add("Menios".intern());
    occuringWords.add("Menios".intern());
    occuringWords.add("Menios".intern());
    occuringWords.add("Moo".intern());
    occuringWords.add("Moo".intern());
    occuringWords.add("Moo".intern());
    occuringWords.add("Moo".intern());
    occuringWords.add("Moo".intern());
    occuringWords.add("Boo".intern());
    occuringWords.add("Boo".intern());
    occuringWords.add("Boo".intern());

    HashMap<String, Integer> occurances = new HashMap<String, Integer>();

    Iterator<String> it = occuringWords.iterator();
    String word;
    Integer count;
    while(it.hasNext())
    {
        word = it.next();

        if((count = occurances.get(word))==null)
        occurances.put(word, 1);
        else
        occurances.put(word, new Integer(count+1)); 
    }       

    ValueComparator bvc =  new ValueComparator(occurances);
    TreeMap<String,Integer> sorted_map = new TreeMap<String,Integer>(bvc);

    System.out.println("unsorted map: "+occuringWords);
    sorted_map.putAll(occurances);
    System.out.println("results: "+sorted_map);
}


class ValueComparator implements Comparator<String> {

    HashMap<String, Integer> base;
    public ValueComparator(HashMap<String, Integer> base) {
        this.base = base;
    }

    // Note: this comparator imposes orderings that are inconsistent with equals.    
    public int compare(String a, String b) {
        if (base.get(a) >= base.get(b)) {
            return -1;
        } else {
            return 1;
        } // returning 0 would merge keys
    }

}

}

Answer 5

public List<String> countOccurences(ArrayList<String> list){
  HashMap<String, Integer> hm = new HashMap<String, Integer>();
  for (String s:list) {
     Integer i = hm.get(s);
     if (i == null){
      i = 0; 
     } 
     i++;

     hm.put(s, i);
  }


  List<String> mapKeys = new ArrayList<String>(hm.keySet());
  List<Integer> mapValues = new ArrayList<Integer>(hm.values());
  HashMap<String, Integer> sortedMap = new LinkedHashMap<String, Integer>();
  TreeSet<Integer> sortedSet = new TreeSet<Integer>(mapValues);
  Object[] sortedArray = sortedSet.toArray();
  int size = sortedArray.length;
  for (int i=0; i<size; i++){
     sortedMap.put(mapKeys.get(mapValues.indexOf(sortedArray[i])), 
                  (Double)sortedArray[i]);
  }
  return new ArrayList<String>(sorted.keyset());

}

Answer 6

THe easiest way to sort your words is alphabetically. But you can also do it by how many letters that word has that exist in another word.