Basic algorithm:
- Open document/huge text file
- Use
Map
andList
to separate the words. \$O(K)\$ time complexity (TC) considering \$K\$ distinct words. - If the word already exists in the list, increment the count of frequency, else add the new word. Constant TC.
- Use a
Collection
to sort the list on the basis of frequency of usage. \$n*log(n)\$ TC. - Print the list,
Entry.getKey
(max count word), and itsEntry.getValue
(max count).
Now, I tried to use Multimap
before sorting so that I can group same frequency count words. This will drastically decrease the sorting complexity as the number of elements to compare will decrease.
Is it efficient enough or are there other ways to make it more efficient?
//Below code works fine (Please include lib files as per your IDE setting)
package Topk;
//---import necessary lib---
class Words
{
int count=1;
String word;
Words(int count, String word)
{
this.count = count;
this.word = word;
}
}
public class TopK
{
public static void main(String argv[]) throws IOException
{
int Tcount = 0;
Map<String,Integer> map = new TreeMap<String,Integer>();
BufferedReader br = new BufferedReader(new FileReader("text.txt"));
String line;
while((line = br.readLine())!=null)
{
String[] words = line.split("\\W");
for(String word:words)
{
word = word.toLowerCase();
Tcount++;
if(word.equals(""))
continue;
insert(word,map);
}
}
Multimap<Integer, String> mm = ArrayListMultimap.create();
Iterator<String> itr = map.keySet().iterator();
while(itr.hasNext())
{
String key = (String) itr.next();
int tempi = map.get(key);
String temps = key;
mm.put(tempi,temps);
}
Map<String,Integer> fmap = new HashMap<String,Integer>();
Set<Integer> keys = mm.keySet();
for(int i : keys)
{
int value = i;
String temps = (mm.get(i).toString());
fmap.put(temps,value);
}
List<Entry<String, Integer>> wordList = sorting(fmap);
display(wordList,Tcount);
br.close();
}
// INSERTING INTO THE MAP////////////////////////////////////////////////////////////////////////////////////////////////
private static void insert(String word, Map<String, Integer> map)
{
if(map.containsKey(word))
{
int temp = map.get(word);
temp++;
map.put(word, temp);
}
else
map.put(word, 1);
}
// SORTING METHOD/////////////////////////////////////////////////////////////////////////////////////////////////////////
private static List<Entry<String, Integer>> sorting(Map<String, Integer> fmap)
{
Set<Entry<String, Integer>> wordSet = fmap.entrySet();
List<Entry<String, Integer>> wordList = new ArrayList<Entry<String, Integer>>(wordSet);
Collections.sort(
wordList,
new Comparator<Map.Entry<String, Integer>>()
{
public int compare( Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2 )
{
return (o2.getValue()).compareTo( o1.getValue() );
}
}
);
return wordList;
}
// DISPLAY METHOD/////////////////////////////////////////////////////////////////////////////////////////////////////////
private static void display(List<Entry<String, Integer>> wordList, int tcount)
{
// Display all the words & count ---------------------------------------------------------------------------------------
for(Map.Entry<String, Integer> entry:wordList) // for every word search the frequency
{
System.out.println(entry.getValue()+": "+entry.getKey());
}
// Top frequently used word --------------------------------------------------------------------------------------------
Entry<String, Integer> max = wordList.get(0);
System.out.println("-------------------------------------------------------------------------------------------");
System.out.println("Total words : "+tcount);
System.out.println("Maximum frueqncy word - "+ max.getKey()+" : "+max.getValue()+" times.");
System.out.println("-------------------------------------------------------------------------------------------");
}
}