An Inverted Index is a data structure used to create full text search.



Task

Given a set of text files, implement a program to create an inverted index.

Also create a user interface to do a search using that inverted index which returns a list of files that contain the query term / terms.

The search index can be in memory.




 
fs = require 'fs'
 
make_index = (fns) ->
  # words are indexed by filename and 1-based line numbers
  index = {}
  for fn in fns
    for line, line_num in fs.readFileSync(fn).toString().split '\n'
      words = get_words line
      for word in words
        word = mangle(word)
        index[word] ||= []
        index[word].push [fn, line_num+1]
  index
 
grep = (index, word) ->
  console.log "locations for '#{word}':"
  locations = index[mangle(word)] || []
  for location in locations
    [fn, line_num] = location
    console.log "#{fn}:#{line_num}"
  console.log "\n"
 
get_words = (line) ->
  words = line.replace(/\W/g, ' ').split ' '
  (word for word in words when word != '')
 
mangle = (word) ->
  # avoid conflicts with words like "constructor"
  '_' + word
 
do ->
  fns = (fn for fn in fs.readdirSync('.') when fn.match /\.coffee/)
  index = make_index(fns)
  grep index, 'make_index'
  grep index, 'sort'
 