<jupyter_start><jupyter_text>Homework 3 <NAME>, <NAME> and <NAME> Import Libraries<jupyter_code>import requests
import lxml
import shutil
import funzioni as fun
import time
import nltk
import datetime
import csv
import os
import math
from tqdm import tqdm
from bs4 import BeautifulSoup
from pathlib import Path
import re
import pandas as pd
from nltk.corpus import stopwords
from string import punctuation
from nltk.stem.snowball import PorterStemmer
from nltk import stem
from nltk.tokenize import word_tokenize 
import json
import numpy 
import heapq<jupyter_output><empty_output><jupyter_text>We define variables that we will use during all the homework<jupyter_code>nFolders = 299
months = ['Jan', 'Feb', 'Mar', 'Apr', 'May', 'Jun','Jul', 'Aug', 'Sep', 'Oct', 'Nov', 'Dec']
url_file = 'urls.txt'
num_lines = sum(1 for line in open(url_file, encoding="utf-8")) 
pagesPerFolder = num_lines/nFolders
outputTSV = "dataset.tsv"<jupyter_output><empty_output><jupyter_text>We create 299 folders because we have seen that we 19136 urls so we have put 64 urls in each folder Tentative of download a single page<jupyter_code>fun.downloadOneFile(1)<jupyter_output>Cartella1.  Page_1<jupyter_text>1. Data Collection Since no dataset was provided for this homework, we had to create our own dataset by scraping the given website, which was done in the following steps.  1.1 Get the list of animes Firstly, we had to get the list of all the anime we wanted to add to our dataset. This included all the anime found in the first 400 pages. Therefore, we created a function that scrapes a certain number of pages from an initial url in order to extract the url of each of them. The initial urls and the following number of pages are given as input, while the resulting urls are stored in a txt file called "urls.txt" .<jupyter_code>fun.link_list(20000) #we give in input the number of anime that we want to retrieve
#Later we will see that in the website there are less link than 20000<jupyter_output><empty_output><jupyter_text>1.2 Crawl books<jupyter_code>fun.crawl("urls.txt")<jupyter_output><empty_output><jupyter_text>1.3 Parse downloaded pages Once we got all the urls in the first 400 pages of the website, we downloaded the html corresponding to each of the collected urls and we organized them into folders. Each folder contains the htmls of the animes in page 1, page 2, ... of the list of animes.Given all this data, it's of our interest understanding its meaning. So, in order to study it, we selected the following features: Anime Name, Anime Type, Number of episode, Release and End Dates of anime, Number of members, Score, Users, Rank, Popularity, Synopsis, Related Anime, Characters, Voices and Staff. We assemble all these informations generating a tsv file in which every previous feature is a column.<jupyter_code>fun.tsvGenerator()<jupyter_output><empty_output><jupyter_text>2. Search Engine We import the dataset.tsv. that we have created and read it as csv to work on a pandas dataframe<jupyter_code>data = pd.read_csv('dataset.tsv', sep='\t')
data.head()<jupyter_output><empty_output><jupyter_text>2.1 We use the function **cleaner** to pre-process all the the anime Description. In order to analyze this data, it's useful cleaning it removing stopwords, removing punctuation, doing the stemming and removing some useless words (such as 'b', 'br', 'span',  'one' ,  'id',  'none').To maintain the original structure of the dataframe we have decided to create and worked on a copy of it<jupyter_code>data2 = data.copy()
data2['animeDescription'] = data2.animeDescription.apply(lambda x: fun.cleaner(x))<jupyter_output><empty_output><jupyter_text>We create a vocabulary in which the keys are the tokens that appear in the anime description. The values of each key are the documents in which is present that token.<jupyter_code>vocabulary = fun.create_vocabulary(data2)
a_file = open("vocabulary.json", "w")
a_file = json.dump(vocabulary, a_file)
a_file = open("vocabulary.json", "r")
vocabulary = json.load(a_file)<jupyter_output><empty_output><jupyter_text>2.1.1) Create your index! At this point we were able to build the inverted index: it is a dictionary where each key is a number that correspond to a token and its values are the documents where that token appears<jupyter_code>inv_lst = fun.create_inverted_list(vocabulary)<jupyter_output><empty_output><jupyter_text>2.1.2) Execute the query First of all we have to clean the query just as we have cleaned the anime description.<jupyter_code>cleanQString = fun.cleaner(input("write query: "))
cleanQString<jupyter_output>write query: SaIyan@ Race#<jupyter_text>Then we have used the function **map_terms_id** to map the key of inverted list to token present in our vocabulary. In this way we can associate to the query's token the corresponding number. This function prints a message of error if the token is not in our list and uses the remaining token.<jupyter_code>fun.map_terms_id(vocabulary, cleanQString)<jupyter_output><empty_output><jupyter_text>We have noticed that for some animes there are more than one row. They are not duplicates because they have different number of members. Maybe in the website this anime is repeated in the list. Attention: they have the same description. But they have the same link, we should not have repetitions.<jupyter_code>data2[data2["animeTitle"] == "Dragon Ball Kai (Dragon Ball Z Kai)"]<jupyter_output><empty_output><jupyter_text>In the result that we obtained we see anime that in their description contain **both** the tokens of the query. We observe anime that have the same title and description: this is due to the fact that they are not duplicates because they are different in other fields like their *popularity* or *number of members*.<jupyter_code>new_dataset = fun.Search1(cleanQString, vocabulary, data2, inv_lst)
new_dataset<jupyter_output><empty_output><jupyter_text>Now we have dropped the animeTitle duplicates<jupyter_code>new_dataset_1 = new_dataset.drop_duplicates(subset="animeTitle").reset_index(drop = True)
new_dataset_1<jupyter_output><empty_output><jupyter_text>2.2) Conjunctive query & Ranking score Now we have created the second inverted list that has the same length of the previous one but we have added for each document the tfidf computed using the formula.<jupyter_code>inv_lst2 = fun.inverted_list_2(vocabulary, data2)<jupyter_output><empty_output><jupyter_text>We have to obtain the query score: for each word of our query we have computed its tf-idf.<jupyter_code>query_score = fun.queries(cleanQString, vocabulary, data2)
query_score<jupyter_output><empty_output><jupyter_text>We use the function **documents** to retrieve all the pages that contain both the token of our query. So in this way it will be easier and faster to compute the cosine similarity. Indeed it will be zero for documents that do not contain these particular words, because the numerator is the dot product between the correspondent tf-idf (tf-idf of document that does not cointain all of them is zero)<jupyter_code>doc = fun.documents(cleanQString, vocabulary, data2, inv_lst)
doc_score = []
for key in cleanQString.split():
    key_ = fun.map_terms_id(vocabulary, key) #each term of our query is mapped to a corresponding number
    #so in this way we can go in our inverted index. Key_ is a list of one element
    d = pd.DataFrame(inv_lst2[key_[0]], columns = ["doc", "tfidf"]) #for each token we create a df in which we have 
    #for each page that contains the single token we have tf-idf.
    word = []
    for i in doc:
        word.append(d[d["doc"] == i]["tfidf"]) #we select pages that contain both of tokens and save their tf-idf
    doc_score.append(word)
