1_classic_ir_inverted_index.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Classic IR\n",
    "\n",
    "IR in it's most basic form answers the question \"how relevant is a given *query* for a *document*\". The challenge is that we don't have just 1 document but potentially millions or billions of documents. So the key challenge is - how can we efficiently find this \"needle in the haystack\" or the \"relevant *documents* for a *query*\".\n",
    "\n",
    "Here, document refers to any kind of text document, typically these could be web pages, emails, plain text documents, etc. There are many technicalities to consider in real world applications of IR like cleaning up the markup in case of web pages. The documents could also be in different languages, encodings, etc. These variations present their own unique sets of challenges. For example, it's common to build separate pre-processing text pipelines for each language."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Relevance\n",
    "\n",
    "To answer the question \"how relevant is a given *query* for a *document*\", we first need to precisely define relevance.\n",
    "\n",
    "Relevance in the context of queries and documents captures the following key ideas:\n",
    " - A query can consist of many words, we break the query down into these individual words using a text processing pipeline which we will cover later.\n",
    " - If a word appears more often in a document, it's more relevant. We can capture this by counting the words in a document .\n",
    " - If a document is longer, words will tend to appear more often. So we need to take the document length into account as well.\n",
    " - It would be pretty slow if we start counting the words in all the documents after a query arrives, hence we need to store the counts in a data structure that supports efficient lookups for a query.\n",
    "\n",
    "| ![](assets/relevance.png) | \n",
    "|:--:| \n",
    "| Fig. 1. Illustration of IR with a query and documents sorted by relevancy. |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Inverted Index\n",
    "\n",
    "An inverted index helps us solve the last point we mentioned under Relevance, \"It would be pretty slow if we start counting the words in all the documents after a query arrives, hence we need to store the counts in a data structure that supports efficient lookups for a query.\"\n",
    "\n",
    "Inverted index allows us to efficiently retrieve documents from large collections. It does this by storing term/word statistics from the documents beforehand(that the scoring model needs).\n",
    "\n",
    "The statistics stored in the inverted index are:\n",
    " - **Document frequency**: How many documents contain the term.\n",
    " - **Term frequency per document**: How often does the term appear in a document.\n",
    " - **Document length**\n",
    " - **Average document length**\n",
    "\n",
    "The statistics are saved in a format that is accessible by a given term/word.\n",
    "\n",
    "| ![](assets/inverted_index.png) | \n",
    "|:--:| \n",
    "| Fig. 2. Illustration of statistics stored in an Inverted Index. |\n",
    "\n",
    "The term frequencies are stored in a \"posting list\" which is nothing but a list of document id and term frequency pairs. Every document gets an internal document id; which can be a simple integers for non web-scale data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating the Inverted Index\n",
    "\n",
    "The process of creating the inverted index involves creating a text processing pipeline which is applied both the documents as well as incoming queries.\n",
    "\n",
    "A typical pipeline looks like: `Tokenization` -> `Stemming` -> `Stop words removal`.\n",
    "\n",
    "### Tokenization\n",
    "\n",
    "Tokenization essentially involves splitting the query or document into individual terms/words.\n",
    "A naive baseline could split each query/document by whitespace and punctuation character.\n",
    "Improvements over the naive model typically involves keeping the abbreviations, names, numbers together as one token, etc. For example, look at the [stanford tokenizer](https://nlp.stanford.edu/software/tokenizer.shtml).\n",
    "\n",
    "```\n",
    "$ cat >sample.txt\n",
    "\"Oh, no,\" she's saying, \"our $400 blender can't handle something this hard!\"\n",
    "$ java edu.stanford.nlp.process.PTBTokenizer sample.txt\n",
    "``\n",
    "Oh\n",
    ",\n",
    "no\n",
    ",\n",
    "''\n",
    "she\n",
    "'s\n",
    "saying\n",
    ",\n",
    "``\n",
    "our\n",
    "$\n",
    "400\n",
    "blender\n",
    "ca\n",
    "n't\n",
    "handle\n",
    "something\n",
    "this\n",
    "hard\n",
    "!\n",
    "''\n",
    "PTBTokenizer tokenized 23 tokens at 370.97 tokens per second.\n",
    "```\n",
    "\n",
    "### Stemming\n",
    "\n",
    "Stemming involves reducing the terms/words to their \"roots\" before indexing. An advanced form of stemming called Lemmatization involves reducing the inflectional/variant forms to base form (am, are, is -> be). Lemmatization is computationally expensive.\n",
    "\n",
    "> For grammatical reasons, documents are going to use different forms of a word, such as organize, organizes, and organizing. Additionally, there are families of derivationally related words with similar meanings, such as democracy, democratic, and democratization. In many situations, it seems as if it would be useful for a search for one of these words to return documents that contain another word in the set.\n",
    ">\n",
    "> The goal of both stemming and lemmatization is to reduce inflectional forms and sometimes derivationally related forms of a word to a common base form. For instance:\n",
    "> `am, are, is -> be`, `car, cars, car's, cars' -> car`.\n",
    "> The result of this mapping of text will be something like:\n",
    "> `the boy's cars are different colors -> the boy car be differ color`\n",
    ">\n",
    "> However, the two words differ in their flavor. Stemming usually refers to a crude heuristic process that chops off the ends of words in the hope of achieving this goal correctly most of the time, and often includes the removal of derivational affixes. Lemmatization usually refers to doing things properly with the use of a vocabulary and morphological analysis of words, normally aiming to remove inflectional endings only and to return the base or dictionary form of a word, which is known as the lemma . If confronted with the token saw, stemming might return just s, whereas lemmatization would attempt to return either see or saw depending on whether the use of the token was as a verb or a noun. The two may also differ in that stemming most commonly collapses derivationally related words, whereas lemmatization commonly only collapses the different inflectional forms of a lemma. Linguistic processing for stemming or lemmatization is often done by an additional plug-in component to the indexing process, and a number of such components exist, both commercial and open-source.\n",
    ">\n",
    "> The most common algorithm for stemming English, and one that has repeatedly been shown to be empirically very effective, is Porter's algorithm (Porter, 1980).\n",
    ">\n",
    "> [Stemming and lemmatization](https://nlp.stanford.edu/IR-book/html/htmledition/stemming-and-lemmatization-1.html)\n",
    "\n",
    "### Stop word removal\n",
    "\n",
    "This simply involves removing the most common words that appear across all the documents. Typically, articles and pronouns are generally classified as stop words. Stop words play no significance in the scoring algorithms used for classic IR hence we remove them.\n",
    "\n",
    "For example, \"a\", \"the\", \"there\", etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Search and Relevance Scoring\n",
    "\n",
    "### Search workflow\n",
    "\n",
    "The search workflow typically involves:\n",
    " - Passing the query through the pre processing pipeline we just discussed to get the terms.\n",
    " - Look up the statistics for each term from the inverted index.\n",
    " - Use a scoring model that uses the term statistics to score the documents.\n",
    " - Sort the documents by the scores in a descending order and show to the user.\n",
    "\n",
    "| ![](assets/search_workflow.png) | \n",
    "|:--:| \n",
    "| Fig. 3. Illustration of the search workflow using Inverted Index. |\n",
    "\n",
    "Note that a document could be relevant without containing the exact query terms. This is the biggest drawback of the classic IR techniques we are discussing here.\n",
    "\n",
    "Dense retrieval techniques which we will cover later help us address this problem.\n",
    "\n",
    "### Types of queries\n",
    "\n",
    "Once the query has been broken into individual words, there are many ways they can be used to fetch statistics from the inverted index:\n",
    " - **Exact matching**: Match full words or concatenate multiple query words with \"or\".\n",
    " - **Boolean queries**: \"and\" / \"or\" / \"not\" operators between words.\n",
    " - **Expanded queries**: Ddd synonyms and other similar words into the query.\n",
    "\n",
    "Beyond this we can also augment the queries using wildcard queries, phonetic queries, etc.\n",
    "\n",
    "### Spell checking\n",
    "\n",
    "Another way to improve the quality of retrieval is to use spell correctors to:\n",
    " - Correct the documents being indexed.\n",
    " - Correct user queries to retrieve correct documents - e.g. the google style \"did you mean\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scoring models\n",
    "\n",
    "The scoring model captures relevance in a mathematical model. Note that here we are only considering the free text queries here or \"ad-hoc\" document retrieval, other factors could also come into play in real life scenarios like pagerank, recency, click counts etc.\n",
    "\n",
    "Another drawback of the scoring models we are about the discuss is the fact they don't consider meaning of the terms. Terms/words are essentially just discrete symbols. Similarly documents are stream of meaningless symbols. The word order is not important as well.\n",
    "\n",
    "Dense retrieval techniques which we will cover later help us address this problem.\n",
    "\n",
    "### TF_IDF\n",
    "\n",
    "The *TF_IDF* has two components:\n",
    " - **Term Frequency *tf*(t,d)**: How often does the term t appear in the document d.\n",
    "Using the raw frequencies here is not the best solution for IR problems. We either use relative frequencies or `log` to dampen the frequencies `tf(t,d) = log(1 + tf(t,d))`.\n",
    " - **Inverse Document Frequency *idf*(t)**: It's a measure of the \"informativeness\" of a term for a document. Not that rare terms are more informative than frequent terms. Common way of defining IDF is `idf(t) = log(|D| / df(t))`. Here `|D|` is the total number of documents and `df(t)` is the number of documents in which the term t appears.\n",
    "\n",
    "$$ TF\\_IDF(q, d) = \\sum_{t\\in T_d \\cap T_q} \\log(1 + tf_{t,d}) * \\log(\\frac{\\vert D \\vert}{df_t}) $$\n",
    "\n",
    "∑ - Sum over all the terms in the query<br>\n",
    "𝑡𝑓(𝑡,𝑑) - Frequency of term t in document d<br>\n",
    "|𝐷| - Total number of documents<br>\n",
    "𝑑𝑓(𝑡) - Number of documents in which the term t appears\n",
    "<br>\n",
    "\n",
    "Beyond IR, *TF_IDF* is also used for other NLP tasks like finding keywords in a document, Latent Semantic Analysis(LSA), classification, etc.\n",
    "\n",
    "Although the formulation in scikit-learn is not exactly the same, we can still look at *TF_IDF* in action."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>and</th>\n",
       "      <th>brown</th>\n",
       "      <th>crow</th>\n",
       "      <th>dog</th>\n",
       "      <th>fox</th>\n",
       "      <th>jumps</th>\n",
       "      <th>lazy</th>\n",
       "      <th>over</th>\n",
       "      <th>quick</th>\n",
       "      <th>smart</th>\n",
       "      <th>the</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>the quick brown fox jumps over the lazy dog</th>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.354136</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.354136</td>\n",
       "      <td>0.269329</td>\n",
       "      <td>0.354136</td>\n",
       "      <td>0.354136</td>\n",
       "      <td>0.354136</td>\n",
       "      <td>0.354136</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.418317</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>the fox and the crow</th>\n",
       "      <td>0.530587</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.403525</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.403525</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.626747</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>the smart crow</th>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.547832</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.720333</td>\n",
       "      <td>0.425441</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                                  and     brown      crow  \\\n",
       "the quick brown fox jumps over the lazy dog  0.000000  0.354136  0.000000   \n",
       "the fox and the crow                         0.530587  0.000000  0.403525   \n",
       "the smart crow                               0.000000  0.000000  0.547832   \n",
       "\n",
       "                                                  dog       fox     jumps  \\\n",
       "the quick brown fox jumps over the lazy dog  0.354136  0.269329  0.354136   \n",
       "the fox and the crow                         0.000000  0.403525  0.000000   \n",
       "the smart crow                               0.000000  0.000000  0.000000   \n",
       "\n",
       "                                                 lazy      over     quick  \\\n",
       "the quick brown fox jumps over the lazy dog  0.354136  0.354136  0.354136   \n",
       "the fox and the crow                         0.000000  0.000000  0.000000   \n",
       "the smart crow                               0.000000  0.000000  0.000000   \n",
       "\n",
       "                                                smart       the  \n",
       "the quick brown fox jumps over the lazy dog  0.000000  0.418317  \n",
       "the fox and the crow                         0.000000  0.626747  \n",
       "the smart crow                               0.720333  0.425441  "
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "docs = [\"the quick brown fox jumps over the lazy dog\", \"the fox and the crow\", \"the smart crow\"]\n",
    "        \n",
    "import pandas as pd\n",
    "from sklearn.feature_extraction.text import TfidfVectorizer\n",
    "\n",
    "vectorizer = TfidfVectorizer()\n",
    "X = vectorizer.fit_transform(docs)\n",
    "\n",
    "df = pd.DataFrame(X.todense(), columns=vectorizer.get_feature_names_out())\n",
    "df.index = docs\n",
    "df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For downstream ML tasks like classification(given we have the class labels), this matrix notation works perfectly.\n",
    "But computing, storing and updating this in matrix form for retrieval problems is not feasible due to the sparsity of this matrix for large number of documents.\n",
    "\n",
    "For example, if we have 1m documents with average term length of 1000 and vocabulary size of 100k(pretty reasonable at scale), we end up with a matrix of size 1,000,000 x 100,000 of which ~1,000,000 x 90,000 or ~90% of the terms will be 0. Though this is a very conservative estimate, it makes it obvious that storing the *TF_IDF* for web scale data is not feasible in this format. We use inverted index we discussed earlier to store this info."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### BM25 aka \"BestMatch25\"\n",
    "\n",
    "*BM25* is the backbone of most open source text based search engines over the last decade. It improves over the *TF_IDF* by taking into account the normalization of document length by average document length.\n",
    "\n",
    "There are two hyperparameters k and b that can be tuned to define the influence of document length normalization.\n",
    "\n",
    "$$ BM25(q, d) = \\sum_{t\\in T_d \\cap T_q} \\frac{tf_{t,d}}{k_1((1-b) + b\\frac{dl_d}{avgdl})+tf_{t,d}} * \\log(\\frac{\\vert D \\vert - df_t + 0.5}{df_t + 0.5}) $$\n",
    "\n",
    "∑ - Sum over all the terms in the query<br>\n",
    "𝑡𝑓(𝑡,𝑑) - Frequency of term t in document d<br>\n",
    "𝑑𝑙(𝑑) - Document length<br>\n",
    "𝑎𝑣𝑔𝑑𝑙 - Average document length<br>\n",
    "|𝐷| - Total number of documents<br>\n",
    "𝑑𝑓(𝑡) - Number of documents in which the term t appears<br>\n",
    "𝑘1,b - Hyperparameters\n",
    "<br>\n",
    "\n",
    "Not that this formulation is simpler than the original formula. More complex parts related to query length have not much practical implications for IR.\n",
    "The key difference between *TF_IDF* vs *BM25* is that the term frequency saturation is stronger in *BM25*.\n",
    "\n",
    "The hyperparametrs:\n",
    " - **k**: Controls term frequency scaling.\n",
    " - **b**: Conrols the document length normalization.\n",
    " \n",
    "Typical values of k and b are `1.2 < k < 2`, `0.5 < b < 0.8`.\n",
    "\n",
    "There are other formulations of *BM25* that take into account the title, abstract, headers etc. from the documents. We can essentially control the weights we want to assign to each component."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Oversimiplified implementation of the Inverted Index (*TF_IDF*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter, defaultdict\n",
    "import math\n",
    "import re\n",
    "from typing import List, Tuple\n",
    "\n",
    "import spacy\n",
    "from spacy.lang.en.stop_words import STOP_WORDS\n",
    "\n",
    "nlp = spacy.load(\"en_core_web_sm\")\n",
    "\n",
    "\n",
    "class InvertedIndex:\n",
    "    \"\"\"\n",
    "    A toy implementation of the \"Inverted Index\".\n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self):\n",
    "        # note that we are not using a postings list here but\n",
    "        # a dictionary to maintain the term frequency counts\n",
    "        self._index = defaultdict(lambda: defaultdict(int))\n",
    "        self._doc_lengths = []\n",
    "\n",
    "    def _check_txt_not_empty(self, txt: str) -> None:\n",
    "        if not txt:\n",
    "            raise Exception(\"txt can't be empty\")\n",
    "\n",
    "    def get_terms_from_text(self, txt: str) -> List[str]:\n",
    "        \"\"\"\n",
    "        Pre-processing pipeline applied to both the query and the documents.\n",
    "        \n",
    "        Args:\n",
    "            txt (str): Input query or document.\n",
    "        \n",
    "        Returns:\n",
    "            List[str]: Terms from a query/document.\n",
    "        \"\"\"\n",
    "        self._check_txt_not_empty(txt)\n",
    "        doc = nlp(\" \".join(re.findall(\"\\w+\", txt.lower())))\n",
    "        return [token.lemma_.lower() for token in doc if token.lemma_.lower() not in STOP_WORDS]\n",
    "\n",
    "    def _update_doc_lenghts(self, doc_length: int) -> None:\n",
    "        \"\"\"\n",
    "        Utility method that helps maintain the statistic \"Document lenghts\".\n",
    "        \n",
    "        Args:\n",
    "            doc_length (int): Length of a new document.\n",
    "        \"\"\"\n",
    "        self._doc_lengths.append(doc_length)\n",
    "\n",
    "    def _add_term_to_index(self, term: str, doc_id: int) -> None:\n",
    "        \"\"\"\n",
    "        Utility method that helps maintain the statistic \"Term frequencies\".\n",
    "        \n",
    "        Args:\n",
    "            term (str): Term from a document.\n",
    "            doc_id (str): Document Id.\n",
    "        \"\"\"\n",
    "        self._index[term][doc_id] += 1\n",
    "\n",
    "    def index_text(self, txt: str) -> None:\n",
    "        \"\"\"\n",
    "        Method used to update the inverted index for a document.\n",
    "        \n",
    "        Args:\n",
    "            txt (str): Input document.\n",
    "        \"\"\"\n",
    "        self._check_txt_not_empty(txt)\n",
    "        terms = self.get_terms_from_text(txt)\n",
    "        self._update_doc_lenghts(len(terms))\n",
    "        for term in terms:\n",
    "            self._add_term_to_index(term, len(self._doc_lengths)-1)\n",
    "\n",
    "    def get_docs_from_term(self, term: str) -> defaultdict:\n",
    "        \"\"\"\n",
    "        Returns document ids and term frequencies for a an input term.\n",
    "        \n",
    "        Args:\n",
    "            term (str): Input term.\n",
    "        \n",
    "        Returns:\n",
    "            defaultdict: Document ids and term frequencies.\n",
    "        \"\"\"\n",
    "        return self._index[term]\n",
    "\n",
    "    def score_query(self, txt: str, k: int=10, match_type: str=\"or\") -> List[Tuple[int, float]]:\n",
    "        \"\"\"\n",
    "        Returns documents and their scores for a query. Documents are sorted in the\n",
    "        descening order of their scores.\n",
    "        \n",
    "        Args:\n",
    "            txt (str): Input query.\n",
    "            k (int): N top documents to return.\n",
    "            match_type (str): Boolean filter to either take an intersection(and) or\n",
    "                union(and) when aggregating documents by terms.\n",
    "        \n",
    "        Returns:\n",
    "            List[Tuple[int, float]]: List of document ids and scores.\n",
    "        \"\"\"\n",
    "        assert match_type in (\"or\", \"and\"), f\"{match_type} is not a valid boolean filter\"\n",
    "\n",
    "        self._check_txt_not_empty(txt)\n",
    "        terms = self.get_terms_from_text(txt)\n",
    "        \n",
    "        valid_docs = set()\n",
    "        for i, term in enumerate(terms):\n",
    "            if i == 0 or match_type == \"or\":\n",
    "                valid_docs.update(self.get_docs_from_term(term).keys())\n",
    "            elif match_type == \"and\":\n",
    "                valid_docs.intersection_update(self.get_docs_from_term(term).keys())\n",
    "\n",
    "        doc_scores = defaultdict(float)\n",
    "        for term in terms:\n",
    "            for doc, term_frequency in self._index[term].items():\n",
    "                if doc in valid_docs:\n",
    "                    score = math.log(1+term_frequency) * math.log(len(self._doc_lengths)/len(self._index[term]))\n",
    "                    doc_scores[doc] += score\n",
    "\n",
    "        return sorted(doc_scores.items(), key=lambda x: x[1], reverse=True)[:k]\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self._doc_lengths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Indexing ...\n",
      "100 200 300 400 500 600 700 800 900 "
     ]
    }
   ],
   "source": [
    "from sklearn.datasets import fetch_20newsgroups\n",
    "\n",
    "inverted_index = InvertedIndex()\n",
    "\n",
    "documents = fetch_20newsgroups()[\"data\"]\n",
    "print(\"Indexing ...\")\n",
    "for i, doc in enumerate(documents[:1000]):  # Index the first 1000 documents\n",
    "    if i > 0 and i % 100 == 0:\n",
    "        print(i, end=\" \")\n",
    "    inverted_index.index_text(doc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "query = \"Computer ram\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Score    : 8.245\n",
      "Document : 'From: richg@sequent.com (Richard Garrett)\\nSubject: Computers for sale ( PC and amiga )\\nArticle-I.D.: sequent.1993Apr21.151726.26547\\nDistribution: na\\nOrganization: Sequent Computer Systems, Inc.\\nLines: 57\\nNntp-Posting-Host: crg8.sequent.com\\n\\nIts time for a little house cleaning after my PC upgrade.  I have the following\\nfor sale:\\n\\nLeading Technology PC partner (286) sytsem.  includes\\n\\t80286 12mhz intel cpu\\n\\t85Mb IDE drive (brand new - canabalized from new system)\\n\\t3.5 and 5.24 f ...\n",
      "---\n",
      "\n",
      "Score    : 7.497\n",
      "Document : \"From: rosa@ghost.dsi.unimi.it (massimo rossi)\\nSubject: ide &scsi controller\\nOrganization: Computer Science Dep. - Milan University\\nLines: 16\\n\\nhi folks\\ni have 2 hd first is an seagate 130mb\\nthe second a cdc 340mb (with a future domain no ram)\\ni'd like to change my 2 controller ide & scsi and buy\\na new one with ram (at least 1mb) that could controll \\nall of them\\nany companies?\\nhow many $?\\nand is it possible via hw or via sw select how divide\\nthe ram cache for 2 hd? (for example usin ...\n",
      "---\n",
      "\n",
      "Score    : 6.218\n",
      "Document : \"From: lingeke2@mentor.cc.purdue.edu (Ken Linger)\\nSubject: 32 Bit System Zone\\nOrganization: Purdue University\\nX-Newsreader: TIN [version 1.1 PL8]\\nLines: 32\\n\\nA week or so ago, I posted about a problem with my SE/30:  I have 20 megs\\nor true RAM, yet if I set my extensions to use a large amount of memory\\n(total of all extensions) then my system will crash before the finder\\ncomes up.  What I meant was having a large amount of fonts load, or\\nsounds, or huge disk caches with a control panel  ...\n",
      "---\n",
      "\n",
      "Score    : 5.523\n",
      "Document : \"From: ebosco@us.oracle.com (Eric Bosco)\\nSubject: Windows 3.1 keeps crashing: Please HELP\\nNntp-Posting-Host: monica.us.oracle.com\\nReply-To: ebosco@us.oracle.com\\nOrganization: Oracle Corp., Redwood Shores CA\\nX-Disclaimer: This message was written by an unauthenticated user\\n              at Oracle Corporation.  The opinions expressed are those\\n              of the user and not necessarily those of Oracle.\\nLines: 41\\n\\n\\nAs the subjects says, Windows 3.1 keeps crashing (givinh me GPF) on me ...\n",
      "---\n",
      "\n",
      "Score    : 5.356\n",
      "Document : 'From: afung@athena.mit.edu (Archon Fung)\\nSubject: wrong RAM in Duo?\\nOrganization: Massachusetts Institute of Technology\\nLines: 9\\nDistribution: world\\nNNTP-Posting-Host: thobbes.mit.edu\\n\\nA few posts back, somebody mentioned that the Duo might crash if it has\\nthe wrong kind (non-self refreshing) of RAM in it.  My Duo crashes\\nsometimes after sleep, and I am wondering if there is any software which\\nwill tell me whether or not I have the right kind of RAM installed.  I\\nhad thought that the ...\n",
      "---\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for doc_id, score in inverted_index.score_query(query, k=5, match_type=\"or\"):\n",
    "    print(f\"Score    : {score:4.3f}\\nDocument : {repr(documents[doc_id])[:500]} ...\\n---\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Score    : 8.245\n",
      "Document : 'From: richg@sequent.com (Richard Garrett)\\nSubject: Computers for sale ( PC and amiga )\\nArticle-I.D.: sequent.1993Apr21.151726.26547\\nDistribution: na\\nOrganization: Sequent Computer Systems, Inc.\\nLines: 57\\nNntp-Posting-Host: crg8.sequent.com\\n\\nIts time for a little house cleaning after my PC upgrade.  I have the following\\nfor sale:\\n\\nLeading Technology PC partner (286) sytsem.  includes\\n\\t80286 12mhz intel cpu\\n\\t85Mb IDE drive (brand new - canabalized from new system)\\n\\t3.5 and 5.24 f ...\n",
      "---\n",
      "\n",
      "Score    : 7.497\n",
      "Document : \"From: rosa@ghost.dsi.unimi.it (massimo rossi)\\nSubject: ide &scsi controller\\nOrganization: Computer Science Dep. - Milan University\\nLines: 16\\n\\nhi folks\\ni have 2 hd first is an seagate 130mb\\nthe second a cdc 340mb (with a future domain no ram)\\ni'd like to change my 2 controller ide & scsi and buy\\na new one with ram (at least 1mb) that could controll \\nall of them\\nany companies?\\nhow many $?\\nand is it possible via hw or via sw select how divide\\nthe ram cache for 2 hd? (for example usin ...\n",
      "---\n",
      "\n",
      "Score    : 5.523\n",
      "Document : \"From: ebosco@us.oracle.com (Eric Bosco)\\nSubject: Windows 3.1 keeps crashing: Please HELP\\nNntp-Posting-Host: monica.us.oracle.com\\nReply-To: ebosco@us.oracle.com\\nOrganization: Oracle Corp., Redwood Shores CA\\nX-Disclaimer: This message was written by an unauthenticated user\\n              at Oracle Corporation.  The opinions expressed are those\\n              of the user and not necessarily those of Oracle.\\nLines: 41\\n\\n\\nAs the subjects says, Windows 3.1 keeps crashing (givinh me GPF) on me ...\n",
      "---\n",
      "\n",
      "Score    : 5.236\n",
      "Document : \"Subject: XV under MS-DOS ?!?\\nFrom: NO E-MAIL ADDRESS@eicn.etna.ch\\nOrganization: EICN, Switzerland\\nLines: 24\\n\\nHi ... Recently I found XV for MS-DOS in a subdirectory of GNU-CC (GNUISH). I \\nuse frequently XV on a Sun Spark Station 1 and I never had problems, but when I\\nstart it on my computer with -h option, it display the help menu and when I\\nstart it with a GIF-File my Hard disk turns 2 or 3 seconds and the prompt come\\nback.\\n\\nMy computer is a little 386/25 with copro, 4 Mega rams, Ts ...\n",
      "---\n",
      "\n",
      "Score    : 4.705\n",
      "Document : \"From: Dale_Adams@gateway.qm.apple.com (Dale Adams)\\nSubject: Re: HELP INSTALL RAM ON CENTRIS 610\\nOrganization: Apple Computer Inc.\\nLines: 23\\n\\nIn article <C5115s.5Fy@murdoch.acc.Virginia.EDU> \\njht9e@faraday.clas.Virginia.EDU (Jason Harvey Titus) writes:\\n>         I had asked everyone about problems installing a 4 meg\\n> simm and an 8 meg simm in my Centris 610, but the folks at the\\n> local Apple store called the folks in Cupertino and found that\\n> you can't have simms of different speeds ...\n",
      "---\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for doc_id, score in inverted_index.score_query(query, k=5, match_type=\"and\"):\n",
    "    print(f\"Score    : {score:4.3f}\\nDocument : {repr(documents[doc_id])[:500]} ...\\n---\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## References\n",
    "\n",
    "[1] Sebastian Hofstätter. \"[Advanced Information Retrieval 2021 @ TU Wien](https://www.youtube.com/playlist?list=PLSg1mducmHTPZPDoal4m59pPxxsceXF-y)\""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}