Memory efficient algorithm to build word occurrence index of a huge text file in C++

Question

I have to write a program that reads a huge file with with operator>>, count things and then insert the whole in multimap.

It works perfectly with small files but with big files the program runs out of memory. It throws a bad_alloc on Windows 32-bit.

I made a 64-bit build on Windows (in order to avoid the memory allocation limit for 32-bit programs on Windows), opened the task manager and what I see is that the memory is increasing continually, and when the RAM is full the program crashes. Do you know how to deal with this ?

Here is the code :

#include <iostream>
#include <string>
#include <fstream>
#include <unordered_map>

using namespace std;

int main()
{
    ifstream fin("C:/text.txt");
    string const outfile("C:/out/out.txt");
    ofstream fout (outfile.c_str());
    string word;
    unordered_multimap<string, int> mymm;
    int intnum = 0;

    while(fin >> word)
    {
        mymm.insert(pair<string, int>(word, intnum));
        ++intnum;
    }

    return 0;
}

You might try to decrease the size of your objects, for example by using fixed-length char arrays instead of std::strings. — Bas in het Veld, Mar 25 '15 at 09:04
what is a huge file ? You don't expect the be able to load a file that is say 20gig in size if you computer does not have that amount of memory ? — Philip Stuyck, Mar 25 '15 at 09:06
Possible duplicate: http://stackoverflow.com/q/29229492/596781 — Kerrek SB, Mar 25 '15 at 09:07
If the strings are large and you're just building a one-way index then consider storing a hash in the map instead of the actual string. — Andy Brown, Mar 25 '15 at 09:10
It's not an issue as such. Your algorithm works correctly, it's just not adequate for the data set. How many unique strings do you expect to have and how many lines in total? — bobah, Mar 25 '15 at 09:11
@KerrekSB - what's your rationale behind the conceptual tip? — bobah, Mar 25 '15 at 10:24
@nwellnhof: Well... counting should [start at zero](http://stackoverflow.com/questions/9963401/why-are-standard-iterator-ranges-begin-end-instead-of-begin-end/9963438#9963438) :-) — Kerrek SB, Mar 25 '15 at 11:27

bobah · Answer 1 · 2015-03-25T10:42:53.803

Modification of divide&conquer will do here:

Dump the map to a file (new file each time) after N lines and clear it. As a side effect you know total number of lines in the file.
Load one file at a time and concatenate all values for keys starting from "a"-"d" into a map. Once all pass-1 files are processed, repeat for "e"-"k", and so on.
You have persistent version of the required map segmented in files ad, ek, ... so if you know the key you can open respective file and find the respective key-values pair (file is sorted so search is logN). Problem solved.

size_t line_number = 0; size_t const fragment_size = 1ul << 19; sorted_index_t segmented_partial_index; // key -> (pos1, pos2, ...) while (fin >> word) { partial_index[key].append(++line_number); // syntax may vary depending on index_t type

    if (!(line_number % fragment_size)) {
        dump_partial_index("segmented/", partial_index);
        segmented_partial_index.clear();
    }

}

if (line_number % fragment_size) {
    dump_partial_index("segmented/", partial_index);
    segmented_partial_index.clear();
}

index_t alphabetical_partial_index;
for (auto range: {"ad", "ek", "lr", "sz"}) {
    for (auto name: partial_index_filenames) {
        // the below loop can be optimized from N to log(N) if needed
        load_partial_index("segmented/", name, segmented_partial_index);
        for (auto x: segmented_partial_index) {
            if (x.first[0] < range[0]) continue;
            if (x.first[0] > range[1]) break;
            alphabetical_partial_index[x.first] += x.second;
        }
    }
    dump_partial_index("alphabetical/", alphabetical_partial_index);
    segmented_partial_index.clear();
    alphabetical_partial_index.clear();
}

Memory efficient algorithm to build word occurrence index of a huge text file in C++

1 Answers1