doc_score2 = list(zip(doc_score[0], doc_score[1])) #our query has two words<jupyter_output><empty_output><jupyter_text>*doc* are the number of pages that contain both of token of the query. These pages are the solution of the first Search Engine.  We have computed the norm two of the query: the root square of the sum of tf-idf of the query. It is always the same.<jupyter_code>q_norm = fun.qnorma(query_score)
q_norm<jupyter_output><empty_output><jupyter_text>We compute the similarity for the documents that contain all the token in their description.<jupyter_code>num = list(range(len(doc_score2))) # initialize numerator of cosine similarity
den = list(range(len(doc_score2))) #initialize denominator of cosine similarity
anime = list(range(len(doc_score2))) #document 
similarity = list(range(len(doc_score2)))
for i in range(len(doc_score2)):
    #numerator of cosine similarity
    num[i] = query_score[0][1] * float(doc_score2[i][0]) + query_score[1][1] * float(doc_score2[i][1])
    #denominator of cosine similarity
    den[i] = math.sqrt(float(doc_score2[i][0])**2 + float(doc_score2[i][1])**2)*q_norm
    similarity[i] = num[i]/den[i]
    #link the title to the similarity obtained 
    anime[i] = data2.iloc[doc[i]]["animeTitle"]<jupyter_output><empty_output><jupyter_text>We use a *heap data structure* to maintain the top-k documents. We have chosen k = 5. We immediately notice that the similarity  is about 1. Since the *cosine similarity* varies between -1 and 1, our result means that the words contained in the documents are mostly the same but this result doesn't imply that their order is identical. This result was surely expectable since we have considered just two words: in fact, following the meaning of the cosine similarity, it's pretty obvious that a query composed just by two words is present in the biggest part of the documents, but if we try with a longer query, we obtain a smaller similarity.<jupyter_code>top = list(zip(anime, similarity))
