main_notebook.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework 3 - Which book would you recommend?\n",
    "\n",
    "*Stefano D'Arrigo 1960500, Alessio Sentinelli 1967001, Iyuele Alemu Korsaye 1421343*\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![goodreads image](./images/goodrreads.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notes before starting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to keep this notebook tidy and agile to read, the majority of the code we wrote to complete the tasks is not included here and is provided into the folder `scripts`. Nevertheless, the crucial pieces of code are directly executed or shown and commented inside this notebook. For further understanding of each operation and choice we made, please refer to the comments to the code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Data collection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Loading libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from bs4 import BeautifulSoup as bs # library for pulling data out of HTML files\n",
    "import requests # library used to  make HTTP requests simpler\n",
    "import re # library for regular expression matching operations\n",
    "from selenium import webdriver # to automate website testing.\n",
    "import chromedriver_binary # for google chrome\n",
    "import spacy # library for advanced natural language processing\n",
    "from spacy_fastlang import LanguageDetector # to detect languages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1. Get the list of books"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we open a txt file and extract the URL of the 30k books, using a for loop over the 300 pages and leveraging the request library we get access to the pages where the books are present.\n",
    "\n",
    "Then using a third-party library, beautiful soup we can pull the data out of the HTML files and use the ‘lxml’ parser to extract the class \"js tooltipTrigger tooltipTrigger\" within a div tag, where the url of the books is present.\n",
    "Finally we write within a loop function the collected 30k url on the text file we opened previously and close the file.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f = open(\"url_list.txt\",\"w\") # open the new txt file\n",
    "for k in range (1,301):  #301 for the pages\n",
    "    page = requests.get(\"https://www.goodreads.com/list/show/1.Best_Books_Ever?page=\" + str(k)) # select the page\n",
    "    soup = BeautifulSoup(page.content, features=\"lxml\") # take the content from the page\n",
    "    URL_con3 = soup.find_all('div', class_=\"js-tooltipTrigger tooltipTrigger\") # to filter what we need \n",
    "    for j in range (0,100): #100 for the books in every page\n",
    "        URL_str = str(URL_con3[j]) \n",
    "        list_split = URL_str.split(\" \")\n",
    "        result = list_split[5] \n",
    "        result_clean = result.split(\"\\\"\")[1] # now we have the URL \n",
    "        f.write(\"https://www.goodreads.com\" + result_clean + \"\\n\") # write the URL on the txt file\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We obtained a txt file with 30k lines with each line containing the URL book, and the txt file is finally saved in the data folder."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2. Crawl books"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The goal of this task is to retrieve all the `HTML` pages of the books, reading the `url_list.txt` file that we created in the previous task.\n",
    "\n",
    "In order to bypass eventual security measures against scraping, we leveraged the library `selenium`, which provides a full and automatized web client agent. \n",
    "\n",
    "To complete this task, we wrote a class `DataCollector`, included in `data_collection.py`. The methods of this class receive the user's input, compute the offset from which start reading the URLs file and save the HTML pages. \n",
    "\n",
    "The core business of this class is included into the following method:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "~~~python\n",
    "def __save_html_pages(self, start_from, stop_at):\n",
    "        \"\"\"\n",
    "        Start collecting from line start_from and stop at line stop_at.\n",
    "        \"\"\"\n",
    "        with open(os.path.join(self.root_dir, 'url_list.txt'), 'r') as urls_file:\n",
    "            try:\n",
    "                urls = urls_file.readlines()[start_from : ] # select the line from which start collecting\n",
    "            except:\n",
    "                print('Error: reached file end!')\n",
    "                exit(-1)\n",
    "            for url, i in zip(urls, tqdm(range(start_from, stop_at))): # \n",
    "                if i % 100 == 0:\n",
    "                    self.__make_dir(i // 100 + 1)\n",
    "                try:\n",
    "                    driver.get(url)\n",
    "                    page_html = driver.page_source\n",
    "                    with open(os.path.join(self.html_dir, f'article_{i + 1:05d}.html'), 'w') as out_file:\n",
    "                        out_file.write(page_html)\n",
    "                except:\n",
    "                    with open('./log/log.csv', 'a') as log:\n",
    "                        log.write(f'[{datetime.datetime.now()}], {i+1}, {url}\\n')\n",
    "                    continue\n",
    "            driver.close()\n",
    "~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the parameter `start_from`, the user can decide from which document start crawling. The eventual errors in retrieving the pages were annotated in a log file and handled manually after the execution of the script."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output of this method are the collected data, structured in the following way:\n",
    "\n",
    "```\n",
    "- html/\n",
    "    - 1/\n",
    "        - article_00001.html\n",
    "        - article_00002.html\n",
    "        - ...\n",
    "        - article_00100.html\n",
    "    - 2/\n",
    "        - article_00101.html\n",
    "        - ...\n",
    "        - article_00200.html\n",
    "    - ...\n",
    "    - 300/\n",
    "        - article_29901.html\n",
    "        - ...\n",
    "        - article_30000.html\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Parse downloaded pages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we have accessed the HTML content of all the 30 000 books, we are left with the task of parsing the data. Since most of the HTML data is nested, we cannot extract data simply through string processing. One needs a parser which can create a nested/tree structure of the HTML data. There are many HTML parser libraries available, the one we have used in our function (book_scraping) is ‘lxml’ parser.\n",
    "\n",
    "Now, we need to navigate and search the parse tree that we created and for this task, we will be using another third-party python library, Beautiful Soup. It is a Python library for pulling data out of HTML and XML files. A really nice feature  about the BeautifulSoup library is that it is built on the top of the HTML parsing libraries like, lxml, html5lib parser, etc. so  that BeautifulSoup object and the parser library can be created at the same time.\n",
    "soup = BeautifulSoup(html_source, features='lxml')\n",
    "\n",
    "Now, we are ready to extract all the relevant data from the HTML content that are crucial for building a book recommendation engine. The soup object contains all the data in the nested structure which can be programmatically extracted using the ‘book scraping’ function, that we have created to retrieve and save for each 30k book all the relevant information (book title, book series, book author, rating value, rating count, review count, plot, number of pages, published date, characters, settings and URL)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def book_scraping(html_source): # this takes the html content and returns a list with the useful info\n",
    "    nlp = spacy.load('en_core_web_sm')\n",
    "    nlp.add_pipe(LanguageDetector())\n",
    "\n",
    "    soup = BeautifulSoup(html_source, features='lxml') # instantiate a BeautifulSoup object for HTML parsing\n",
    "\n",
    "    bookTitle = soup.find_all('h1', id='bookTitle')[0].contents[0].strip() # get the book title\n",
    "\n",
    "    # if bookSeries is not present, then set it to the empty string\n",
    "    try:\n",
    "        bookSeries = soup.find_all('h2', id='bookSeries')[0].contents[1].contents[0].strip()[1:-1]\n",
    "    except:\n",
    "        bookSeries = ''\n",
    "\n",
    "    # if bookAuthors is not present, then set it to the empty string\n",
    "    try:\n",
    "        bookAuthors = soup.find_all('span', itemprop='name')[0].contents[0].strip()\n",
    "    except:\n",
    "        bookAuthors = ''\n",
    "    \n",
    "    # the plot of the book is essential; if something goes wrong with the plot, raise an error\n",
    "    try:\n",
    "        Plot = soup.find_all('div', id='description')[0].contents  # get the main tag where the plot is found \n",
    "        filter_plot = list(filter(lambda i: i!='\\n', Plot))  # filter the plot by removing tags that doesn’t contain the description \n",
    "        if len(filter_plot) == 1:    \n",
    "            Plot = filter_plot[0].text\n",
    "        else:                          # getting all the plot within the tag\n",
    "            Plot = filter_plot[1].text  \n",
    "        doc = nlp(Plot)\n",
    "        if doc._.language != 'en':          \n",
    "            raise Exception # if the plot is not in english, raise an error\n",
    "    except:\n",
    "        raise # pass the error to the caller function\n",
    "\n",
    "\n",
    "    # if NumberofPages is not present, then set it to the empty string\n",
    "    try:\n",
    "        NumberofPages = soup.find_all('span', itemprop='numberOfPages')[0].contents[0].split()[0]\n",
    "    except:\n",
    "        NumberofPages = ''\n",
    "    \n",
    "    # if ratingValue is not present, then set it to the empty string\n",
    "    try:\n",
    "        ratingValue = soup.find_all('span', itemprop='ratingValue')[0].contents[0].strip()\n",
    "    except:\n",
    "        ratingValue = ''\n",
    "    \n",
    "    # if rating_reviews is not present, then set it to the empty string\n",
    "    try:\n",
    "        ratings_reviews = soup.find_all('a', href='#other_reviews')\n",
    "        for i in ratings_reviews:\n",
    "            if i.find_all('meta',itemprop='ratingCount'):\n",
    "                ratingCount = i.contents[2].split()[0]\n",
    "            if i.find_all('meta',itemprop='reviewCount'):\n",
    "                reviewCount = i.contents[2].split()[0]\n",
    "    except:\n",
    "        ratings_reviews = ''\n",
    "\n",
    "    # if Published is not present, then set it to the empty string\n",
    "    try:        \n",
    "        pub = soup.find_all('div', class_='row')[1].contents[0].split()[1:4]\n",
    "        Published = ' '.join(pub) # join the list of publishers\n",
    "    except:\n",
    "        Published = ''\n",
    "    \n",
    "    # if Character is not present, then set it to the empty string\n",
    "    try:\n",
    "        char = soup.find_all('a', href=re.compile('characters')) # find the regular expression(re) 'characters' within the attribute href \n",
    "        if len(char) == 0:\n",
    "            Characters = '' # no characters in char\n",
    "        else:\n",
    "            Characters = ', '.join([i.contents[0] for i in char])\n",
    "    except:\n",
    "        Characters = '' # something went wrong with char\n",
    "    \n",
    "    # if Setting is not present, then set it to the empty string\n",
    "    try:\n",
    "        sett = soup.find_all('a', href=re.compile('places')) # find the regular expression(re) 'places' within the attribute href \n",
    "        if len(sett) == 0:\n",
    "            Setting = ''\n",
    "        else:\n",
    "            Setting = ', '.join([i.contents[0] for i in sett])\n",
    "    except:\n",
    "        Setting = '' # something went wrong with Setting\n",
    "    \n",
    "    # get the URL to the page\n",
    "    Url = soup.find_all('link', rel='canonical')[0].get('href')\n",
    "\n",
    "    return [bookTitle, bookSeries, bookAuthors, ratingValue, ratingCount, reviewCount, Plot, NumberofPages, Published, Characters, Setting, Url]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output of the function is structured in a manner that for each book, the extracted relevant information are in a tab separated values extensions ready to be feed-in for the next stage.\n",
    "During the scraping procedure, if the information we were seeking was not available then an empty string is returned and also books with a description written in a different language than in English were discarded. The code used to create the .tsv files is in `scripts.build_tsv`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Search Engine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we have collected all the raw HTML pages and scraped the target information, we apply some natural language processing (NLP) techniques in order to create the files which the search engine will work on.\n",
    "\n",
    "The text tools we use are available in the `ntlk` library:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk # Natural Language Toolkit\n",
    "nltk.download('punkt') # a library for tokenizing texts\n",
    "nltk.download('stopwords') # a library containg a list of stop-words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First thing first, it is worth to tokenize the text, i.e. split it into a list of single words, according to punctuation and words formation rules:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tokenize(text:str):\n",
    "    return nltk.word_tokenize(text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, we filter the words that contain alphanumeric characters only and we convert all of them into lower case: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def alphanum(text:list): \n",
    "    text_result = []\n",
    "    for w in text:\n",
    "        if w.isalnum():\n",
    "            text_result.append(w.lower()) # to transform all the characters in lower case\n",
    "    return text_result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The input text is full of very common words which, then, are very poor of information (according to the concept of self-information in information theory). These words are known as \"stop words\". The following function aims to remove all of them, comparing each word with a pre-build stopwords list: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stopwords(text:list):\n",
    "    text_result = []\n",
    "    stop_words = nltk.corpus.stopwords.words('english') # we select the stopwords of english language\n",
    "    for w in text:\n",
    "        if w not in stop_words:\n",
    "            text_result.append(w) # we filter out the stopwords\n",
    "    return text_result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The last step of the natural language processing pipeline that we reckon is useful at this point is the mapping of each word to its corresponding root, so that words derivated from the same root are mapped into it; e.g. verbs forms are mapped into the base form of the verb. This task can be carried out by two different techniques: the stemming and the lemmatization. The former applies to each word some fixed rules of words formation to remove prefixes and suffixes; it sometimes lacks in accuracy, giving in output not meaningful words, but it is quite fast. On the contrary, the latter is way more accurate because it considers a language’s vocabulary to apply a morphological analysis to words, but its application is slower. For the purpose of this excercise, a stemmer is enought. Again, it is easy to plug-in a lemmatizer instead of the stemmer for future needs, thanks to the modular nature of our code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stemming(text:list):\n",
    "    stemmer = nltk.stem.PorterStemmer()\n",
    "    return [stemmer.stem(w) for w in text]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, to summarize and to clarify, the NLP pipeline we follow is:\n",
    "1. tokenization\n",
    "2. alphanumeric filtering and lower case conversion\n",
    "3. stopwords removing\n",
    "4. stemming\n",
    "\n",
    "The function below summarizes this pipeline, taking as input a row text and giving as output the processed text:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pre_process(text:str):\n",
    "    return ' '.join(stemming(stopwords(alphanum(tokenize(text)))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the sake of grouping the functions above, we put them into the class `scripts.utilities.TextTools`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1. Conjunctive query"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this part, we import the following classes. The class `IndexBuilder` holds the logic to concatenate the books' dataset, to create the vocabulary and the inverted indexes.\n",
    "\n",
    "The class `TextTools`, as said before, is a utility class for applying the NLP."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scripts.index_creation import IndexBuilder # to create inverted indexes\n",
    "from scripts.utilities import TextTools # for text processing\n",
    "import pandas as pd\n",
    "\n",
    "pd.set_option(\"display.max_colwidth\", 102)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.1.1) Create your index!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We start getting an instance of the class `IndexBuilder`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "index_builder = IndexBuilder()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the following code line we concatenate into a dataset the content of all the .tsv files."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = index_builder.concatenate_dataset('./data/tsv/*/*.tsv', fields=None) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to avoid errors, we filter out the records that might have no plot. Even thought we filtered the books without a valid description, two books appear to have a blank description, perhaps due to the structure of `pandas.DataFrame`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = dataset[dataset['Plot'].notnull()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": true
   },
   "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>bookTitle</th>\n",
       "      <th>bookSeries</th>\n",
       "      <th>bookAuthors</th>\n",
       "      <th>ratingValue</th>\n",
       "      <th>ratingCount</th>\n",
       "      <th>reviewCount</th>\n",
       "      <th>Plot</th>\n",
       "      <th>NumberofPages</th>\n",
       "      <th>Published</th>\n",
       "      <th>Characters</th>\n",
       "      <th>Setting</th>\n",
       "      <th>Url</th>\n",
       "      <th>file_num</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>The Hunger Games</td>\n",
       "      <td>The Hunger Games #1</td>\n",
       "      <td>Suzanne Collins</td>\n",
       "      <td>4.33</td>\n",
       "      <td>6,413,302</td>\n",
       "      <td>172,615</td>\n",
       "      <td>Could you survive on your own in the wild, with every one out to make sure you don't live to see t...</td>\n",
       "      <td>374.0</td>\n",
       "      <td>September 14th 2008</td>\n",
       "      <td>Katniss Everdeen, Peeta Mellark, Cato (Hunger Games), Primrose Everdeen, Gale Hawthorne, Effie Tri...</td>\n",
       "      <td>District 12, Panem, Capitol, Panem, Panem</td>\n",
       "      <td>https://www.goodreads.com/book/show/2767052-the-hunger-games</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Harry Potter and the Order of the Phoenix</td>\n",
       "      <td>Harry Potter #5</td>\n",
       "      <td>J.K. Rowling</td>\n",
       "      <td>4.50</td>\n",
       "      <td>2,527,001</td>\n",
       "      <td>42,768</td>\n",
       "      <td>There is a door at the end of a silent corridor. And it’s haunting Harry Pottter’s dreams. Why els...</td>\n",
       "      <td>870.0</td>\n",
       "      <td>September 2004 by</td>\n",
       "      <td>Sirius Black, Draco Malfoy, Ron Weasley, Petunia Dursley, Vernon Dursley, Dudley Dursley, Severus ...</td>\n",
       "      <td>Hogwarts School of Witchcraft and Wizardry, London, England</td>\n",
       "      <td>https://www.goodreads.com/book/show/2.Harry_Potter_and_the_Order_of_the_Phoenix</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>To Kill a Mockingbird</td>\n",
       "      <td>To Kill a Mockingbird</td>\n",
       "      <td>Harper Lee</td>\n",
       "      <td>4.28</td>\n",
       "      <td>4,530,963</td>\n",
       "      <td>91,866</td>\n",
       "      <td>The unforgettable novel of a childhood in a sleepy Southern town and the crisis of conscience that...</td>\n",
       "      <td>324.0</td>\n",
       "      <td>May 23rd 2006</td>\n",
       "      <td>Scout Finch, Atticus Finch, Jem Finch, Arthur Radley, Mayella Ewell, Aunt Alexandra, Bob Ewell, Ca...</td>\n",
       "      <td>Maycomb, Alabama</td>\n",
       "      <td>https://www.goodreads.com/book/show/2657.To_Kill_a_Mockingbird</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Pride and Prejudice</td>\n",
       "      <td>NaN</td>\n",
       "      <td>Jane Austen</td>\n",
       "      <td>4.26</td>\n",
       "      <td>3,020,392</td>\n",
       "      <td>67,869</td>\n",
       "      <td>Alternate cover edition of ISBN 9780679783268Since its immediate success in 1813, Pride and Prejud...</td>\n",
       "      <td>279.0</td>\n",
       "      <td>October 10th 2000</td>\n",
       "      <td>Mr. Bennet, Mrs. Bennet, Jane Bennet, Elizabeth Bennet, Mary Bennet, Kitty Bennet, Lydia Bennet, L...</td>\n",
       "      <td>United Kingdom, Derbyshire, England, England, Hertfordshire, England</td>\n",
       "      <td>https://www.goodreads.com/book/show/1885.Pride_and_Prejudice</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Twilight</td>\n",
       "      <td>The Twilight Saga #1</td>\n",
       "      <td>Stephenie Meyer</td>\n",
       "      <td>3.60</td>\n",
       "      <td>4,993,492</td>\n",
       "      <td>104,954</td>\n",
       "      <td>About three things I was absolutely positive.First, Edward was a vampire.Second, there was a part ...</td>\n",
       "      <td>501.0</td>\n",
       "      <td>September 6th 2006</td>\n",
       "      <td>Edward Cullen, Jacob Black, Laurent, Renee, Bella Swan, Billy Black, Esme Cullen, Alice Cullen, Ja...</td>\n",
       "      <td>Forks, Washington, Phoenix, Arizona, Washington (state)</td>\n",
       "      <td>https://www.goodreads.com/book/show/41865.Twilight</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                   bookTitle             bookSeries  \\\n",
       "0                           The Hunger Games    The Hunger Games #1   \n",
       "1  Harry Potter and the Order of the Phoenix        Harry Potter #5   \n",
       "2                      To Kill a Mockingbird  To Kill a Mockingbird   \n",
       "3                        Pride and Prejudice                    NaN   \n",
       "4                                   Twilight   The Twilight Saga #1   \n",
       "\n",
       "       bookAuthors  ratingValue ratingCount reviewCount  \\\n",
       "0  Suzanne Collins         4.33   6,413,302     172,615   \n",
       "1     J.K. Rowling         4.50   2,527,001      42,768   \n",
       "2       Harper Lee         4.28   4,530,963      91,866   \n",
       "3      Jane Austen         4.26   3,020,392      67,869   \n",
       "4  Stephenie Meyer         3.60   4,993,492     104,954   \n",
       "\n",
       "                                                                                                    Plot  \\\n",
       "0  Could you survive on your own in the wild, with every one out to make sure you don't live to see t...   \n",
       "1  There is a door at the end of a silent corridor. And it’s haunting Harry Pottter’s dreams. Why els...   \n",
       "2  The unforgettable novel of a childhood in a sleepy Southern town and the crisis of conscience that...   \n",
       "3  Alternate cover edition of ISBN 9780679783268Since its immediate success in 1813, Pride and Prejud...   \n",
       "4  About three things I was absolutely positive.First, Edward was a vampire.Second, there was a part ...   \n",
       "\n",
       "   NumberofPages            Published  \\\n",
       "0          374.0  September 14th 2008   \n",
       "1          870.0    September 2004 by   \n",
       "2          324.0        May 23rd 2006   \n",
       "3          279.0    October 10th 2000   \n",
       "4          501.0   September 6th 2006   \n",
       "\n",
       "                                                                                              Characters  \\\n",
       "0  Katniss Everdeen, Peeta Mellark, Cato (Hunger Games), Primrose Everdeen, Gale Hawthorne, Effie Tri...   \n",
       "1  Sirius Black, Draco Malfoy, Ron Weasley, Petunia Dursley, Vernon Dursley, Dudley Dursley, Severus ...   \n",
       "2  Scout Finch, Atticus Finch, Jem Finch, Arthur Radley, Mayella Ewell, Aunt Alexandra, Bob Ewell, Ca...   \n",
       "3  Mr. Bennet, Mrs. Bennet, Jane Bennet, Elizabeth Bennet, Mary Bennet, Kitty Bennet, Lydia Bennet, L...   \n",
       "4  Edward Cullen, Jacob Black, Laurent, Renee, Bella Swan, Billy Black, Esme Cullen, Alice Cullen, Ja...   \n",
       "\n",
       "                                                                Setting  \\\n",
       "0                             District 12, Panem, Capitol, Panem, Panem   \n",
       "1           Hogwarts School of Witchcraft and Wizardry, London, England   \n",
       "2                                                      Maycomb, Alabama   \n",
       "3  United Kingdom, Derbyshire, England, England, Hertfordshire, England   \n",
       "4               Forks, Washington, Phoenix, Arizona, Washington (state)   \n",
       "\n",
       "                                                                               Url  \\\n",
       "0                     https://www.goodreads.com/book/show/2767052-the-hunger-games   \n",
       "1  https://www.goodreads.com/book/show/2.Harry_Potter_and_the_Order_of_the_Phoenix   \n",
       "2                   https://www.goodreads.com/book/show/2657.To_Kill_a_Mockingbird   \n",
       "3                     https://www.goodreads.com/book/show/1885.Pride_and_Prejudice   \n",
       "4                               https://www.goodreads.com/book/show/41865.Twilight   \n",
       "\n",
       "   file_num  \n",
       "0         1  \n",
       "1         2  \n",
       "2         3  \n",
       "3         4  \n",
       "4         5  "
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dataset.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "The column `file_num` contains the position in the books' ranking. The `dataset` is sorted by this column."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, we make a copy of the dataset not to modify the column `Plot`, that we will use later. On the copy we apply the NLP techniques."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset_preprocessed = dataset.copy()\n",
    "dataset_preprocessed['Plot'] = dataset_preprocessed['Plot'].map(TextTools.pre_process)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At this point, we create the vocabulary file using `IndexBuilder.create_vocabulary(..)` and we save it into the folder `./data`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "index_builder.create_vocabulary(dataset_preprocessed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, we create the first inverted index in order to create our search engine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "index_builder.create_index(dataset_preprocessed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The inverted index has the format\n",
    "\n",
    "```json\n",
    "{\n",
    "term_id_1:[document_1, document_2, document_4],\n",
    "term_id_2:[document_1, document_3, document_5, document_6],\n",
    "...}\n",
    "```\n",
    "and is saved as a JSON file. We chose this file extension to ease the reading/writing operations, since the conversion between JSON and Python `dict()` is straightforward."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.1.2) Execute the query"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We wrote the class `SearchEngine` to handle the research of the queries. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scripts.search_engine import SearchEngine\n",
    "\n",
    "search_engine = SearchEngine()\n",
    "search_engine.select_mode(use_tfidf=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the method `select_mode(..)` we change the behaviour of the object `search_engine`: for the present task we set the `use_tfidf` parameter to `False` to leverage the simple inverted index we created in the previous subpoint.\n",
    "<br><br><br>\n",
    "At this point, we can test the search engine:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hunger games\n"
     ]
    }
   ],
   "source": [
    "query = input()\n",
    "result = search_engine.search(query, dataset)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "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>bookTitle</th>\n",
       "      <th>Plot</th>\n",
       "      <th>Url</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>The Hunger Games</td>\n",
       "      <td>Could you survive on your own in the wild, with every one out to make sure you don't live to see t...</td>\n",
       "      <td>https://www.goodreads.com/book/show/2767052-the-hunger-games</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>183</th>\n",
       "      <td>The Hunger Games Trilogy Boxset</td>\n",
       "      <td>The extraordinary, ground breaking New York Times bestsellers The Hunger Games and Catching Fire, ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/7938275-the-hunger-games-trilogy-boxset</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>219</th>\n",
       "      <td>Catching Fire</td>\n",
       "      <td>SPARKS ARE IGNITING.FLAMES ARE SPREADING.AND THE CAPITAL WANTS REVENGE.Against all odds, Katniss E...</td>\n",
       "      <td>https://www.goodreads.com/book/show/6148028-catching-fire</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>315</th>\n",
       "      <td>Mockingjay</td>\n",
       "      <td>The final book in the ground-breaking HUNGER GAMES trilogy, this new foiled edition of MOCKINGJAY ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/7260188-mockingjay</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1301</th>\n",
       "      <td>Crossing the Seas: A Diary of My Thoughts</td>\n",
       "      <td>About the book (A teaser) \"Crossing the Seas: A Diary of My Thoughts\" \"We can forgive a child who ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/16243767-crossing-the-seas</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1421</th>\n",
       "      <td>Sliding on the Snow Stone</td>\n",
       "      <td>It is astonishing that anyone lived this story. It is even more astonishing that anyone survived i...</td>\n",
       "      <td>https://www.goodreads.com/book/show/12853168-sliding-on-the-snow-stone</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2261</th>\n",
       "      <td>Best Served Cold</td>\n",
       "      <td>Springtime in Styria. And that means war. Springtime in Styria. And that means revenge.There have ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/2315892.Best_Served_Cold</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2868</th>\n",
       "      <td>Morning Star</td>\n",
       "      <td>#1 NEW YORK TIMES BESTSELLER • Red Rising thrilled readers and announced the presence of a talente...</td>\n",
       "      <td>https://www.goodreads.com/book/show/18966806-morning-star</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4457</th>\n",
       "      <td>The Hunger Games: Official Illustrated Movie Companion</td>\n",
       "      <td>Go behind the scenes of the making of The Hunger Games with exclusive images and interviews. From ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/11742691-the-hunger-games</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4508</th>\n",
       "      <td>The Maze Runner Trilogy (Maze Runner, #1-3)</td>\n",
       "      <td>The perfect gift for fans of The Hunger Games and Divergent, this boxed set of the paperback editi...</td>\n",
       "      <td>https://www.goodreads.com/book/show/17292676-the-maze-runner-trilogy</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                                   bookTitle  \\\n",
       "0                                           The Hunger Games   \n",
       "183                          The Hunger Games Trilogy Boxset   \n",
       "219                                            Catching Fire   \n",
       "315                                               Mockingjay   \n",
       "1301               Crossing the Seas: A Diary of My Thoughts   \n",
       "1421                               Sliding on the Snow Stone   \n",
       "2261                                        Best Served Cold   \n",
       "2868                                            Morning Star   \n",
       "4457  The Hunger Games: Official Illustrated Movie Companion   \n",
       "4508             The Maze Runner Trilogy (Maze Runner, #1-3)   \n",
       "\n",
       "                                                                                                       Plot  \\\n",
       "0     Could you survive on your own in the wild, with every one out to make sure you don't live to see t...   \n",
       "183   The extraordinary, ground breaking New York Times bestsellers The Hunger Games and Catching Fire, ...   \n",
       "219   SPARKS ARE IGNITING.FLAMES ARE SPREADING.AND THE CAPITAL WANTS REVENGE.Against all odds, Katniss E...   \n",
       "315   The final book in the ground-breaking HUNGER GAMES trilogy, this new foiled edition of MOCKINGJAY ...   \n",
       "1301  About the book (A teaser) \"Crossing the Seas: A Diary of My Thoughts\" \"We can forgive a child who ...   \n",
       "1421  It is astonishing that anyone lived this story. It is even more astonishing that anyone survived i...   \n",
       "2261  Springtime in Styria. And that means war. Springtime in Styria. And that means revenge.There have ...   \n",
       "2868  #1 NEW YORK TIMES BESTSELLER • Red Rising thrilled readers and announced the presence of a talente...   \n",
       "4457  Go behind the scenes of the making of The Hunger Games with exclusive images and interviews. From ...   \n",
       "4508  The perfect gift for fans of The Hunger Games and Divergent, this boxed set of the paperback editi...   \n",
       "\n",
       "                                                                              Url  \n",
       "0                    https://www.goodreads.com/book/show/2767052-the-hunger-games  \n",
       "183   https://www.goodreads.com/book/show/7938275-the-hunger-games-trilogy-boxset  \n",
       "219                     https://www.goodreads.com/book/show/6148028-catching-fire  \n",
       "315                        https://www.goodreads.com/book/show/7260188-mockingjay  \n",
       "1301               https://www.goodreads.com/book/show/16243767-crossing-the-seas  \n",
       "1421       https://www.goodreads.com/book/show/12853168-sliding-on-the-snow-stone  \n",
       "2261                 https://www.goodreads.com/book/show/2315892.Best_Served_Cold  \n",
       "2868                    https://www.goodreads.com/book/show/18966806-morning-star  \n",
       "4457                https://www.goodreads.com/book/show/11742691-the-hunger-games  \n",
       "4508         https://www.goodreads.com/book/show/17292676-the-maze-runner-trilogy  "
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We chose to show the first 10 results in the same order they appear in the site's list. As we can see, the search gives us the books that contain both \"hunger\" and \"games\" in the plot."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2) Conjunctive query & Ranking score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, for each document and word we take in consideration the TF-IDF score and we select the top k books that have the highest cosine similarity.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.2.1) Inverted index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We create the second inverted index."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "25821it [00:24, 1064.29it/s]\n"
     ]
    }
   ],
   "source": [
    "index_builder.create_index_tfidf(dataset_preprocessed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The inverted index has the format\n",
    "\n",
    "```\n",
    "{\n",
    "term_id_1:[(document1, tfIdf_{term,document1}), (document2, tfIdf_{term,document2}), (document4, tfIdf_{term,document4}), ...],\n",
    "term_id_2:[(document1, tfIdf_{term,document1}), (document3, tfIdf_{term,document3}), (document5, tfIdf_{term,document5}), (document6, tfIdf_{term,document6}), ...],\n",
    "...}\n",
    "```\n",
    "and, as before, is saved into JSON file."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.2.2) Execute the query"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this task, we switch the mode of the `search_engine`, so that it works on the second inverted index."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "search_engine.select_mode(use_tfidf=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>\n",
    "Now, we are ready to test our search engine again. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hunger games\n"
     ]
    },
    {
     "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>bookTitle</th>\n",
       "      <th>Plot</th>\n",
       "      <th>Url</th>\n",
       "      <th>Similarity</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>25651</th>\n",
       "      <td>The Hunger Games Tribute Guide</td>\n",
       "      <td>The New York Times bestselling Hunger Games is now a major motion picture—and here is the ultimate...</td>\n",
       "      <td>https://www.goodreads.com/book/show/13027304-the-hunger-games-tribute-guide</td>\n",
       "      <td>0.670</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>183</th>\n",
       "      <td>The Hunger Games Trilogy Boxset</td>\n",
       "      <td>The extraordinary, ground breaking New York Times bestsellers The Hunger Games and Catching Fire, ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/7938275-the-hunger-games-trilogy-boxset</td>\n",
       "      <td>0.625</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11199</th>\n",
       "      <td>Throne of Glass Collection</td>\n",
       "      <td>Perfect for the Fans of Hunger Games, Game Of Throne, Throne Of Glass Series Collection 3 Books Se...</td>\n",
       "      <td>https://www.goodreads.com/book/show/26309016-throne-of-glass-collection</td>\n",
       "      <td>0.403</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4457</th>\n",
       "      <td>The Hunger Games: Official Illustrated Movie Companion</td>\n",
       "      <td>Go behind the scenes of the making of The Hunger Games with exclusive images and interviews. From ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/11742691-the-hunger-games</td>\n",
       "      <td>0.378</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>315</th>\n",
       "      <td>Mockingjay</td>\n",
       "      <td>The final book in the ground-breaking HUNGER GAMES trilogy, this new foiled edition of MOCKINGJAY ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/7260188-mockingjay</td>\n",
       "      <td>0.378</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4949</th>\n",
       "      <td>SAMPLER ONLY: Catching Fire (The Hunger Games, #2)</td>\n",
       "      <td>Against all odds, Katniss Everdeen has won the annual Hunger Games with fellow district tribute Pe...</td>\n",
       "      <td>https://www.goodreads.com/book/show/20349441-sampler-only</td>\n",
       "      <td>0.368</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6437</th>\n",
       "      <td>Catching Fire: The Official Illustrated Movie Companion</td>\n",
       "      <td>Catching Fire, the New York Times bestseller by Suzanne Collins, is now a major motion picture -- ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/17623910-catching-fire</td>\n",
       "      <td>0.273</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>23555</th>\n",
       "      <td>The Dust Lands Trilogy: Blood Red Road; Rebel Heart; Raging Star (Dust Lands, #1-3)</td>\n",
       "      <td>All three books in the highly praised Dust Lands trilogy, which MTV’s Hollywood Crush blog called ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/24885710-the-dust-lands-trilogy</td>\n",
       "      <td>0.269</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>The Hunger Games</td>\n",
       "      <td>Could you survive on your own in the wild, with every one out to make sure you don't live to see t...</td>\n",
       "      <td>https://www.goodreads.com/book/show/2767052-the-hunger-games</td>\n",
       "      <td>0.262</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9310</th>\n",
       "      <td>Eeny Meeny</td>\n",
       "      <td>The \"dark, twisted, thought-provoking\" (#1 New York Times bestseller Tami Hoag) international best...</td>\n",
       "      <td>https://www.goodreads.com/book/show/23398806-eeny-meeny</td>\n",
       "      <td>0.258</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                                                                 bookTitle  \\\n",
       "25651                                                       The Hunger Games Tribute Guide   \n",
       "183                                                        The Hunger Games Trilogy Boxset   \n",
       "11199                                                           Throne of Glass Collection   \n",
       "4457                                The Hunger Games: Official Illustrated Movie Companion   \n",
       "315                                                                             Mockingjay   \n",
       "4949                                    SAMPLER ONLY: Catching Fire (The Hunger Games, #2)   \n",
       "6437                               Catching Fire: The Official Illustrated Movie Companion   \n",
       "23555  The Dust Lands Trilogy: Blood Red Road; Rebel Heart; Raging Star (Dust Lands, #1-3)   \n",
       "0                                                                         The Hunger Games   \n",
       "9310                                                                            Eeny Meeny   \n",
       "\n",
       "                                                                                                        Plot  \\\n",
       "25651  The New York Times bestselling Hunger Games is now a major motion picture—and here is the ultimate...   \n",
       "183    The extraordinary, ground breaking New York Times bestsellers The Hunger Games and Catching Fire, ...   \n",
       "11199  Perfect for the Fans of Hunger Games, Game Of Throne, Throne Of Glass Series Collection 3 Books Se...   \n",
       "4457   Go behind the scenes of the making of The Hunger Games with exclusive images and interviews. From ...   \n",
       "315    The final book in the ground-breaking HUNGER GAMES trilogy, this new foiled edition of MOCKINGJAY ...   \n",
       "4949   Against all odds, Katniss Everdeen has won the annual Hunger Games with fellow district tribute Pe...   \n",
       "6437   Catching Fire, the New York Times bestseller by Suzanne Collins, is now a major motion picture -- ...   \n",
       "23555  All three books in the highly praised Dust Lands trilogy, which MTV’s Hollywood Crush blog called ...   \n",
       "0      Could you survive on your own in the wild, with every one out to make sure you don't live to see t...   \n",
       "9310   The \"dark, twisted, thought-provoking\" (#1 New York Times bestseller Tami Hoag) international best...   \n",
       "\n",
       "                                                                               Url  \\\n",
       "25651  https://www.goodreads.com/book/show/13027304-the-hunger-games-tribute-guide   \n",
       "183    https://www.goodreads.com/book/show/7938275-the-hunger-games-trilogy-boxset   \n",
       "11199      https://www.goodreads.com/book/show/26309016-throne-of-glass-collection   \n",
       "4457                 https://www.goodreads.com/book/show/11742691-the-hunger-games   \n",
       "315                         https://www.goodreads.com/book/show/7260188-mockingjay   \n",
       "4949                     https://www.goodreads.com/book/show/20349441-sampler-only   \n",
       "6437                    https://www.goodreads.com/book/show/17623910-catching-fire   \n",
       "23555          https://www.goodreads.com/book/show/24885710-the-dust-lands-trilogy   \n",
       "0                     https://www.goodreads.com/book/show/2767052-the-hunger-games   \n",
       "9310                       https://www.goodreads.com/book/show/23398806-eeny-meeny   \n",
       "\n",
       "       Similarity  \n",
       "25651       0.670  \n",
       "183         0.625  \n",
       "11199       0.403  \n",
       "4457        0.378  \n",
       "315         0.378  \n",
       "4949        0.368  \n",
       "6437        0.273  \n",
       "23555       0.269  \n",
       "0           0.262  \n",
       "9310        0.258  "
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "query = input()\n",
    "result = search_engine.search(query, dataset, k=10)\n",
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Define a new score!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this part, we take into account the result of the top k documents with the highest cosine similarity computed on the `Plot` column, sorted by a new custom metric.\n",
    "\n",
    "For the new score, we consider a linear combination defined as:\n",
    "\n",
    "$\n",
    "newScore = similarity_{Plot} \\cdot 0.4 + score_{Title} \\cdot 0.3 + score_{Authors} \\cdot 0.07 + score_{Characters} \\cdot 0.05 + score_{Series} \\cdot 0.03 +\\\\ 0.15 \\cdot \\left(\\frac{ratingValue}{5} \\cdot \\frac{30001 - fileNum}{30000}\\right), \n",
    "$\n",
    "\n",
    "having\n",
    "\n",
    "$\n",
    "    similarity_{Plot} = \\frac{\\sum_i p_i \\cdot q_i}{\\sqrt{\\sum_i q_i^2} \\cdot \\sqrt{\\sum_i p_i^2}} \\\\\n",
    "    score_{Title} = 1 \\text{ if at least one word is in Title, } 0 \\text{ otherwise.} \\\\\n",
    "    score_{Authors} = 1 \\text{ if at least one word is in Authors, } 0 \\text{ otherwise.} \\\\\n",
    "    score_{Characters} = 1 \\text{ if at least one word is in Characters, } 0 \\text{ otherwise.} \\\\\n",
    "    score_{Series} = 1 \\text{ if at least one word is in Series, } 0 \\text{ otherwise.} \n",
    "$\n",
    "\n",
    "The weights of the scores are assigned considering the specificity and the \"importance\" of the field; so, we weight more the `Plot` and the `Title`. We also consider the rating of the book - the higher, the more relevant - and the position of the book in the GoodReads ranking: the books in the first pages of the site probably are more interesting or more appreciated.\n",
    "\n",
    "Moreover, as suggested during the lectures, since $\\sqrt{\\sum_i q_i^2}$ is invariant with respect to all the documents, we decided to ignore it. We decided also not to consider the term frequency and the inverse document frequency for the query vector; thus, each of the component of query vector is equal to 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hunger games\n",
      "collins catching katniss\n"
     ]
    },
    {
     "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>bookTitle</th>\n",
       "      <th>Plot</th>\n",
       "      <th>Url</th>\n",
       "      <th>Similarity</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>4949</th>\n",
       "      <td>SAMPLER ONLY: Catching Fire (The Hunger Games, #2)</td>\n",
       "      <td>Against all odds, Katniss Everdeen has won the annual Hunger Games with fellow district tribute Pe...</td>\n",
       "      <td>https://www.goodreads.com/book/show/20349441-sampler-only</td>\n",
       "      <td>0.629</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6437</th>\n",
       "      <td>Catching Fire: The Official Illustrated Movie Companion</td>\n",
       "      <td>Catching Fire, the New York Times bestseller by Suzanne Collins, is now a major motion picture -- ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/17623910-catching-fire</td>\n",
       "      <td>0.514</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>183</th>\n",
       "      <td>The Hunger Games Trilogy Boxset</td>\n",
       "      <td>The extraordinary, ground breaking New York Times bestsellers The Hunger Games and Catching Fire, ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/7938275-the-hunger-games-trilogy-boxset</td>\n",
       "      <td>0.504</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>315</th>\n",
       "      <td>Mockingjay</td>\n",
       "      <td>The final book in the ground-breaking HUNGER GAMES trilogy, this new foiled edition of MOCKINGJAY ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/7260188-mockingjay</td>\n",
       "      <td>0.391</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>The Hunger Games</td>\n",
       "      <td>Could you survive on your own in the wild, with every one out to make sure you don't live to see t...</td>\n",
       "      <td>https://www.goodreads.com/book/show/2767052-the-hunger-games</td>\n",
       "      <td>0.355</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>25651</th>\n",
       "      <td>The Hunger Games Tribute Guide</td>\n",
       "      <td>The New York Times bestselling Hunger Games is now a major motion picture—and here is the ultimate...</td>\n",
       "      <td>https://www.goodreads.com/book/show/13027304-the-hunger-games-tribute-guide</td>\n",
       "      <td>0.269</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4457</th>\n",
       "      <td>The Hunger Games: Official Illustrated Movie Companion</td>\n",
       "      <td>Go behind the scenes of the making of The Hunger Games with exclusive images and interviews. From ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/11742691-the-hunger-games</td>\n",
       "      <td>0.265</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11199</th>\n",
       "      <td>Throne of Glass Collection</td>\n",
       "      <td>Perfect for the Fans of Hunger Games, Game Of Throne, Throne Of Glass Series Collection 3 Books Se...</td>\n",
       "      <td>https://www.goodreads.com/book/show/26309016-throne-of-glass-collection</td>\n",
       "      <td>0.246</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9310</th>\n",
       "      <td>Eeny Meeny</td>\n",
       "      <td>The \"dark, twisted, thought-provoking\" (#1 New York Times bestseller Tami Hoag) international best...</td>\n",
       "      <td>https://www.goodreads.com/book/show/23398806-eeny-meeny</td>\n",
       "      <td>0.181</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>23555</th>\n",
       "      <td>The Dust Lands Trilogy: Blood Red Road; Rebel Heart; Raging Star (Dust Lands, #1-3)</td>\n",
       "      <td>All three books in the highly praised Dust Lands trilogy, which MTV’s Hollywood Crush blog called ...</td>\n",
       "      <td>https://www.goodreads.com/book/show/24885710-the-dust-lands-trilogy</td>\n",
       "      <td>0.120</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                                                                 bookTitle  \\\n",
       "4949                                    SAMPLER ONLY: Catching Fire (The Hunger Games, #2)   \n",
       "6437                               Catching Fire: The Official Illustrated Movie Companion   \n",
       "183                                                        The Hunger Games Trilogy Boxset   \n",
       "315                                                                             Mockingjay   \n",
       "0                                                                         The Hunger Games   \n",
       "25651                                                       The Hunger Games Tribute Guide   \n",
       "4457                                The Hunger Games: Official Illustrated Movie Companion   \n",
       "11199                                                           Throne of Glass Collection   \n",
       "9310                                                                            Eeny Meeny   \n",
       "23555  The Dust Lands Trilogy: Blood Red Road; Rebel Heart; Raging Star (Dust Lands, #1-3)   \n",
       "\n",
       "                                                                                                        Plot  \\\n",
       "4949   Against all odds, Katniss Everdeen has won the annual Hunger Games with fellow district tribute Pe...   \n",
       "6437   Catching Fire, the New York Times bestseller by Suzanne Collins, is now a major motion picture -- ...   \n",
       "183    The extraordinary, ground breaking New York Times bestsellers The Hunger Games and Catching Fire, ...   \n",
       "315    The final book in the ground-breaking HUNGER GAMES trilogy, this new foiled edition of MOCKINGJAY ...   \n",
       "0      Could you survive on your own in the wild, with every one out to make sure you don't live to see t...   \n",
       "25651  The New York Times bestselling Hunger Games is now a major motion picture—and here is the ultimate...   \n",
       "4457   Go behind the scenes of the making of The Hunger Games with exclusive images and interviews. From ...   \n",
       "11199  Perfect for the Fans of Hunger Games, Game Of Throne, Throne Of Glass Series Collection 3 Books Se...   \n",
       "9310   The \"dark, twisted, thought-provoking\" (#1 New York Times bestseller Tami Hoag) international best...   \n",
       "23555  All three books in the highly praised Dust Lands trilogy, which MTV’s Hollywood Crush blog called ...   \n",
       "\n",
       "                                                                               Url  \\\n",
       "4949                     https://www.goodreads.com/book/show/20349441-sampler-only   \n",
       "6437                    https://www.goodreads.com/book/show/17623910-catching-fire   \n",
       "183    https://www.goodreads.com/book/show/7938275-the-hunger-games-trilogy-boxset   \n",
       "315                         https://www.goodreads.com/book/show/7260188-mockingjay   \n",
       "0                     https://www.goodreads.com/book/show/2767052-the-hunger-games   \n",
       "25651  https://www.goodreads.com/book/show/13027304-the-hunger-games-tribute-guide   \n",
       "4457                 https://www.goodreads.com/book/show/11742691-the-hunger-games   \n",
       "11199      https://www.goodreads.com/book/show/26309016-throne-of-glass-collection   \n",
       "9310                       https://www.goodreads.com/book/show/23398806-eeny-meeny   \n",
       "23555          https://www.goodreads.com/book/show/24885710-the-dust-lands-trilogy   \n",
       "\n",
       "       Similarity  \n",
       "4949        0.629  \n",
       "6437        0.514  \n",
       "183         0.504  \n",
       "315         0.391  \n",
       "0           0.355  \n",
       "25651       0.269  \n",
       "4457        0.265  \n",
       "11199       0.246  \n",
       "9310        0.181  \n",
       "23555       0.120  "
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "query = input()\n",
    "additional_query = input()\n",
    "search_engine.search(query, dataset, k=10, new_score=True, additional_query=additional_query)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Algorithmic Question"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This problem can be solved with a recursive approach.\n",
    "\n",
    "Given a string $S$ and $i\\in [0,length(S)]$, let $X[i]$ be the length of the longest increasing subsequence ending at position $i$. \n",
    "\n",
    "Then, $X[i]=1+\\max\\{X[j]; j\\in[0,i-1] : S[j]<S[i]\\}$.\n",
    "\n",
    "The recursive solution is the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_len = 1\n",
    "\n",
    "def max_length_recursive(s, i):\n",
    "    global max_len\n",
    "    max_len_i = 1\n",
    "    for j in range(0, i):\n",
    "        res = max_length_recursive(s, j)\n",
    "        if s[j] < s[i]:\n",
    "            if res+1 > max_len_i:\n",
    "                max_len_i = res + 1\n",
    "    max_len = max(max_len, max_len_i)\n",
    "    return max_len_i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_length(s):\n",
    "    max_len = 0\n",
    "    for i in range(1, len(s)):\n",
    "        res = max_length_recursive(s, i)\n",
    "        if res > max_len:\n",
    "            max_len = res\n",
    "    return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = 'ZQABWARSTA' # 'CADFECEILGJHABNOPSTIRYOEABILCNR'\n",
    "max_length_recursive(s, len(s)-1)\n",
    "max_len"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The time complexity for the recursive technique is of $O(2^n)$, which is exponential. For larger values of n, there will be many values for which the function has to be repeated and thus this approach results to be inefficient and may not give a result in reasonable time. For example, the algorithm gives the right answer with short strings like `ZQABWARSTA`, while it doesn't terminate with the string `CADFECEILGJHABNOPSTIRYOEABILCNR`. Indeed, in the latter case, the time taken by the algorithm is $2^{31}$!\n",
    "\n",
    "<center>\n",
    "$\n",
    "T(n)=c + \\sum_{i=1}^{n-1}T(i) = c + T(n-1) + \\sum_{i=1}^{n-2}T(i) =\\\\\n",
    "= c + \\sum_{i=1}^{n-2}T(i) + \\sum_{i=1}^{n-2}T(i) =\\\\\n",
    "= c + 2 \\cdot \\left(\\sum_{i=1}^{n-2}T(i)\\right) =\\\\\n",
    "= c + 2 \\cdot \\left(T(n-2) + \\sum_{i=1}^{n-3}T(i)\\right) =\\\\\n",
    "= c + 2 \\cdot \\left(c + \\sum_{i=1}^{n-3}T(i) + \\sum_{i=1}^{n-3}T(i)\\right) =\\\\\n",
    "= c + 4 \\cdot \\left(\\sum_{i=1}^{n-3}T(i)\\right) = ... \\approx 2^n\n",
    "$\n",
    "</center>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def max_length_dynamic(str):\n",
    "    n = len(str)\n",
    "    # Declare the list (array) for LIS and\n",
    "    # initialize LIS values for all indexes\n",
    "    lis = [1] * n\n",
    "    # Compute optimized LIS values in bottom up manner\n",
    "    for i in range(1, n):\n",
    "        for j in range(0, i):\n",
    "            if str[i] > str[j] and lis[i] < lis[j] + 1:\n",
    "                lis[i] = lis[j] + 1\n",
    "    # Initialize maximum to 0 to get\n",
    "    # the maximum of all LIS\n",
    "    maximum = 0\n",
    "    # Pick maximum of all LIS values\n",
    "    for i in range(n):\n",
    "        maximum = max(maximum, lis[i])\n",
    "    return maximum\n",
    "\n",
    "\n",
    "max_length_dynamic(\"CADFECEILGJHABNOPSTIRYOEABILCNR\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On the contrary, using  the bottom-up approach of the dynamic programming we can improve the time complexity of the algorithm to the order of $O(n^2)$. This approch takes into account the result of the subproblems, without recomputing them each time. Then, the complexity is only due to the 2 nested loops."
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}