Tag archives for architecture

For a quick assignment I was asked to write the following program:

In the language of your choosing build an application that, given an English language document as input, builds a data structure capturing the count of each word in the document.

Bonus:
Create an inverted index as well: a mapping of the words to absolute positions in the document.

As context, this is a foundational algorithm for search systems and information retrieval. Be sure to consider accuracy, complexity, and intent in the design of your program.

The last phrase was the one that got me thinking.
This sounded a little vague, so I started thinking what kind of design I can implement that would be flexible enough so I can apply the algorithms later.
This kind of program usually runs on the back end using Java/Python/etc, but obviously, the language of my choice was javascript.

I started by defining a master processor:

var Processor = function(doc) {
    this.doc = doc;
};
Processor.prototype.parse = function(parser, sorter) {
    data = parser.parse(this.doc);
    if (sorter && typeof sorter.sort === 'function') {
        return sorter.sort(data);
    }
    else {
        return data;
    }
};

This processor gets a document (in our simple example, a long string) and has parse method, which accepts a “parser” object that has a parse() method and an optional “sorter” object that has a sort() method.
As the names suggest, the former will parse the document, and the latter will sort the results.
This use of the Strategy Design Pattern will allow the application to be flexible for algorithm changes, in the future.

First, I defined an abstract Parser object.
This object is responsible to convert the input to a standard format, and apply an algorithm

var Parser = function(){};
/**
 * The implementation will return an object literal 
 * with the format {word: num, word: num ...}
 * 
 * @param str {String}
 * @returns {Object}
 */
Parser.prototype.parse = function(str){
    throw 'please extned abstract object';
};

/**
 * Convert an object literal into a sortable array
 * with the format [[word, num], [word, num], ...]
 * 
 * @param data {Object}
 * @returns {Array}
 */
Parser.prototype.convert = function(data) {
    var arr = [],
        data = data || {};
    for(var key in data) {
        if(data.hasOwnProperty(key)) {
            arr.push([key, data[key]]);
        }
    }
    return arr;
};

My next step was defining the parsers I was requested to write:
One for capturing the count of each word in the document:

var CountParser = function(arr) {
    this.arr = arr;
};
CountParser.prototype = new Parser; // extend the base parser
CountParser.prototype.parse = function(str) {
    var value, i, l, data = {},
        arr = str.split(/[\s]+/);
    for(i=0, l=arr.length; i<l; i++) {
        value = arr[i];
        data[value] = data[value] || 0;
        data[value]++;
    }
    // convert our object literal into a sortable array
    return this.convert(data); 
};

And another one for a mapping of the words to absolute positions in the document:

var IndexParser = function(arr) {
    this.arr = arr;
};
IndexParser.prototype = new Parser; 
IndexParser.prototype.parse = function(str) {
    var value, i, l, data = {},
        arr = str.split(/[\s]+/);
    for(i=0, l=arr.length; i<l; i++) {
        value = arr[i];
        if( ! data[value] ) {
            data[value] = i;
        }
    }
    return this.convert(data);
};

Next, I defined my Sorter object. It is an object that takes a comparator function as an argument and can later be ran agains arrays using the Array.sort method:

var Sotrer = function(comparator) {
    this.comparator = comparator;
};
Sotrer.prototype.sort = function(arr) {
    arr.sort(this.comparator);
    return arr;
};

Then, I implemented the two basic comparator algorithms: Ascending and Descending:

var ascCompare = function(a, b){
    return a[1] - b[1];
};
var descCompare = function(a, b){
    return b[1] - a[1];
};

The only thing left now is to run an example:

var doc = "Sed ut perspiciatis unde omnis iste natus error sit voluptatem accusantium doloremque laudantium, totam rem aperiam, eaque ipsa quae ab illo inventore veritatis et quasi architecto beatae vitae dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit aspernatur aut odit aut fugit, sed quia consequuntur magni dolores eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci velit, sed quia non numquam eius modi tempora incidunt ut labore et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam, nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure reprehenderit qui in ea voluptate velit esse quam nihil molestiae consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla pariatur?";
var processor = new Processor(doc);

var indexParser = new IndexParser(), 
    ascSorter = new Sotrer(ascCompare),
    countParser = new CountParser(),
    descSorter = new Sotrer(descCompare);
    
console.log(processor.parse(indexParser, ascSorter));
console.log(processor.parse(countParser, descSorter));

This design, based on strategy pattern, can later on take any parsing algorithm and any sorting algorithm with out the need for refactoring the core application.