# Calculating cooccurrence probabilities for pairs of words in a document

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;
}
}

• The task quoted said various pairs of words A and B, you seem to be handling each and every pair. (I'd probably claim the task insufficiently specified, associate ordinals with "each" word and wait for queries…) – greybeard Sep 7 '16 at 7:14
• @greybeard I think the question is asking about each and every pair within the K distance. – SmallChess Sep 7 '16 at 7:14

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 . As luck would have it, Boost has a circular buffer.

#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.