heapq.heapify(top)
heapq.nlargest(5, top)<jupyter_output><empty_output><jupyter_text>It's the dataframe of the first Search Engine but in the last column we have put the similarity<jupyter_code>new_dataset["Similarity"] = similarity
new_dataset.sort_values(by = "Similarity", ascending = False).reset_index(drop = True).head()<jupyter_output><empty_output><jupyter_text>Tentative of implementation with sklearn. Useless<jupyter_code>import numpy as np
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.metrics.pairwise import cosine_similarity

# Calculate the tfidf and cosine similarity score for all books with the query

vectorizer = TfidfVectorizer() # Get tf-idf matrix using fit_transform function
X = vectorizer.fit_transform(data2['animeDescription'].values.astype('U')) # Store tf-idf representations of all docs

query = 'saiyan race' # Ask the user to write the query

query_vec = vectorizer.transform([query]) # Ip -- (n_docs,x), Op -- (n_docs,n_Feats)
results = cosine_similarity(X,query_vec).reshape((-1,)) # Op -- (n_docs,1) -- Cosine Sim with each doc
cos_sim = results.tolist() # Convert the cosine similarity result to list format
data2['Similarity'] = cos_sim # Write the similarity score to Similarity column of dataframe
    
#data2.nlargest(10,'Similarity') # Take the first 10 most similar books
data2_top = data2.nlargest(10,'Similarity')[["animeTitle",'animeDescription', "Url", "Similarity"]].reset_index()
data2_top<jupyter_output><empty_output><jupyter_text>3. Define a new score!<jupyter_code>data1 = data.copy()
data1['animeTitle'] = data1.animeTitle.apply(lambda x: fun.cleaner(x))
data1['animeDescription'] = data1.animeDescription.apply(lambda x: fun.cleaner(x))
data1['animeRelated'] = data1.animeRelated.apply(lambda x: fun.cleaner(x))

data1.head()
vocabulary2 = create_vocabulary2(data1)

