CSE 163, Winter 2020: Homework 4: Python Classes and Search Engines

Submission

This assignment and its reflection are due by Thursday, Feb 6 at 11:59 pm.

You should submit your finished document.py, search_engine.py, and hw4_test.py on Ed and the reflection on Google Forms

DO NOT submit the wikipedia dataset.

Overview

At a high-level, a search-engine is an algorithm that accepts a query from the user, and computes how relevant a given document is to that query. The search engine can then rank documents according to their relevance.

In this assignment you will implement your own search engine by defining two classes, Documentand SearchEngine. The Document class represents a single file in the search engine, and the SearchEngine class handles the functionality of querying the collection of stored Documents. The SearchEngine will use the TF-IDF (term frequency - inverse document frequency) algorithm to compute the relevance of a document to a given term.

The purpose of this assignment is to introduce you to writing cohesive python classes. This will include public methods, private methods, and data structures stored as fields. Additionally, you will work with common indexing algorithms, and consider efficient ways to store data that will be frequently accessed by the TF-IDF algorithm.

You will probably find that this is the most challenging assignment of the whole quarter. This is intended since it is the last assignment that you will be doing without working on your project in parallel. The remaining assignments won't be as complex as this one so it's okay to feel a bit lost the first time you read over this spec. There are a lot of instructions and it gives guidance on how to develop this assignment in parts to this complexity.

Learning Objectives

After this homework, students will be able to:

  • Write a complete Python class from scratch.
    • This will include writing two classes which interact with each other.
  • Implement basic Python classes to represent Documents and SearchEngines.
  • Identify appropriate data structures to store/access term indexes efficiently.
  • Understand fundamental document and term ranking algorithms to implement a basic search engine.
    • Specifically the TF-IDF algorithm which computes term-frequency and inverse document frequency.

Expectations

Here are some baseline expectations we expect you to meet:

Files

The files included are:

  • main.py: A python file which will allow a user to run a new search engine at the command line. More information about this file is included later in the specification.
  • wikipedia: This directory contains a number of wikipedia files, and your SearchEngine can be used to query and rank the files.
  • small-wiki: This directory contains a smaller number of wikipedia files, and your SearchEngine can be used to query and rank the files.
  • hw4_test.py: The file you should put your tests for document.py and search_engine.py in.
  • cse163_utils.py: A file where we will store utility functions for helping you write tests.

If you are working locally, you should download the starter code hw4.zip and open it as the project in Visual Studio Code.

If you are developing on Ed, you don't need to download anything. An important thing to note, is that on Ed the wikipedia directory is stored at the path /course/wikipedia.

The Algorithm

To implement the document ranking algorithm you will use the TF-IDF (term frequency- inverse document frequency) algorithm. This is just a fancy way of weighting documents based on their relevance to a search term. TF-IDF is one of the most popular term-weighting schemes - 83% of text-based recommender systems use TF-IDF.

The TF-IDF algorithm consists of two main computations. The following information describes these computations at a high-level, and the exact equations will be included later in the spec.

Term Frequency

The term frequency is computed on a document level, and it represents how often a search term appears in a specific document.

Inverse Document Frequency

Because filler words such as “the” are so common, term frequency tends to incorrectly weight documents that use the word “the” often. The inverse document frequency is a measure of how often the word appears in the entire set of documents. We then use this value to diminish the weight of terms that occur very frequently.

Optional: TF-IDF

You are only required to understand the information about the algorithm covered in the spec. For those interested, more information about TF-IDF can be found here.

Table of Contents

Note: The instructions for running the main program and testing are not until Part 3, but you might want to read that earlier!

Evaluation

Your submission will be evaluated on the following dimensions

  • Your solution correctly implements the described behaviors. You will not have access to tests when you turn in your assignment, All behavior we test is completely described by the problem specification or shown in an example.
  • Your code meets our style requirements:
    • All code files submitted pass flake8
    • Every function written is commented, in your own words, using a doc-string format that describes its behavior, parameters, returns, and highlights any special cases.
      • Each class you write should also have a doc-string format
    • There is a comment at the top of each code file you write with your name, section, and a brief description of what that program does.
    • Any expectations on this page or the sub-pages for the assignment are met as well as all requirements for each of the problems are met.
    • The fields of all your classes should be private (by having the names start with a _. You are allowed to access the fields directly in your tests since they are something you wrote personally and the tests don't need to behave like a true client should.