Most frequent word in an array of strings - Java

Question

Input word array is
{ "geeks", "for", "geeks", "a", "portal", "to", "learn", "can", "be", "computer","science", "zoom", "yup", "fire", "in", "be", "data", "a", "portal","geeks" };

Problem is to find most frequent word in array. I want to find solution that can support on adding more element.

I have tried this code :-

package com.techiekunal.examples.datastructure;

import java.util.Iterator;
import java.util.PriorityQueue;

/**
 * MyWord objects will have word and its frequency
 * 
 * @author Kunal.Saxena
 *
 */
class MyWord implements Comparable<MyWord>{

    // word from array
    private String word;

    // word's frequency
    private int count;

    public MyWord(int count, String word) {
        this.count = count;
        this.word = word;
    }

    public String getWord() {
        return word;
    }

    public void setWord(String word) {
        this.word = word;
    }

    public int getCount() {
        return count;
    }

    public void setCount(int count) {
        this.count = count;
    }

    // Objects are equals if words are same
    @Override
    public boolean equals(Object obj) {
        if(obj == null)
            return false;
        if(this.getClass() != obj.getClass())
            return false;

        MyWord myWord = (MyWord) obj;
        return this.word.equals(myWord.word);
    }

    @Override
    public int hashCode() {
        return super.hashCode();
    }

    // Printing word and count against it
    @Override
    public String toString() {
        return this.word + " : " + this.count;
    }

    // comparison for descending order of count
    @Override
    public int compareTo(MyWord o) {
        if(this.count > o.count) {
            return -1;
        }
        if(this.count < o.count) {
            return 1;
        }
        return 0;
    }

}

public class MostFrequentUsedWords {

    // Input array
    private static String[] arr = { "geeks", "for", "geeks", "a", "portal", "to", "learn", "can", "be", "computer",
            "science", "zoom", "yup", "fire", "in", "be", "data", "a", "portal","geeks" };

    // Queue will work as max heap to store words
    private static PriorityQueue<MyWord> queue = new PriorityQueue<>();

    // Creating PriorityQueue from given input array
    private static void createQueue() {

        for (String word : arr) {
            // check if word already exists
            if (queue.contains(new MyWord(1, word))) {

                MyWord oldWord = null;
                // iterate to find word : we need latest frequency of that word
                Iterator<MyWord> itr = queue.iterator();
                while (itr.hasNext()) {

                    MyWord next = itr.next();
                    if (next.getWord().equals(word)) {
                        oldWord = next;
                    }
                }
                // create new word by incrementing frequency, remove old word from queue, adding new word to queue
                MyWord newWord = new MyWord(oldWord.getCount() + 1, oldWord.getWord());
                queue.remove(oldWord);
                queue.add(newWord);

            } else {
                // if word is not in queue : add it with frequency 1
                MyWord newWord = new MyWord(1, word);
                queue.add(newWord);
            }
        }

    }

    public static void main(String[] args) {

        // Create priority queue
        createQueue();

        // Print Queue
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }

}

My output is :-

geeks : 3
a : 2
portal : 2
be : 2
yup : 1
zoom : 1
science : 1
computer : 1
in : 1
can : 1
learn : 1
to : 1
data : 1
fire : 1
for : 1

---

I implemented this using priority queue and it is working fine. it is like creating max heap. But its complexity is n^2. Need help if this can be solve in less complex way.

Answer 1

As you noticed, searching for your entries is adding to your time complexity, because you have to run down your queue. Priority queues are very good at polling the top element, but not optimized for searching for specific entries.

You can optimize for searching by using a Map<String, Integer> for counting frequency, and then use a NavigableMap<Integer, Set<String>> for maintaining order ⁽¹⁾. Adding an entry will look like this:

NavigableMap<Integer, Set<String>> ordered;
Map<String, Integer> frequency;

void add(String word) {
  int count = frequency.getOrDefault(word, 0);
  if ( count > 0 ) {
    ordered.get(count).remove(word);
  }
  ordered.computeIfAbsent(count + 1, HashSet::new).add(word);
  frequency.put(word, count + 1);
}

