File Explorer

1/**2 * Mnemonist Inverted Index3 * =========================4 *5 * JavaScript implementation of an inverted index.6 */7var Iterator = require('obliterator/iterator'),8    forEach = require('obliterator/foreach'),9    helpers = require('./utils/merge.js');10 11function identity(x) {12  return x;13}14 15/**16 * InvertedIndex.17 *18 * @constructor19 * @param {function} tokenizer - Tokenizer function.20 */21function InvertedIndex(descriptor) {22  this.clear();23 24  if (Array.isArray(descriptor)) {25    this.documentTokenizer = descriptor[0];26    this.queryTokenizer = descriptor[1];27  }28  else {29    this.documentTokenizer = descriptor;30    this.queryTokenizer = descriptor;31  }32 33  if (!this.documentTokenizer)34    this.documentTokenizer = identity;35  if (!this.queryTokenizer)36    this.queryTokenizer = identity;37 38  if (typeof this.documentTokenizer !== 'function')39    throw new Error('mnemonist/InvertedIndex.constructor: document tokenizer is not a function.');40 41  if (typeof this.queryTokenizer !== 'function')42    throw new Error('mnemonist/InvertedIndex.constructor: query tokenizer is not a function.');43}44 45/**46 * Method used to clear the InvertedIndex.47 *48 * @return {undefined}49 */50InvertedIndex.prototype.clear = function() {51 52  // Properties53  this.items = [];54  this.mapping = new Map();55  this.size = 0;56  this.dimension = 0;57};58 59/**60 * Method used to add a document to the index.61 *62 * @param  {any} doc - Item to add.63 * @return {InvertedIndex}64 */65InvertedIndex.prototype.add = function(doc) {66 67  // Increasing size68  this.size++;69 70  // Storing document71  var key = this.items.length;72  this.items.push(doc);73 74  // Tokenizing the document75  var tokens = this.documentTokenizer(doc);76 77  if (!Array.isArray(tokens))78    throw new Error('mnemonist/InvertedIndex.add: tokenizer function should return an array of tokens.');79 80  // Indexing81  var done = new Set(),82      token,83      container;84 85  for (var i = 0, l = tokens.length; i < l; i++) {86    token = tokens[i];87 88    if (done.has(token))89      continue;90 91    done.add(token);92 93    container = this.mapping.get(token);94 95    if (!container) {96      container = [];97      this.mapping.set(token, container);98    }99 100    container.push(key);101  }102 103  this.dimension = this.mapping.size;104 105  return this;106};107 108/**109 * Method used to query the index in a AND fashion.110 *111 * @param  {any} query - Query112 * @return {Set}       - Intersection of documents matching the query.113 */114InvertedIndex.prototype.get = function(query) {115 116  // Early termination117  if (!this.size)118    return [];119 120  // First we need to tokenize the query121  var tokens = this.queryTokenizer(query);122 123  if (!Array.isArray(tokens))124    throw new Error('mnemonist/InvertedIndex.query: tokenizer function should return an array of tokens.');125 126  if (!tokens.length)127    return [];128 129  var results = this.mapping.get(tokens[0]),130      c,131      i,132      l;133 134  if (typeof results === 'undefined' || results.length === 0)135    return [];136 137  if (tokens.length > 1) {138    for (i = 1, l = tokens.length; i < l; i++) {139      c = this.mapping.get(tokens[i]);140 141      if (typeof c === 'undefined' || c.length === 0)142        return [];143 144      results = helpers.intersectionUniqueArrays(results, c);145    }146  }147 148  var docs = new Array(results.length);149 150  for (i = 0, l = docs.length; i < l; i++)151    docs[i] = this.items[results[i]];152 153  return docs;154};155 156/**157 * Method used to iterate over each of the documents.158 *159 * @param  {function}  callback - Function to call for each item.160 * @param  {object}    scope    - Optional scope.161 * @return {undefined}162 */163InvertedIndex.prototype.forEach = function(callback, scope) {164  scope = arguments.length > 1 ? scope : this;165 166  for (var i = 0, l = this.documents.length; i < l; i++)167    callback.call(scope, this.documents[i], i, this);168};169 170/**171 * Method returning an iterator over the index's documents.172 *173 * @return {Iterator}174 */175InvertedIndex.prototype.documents = function() {176  var documents = this.items,177      l = documents.length,178      i = 0;179 180  return new Iterator(function() {181    if (i >= l)182      return {183        done: true184      };185 186      var value = documents[i++];187 188      return {189        value: value,190        done: false191      };192  });193};194 195/**196 * Method returning an iterator over the index's tokens.197 *198 * @return {Iterator}199 */200InvertedIndex.prototype.tokens = function() {201  return this.mapping.keys();202};203 204/**205 * Attaching the #.values method to Symbol.iterator if possible.206 */207if (typeof Symbol !== 'undefined')208  InvertedIndex.prototype[Symbol.iterator] = InvertedIndex.prototype.documents;209 210/**211 * Convenience known methods.212 */213InvertedIndex.prototype.inspect = function() {214  var array = this.items.slice();215 216  // Trick so that node displays the name of the constructor217  Object.defineProperty(array, 'constructor', {218    value: InvertedIndex,219    enumerable: false220  });221 222  return array;223};224 225if (typeof Symbol !== 'undefined')226  InvertedIndex.prototype[Symbol.for('nodejs.util.inspect.custom')] = InvertedIndex.prototype.inspect;227 228/**229 * Static @.from function taking an arbitrary iterable & converting it into230 * a InvertedIndex.231 *232 * @param  {Iterable} iterable - Target iterable.233 * @param  {function} tokenizer - Tokenizer function.234 * @return {InvertedIndex}235 */236InvertedIndex.from = function(iterable, descriptor) {237  var index = new InvertedIndex(descriptor);238 239  forEach(iterable, function(doc) {240    index.add(doc);241  });242 243  return index;244};245 246/**247 * Exporting.248 */249module.exports = InvertedIndex;250