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.




procedure main()
 
  texts := table()     # substitute for read and parse files
  texts["T0.txt"] := ["it", "is", "what", "it", "is"]
  texts["T1.txt"] := ["what", "is", "it"]
  texts["T2.txt"] := ["it", "is", "a", "banana"]
 
  every textname := key(texts) do  # build index for each 'text'
     SII := InvertedIndex(SII,textname,texts[textname])
 
  TermSearchUI(SII)  # search UI
 
end
 
procedure InvertedIndex(ii,k,words)  #: accumulate a simple inverted index
 
/ii := table(set())    # create lookup table and null set
every w := !words do {
   if *ii[w] = 0 then ii[w] := set()  # new word, new set
   insert(ii[w],k)
   }
 
return ii
end
 
procedure TermSearchUI(ii)    #: search UI, all words must match
 
repeat {
   writes("Enter search terms (^z to quit) : ")
   terms := map(trim(read() | break))
 
   x := []
   terms ? while not pos(0) do {
      tab(many(' \t'))
      put(x,tab(upto('\ \t')|0))
      }
 
   show("Searching for : ",x)
   show("Found in : ",s := TermSearch(ii,x)) | show("Not found : ",x)
   }
write("End of search")
return
end
 
procedure TermSearch(ii,x)  #: return set of matches or fail
every s := !x do
   ( /u := ii[s] ) | (u **:= ii[s])
if *u > 0 then return u
end
 
procedure show(s,x) # display helper
every writes(s|!x) do writes(" ")
write()
return
end