Calculating cooccurrence probabilities for pairs of words in a document

Question

It is a 1.5 hour coding test, started the moment when the question was sent by email. My solution was done under the strict condition. I was not told anything before the test.

The question is about counting word occurrence in natural language processing. Paraphrased, it asks:

Given an input document and a range k (with 1 ≤ k ≤ 5), calculate all cooccurrence probabilities for various pairs of words A and B:

$$ p(A, B, k) = \frac{\textit{cooccurrence(A, B, k)}}{\textit{count}(A)} $$

In other words, out of every time the word A appears, what is the probability that B appears within ±k words?

My solution in C++ is below. I think I could do better in my attempt. What are the areas that I should prepare & learn? I failed to come up with a better data structure under the exam condition.

During the test, I briefly tried stack but later found out I couldn't iterate all elements without changing the data structure. That wasted my time and I wonder if a stack can be used?

#include <set>
#include <map>
#include <stack>
#include <vector>
#include <fstream>
#include <sstream>
#include <iostream>
#include <boost/algorithm/string.hpp>
#include <boost/algorithm/string/predicate.hpp>

int main(int argc, char* argv[])
{
    const auto file = argv[0];
    const auto K = atoi(argv[1]);

    std::string line;

    // Mapping for coocurrence
    std::map<std::pair<std::string, std::string>, unsigned> coo;

    std::map<std::string, unsigned> count;

    // History of the last K words
    std::vector<std::string> hist;

    std::ifstream ss(file);

    while (std::getline(ss, line))
    {
        std::vector<std::string> toks;
        boost::split(toks, line, boost::is_any_of(" "));

        for (auto &tok : toks)
        {
            boost::replace_all(tok, ",", "");
            boost::replace_all(tok, ".", "");
            boost::replace_all(tok, "!", "");
            std::transform(tok.begin(), tok.end(), tok.begin(), ::tolower);

            if (tok == "\t" || tok == "," || tok == "")
            {
                continue;
            }

            // Required for dennominator
            count[tok]++;

            std::set<std::string> known;

            // Checking the last K history
            for (auto &i : hist)
            {
                if (!known.count(i))
                {
                    coo[std::pair<std::string, std::string>(tok, i)]++;
                    //coo[std::pair<std::string, std::string>(i, tok)]++;
                }

                known.insert(i);
            }

            if (hist.size() != K)
            {
                hist.push_back(tok);
            }
            else
            {
                /*
                 * Reconstruct the history of recent words
                 */

                for (auto i = 0; i < hist.size()-1; i++)
                {
                    hist[i] = hist[i+1];
                }

                hist[hist.size()-1] = tok;
            }
        }
    }

    std::vector<std::string> toks;
    boost::split(toks, line, boost::is_any_of(" "));

    for (std::string line; std::getline(std::cin, line);)
    {
        std::vector<std::string> toks;
        boost::split(toks, line, boost::is_any_of(" "));

        std::string x1 = toks[0];
        std::string y1 = toks[1];
        std::transform(x1.begin(), x1.end(), x1.begin(), ::tolower);
        std::transform(y1.begin(), y1.end(), y1.begin(), ::tolower);

        if (!count.count(x1))
        {
            return 0;
        }

        const auto den = count.at(x1);
        auto num1 = coo.count(std::pair<std::string, std::string>(x1, y1)) ? coo.at(std::pair<std::string, std::string>(x1, y1)) : 0;
        auto num2 = coo.count(std::pair<std::string, std::string>(y1, x1)) ? coo.at(std::pair<std::string, std::string>(y1, x1)) : 0;

        if (x1 == y1)
        {
            num1++;
            num2++;
        }

        std::cout << (double)(std::max(num1, num2)) / den << std::endl;
    }
}

Answer 1

You have used a std::vector<std::string> for hist, a history of the last K words. To limit that vector to size K, you shift the words over like this:

    if (hist.size() != K)
    {
        hist.push_back(tok);
    }
    else
    {
        /*
         * Reconstruct the history of recent words
         */

        for (auto i = 0; i < hist.size()-1; i++)
        {
            hist[i] = hist[i+1];
        }

        hist[hist.size()-1] = tok;
    }

But that loop is essentially doing erase() on the first element — and, as you can see, it's an inefficient O(K) operation on a vector.

A std::deque would be an improvement:

std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. … As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.