b_file = open("vocabulary2.json", "w")
b_file = json.dump(vocabulary2, b_file)
b_file = open("vocabulary2.json", "r")
vocabulary2 = json.load(b_file)
inv_lst3 = fun.create_inverted_list(vocabulary2)<jupyter_output><empty_output><jupyter_text>New query<jupyter_code>query2 = input("Insert a new query: ")
query2 = fun.cleaner(query2)
query2<jupyter_output><empty_output><jupyter_text>Get the query-related documents by exploiting the search engine of Step 3.1. We retrieve documents that contains all the tokens in the query<jupyter_code>new_dataset2 = fun.Search3(query2, vocabulary2, data1, inv_lst3).drop_duplicates(subset="animeTitle")
new_dataset2.head()
data1.describe()<jupyter_output><empty_output><jupyter_text>To define a new score we decide this kind of score based on the function .describe() of our dataframe:- We have decided to give 0.5 points to anime that have more than 4000 of animeRank, 0 otherwise- We have decided to give 0.5 point to anime that have more anime score greater than 7.5, 0 otherwise<jupyter_code>make = list(numpy.zeros(len(new_dataset2)))
new_dataset2["new_score"] = make
new_dataset2.head()<jupyter_output><empty_output><jupyter_text>We can observe that the first html pages with our new score are the first because they have the best anime rank and anime score<jupyter_code>new_dataset2.loc[new_dataset2["animeRank"]<=100, "new_score"] += 0.5
new_dataset2.loc[new_dataset2["animeScore"]>7.5, "new_score"] += 0.5
new_dataset2.sort_values(by = "new_score", ascending = False).reset_index(drop=True)<jupyter_output><empty_output><jupyter_text>5. Algorithmic question The algorithm is using Dynamic Programing to solve it. Basically, we use 2 variables to know if we should take the i-th value or not. These variables are, incl, which will store the higher sum we can get including the i-th value, and excl, which will store the higher sum we can get without including the i-th value. We start iterating the list of values from the first index. So initially incl = or[0], Because the higher sum we can obtain till the moment it's getting the first element. And excl = 0, because as we are in the beginning, if we don't take the only element we have, the sum is 0. Hereinafter, for each of the next documents, we will check if the best sum we got excluding the last element plus the current element, it's better or not than the highest sum including the last element. If the sum of including the last element its higher, we can't use the current one because are consecutive. If the sum of the excl and the current is higher, means that till the moment we are going to include in our solution the current element. If we keep going , at the end of the array we will obtain the highest sum of the whole array.To also get the values that are used in the correct solution, we can store in an array the values that we are including. The problem is that as we can't have consecutive elements, if we decide that we want to use the current value, and the last value iterated is in the solution array, we have to switch to the state of the solution before we added the last element, and append the current one. In case that the last element is not in the list, we don't have any conflict into adding the current one. That way, at every iteration, we have the values used for getting the best solution till the moment, so at the end of the array, we will also have the values that we used for the solution.<jupyter_code>def optimalSol(arr):
    incl = arr[0] # list of max sum including the previous element 
    excl = 0 #list of max sum excluding the previous element
    indexOfOptimalSol = [0] #index of the best solution 
    #print("$$$$$$$$$$$$$$$$$$$$")
    #print("index: ", 0)
    #print("incl = ", incl)
    #print("excl = ", excl)
    #print("indexOfOptimalSol: ", indexOfOptimalSol)
    #print("$$$$$$$$$$$$$$$$$$$$")
    lastElem = 0
    lastIndexArrayState = []
    for i in range(1,len(arr)): # i is the actual position
        oldIncl = incl
        if excl+arr[i] > incl:
            aux = indexOfOptimalSol
            if i - 1 in indexOfOptimalSol:
                indexOfOptimalSol = lastIndexArrayState + [i] #update of the index in the best solution
            else: 
                indexOfOptimalSol = indexOfOptimalSol + [i] #update of the index in the best solution
            lastIndexArrayState = aux
            incl = excl+arr[i]
        excl = oldIncl
        #print("$$$$$$$$$$$$$$$$$$$$")
        #print("index: ", i)
        #print("incl = ", incl)
        #print("excl = ", excl)
        #print("indexOfOptimalSol: ", indexOfOptimalSol)
        #print("$$$$$$$$$$$$$$$$$$$$")
        lastElem = i
        
        
    
    sol = list(map(lambda x: arr[x],indexOfOptimalSol))
    print("SOLUTION: ", incl)
    print("The solution is the sum of the elements: ", sol)
    return incl, sol<jupyter_output><empty_output><jupyter_text>example<jupyter_code>optimalSol([30, 40, 25, 50, 30, 20])<jupyter_output>SOLUTION:  110
The solution is the sum of the elements:  [40, 50, 20]<jupyter_text>Program that given in input an instance in the form given above, gives the optimal solution.<jupyter_code>print("Good morning personal trainer!")
n = int(input("How many appointments do you have today? ")) #len of the list
l = []
for app in range(1, n+1):
    l.append(int(input("How much time want to spend the "+ str(app)+"th client? "))) #item of the list
optimalSol(l)<jupyter_output>Good morning personal trainer!
How many appointments do you have today? 5
How much time want to spend the 1th client? 60
How much time want to spend the 2th client? 30
How much time want to spend the 3th client? 20
How much time want to spend the 4th client? 50
How much time want to spend the 5th client? 45
SOLUTION:  125
The solution is the sum of the elements:  [60, 20, 45]
{'fraction_non_alphanumeric': 0.08577670461078533, 'fraction_numerical': 0.013567896975968725, 'mean_word_length': 5.142302259887006, 'pattern_counts': {'":': 0, '<': 125, '<?xml version=': 0, '>': 126, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 1}, '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': '31', 'dir': 'jupyter-structured-clean-dedup', 'id': '448072', 'license': 'MIT', 'n_tokens_mistral': 5400, 'n_tokens_neox': 5172, 'n_words': 2128, 'path': 'Homework.ipynb', 'repo_name': 'michele1783/ADM-HW3', 'size': '17427'}