solutions/20200922/Query_processing_DaaT.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Query processing with document-at-a-time scoring\n",
    "\n",
    "Implement term-at-a-time scoring using a simple retrieval function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import ipytest\n",
    "import math\n",
    "import pytest\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "ipytest.autoconfig()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Inverted index\n",
    "\n",
    "For simplicity, the inverted index for the document collection is given as a dictionary, with a terms as keys and posting lists as values. Each posting is a (document ID, term frequency) tuple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "index = {\n",
    "    'beijing': [(1, 1), (4, 1)],\n",
    "    'dish': [(1, 1), (4, 1)],\n",
    "    'duck': [(0, 3), (1, 2), (2, 2), (4, 1)],\n",
    "    'rabbit': [(2, 1), (3, 1)],\n",
    "    'recipe': [(2, 1), (3, 1), (4, 1)]\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Document lengths\n",
    "\n",
    "The length of each document is provided in a list. (Normally, this information would be present in a document metadata store or in a forward index.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "doc_len = [3, 4, 4, 2, 4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Document-at-a-time scoring\n",
    "\n",
    "We utilize the fact that the posting lists are ordered by document ID.  Then, it's enough to iterate through each query term's posting list only once.  We keep a pointer for each query term.\n",
    "\n",
    "Normally, document scores would be kept in a priority queue. Here, for simplicity, we will keep them in a dictionary.\n",
    "\n",
    "The retrieval function we use is the following:\n",
    "\n",
    "$$score(q,d) = \\sum_{t \\in q} w_{t,d} \\times w_{t,q}$$\n",
    "\n",
    "where $w_{t,d}$ and $w_{t,q}$ are length-normalized term frequencies. I.e., $w_{t,d}=\\frac{c_{t,d}}{|d|}$, where $c_{t,d}$ is the number of occurrences of term $t$ in document $d$ and $|d|$ is the document length (=total number of terms). (It goes analogously for the query.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def score_collection(index, doc_len, query):\n",
    "    \"\"\"Scores all documents in the collection.\n",
    "    \n",
    "    Args:\n",
    "        index: Dict holding the inverted index.\n",
    "        doc_len: List with document lengths.\n",
    "        query: Search query (string).\n",
    "    \n",
    "    Returns:\n",
    "        List with (document_id, score) tuples, ordered by score desc.\n",
    "    \"\"\"\n",
    "    \n",
    "    # Turns the query string into a \"term: freq\" dictionary.\n",
    "    query_freqs = dict(Counter(query.split()))\n",
    "\n",
    "    doc_scores = {}  # Holds the final document scores (this should be a priority list, but for simplicity we use a dictionary here).\n",
    "    \n",
    "    pos = {term: 0 for term in query_freqs}  # Holds a pointer for each query term's posting list.\n",
    "        \n",
    "    # Iterate through each document.\n",
    "    for doc_id in range(len(doc_len)):            \n",
    "        # First, we collect the document term frequencies from the index.\n",
    "        # (Essentially, we just \"recover\" the document's contents from the index.)\n",
    "        c_td = {}  # Holds the term frequencies in the document\n",
    "        for term in query_freqs.keys(): \n",
    "            # Get the term frequency from the posting list.\n",
    "            # Utilize the fact that the posting lists are ordered by document ID!\n",
    "            (d, freq) = index[term][pos[term]]\n",
    "            if d == doc_id:\n",
    "                c_td[term] = freq\n",
    "                pos[term] += 1\n",
    "            else:\n",
    "                # This means that d > doc_id, i.e., the term is not present in this doc.\n",
    "                pass\n",
    "                    \n",
    "        # Then, we score the document.\n",
    "        score = 0  # Holds the document's retrieval score\n",
    "        for term, c_tq in query_freqs.items():\n",
    "            # Incement the document's score according to the given query term\n",
    "            w_td = c_td.get(term, 0) / doc_len[doc_id]\n",
    "            w_tq = c_tq / len(query)\n",
    "            score += w_td * w_tq\n",
    "        # Record final document score.\n",
    "        doc_scores[doc_id] = score\n",
    "        \n",
    "    return sorted(doc_scores.items(), key=lambda x: x[1], reverse=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".                                                                                  [100%]\n",
      "1 passed in 0.01s\n"
     ]
    }
   ],
   "source": [
    "%%run_pytest[clean]\n",
    "\n",
    "def test_scoring():\n",
    "    scores = score_collection(index, doc_len, 'beijing duck recipe')    \n",
    "    assert scores[0][0] == 0\n",
    "    assert scores[0][1] == pytest.approx(0.0526, rel=1e-2)\n",
    "    assert scores[2][0] == 2\n",
    "    assert scores[2][1] == pytest.approx(0.0394, rel=1e-2)\n",
    "    assert scores[4][0] == 3\n",
    "    assert scores[4][1] == pytest.approx(0.0263, rel=1e-2)    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Feedback\n",
    "\n",
    "Please give (anonymous) feedback on this exercise by filling out [this form](https://forms.gle/2jPayczbFhEcC9K68)."
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}