That non-contiguous caveat is a bit of a disappointment, though. Since you want a bounded-size buffer where adding an entry at the end causes the first entry to drop out, the data structure that you really want is a circular-list. As luck would have it, Boost has a circular buffer.

Answer 2

#include <set>
#include <map>
#include <stack>
#include <vector>
#include <fstream>
#include <sstream>
#include <iostream>
#include <boost/algorithm/string.hpp>
#include <boost/algorithm/string/predicate.hpp>

Each file should be self-sufficient by including the specific header a symbol relies on. You forgot to remove the <sstream> and <stack> artifacts. You are missing:

#include <algorithm>  // std::transform
#include <cstdlib>    // std::atoi
#include <string>     // std::string<>
#include <utility>    // std::pair<>

Prefer to organize your headers in logical groups. A common logical ordering would be by ascending hardiness. Code that isn't as rigorously tested is processed before other libraries that are better tested.

When searching a list of includes, binary search is faster than linear search. so prefer to order lexicographically.

#include "class.h"            // Prototype/Interface

#include "range/algorithm.h"  // Project-Level libraries
#include "utils/string.h"

#include <boost/algorithm/string.hpp>  // Third-Party Libraries
#include <boost/algorithm/string/predicate.hpp>

#include <algorithm>          // Standard Library
#include <cstdlib>
// ...
#include <vector>

---

int main(int argc, char* argv[]) {
    const auto file = argv[0];
    const auto K = atoi(argv[1]);

Always check argc before accessing argv. argc is only guaranteed by the standard to be non-negative, not non-zero. argv[0] is also special.

3.6.1 Main function [basic.start.main]

\$^2\$ ... If argc is nonzero these arguments shall be supplied in argv[0] through argv[argc-1] as pointers to the initial characters of null-terminated multibyte strings (NTMBSs) (17.5.2.1.4.2) and argv[0] shall be the pointer to the initial character of a NTMBS that represents the name used to invoke the program or "".

---

    // Mapping for coocurrence
    std::map<std::pair<std::string, std::string>, unsigned> coo;

Don't say in comments what can be stated in code. Keep code-related comments minimal and crisp. When something is important and not obvious (unusual/obscure code), clarify through a comment.

Don't pay for what you don't use. Unless you require that keys be sorted at all times, prefer using std::unordered_[map|set].

---

    std::ifstream ss(file);

Give variables appropriate names. ss doesn't give the reader an idea of what the variable is holding.

---

    while (std::getline(ss, line)) {
        std::vector<std::string> toks;
        boost::split(toks, line, boost::is_any_of(" "));

std::string::operator>> already delimits on whitespace.

---

        boost::replace_all(tok, ",", "");
        boost::replace_all(tok, ".", "");
        boost::replace_all(tok, "!", "");

This is probably not the intended purpose of boost::replace_all as copies and buffers are used in the background to handle resizing. You could just use the erase-remove idiom.

        auto is_nonalpha = std::not1(std::fun_ptr(std::isalpha));
        tok.erase(std::remove_if(tok.begin(), tok.end(), is_nonalpha), tok.end());

C++17 will introduce uniform container erasure.

        std::erase_if(tok, is_nonalpha);

---

            for (auto i = 0; i < hist.size()-1; i++) {
                hist[i] = hist[i+1];
            }

            hist[hist.size()-1] = tok;

Prefer to use standard algorithms as they may afford you optimizations.

            std::copy(std::next(hist.begin()), hist.end(), hist.begin());
            hist.back() = tok;

Rather than paying the cost of cycling, consider using a Circular container adaptor.

---

    if (!count.count(x1)) {
        return 0;
    }

Are you sure you want to exit if a word doesn't appear in the corpus? This doesn't seem like a case where termination is necessary.

---

    std::cout << (double)(std::max(num1, num2)) / den << std::endl;

std::endl outputs '\n' and flushes the stream. If you did not intend to flush the stream, just output '\n'.

---

My solution in C++ is below. I think I could do better in my attempt. What are the areas that I should prepare & learn? I failed to come up with a better data structure under the exam condition.

Seems like you already know where you should be looking.

During the test, I briefly tried stack but later found out I couldn't iterate all elements without changing the data structure. That wasted my time and I wonder if a stack can be used?

You can write a non-owning read-only adaptor. The underlying container is a protected data member of the Standard Library container adaptors.