N-gram Search (Information Retrieval)

• Problem definition
• Suggested approach
• Input/output formats
• Requirements and suggestions
• Datasets

Problem definition

Google's Web 1T dataset is a big collection of n-grams (with n=2, 3, 4, and 5) of English that can be used for various applications, including machine translation, speech recognition, English usage correction, etc. In this assignment, we need to implement an efficient information retrieval method for querying a slim version of the Web 1T dataset.

Given a query of n-gram, you program should return its frequency based on the slim Web 1T. The given n-gram query can be a simple query such as "listen to music" or "in a position to". Additionally, it can contains wildcards and special characters to make the query more flexible, as explain next.

• "-" (underscore) can be used to represent a word (token).
  For instance, "listen _ music"
• "*" (asterisk) can be used to represent zero or more words
  For instance, "a * book"
• "?" can be used as a prefix to denote a word as optional
  For instance, "discuss ?about the issue"
• "/" can be used to denote all alternatives
  For instance, "in/at/on the afternoon"

Please check out the recording and slides of this homework.

Suggested approach

• An example information retrieval problem
• A first take at building an inverted index
• Processing Boolean queries

Tutorials by Stanford NLP-Professor Dan Jurafsky & Chris Manning

• Inverted index
• Merge postings

To be more precise, here is a typical approach to the problem:

• Preprocess
  1. Extract all words from the n-gram dataset
  2. Create a dictionary of all sorted unique words
  3. Generate a posting for each word in the dictionary
• Online processing
  1. Expand the query until it contains only words or "_".
  2. Extract words from the query
  3. Retrieve each word (by binary search or the likes) and its posting from one of the n-gram sets
  4. Combine postings to have the candidate output set
  5. Generate final output by considering ordering.
  6. Sort and print the output ordered by frequency

1. First, expand "?" (which, if exist, always applear as the first character in a token). For instance, "abc ?x/y/z _ ?*/p" can be expanded into the following 4 queries:
   • abc _
   • abc _ */p
   • abc x/y/z _
   • abc x/y/z _ */p
2. Second, expand "/". For instance, "abc x/y/z _ */p" can be expanded into the following 6 queries:
   • abc x _ *
   • abc x _ p
   • abc y _ *
   • abc y _ p
   • abc z _ *
   • abc z _ p
3. Last, expand "*" into emptiness or combinations of "_". For instance, "give * a *" can be expaneded into the following 10 queries:
   • give a
   • give a _
   • give a _ _
   • give a _ _ _
   • give _ a
   • give _ a _
   • give _ a _ _
   • give _ _ a
   • give _ _ a _
   • give _ _ _ a

Input/output formats

An typical example of input file is as follows, where each line is a query:

For each query, you only need to generate at most top-5 output with ascending order of frequency. If there is tie, list them according to alphabetical order of the n-grams. The output file corresponding to the previous input file is shown next:

Requirements

• Limits:
  • Max time: 180 second.
  • Max memory: 7 GB.
  • Max submissions: 20 times each week, starting at "20170320 23:59:59" and ending at "20170403 23:59:59".
• Program usage: Your program should take an input argument to indicate the directory which holds the n-gram files. The default file names are shown in the download links listed below. And the input file (which holds the queries) can be redirect to the program. An example follows. myProgram /tmp2/dsa2017_hw02/ < input00.txt

Datasets

1. The original Google Web 1T dataset is too big to process for machines with limited memory. Hence we shall use a subset for this project, as shown next. These files are already available under /tmp2/dsa2017_hw02/ of linux1 to linux13.
   • 2-grams (bigrams)
   • 3-grams (trigrams)
   • 4-grams (fourgrams)
   • 5-grams (fivegrams)
2. Open test sets
   • input0010.txt, output0010.txt
   • input0100.txt, output0100.txt
   • input1000.txt, output1000.txt
3. Hidden test sets
   • input1000-hidden.txt, output1000-hidden.txt