Find the 'n' most repeating words/strings in a huge file that does not fit in memory

algorithm

Solution

There's no need to sort the files ahead of time. Doing so is just a bunch of unnecessary I/O.

A more straightforward way to do this is:

Create an empty dictionary (hash map), keyed by word. The value is the count.
for each file
    while not end of file
        read word
        if word in dictionary
            update count
        else
            if dictionary full
                sort dictionary by word
                output dictionary to temporary file
                Clear dictionary
            Add word to dictionary, with count 1
    end
end
if dictionary not empty
    sort dictionary by word
    output dictionary to temporary file

You now have some number of temporary files, each sorted by word and containing one word/count pair per line. Like:

aardvark,12
bozo,3
zebra,5

Create a min-heap that you will use to hold your n largest items. Call it `largest_items`.

Do a standard n-way merge of those temporary files. As you find each unique item (i.e. you merge all of the "aardvark" entries across the multiple files), you do this:

if (largest_items.count < n)
    largest_items.add(word)
else if (word.count > largest_items.peek().count)
{
    // the count for this word is more than the smallest count
    // already on the heap. So remove the item with the
    // smallest count, and add this one.
    largest_items.remove_root()
    largest_items.add(word)
}

Complexity:

- Building the dictionaries is O(N), where `N` is the total number of individual words in the file.

- Sorting each temporary dictionary is O(k log k), where 'k' is the number of words in the dictionary.

- Writing each temporary dictionary is O(k)

- The merge is O(M log x), where `M` is the combined number of entries across all the temporary files, and `x` is the number of temporary files.

- Selecting the items is O(m log n), where `m` is the number of unique words, and `n` is the number of words you want to select.

If you look at worst case behavior (i.e. all the words are unique), the complexity works out to (`n` is the total number of words):

- Building the dictionaries is O(n)

- Sorting and writing the temporary files is `(n/m) * (m log m)`, where `m` is the dictionary size.

- The merge is `n log (n/m)`.

- Selection is O(m + (k log k)), where `k` is the number of words you want to select and `m` is the number of unique words. Because all words are unique they have the same count, so you'll only do `k` inserts into the heap. The `m` term dominates when `k` is much smaller than `m` (which is usually the case in these situations). So selection turns out to be O(m).

When you're working with data sets larger than memory, very often your bottleneck is file I/O. The algorithm I've outlined above tries to minimize the I/O. In the worst case (all words are unique), each word will be read twice and written once. But in the general case each word is read once and then each hash page is written once and read once. Plus, your sorts are on hash pages rather than raw words, and the total size of your temporary files will be much smaller than the original text.

Problem

Original source

Related problems

• Algorithm for N-way merge