(1) If you're confident about your data being densely distributed and bounded, you can replace this with an array for quicker access—approaching O(1) i.o. O(log N)—but it's going to make your code messier dealing with edge cases.

---

I do have two recommendations for your code.

When searching for an element in the queue, you can abort once it's found. On average, this will halve your time spent searching:

Iterator<MyWord> itr = queue.iterator();
while (itr.hasNext()) {
   MyWord next = itr.next();
   if (next.getWord().equals(word)) {
       oldWord = next;
       break;  // <-- found, abort search
   }
}

And a nitpick from an 'elegance' point of view: consider adding a method to MyWord that creates a new, incremented instance. Right now, outside code is accessing the fields and creating new instances with it. This is something MyWord can handle internally.

public MyWord incremented() {
    return new MyWord(count + 1, word);
}

Answer 2

Advice 1

Instead of rolling MyWord, you could use a Map<String, Integer> for counting the frequencies of each word.

Advice 2

@Override
public boolean equals(Object obj) {
    if(obj == null)
        return false;
    if(this.getClass() != obj.getClass())
        return false;

    MyWord myWord = (MyWord) obj;
    return this.word.equals(myWord.word);
}

I suggest you use { and } even if the block is a one-liner.

Opinion 1

@Override
public int hashCode() {
    return super.hashCode();
}

I believe a better hash might be simply

return word.hashCode();

or

return word.hashCode() ^ count;

Advice 3

@Override
public int compareTo(MyWord o) {
    if(this.count > o.count) {
        return -1;
    }
    if(this.count < o.count) {
        return 1;
    }
    return 0;
}

write simply

@Override
public int compareTo(MyWord o) {
    return Integer.compare(count, o.count);
}

Opinion 2

private static PriorityQueue<MyWord> queue = new PriorityQueue<>();
private static void createQueue() { ... }

I suggest you have a more dedicated method that uses the words as input, and returns a frequency map mentioned in the 1st advice.

Advice 4

createQueue looks a little bit overkill.

