<jupyter_start><jupyter_text>Homework 3 - Which book would you recomend?Jupyter Notebook of the third homework, finished by <NAME> and <NAME> ![alt text](https://camo.githubusercontent.com/406644a4e60cd793ef853c47ee30ec2206f3b87081731fb80976824b56417a41/68747470733a2f2f73323938322e7063646e2e636f2f77702d636f6e74656e742f75706c6f6164732f323031352f31322f676f6f6472656164732d65313435373535353432343738302e6a70672e6f7074696d616c2e6a7067) List of all the imported libraries<jupyter_code>from bs4 import BeautifulSoup
import requests
import urllib.request
from urllib.request import urlopen
import os
import regex as re
from langdetect import detect
import csv
import pandas as pd
import inflect #convert the numbers into words
from nltk.stem.porter import PorterStemmer 
from nltk.tokenize import word_tokenize 
from nltk.corpus import stopwords 
import nltk
import string
from pandas import DataFrame
from collections import defaultdict
import pickle
import math
import numpy as np
import heapq<jupyter_output><empty_output><jupyter_text>1. Data collection  1.1 Get the list of booksWe start taking the url of the first 300 books, from the list of [**the best book ever**](https://www.goodreads.com/list/show/1.Best_Books_Ever?page=1)We save them in a .txt file<jupyter_code>web_page = requests.get("https://www.goodreads.com/list/show/1.Best_Books_Ever?page=1")

def get_url(url):
    req = urllib.request.Request(url)
    return urllib.request.urlopen(req)

def listToString(s):  
    
    # initialize an empty string 
    str1 = "\n"
  
    return (str1.join(s))
page = 1
books_urls = []

while (page <= 300):
    web_page = requests.get("https://www.goodreads.com/list/show/1.Best_Books_Ever?page={}".format(page))
    soup = BeautifulSoup(web_page.content, features="lxml")
    
    for link in soup.find_all('a', class_='bookTitle', itemprop = 'url', href = True):
        url = link.get('href')
        url = "https://www.goodreads.com/"+url
        books_urls.append(url)

    str_book_links = listToString(books_urls)
    page+=1
#save all links found into a file.txt
f = open("BookLinks.txt", "w")
f.write(str_book_links)
f.close()<jupyter_output><empty_output><jupyter_text>1.2. Crawl booksWe download the htlm of each book in the first 300 pages.To store the code, we create some folders, named as "HTLMSources_Page" (with number of page), and in each one we saved the htmls of each page as "Book_Page" with the number of books and pages.To do this we split the work, we crawled 150 pages for each.<jupyter_code>page = 1
htmls = []
while page <= 300:
    
    directory = "HTMLSources_Page"+str(page)
    parent_dir = "E:\\HW3"
    path = os.path.join(parent_dir, directory)
    os.mkdir(path)
    
    web_page = requests.get("https://www.goodreads.com/list/show/1.Best_Books_Ever?page={}".format(page))
    soup = BeautifulSoup(web_page.content, features="lxml")
    
    i = 1
    
    for link in soup.find_all('a', class_='bookTitle', itemprop = 'url', href = True):
        url = link.get('href')
        url = "https://www.goodreads.com/"+url
        html = urllib.request.urlopen(url).read()
        html_formatted = html.decode("utf-8")
        
        namefile = "Book"+str(i)+"_"+"Page"+str(page)
        with open(os.path.join(path,namefile), 'w') as f:
            f.write(str(html_formatted))
            f.close()
        i += 1
    
    page += 1<jupyter_output><empty_output><jupyter_text>1.3 Parse downloaded pagesWe start to extract the books informations we desire:- Title - Series - Author- Ratings, average stars - Number of givent ratings - Number of reviews - The entire plot - Number of pages - Published - Characters- Setting- UrlWe save each book as "article_i.tsv" with *i* number of article. We use langdetect to choose only the book in english. Because of the different encoding we have to use, we do a first check on book author and title, if they don't exist, we discard the book because it means that this book as a language with non-alphanumeric characters.<jupyter_code>#function to parse the html pages
def parse_pages(parent_dir):
    '''
    function to parse the downloded pages and take the infos we need
    input: parent_dir with the downloaded pages
    output: .tsv files
    '''
    p = 1 #pages, starting from 1
    n = 1 #index for the article's name
    
    while (p<=300):                                 #we start opening the folder related to a specific page
        directory = "HTMLSources_Page"+str(p)       #directory of the page
        path = os.path.join(parent_dir, directory)  #create path
        os.chdir(path)
        
        book_id = 1  #book id per page, starting from 1
        
        while(book_id <= 100): #we have 100 books per page
            book = "Book"+str(book_id)+"_"+"Page"+str(p)
            file = open(book, 'r')
            html_doc =  BeautifulSoup(file.read(), features="lxml") #open 
            
            #check if the Book Title exists and it's not an empty string 
            #it appens when the language's book have non-alphanumeric characters--->discard book
            
            if html_doc.find_all('h1') and len(html_doc.find_all('h1')[0]) > 0: 
                bookTitle = html_doc.find_all('h1')[0].contents[0]
                bookTitle = bookTitle.split('\n')[1].strip()
                article.append(bookTitle)
                
                #check if the Book Author exists and it's not an empty string 
                #it appens when the language's book have non-alphanumeric characters--->discard book

                if html_doc.find_all('span', itemprop="name") and len(html_doc.find_all('span', itemprop="name")[0]) > 0: 
                    bookAuthors = html_doc.find_all('span', itemprop="name")[0].contents[0]
                    article.append(bookAuthors)
                            
                    if html_doc.find_all('a', class_="greyText"):
                        bookSeries = html_doc.find_all('a', class_="greyText")[0].contents[0]
                        if bookSeries == 'Edit Details':    #no book series
                            bookSeries = ''                 # we store empty string
                            article.append(bookSeries)
                        else:
                            bookSeries = bookSeries.split('\n')[1].strip()
                            article.append(bookSeries)
                    
                    if html_doc.find(itemprop="ratingValue"):
                        ratingValue = html_doc.find(itemprop="ratingValue").text
                        ratingValue = ratingValue.split('\n')[1].strip()
                        article.append(ratingValue)
                    if html_doc.find(itemprop="ratingCount"):
                        ratingCount = html_doc.find(itemprop="ratingCount").get('content')
                        article.append(ratingCount)
                        
                    if html_doc.find(itemprop="reviewCount"):
                        reviewCount = html_doc.find(itemprop="reviewCount").get('content')
                        article.append(reviewCount)
                    
                    if html_doc.find_all('div', id="description"):
                        Plot = (html_doc.find(id="description").find_all('span')[-1]).text
                        article.append(Plot)
                    else:
                        Plot = ''
                        article.append(Plot)
                    
                    if (html_doc.find_all('span', {'itemprop' : "numberOfPages"})):      
                        NumberofPages = html_doc.find_all('span', itemprop="numberOfPages")[0].contents[0]
                        NumberofPages = NumberofPages.split(' ')[0]
                        article.append(NumberofPages)
                    else:
                        NumberofPages = ''
                        article.append(NumberofPages)
                    
                    if (html_doc.find_all('div', {'class' : "row"})):
                        PublishingDate = html_doc.find(id="details").find_all('div')[1].text
                        PublishingDate = PublishingDate.split('\n')[2].strip()
                        article.append(PublishingDate)
                    else:
                        PublishingDate = ""    
                        article.append(PublishingDate)
                    
                    if html_doc.find_all('a', {'href' : re.compile(r'/characters')}):
                        Characters = ','.join([item.text for item in  html_doc.find_all('a', href = re.compile(r'/characters'))])
                        article.append(Characters)
                    else:
                        Characters = ""
                        article.append(Characters)
                    
                    if html_doc.find_all('a', {'href' : re.compile(r'/places')}):
                        Setting = ' '.join([item.text for item in  html_doc.find_all('a', href = re.compile(r'/places'))]) 
                        article.append(Setting)
                    else:
                        Setting = ""
                        article.append(Setting)
                    
                    if html_doc.find('link'):
                        Url = html_doc.find('link').get('href')
                        article.append(Url)
                        
                    # we want to save only the books with english plot, so we control with nltk if the language is correct
                    try: 
                        if detect(Plot) =='en':
                            path = 'E:\\HW3\\Articles_test'
                            name_article = "article_"+str(n)+".tsv"
                    
                            with open(os.path.join(path,name_article), 'w', newline='') as f_output:
                                tsv_output = csv.writer(f_output, delimiter='\t')
                                tsv_output.writerow(article)
                                n += 1
                                article.clear()
                    except:
                        #go on
                        pass  

            book_id +=1
            
        p +=1<jupyter_output><empty_output><jupyter_text>We applied the function to our pages<jupyter_code>article = [] #to create .tsv file
parent_dir = "E:/HW3"
parse_pages(parent_dir)<jupyter_output><empty_output><jupyter_text>2. Search Engine  First we must pre-process 1. Removing stopwords2. Removing punctuation3. Stemming4. Anything else you think it's needed<jupyter_code>def preprocessing_text(plot):
    """
    Function to pre-process text, returns the text filtered by stopwords, punctuactions and so on 
    Input: text
    Output: list of processed words 
    """  
    article_new = " "
    
    #lower case 
    article_new = plot.lower()
    
    # Remove numbers 
    article_new = re.sub(r'\d+', '', str(article_new))
        
    #remove genitive
    article_new = article_new.replace("'", " ")

    # remove punctuation
    article_new = " ".join(re.split('\W+', article_new)) #splits string on all non-word characters, joins substrings by single spaces

    # remove whitespace from text 
    article_new =  " ".join(article_new.split())  #singolo spazio
    
    ## remove stopwords function
    stop_words = set(stopwords.words("english")) 
    word_tokens = word_tokenize(str(article_new))
    filtered_text = [word for word in word_tokens if word not in stop_words] 
    article_new = filtered_text 
    
    ## stem words 
    porter = PorterStemmer()
    article_new = [porter.stem(word) for word in article_new]
  
    return article_new<jupyter_output><empty_output><jupyter_text>Function to create a list containing all the words found in the plots of the articles.We decide to write this function to have the list of words we'll use to create our inverted index<jupyter_code>def list_of_words(text_to_list):
    
    """
    Function to create the list with all the words in the plots 
    Input: list 
    Output: list of words
    """
    
    words_list = set()
    article_id = 1 #index of the article  

    while article_id <= 26572:
        article = pd.read_csv('E:\\HW3\\Articles_test\\article_'+str(article_id)+'.tsv',delimiter='\t',encoding='utf-8') #cp1252 for windows
        article = article.columns        
        plot = article[6]        #take plot to pre-process
        text = preprocessing_text(plot) #pre processed text
        text_to_list += text #list with all the words
        article_id +=1    
        
    words_list = set(text_to_list) #list with all the words, without repetitions

    return words_list<jupyter_output><empty_output><jupyter_text>We run the funtion to have the list of words as input for the next step: the vocabulary<jupyter_code>text_to_list = []
words_list = list_of_words(text_to_list)<jupyter_output><empty_output><jupyter_text>2.1. Conjunctive query  2.1.1 Create your index! We create a file named `vocabulary_dict`, in the format pickle, that maps each word to an integer (`term_id`).We decide to use *pickle* as format to mantain our data structure.<jupyter_code>def vocabulary(words_list):
    
    """
    Function to create the vocabulary that maps each word to an integer 
    Input: words_list
    Output: vocabulary
    """
    
    index = 1
    
    for word in words_list:
        if word not in vocabulary_dict.keys(): 
            vocabulary_dict[word] = index
            index +=1

    return vocabulary_dict<jupyter_output><empty_output><jupyter_text>We call the function to our list of words of the previous step<jupyter_code>vocabulary_set = []
vocabulary_dict = {}

voc_dict = vocabulary(text_to_list)<jupyter_output><empty_output><jupyter_text>We decided to store it in a separate file as pikle file. In this way we mantain our data structure also in the future<jupyter_code>with open('E:\\HW3\\Files\\vocabulary_final.pkl', 'wb') as f:
    pickle.dump(voc_dict, f)<jupyter_output><empty_output><jupyter_text>load the vocabulary<jupyter_code>with open('E:\\HW3\\Files\\vocabulary_final.pkl', 'rb') as f:
    vocabulary_dict = pickle.load(f)<jupyter_output><empty_output><jupyter_text>Then we create the **Inverted Index**. It is be a `dictionary` of this format:`{term_id_1:[document_1, document_2, document_4],term_id_2:[document_1, document_3, document_5, document_6],...}`where document_i is the id of a document that contains the word.We use the `vocabulary_dict` to take our *term_id* as the new key. The values are the list of document that has the word in their plots<jupyter_code>def inverted_index(vocabulary_dict):
    
    """
    Function to create the inverted index  
    Input: vocabulary_dict
    Output: dictionary with Inverted Index
    """
    
    doc_list = []
    article_id = 1 #index of the article  
    
    while article_id <= 26572:
        article = pd.read_csv('E:\\HW3\\Articles_test\\article_'+str(article_id)+'.tsv',delimiter='\t',encoding='utf-8') #cp1252 for windows
        article = article.columns        
        plot = article[6]        #take plot to search the word    
        text = preprocessing_text(plot) #pre processed text
        text_no_rep = set(text)  #plot without repetitions

        for word in vocabulary_dict.keys():
            
            index = vocabulary_dict[word]
            
            for el in text_no_rep:
                if word == el:
                    dictionary_inv_index[index].append('article_'+str(article_id))
                    
        article_id += 1
       
    return dictionary_inv_index
dictionary_inv_index = defaultdict(list)

dict_inv_ind = inverted_index(vocabulary_dict)<jupyter_output><empty_output><jupyter_text>Save dictionary inverted index<jupyter_code>with open('E:\\HW3\\Files\\dictionary_inv_index1.pkl', 'wb') as f:
    pickle.dump(dictionary_inv_index, f)<jupyter_output><empty_output><jupyter_text>Load dictionary inverted index<jupyter_code>with open('E:\\HW3\\Files\\dictionary_inv_index1.pkl', 'rb') as f:
    inverted_index = pickle.load(f)<jupyter_output><empty_output><jupyter_text>2.1.2 Execute the queryGiven a query, our Search Engine will return a table with these informations:- ` bookTitle `- ` Plot `- ` Url `We create some function to have the indexes related to the words and to compute the intersection, to have only the documents in which there are all the words.<jupyter_code>def query_info_article(query,vocabulary_dict):
    '''
    Function to get the infos from the vocabulary
    input: query and vocabulary_dict
    output list of the indices related to the words of the query
    '''
    input_words = []
    
    for w in range(len(query)):
        if query[w] in vocabulary_dict:
            index_term = vocabulary_dict[query[w]]
            input_words.append(index_term)
            
    return input_words # ho i numeri associati alle parole della query
def query_function(input_words,inverted_index):
    
    '''
    Function to compute the query and search the list of documents in which there are all the words
    input: list of words and inverted_index
    output list of documents in which there are all the words taken in input
    '''
    
    doc_list = []
    final_list = []
    
    for i in input_words:
        i = int(i)
        doc= inverted_index[i] #take the list of documents
        
        if len(doc_list) == 0:
            doc_list = doc #base case
        else:
            final_list = list(set(doc) & set(doc_list))  #intersection
            
        if len(final_list) == 0:
            return doc_list #if I have only one document it'll be in doc_list
        else:
            return final_list  #list with the documents with all the words
def display_result(query, inverted_index,vocabulary_dict):
    '''
    Function display results of the query
    input: query, inverted index, vocabulary
    output BookTitle, plot and url per document
    '''
    list_infos = []
    list_to_display = []
    
    query = preprocessing_text(query)
    input_words = query_info_article(query,vocabulary_dict) 
    final_list = query_function(input_words,inverted_index)
    
    for d in final_list:
        article = pd.read_csv('E:\\HW3\\Articles_test\\'+str(d)+'.tsv',delimiter='\t',encoding='utf-8') #cp1252 for windows
        article = article.columns
        title = article[0]       # book title
        plot = article[6]        #take plot  
        url = article[11]        # take url
        
        list_infos = [title, plot, url]
        
        list_to_display.append(list_infos)

    return  DataFrame(list_to_display,columns=['Book Title', 'Plot', 'Url'])<jupyter_output><empty_output><jupyter_text>Search Engine: Query: " Search for: *friends adventure* "<jupyter_code>query = input('Search for:  ')
display = display_result(query,inverted_index,vocabulary_dict)
display<jupyter_output>Search for:   friends adventure<jupyter_text>2.2) Conjunctive query & Ranking scoreFor the second search engine, given a query, we want to get the top-k (the choice of k it's up to you!) documents related to the query. In particular:* Find all the documents that contains all the words in the query.* Sort them by their similarity with the query* Return in output k documents, or all the documents with non-zero similarity with the query when the results are less than k. You must use a heap data structure (you can use Python libraries) for maintaining the top-k documents.        To solve this task, we have to use the tfIdf score, and the Cosine similarity, applied to the plot.First, we create the functions to compute TF, IDF, TFIDF and cosine similarity. We create a second inverted index, similar to the first one, but as *values* we have a list of tuples. The tuple is a couple composed by article and its tfidf value.We'll compute the cosine similarity between query and article.To display the top-15 documents, we use a heap-data structure through the *heapq* Python library<jupyter_code>def compute_TF(word,document):
    '''
    Function to compute TF for a given word in a document
    input:  word, document
    output: TF
    '''
    
    counter = 0
    len_doc = len(document)
    
    for word_d in document:
        if word == word_d:
            counter +=1
            
    tf = counter / len_doc
    
    return tf

def compute_IDF(documents_list):   
    '''
    Function to compute IDF of a given lists of document in which there is the same word
    input:  documents_list
    output: IDF
    '''
    
    tot_documents = 26572
    len_doc_word = len(documents_list)
    idf = math.log(tot_documents / len_doc_word)
    
    return idf

def compute_TFIDF(documents_list,word,document):   
    '''
    Function to compute TFIDF as the product of TF e IDF
    input:  documents_list,word,document
    output: TFIDF
    '''
    tf = compute_TF(word,document)
    idf = compute_IDF(documents_list)
    tf_idf = tf * idf
    
    return tf_idf
def second_inverted_index(vocabulary_dict,inverted_index):
    """
    Function to create the second inverted index with tf_idf values per document, related to a specific word 
    Input: vocabulary_dict
    Output: dictionary Inverted Index
    """
    
    
    dictionary_inv_index2 = defaultdict(list)
    doc_list2 = []
    article_id2 = 1 #index of the article
    
    while article_id2 <= 26572: 

        article = pd.read_csv('E:\\HW3\\Articles_test\\article_'+str(article_id2)+'.tsv',delimiter='\t',encoding='utf-8') #cp1252 for windows
        article = article.columns        
        plot = article[6]        #take plot to search the word    
        plot_processed = preprocessing_text(plot) #pre processed text
        
        text_no_rep = set(plot_processed)  #plot without repetitions, we'll use it 
        tupla_valori = ()
        
        for word in vocabulary_dict.keys():
            
            index = vocabulary_dict[word]
            documents_list = inverted_index[index]
            
            if word in plot_processed:
                tf_idf = compute_TFIDF(documents_list,word,plot_processed)
                tupla_valori = ('article_'+str(article_id2)+'.tsv',tf_idf)
                
                for el in text_no_rep:
                    if word == el:
                        dictionary_inv_index2[index].append(tupla_valori)
            else:
                pass
                    
        article_id2 += 1
        
    
    return dictionary_inv_index2
dictionary_inv_index2 = second_inverted_index(vocabulary_dict,inverted_index)<jupyter_output><empty_output><jupyter_text>Store the second dictionary_inverted_index<jupyter_code>with open('E:\\HW3\\Files\\inverted_index2_final.pkl', 'wb') as f:
    pickle.dump(dictionary_inv_index2, f)<jupyter_output><empty_output><jupyter_text>Load the second dictionary_inverted_index<jupyter_code>with open('E:\\HW3\\Files\\inverted_index2_final.pkl', 'rb') as f:
    dictionary_inv_index2 = pickle.load(f)<jupyter_output><empty_output><jupyter_text><jupyter_code>def compute_cosine_similarity(query, document):
    
    """
    Function to compute cosine similarity
    input: query, document
    output: cosine similarity between query and document
    """
    dot_product = np.dot(query, document)
    norm_a = np.linalg.norm(query)
    norm_b = np.linalg.norm(document)
    return dot_product / (norm_a * norm_b)<jupyter_output><empty_output><jupyter_text>Search Engine with similarity<jupyter_code>def display_second_result(query_2, vocabulary_dict, dictionary_inv_index2,inverted_index):
    '''
    Function to compute cosine similarity and display the results. Organised data as heap to display top-15
    input: query_2, vocabulary_dict, dictionary_inv_index2, inverted_index
    output Similarity, BookTitle, plot and url top 15 
    '''
    list_infos = []
    list_to_display = []
    
    query_2 = preprocessing_text(query_2) #lista di parole
    input_words = query_info_article(query_2, vocabulary_dict) #ho una lista con gli indici
    final_list = query_function(input_words, inverted_index) #lista dei documenti che hanno tutte le parole della query
    
    #compute tfidf of the query
    tfidf_query_list = []
    for i in query_2:
        word = i
        indice = vocabulary_dict[word]
        documents_list = dictionary_inv_index2[indice]
        
        tfidf_query = compute_TFIDF(documents_list, word, query_2)   #parola = elementi della query, documents_list = final_list query intera = document
        tfidf_query_list.append(tfidf_query)
        
    tfidf_query_arr = np.array(tfidf_query_list) #np array with tfidf of the query
    
    
    dictionary_article_tfidf_values = defaultdict(list) #dictionary in wich we store tfidf for each article (key) as a list of the tfidf of the query's word
    
    for ind_word in input_words: #For each index related to the query's word taken in input
        tfidf_lists = dictionary_inv_index2[ind_word]  #Take the list of tulpe with doc and tfidf from the dictionary
        for tuple_article_tfidf in tfidf_lists: 
            article = tuple_article_tfidf[0]  # take article 
            if article in final_list:   # If it's one of the article that has all the input words 
                tfidf_article = tuple_article_tfidf[1] #take tfidf
                
                dictionary_article_tfidf_values[article].append(tfidf_article) #save tfidf in a list of values with article as key-->list with all the tfidf of the words
                
    #COMPUTE COSINE SIMILARITY 
    diz_cosine = {}
    
    for article_finale in final_list: #for each article with all the input words
        list_of_tfidf_art = dictionary_article_tfidf_values[article_finale] # take the list of tfidf related to each words 
        list_of_tfidf_art_arr = np.array(list_of_tfidf_art) #trasform list of tfidf in np.array
        
    #cosine similarity between query and article 
        cosine_similarity = compute_cosine_similarity(tfidf_query_arr, list_of_tfidf_art_arr)  #tfidf_query_arr = query, list_of_tfidf_art_arr = document
        diz_cosine[article_finale] = cosine_similarity
        
        
    #Display result 

    for art in final_list:
        article = pd.read_csv('E:\\HW3\\Articles_test\\'+str(art)+'.tsv',delimiter='\t',encoding='utf-8') #cp1252 for windows
        article = article.columns
        title = article[0]       # book title
        plot = article[6]        #take plot  
        url = article[11]        # take url
        similarity = diz_cosine[art] #take similarity
        list_infos = [similarity, title, plot, url ] 
        list_to_display.append(list_infos)
        
    nostro_heap = heapq.nlargest(15, list_to_display)
    dataframe_def = DataFrame(nostro_heap,columns=['Similarity', 'Book Title', 'Plot', 'Url'])
    
    return   dataframe_def[['Book Title', 'Plot', 'Url', 'Similarity']]<jupyter_output><empty_output><jupyter_text>Search Engine: Query: " Search for: *Forest street* "<jupyter_code>query_2 = input('Search for:  ')

result2 = display_second_result(query_2, vocabulary_dict, dictionary_inv_index2)
result2<jupyter_output>Choose kind of plot Forest street<jupyter_text>3. Define a new score! **Idea:** We think that people who are looking for a book take into account its rating. But sometimes this values it's not really accurate, in fact there can be two books with the same rating values but a different number of total ratings. This means that the accurancy of the rating value of the book with an higher number un ratings it's better then the other. The choice of the parameters of the function was made following the logic described here. Our first goal is to take into consideration the RatingValue for each book; However, it would not be possible to define a consistent score without taking into account the RatingCount parameter: a book with a RatingValue of 5 and a high number of RatingCount will have to have a higher score than one with a RatingValue of 5 and a lower RatingCount. In addition to this, we have also decided to give importance to the ReviewCount parameter as we want a book that has been reviewed many times to have a higher score than a book that has received few reviews. Since this last parameter will have to influence the final score much less than the previous two, it has been divided by the total number of documents to be analyzed.Finally, the score obtained is processed by a LOG function in order to obtain lower values that differ less from each other. 1. We want to take into account the `ratingValue`, the `ratingCount` and the `reviewCount`    2. For each articles, we compute the *"new score function"* as **F = log(ratingValue X ratingCount)  + reviewCount / total_of_documents)** 3. We create a  dictionary in which we store as "key" the article and as "value" the new score related to the book<jupyter_code>def new_score_function(article):
    '''
    Function to compute the new score. It takes account of the rating values related to the number of ratings and the reviews
    input: article
    output: new score
    '''
    numDoc =26572  
    
    article = article.columns
    ratingValue = article[3]       # ratingValue
    ratingCount = article[4]        # ratingCount  
    reviewCount = article[5]        # reviewCount
    
    #We want to exclude the books in which we haven't these infos. It's default score will be zero
    
    try:
        new_score = math.log((float(ratingValue) * float(ratingCount))  + (float(reviewCount) / float(numDoc)))
       
    except:
        return
        
    return new_score
def dictionary_score_function(vocabulary_dict, inverted_index):
    """
    Function to create the dictionary with the new score  per document
    Input: vocabulary_dict, inverted_index
    Output: dictionary with document as key and new score as value
    """

    article_id3 = 1 #index of the article
    d_score_article = {}
    new_score = 0
    
    while article_id3 <= 26572:
        print(article_id3)
        article = pd.read_csv('E:\\HW3\\Articles_test\\article_'+str(article_id3)+'.tsv',delimiter='\t',encoding='utf-8') #cp1252 for windows
        
        new_score = (new_score_function(article))
        
        article = article.columns  
        plot = article[6]        #take plot to search the word    
        plot_processed = preprocessing_text(plot) #pre processed text
        text_no_rep = set(plot_processed)  #plot without repetitions
        
        d_score_article['article_'+str(article_id3)] = new_score
        article_id3 +=1
        
    return d_score_article
d_score_article1 = dictionary_score_function(vocabulary_dict,inverted_index)<jupyter_output><empty_output><jupyter_text>Save the new dictionary with the score<jupyter_code>with open('E:\\HW3\\Files\\d_score_article.pkl', 'wb') as f:
    pickle.dump(d_score_article1, f)<jupyter_output><empty_output><jupyter_text>Load the new dictionary with the score<jupyter_code>with open('E:\\HW3\\Files\\new_score_dict_final.pkl', 'rb') as f:
    d_score_article = pickle.load(f)
def display_third_result(query_3, vocabulary_dict, d_score_article, inverted_index):
    '''
    Function to display the results of the query with new score
    input: query_3, vocabulary_dict, d_score_article
    output BookTitle, plot, url and new score per document
    '''

    list_infos = []
    list_to_display = []
    
    query_3 = preprocessing_text(query_3)
    input_words = query_info_article(query_3, vocabulary_dict) #ho una llista con gli indici
    final_list = query_function(input_words, inverted_index)

    for art in final_list:
        #print(art)
        article = pd.read_csv('E:\\HW3\\Articles_test\\'+str(art)+'.tsv',delimiter='\t',encoding='cp1252')
        article = article.columns
        title = article[0]       # book title
        plot = article[6]        #take plot  
        url = article[11]        # take url
        
        new_score_f = d_score_article[f'{art}'] #take new score
        
        list_infos = [new_score_f, title, plot, url ] #save infos for each document in a list-->will be a df
        list_to_display.append(list_infos)
            
    #Heap structure
    nostro_heap = heapq.nlargest(15, list_to_display)
    dataframe_def = DataFrame(nostro_heap,columns=['New Score', 'Book Title', 'Plot', 'Url'])
    return   dataframe_def[['Book Title', 'Plot', 'Url', 'New Score']]<jupyter_output><empty_output><jupyter_text>Search Engine: Query: " Search for: *Harry Potter!* "<jupyter_code>query_3 = input('Search for: ')

result3 = display_third_result(query_3, vocabulary_dict, d_score_article)
result3<jupyter_output>Choose kind of plot Harry Potter!<jupyter_text>We notice that *The Devil Wears Prada* appears in the list because it has both "Harry" and "Potter" *From sending the latest, not-yet-in-stores Harry Potter to Miranda’s children in Paris by private jet* (cit). It's position it's correct because it is more popular than the other books below in the list.              5. Algorithmic Question You are given a string written in english capital letters, for example S="CADFECEILGJHABNOPSTIRYOEABILCNR." You are asked to find the maximum length of a subsequence of characters that is in alfabetical order. For example, here a subsequence of characters in alphabetical order is the "ACEGJSTY": "CADFECEILGJHABNOFPSTIRYOEABILCNR." Among all the possible such sequences, you are asked to find the one that is the longest.Define as X[i] = "the length of the longest sequence of characters in alphabetical order that terminates at the i-th character". One can prove thatX[i] = 1 + max{X[j]; j = 0, ..., i-1, such that S[j]<S[i]}X[i] = 1, if there does not exist such a j.1) Write a recursive program that, given a string, computes the length of the subsequence of maximum length that is in alphabetical order. Try some examples. Are the examples of short strings correct? Can you find examples that your algorithm does not terminate in reasonable time?2) Show that the running time of the algorithm is exponential.3) Write a program that computes the length of the subsequence of maximum length, using dynamic programming.4) What is its runtime complexity?  1) Recursive program<jupyter_code>def len_subs_rec(arr, i, n, prev):
 
    if i == n:
        return 0

    excl = len_subs_rec(arr, i + 1, n, prev)

    incl = 0
    if arr[i] > prev:
        incl = 1 + len_subs_rec(arr, i + 1, n, arr[i])

    return max(incl, excl)

