Find most occurring word in a txt file

Question

Assume that we have a .txt file that has one word per line. Find out the word that occurs the most.

Here's what I was able to write (I used array of strings instead of a file in this example):

string[] source = { "test1", "test2", "test3", "test4", "test1", "test1", "test3" };
Dictionary<string, int> dic = source.Distinct().ToDictionary(p => p, p => 0);
var keys = new List<string>(dic.Keys);
foreach (string key in keys)
{
  dic[key]=source.Count(f => f == key);
}
int max = dic.Values.Max();
foreach (KeyValuePair<string, int> kvp in dic)
{
    if (kvp.Value == max)
    {
        Console.WriteLine(kvp.Key + " " + max);
        break;
    }
}

Questions:

1. Can this be done better and more efficient way (speed/ memory)?
2. What if file size is 10GB. How would you do it differently from my approach?

Answer 1

You are trying to count each key separately. This means you need to iterate through the entire list to count each key. Instead you can keep a running total of your key's and only have to iterate through your list once:

string[] source = { "test1", "test2", "test3", "test4", "test1", "test1", "test3" };
Dictionary<string, int> dic = new Dictionary<string, int>();

foreach(string s in source){
    if(dic.Keys.Contains(s))
         dic[s] = dic[s]++;
    else
       dic.Add(s, 1);
}

EDIT: I did not include getting the max value as what you have works for that and has already been re-written by thantos

Answer 2

I wrote this little business back in 2009. It counts unique words in a file (separated by certain delimiters) and spits them out in frequency order, highest to lowest.

    private static readonly char[] delimiters = { ' ', '.', ',', ';', '\'', '-', ':', '!', '?', '(', ')', '<', '>', '=', '*', '/', '[', ']', '{', '}', '\\', '"', '\r', '\n' };

    private static readonly Func<string, string> theWord = Word;

    private static readonly Func<IGrouping<string, string>, KeyValuePair<string, int>> theNewWordCount =
        NewWordCount;

    private static readonly Func<KeyValuePair<string, int>, int> theCount = Count;

    private static void Main(string[] args)
    {
        foreach (var wordCount in File.ReadAllText(args.Length > 0 ? args[0] : @"C:\Test\WarAndPeace.txt")
            .Split(delimiters, StringSplitOptions.RemoveEmptyEntries)
            .AsParallel()
            .GroupBy(theWord, StringComparer.OrdinalIgnoreCase)
            .Select(theNewWordCount)
            .OrderByDescending(theCount))
        {
            Console.WriteLine(
                "Word: \""
                + wordCount.Key
                + "\" Count: "
                + wordCount.Value);
        }

        Console.ReadLine();
    }

    private static string Word(string word)
    {
        return word;
    }

    private static KeyValuePair<string, int> NewWordCount(IGrouping<string, string> wordCount)
    {
        return new KeyValuePair<string, int>(wordCount.Key, wordCount.Count());
    }

    private static int Count(KeyValuePair<string, int> wordCount)
    {
        return wordCount.Value;
    }

Answer 3

I think it is worth mentioning that for large data a different approach could be used, since keeping exact frequency counts of words is too time consuming.

Streaming Algorithms like "Count Sketch" makes a single pass over the data, uses low amount of space, and based on the amount of space you allocate to it, can guarantee to get the Maximum Frequency Word with say 99% probability.

Algorithms like these are used every day in routers to approximate which IP addresses are requested the most frequently, given that routers do not have enough memory to store everything it sees and only sees each IP address once.

For large data, I would recommend this approach.

Not sure if 10 GB of text counts as big data for this problem though, however if every word in the file was unique (except one word which occurs twice), you probably don't want to try storing them all in a Dictionary :p.

As an aside,

Multi-threading may be able to help give a speed-up, although pulling data from a single .txt file seems intrinsically IO bound. It seems possible to pre-partition the .txt file into parts for each thread to process independently, using "unsafe" code with pointers directly at the partition locations in memory, and writing the line parsing yourself from the bit representations of chars.

I doubt the above would be worth doing in C#, since you might as well manage memory as well using C or another low-level language for that extra gain in speed-up.

Multiple threads would exhibit higher speed-ups on certain processors like the intel i7 which has 3 channels to memory, and this is a highly IO dependent task.

If it happened to be hundreds of thousands of 10 GB .txt files across a cluster of computers, I would consider using an approach utilizing MapReduce on a distributed file system.

Answer 4

Can this be done better and more efficient way (speed/ memory)?

Your code iterates once over the input, Distinct internally creates a set, of which you then create a dictionary (redundant work).

You then copy the keys of the dictionary to a list to iterate over them (redundant work).

You then iterate over all keys, and for each, iterate over the input again (redundant work).

Then you iterate over the dictionary again (redundant work).

This code has almost more redundant operations than lines.

This can be vastly simplified, both conceptually and concerning runtime. Unfortunately, the resulting code will be slightly longer and still contain one redundancy since C#’s dictionary implementation has a fatal error in its interface: it doesn’t allow querying and updating a value at the same time.

string[] source = { "test1", "test2", "test3", "test4", "test1", "test1", "test3" };

var frequencies = new Dictionary<string, int>();
string highestWord = null;
int highestFreq = 0;

foreach (string word in source) {
    int freq;
    frequencies.TryGetValue(word, out freq);
    freq += 1;

    if (freq > highestFreq) {
        highestFreq = freq;
        highestWord = word;
    }
    frequencies[word] = freq;
}

Console.WriteLine(highestWord);

What if file size is 10GB. How would you do it differently from my approach?

If you expect comparably few different word (say, less than 100.000), use the same approach as above, just don’t load the whole input at once, instead, do it in chunks. You can also process chunks in parallel, with each thread working on its own dictionary, and afterwards you merge those dictionaries in one final step.

If you expect that almost every word in the input is distinct (not realistic with natural language words, but if your “words” are generated strings, this could happen) then the frequency dictionary could become quite large in size and might require special treatment. But this is an extreme scenario.

Answer 5

You could use a collection type which is called Bag. A bag counts the items added to it. Here is a suggestion of how a bag can be implemented. (It is not necessarily feature-complete; however you get the idea.)

public class Bag<T>
{
    private Dictionary<T, int> _dict = new Dictionary<T, int>();

    public void Add(T item)
    {
        int count;
        if (_dict.TryGetValue(item, out count)) {
            _dict[item] = count + 1;
        } else {
            _dict.Add(item, 1);
        }
    }

    public bool Remove(T item)
    {
        int count;
        if (_dict.TryGetValue(item, out count)) {
            if (count == 1) {
                _dict.Remove(item);
            } else {
                _dict[item] = count - 1;
            }
            return true;
        }
        return false;
    }

    public IEnumerator<KeyValuePair<T, int>> GetEnumerator()
    {
        return _dict.GetEnumerator();
    }

    public int CountOf(T item)
    {
        int count;
        _dict.TryGetValue(item, out count);
        return count;
    }
}