if (queue.contains(new MyWord(1, word))) { // Runs in worst-case linear time!
    MyWord oldWord = null;
    // iterate to find word : we need latest frequency of that word
    Iterator<MyWord> itr = queue.iterator();
    while (itr.hasNext()) {
        MyWord next = itr.next();
        if (next.getWord().equals(word)) {
            oldWord = next;
            // You could break here!
        }
    }
    MyWord newWord = new MyWord(oldWord.getCount() + 1, oldWord.getWord());
    queue.remove(oldWord); // Runs in worst-case linear time!
    queue.add(newWord);

Alternative implementation

package com.techiekunal.examples.datastructure;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public final class MostFrequentUsedWords2 {

    private MostFrequentUsedWords2() {
    }

    public static String[] sortWordsViaFrequencies(String[] words) {
        Map<String, Integer> frequencyMap = computeWordFrequencyMap(words);

        String[] uniqueWords = 
                frequencyMap.keySet().toArray(new String[frequencyMap.size()]);

        sortWordsUsingFrequencies(uniqueWords, frequencyMap);
        return uniqueWords;
    }

    private static Map<String, Integer> computeWordFrequencyMap(String[] words) {
        Map<String, Integer> result = new HashMap<>(words.length);

        for (String word : words) {
            result.put(word, result.getOrDefault(word, 0) + 1);
        }

        return result;
    }

    private static void sortWordsUsingFrequencies(String[] words,
            Map<String, Integer> frequencyMap) {
        Arrays.sort(words, new Comparator<String>() {

            @Override
            public int compare(String o1, String o2) {
                // Largest frequency first:
                return Integer.compare(frequencyMap.get(o2),
                        frequencyMap.get(o1));
            }
        });
    }

    public static void main(String[] args) {
        // Input array
        String[] arr = {"geeks", "for", "geeks", "a", "portal", "to", "learn",
                        "can", "be", "computer", "science", "zoom", "yup",
                        "fire", "in", "be", "data", "a", "portal", "geeks"};
        arr = sortWordsViaFrequencies(arr);
        System.out.println(Arrays.asList(arr));
    }
}

Answer 3

Current implementation

You can reduce the variable scope of your static variables by accepting the array input as parameter and returning the queue.
You are currently iterating the queue three times if the queue contains the word (contains, iterator loop, remove), this can be reduced to one iteration by only using the iterator.

private static PriorityQueue<MyWord> createQueue(String[] arr) {
    PriorityQueue<MyWord> queue = new PriorityQueue<>();
    for (String word : arr) {
        int previousCount = 0;
        for (Iterator<MyWord> it = queue.iterator(); it.hasNext();) {
            MyWord current = it.next();
            if (current.getWord().equals(word)) {
                it.remove();
                previousCount = current.getCount();
                break;
            }
        }
        queue.add(new MyWord(previousCount + 1, word));
    }
    return queue;
}

MyWord

Your equals/hashcode implementation is not conform with the specification of hashCode - equal objects can currently return different hash codes. The implementation of hashCode should return the hash code of word instead of super.hashCode().
The constructor performs no argument checks -> it is possible to create i.e. an instance with word==null, which will lead to NullPointerExceptions thrown by the equals method.
The compareTo method could return Integer.compare(o.count, count).

Alternative implementation

A priority queue is not a good data structure to determine the frequencies as you have to iterate the queue for each input element. You can use a Map to convert the input array to the frequencies with O(n) complexity (plus additional O(n log(n)) to sort the resulting frequencies, or O(n) to create a heap).

Using the stream api this could be written as:

Stream<MyWord> sortedByFrequency = Stream.of(arr).collect(groupingBy(identity(), counting()))
        .entrySet().stream().map(e -> new MyWord(e.getValue().intValue(), e.getKey())).sorted();

As sorting by frequency works for every input type and not only strings, I would use a parameterized class instead of MyWord to support all types.

Possible implementation:

private static final Occurrence<?>[] EMPTY = new Occurrence[0];

@SafeVarargs
public static <T> Occurrence<T>[] sortedByFrequency(T... values) {
    Map<T, Occurrence<T>> frequencies = new HashMap<>();
    for (T t : values)
        frequencies.computeIfAbsent(t, Occurrence::new).frequency++;
    @SuppressWarnings("unchecked")
    Occurrence<T>[] result = frequencies.values().toArray((Occurrence<T>[]) EMPTY);
    Arrays.sort(result, comparingInt(t -> ~t.frequency));
    return result;
}

public static final class Occurrence<T> {

    private final T value;
    int frequency;

    Occurrence(T value) {
        this.value = value;
    }

    public T value() {
        return value;
    }

    public int frequency() {
        return frequency;
    }

    @Override
    public String toString() {
        return value + "[" + frequency + "]";
    }
}

Which can be simplified if only the first element is needed:

@SafeVarargs
public static <T> T mostFrequent(T... values) {
    class Counter { int c; }
    Map<T, Counter> frequencies = new HashMap<>();
    T val = null;
    int max = 0;
    for (T t : values) {
        if (++frequencies.computeIfAbsent(t, u -> new Counter()).c > max) {
            max++;
            val = t;
        }
    }
    return val;
}

Answer 4

Naming: MyWord is weak - it has a doc comment (way to go) suggesting WordWithFrequency or CountedWord.

Contracts: MyWord.compareTo() doesn't follow Comparable.compareTo()'s "strong recommendation" to document the inconsistency with equals() (I do that on both class and method).
MyWord.hashCode(): could be different for mw1 and mw2 with mw1.equals(mw2). I suggest return word.hashCode();.

Tactics:
// create new word by incrementing frequency, remove old word from queue, adding new word to queue
What do you need a new word for? Just remove the one found, up its count, and re-insert.
(If this was the second time to manipulate count, this would be an opportunity to re-think CountedWord's interface: perhaps increment() or increment(int amount) would be more useful than setCount().)
iterate to find word and next remove it…
Don't write naked code - use a foreach loop, or streams.
Here, newWord = new MyWord(1, word); oldWord = queue.remove(newWord); should do. (Proper handling of null == oldWord obviates the contains())

Source organisation:
I'd make arr a parameter to createQueue() - which doesn't lend itself to dynamic/incremental use. tally(String[] words), invoked/invocable more than once, would seem better.

Strategy: Try to make do with run-time supplied classes.
You stated that you want to be able to query which words are most frequent "dynamically".
Imagine keeping Sets of words, one for each count. For each word, remove from current Set (if any) and insert into set of words occurring once more frequently.
With standard Sets - say, HashSets, keep a "global" set of your CountedWords to determine the count.
Set up a test scaffold to get your approach working.
Benchmark some to get an idea of resource usage.
If and only if not acceptable, set and document an improvement goal and use your "first" approach as a baseline.

Stressing fast What is most frequent? queries
(and using a Map instead of CountedWord):

/** Keep count of how often each <code>T</code> is added.<br/>
 * Iterates in order of decreasing "add count".<br/>
 * <code>mostFrequent()</code> gets a set of the <code>T</code>s
 * added most frequently
 */// add-only MultiSet<T> with PriorityQueue<T> on occurrence
   // -Spliterator +priority value query
public class MostFrequent<T> 
    extends java.util.AbstractCollection<T> {
 // interface, sort of
    @Override
    public boolean add(T e) {
        int count = occurs.merge(e,
            BigInteger.ONE, BigInteger::add).intValue();
        bins.get(count-1).remove(e);
        if (bins.size() <= count)
            bins.add(new HashSet<>(Collections.singleton(e)));
        else
            bins.get(count).add(e);
        return count <= 1;
    }

 /** tally elements */
    public void tally(T[] elements ) { addAll(Arrays.asList(elements)); }

 /** @return how many times <code>e</code>
  *  has been <code>add()</code>ed */
    public int count(T e) {
        // return occurs.getOrDefault(e, BigInteger.ZERO).intValue();
        Number count = occurs.get(e);
        return null == count ? 0 : count.intValue();
    }
 /** Gets most frequent elements. */
    public Set<T> mostFrequent() {
        return Collections.unmodifiableSet(
            bins.get(bins.size() - 1));
    }

 // implementation
    private java.util.Map<T, BigInteger>
        occurs = new java.util.HashMap<>();
    java.util.List<Set<T>> bins = new java.util.ArrayList<>();
    { bins.add(Collections.EMPTY_SET); }

 /** Iterator for MostFrequent:
  *  in order of decreasing occurrence count.<br/>
  *  No support re. <code>ConcurrentModification<code> (yet). */
    class Itor implements Iterator<T> {
        java.util.ListIterator<? extends java.util.Collection<T>>
        iter = bins.listIterator(bins.size());
        Iterator<T> it = Collections.EMPTY_SET.iterator();
        @Override
        public boolean hasNext() {
            while (!it.hasNext() && iter.hasPrevious())
                it = iter.previous().iterator();
            return it.hasNext();
        }
        @Override
        public T next() {
            if (!hasNext())
                throw new NoSuchElementException();
            return it.next();
        }
    }
    @Override
    public Iterator<T> iterator() { return new Itor(); }

    @Override
    public int size() { return occurs.size(); }
}

class MostFrequentWords
    extends MostFrequent<String> { 
    // Input array
    private static String[] arr = { "geeks", "for", "geeks", "a",
        "portal", "to", "learn", "can", "be", "computer",
            "science", "zoom", "yup", "fire", "in", "be", "data",
            "a", "portal","geeks" };
    public static void main(String[] args) {
        MostFrequentWords me = new MostFrequentWords();
        me.tally(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println(me.bins.get(me.bins.size()-1));
    // Print Queue
        System.out.println(me);
        me.tally(new String[] { "a", "a", "geeks"});
        System.out.println(-1+me.bins.size() + ": "
            + me.mostFrequent());
    }
}