word = "ABITARE"
n = len(word)
nums = []

#convert to lowercase
word = word.lower()

#convert letters into nums
for letter in word:
    number = ord(letter) - 96
    nums.append(number)

print(nums)
 
print("Length of the longest ordered substring is", len_subs_rec(nums, 0, len(nums), float('-inf')))<jupyter_output>[1, 2, 9, 20, 1, 18, 5]
Length of the longest ordered substring is 4<jupyter_text>2) Running time of the recursive program We can see how the running time of our last code increases when "n" (the lenght of the string) gets higher.In this solution it is possible to notice how the function for calculating the length of the LIS calls itself twice.We can calculate the execution time as follows: At each cycle the number of letters to be checked decreases by 1, so given $N$ = $numberOfLetters$ we can write that $$T(N) = T(N-1) + T(N-1) + const$$since the function calls itself recursively and the remaining operations have a weight equal to "const" for complexity.By iterating the previous formula we obtain that:$T(N) = T(N-1) + T(N-1) + const = 2T(N-1) + const \le 2T(N-1) = 4T(N-2) = 8T(N-3) = 16T(N-4) = ... = 2^k T(N-k)$So, as we can see, the running time is exponential.  3) Attempt with dynamic programming<jupyter_code>def len_subs_dyn(arr): 
    n = len(arr) 
  
    lis = [1]*n 
  
    for i in range (1 , n):
        
        for j in range(0 , i): 
            
            if arr[i] > arr[j] and lis[i] < lis[j] + 1 : 
                lis[i] = lis[j] + 1
  
    maximum = 0

    for i in range(n): 
        maximum = max(maximum , lis[i]) 
  
    return maximum

word = "ABITARE"
n = len(word)
nums = []

#convert to lowercase
word = word.lower()

#convert letters into nums
for letter in word:
    number = ord(letter) - 96
    nums.append(number)

print(nums)
print("Length of the longest ordered substring is ", len_subs_dyn(nums))<jupyter_output>[1, 2, 9, 20, 1, 18, 5]
Length of the longest ordered substring is  4
{'fraction_non_alphanumeric': 0.08823042542625394, 'fraction_numerical': 0.015063731170336037, 'mean_word_length': 2.7670962377884014, 'pattern_counts': {'":': 1, '<': 124, '<?xml version=': 0, '>': 122, 'https://': 7, 'lorem ipsum': 0, 'www.': 6, 'xml': 3}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '29', 'dir': 'jupyter-structured-clean-dedup', 'id': '133439', 'license': 'MIT', 'n_tokens_mistral': 11239, 'n_tokens_neox': 10633, 'n_words': 3313, 'path': 'ADM_HW3_main.ipynb', 'repo_name': 'LorenzoPetr/ADM-HW3-Group17', 'size': '36267'}