Ranked Retrieval Search Engine

Overview

A basic textual search engine / ranked retrieval system is implemented in this project for ranking documents based on the proximity of query terms. The system comprises two main components: an index program for constructing an inverted positional index from a textual dataset, and a search program that uses the generated index and a ranked algorithm to answer textual queries.

A small subset of the Reuters-21578 dataset is provided in the data folder for testing purposes.

Assumptions

• Search queries consist of space-separated terms.
• Search terms contain only alphanumeric characters, with no punctuation.
• Index files' total size does not exceed 20MB.
• Text files are named with numbers only (e.g., 1, 2, 3) without extensions or leading zeros.
• A line is defined by the newline character (\n), ignoring punctuation.
• Document paths remain consistent once defined in the index program and can be reused by the search program.

Search Rules

• Searches are case-insensitive.
• Full stops in abbreviations are ignored (e.g., U.S. vs US).
• Singular and plural forms are treated as the same (e.g., cat vs cats).
• Tense variations are treated as the same (e.g., breach, breached, breaching).
• Sentences end with full stops, question marks, or exclamation marks.
• Numbers are indexed and searchable; commas in numbers are ignored (e.g., 1,000,000 vs 1000000).
• All other punctuation is treated as token dividers.

Ranking Rules

• Proximity distance is defined as the number of terms between pairs of matching terms without considering decimal numbers.
• The ranking results are sorted with respect to the following criteria:
  • Primarily by the minimum sum of pairwise proximity distances (left-to-right by query terms).
  • Secondarily by the number of matching terms in the same order as the query.
  • Finally by document ID numeric values.

Display Rules

• Only one line of text containing the closest matching term is displayed per query term.
• Lines are displayed in the order they appear in the document.
• If multiple closest terms are found on different lines, only the first line is shown.

Index Program

To index the files, use the following command:

python3 index.py folderOfDocuments folderOfIndexes

• folderOfDocuments: Path to the directory containing document(s) to be indexed.
• folderOfIndexes: Path to the directory where index file(s) will be created.

Example output:

$ python3 index.py ./data ./index
Total number of documents: 1000
Total number of tokens: 250000
Total number of terms: 10000

Search Program

To search the indexed files, use the following command:

python3 search.py folderOfIndexes

• folderOfIndexes: Path to the directory containing the index file(s).

The program reads search queries from standard input and outputs document IDs to standard output. It continues to accept and process queries until EOF (Ctrl-D).

$ python3 search.py ./index
Apple
1234
2345
3456

For queries starting with > followed by a space, the program also displays lines with the closest matching terms.

$ python3 search.py ./index
> bank expect distribution
> 3123
 The bank said it expects the distribution will be made in
> 4456
 Closing is expected to take place in early April and the
 The partnership will acquire the refining and distribution
 facility with U.S. and foreign banks to finance inventories and

Implementation

Index Program:

• For each file in the input directory:
  • It reads the content of the file.
  • It performs several text preprocessing steps, such as removing decimal numbers, commas in numeric tokens, and certain apostrophes.
  • It tokenizes the text into individual words.
  • It converts all tokens to lowercase.
  • It lemmatizes the tokens to their base forms.
  • It increments the token counter by the number of tokens.
  • It inserts the tokens into the dictionary, recording their positions in the document.
• It calculates the number of unique terms in the dictionary.
• It saves the dictionary to an index file in the output directory.
• It saves the input directory path to a file in the output directory.
• It prints the total number of documents, tokens, and terms.

Search Program:

• It loads the dictionary and original directory path from the index files.
• It enters a loop to continuously accept search queries from the user.
• For each query:
  • It checks if the query starts with ">" to enable line display mode.
  • It tokenizes the query into individual words.
  • It converts all tokens to lowercase.
  • It lemmatizes the tokens to their base forms.
  • It checks if all terms in the query exist in the dictionary.
  • It finds documents containing all the terms in the query.
  • If there is only one query term, it displays the document IDs or lines containing the term.
  • If there are multiple query terms, it computes advanced results by finding the best path of term positions in the documents.
  • It sorts the results based on proximity distance, in-order count, and document ID.
  • It displays the document IDs or lines containing the terms based on the results.

Disclaimer

This project presents a straightforward attempt at the problem with limited focus on performance optimisation.