# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Sampling algorithm
# ---
# Implementation of Vertex's sampling algorithm described in [_Web-scale information extraction with vertex_](https://ieeexplore.ieee.org/abstract/document/5767842)
#
# ## Outline
# ---
# 1. [Retrieve XPaths from a page](#1.-retrieve-xpaths-from-a-page)
# 2. [Compute XPath weight]()
# 3. [Sampling algorithm]()
#
# ## 1. Retrieve XPaths from a page
# As reported in the paper:
#
# > One simple way to achieve this is to treat each page as a set of XPaths contained in it, and then greedily select pages that cover the most number of uncovered XPaths. 
#
# However, the paper does not specify which Xpaths are extracted from a page. Therefore we decided to extract XPaths which retrieves textual leaf nodes.
#
# To do so we used the [lxml]() library to select all leaf textual nodes in a page. Then, using the same library we obtained the respective XPath of each leaf node previously selected. 

import requests
from lxml import html
from collections import defaultdict


# ### ``get_all_xpath``
# Given a page HTML source code returns a dict { _xpath_ : _value_ }, where _xpath_ is an xpath and _value_ is the string retrieved from the xpath on _src_

def get_all_xpath(html_src):
        
    # select nodes whose children include text nodes
    XPATH_SELECTOR = "//*[child::text()]" 
        
    root = html.fromstring(html_src)
    
    tree = root.getroottree()
    
    # leaf_nodes is not properly a list of all leaf nodes. 
    # It contains nodes which are parent of text elements in the DOM
    leaf_nodes = root.xpath(XPATH_SELECTOR)
    
    xpath_value_dict = {}
    
    # extract xpath from previously selected nodes and filter out "noisy" nodes
    for leaf in leaf_nodes:
        
        xpath = tree.getpath(leaf) + "/text()"
        
        # Filtering out xpaths which extract javascript code or css stylesheet
        if  "/script" not in xpath and "/noscript" not in xpath and "/style" not in xpath:
                        
            selected_values = root.xpath(xpath)
            selected_string = ''.join(selected_values).strip()
            
            # Filtering out xpaths which extract empty strings
            if selected_string:
                xpath_value_dict.update({xpath: selected_string})
    
    return xpath_value_dict    


# ## 2. Compute XPaths weights
# ---

# #### get_data_structures
# Return necessary data structures for computing xpaths weights

def get_data_structures(url_to_html_map):
        
    url_to_xpaths = {}
    xpath_to_value_list = defaultdict(list)
    
    for url in list(url_to_html_map):
        
        page = url_to_html_map[url]
        xpath_to_single_value = get_all_xpath(page)
        xpath_list = list(xpath_to_single_value)
        url_to_xpaths[url] = xpath_list
                
        for xpath in xpath_to_single_value:
            value = xpath_to_single_value[xpath]
            xpath_to_value_list[xpath].append(value)
    
    return (url_to_xpaths, xpath_to_value_list)


# ### Compute frequency
# Given a list of values extracted from a xpath _Xi_ returns the frequency of _Xi_

def compute_frequency(values_list):
    return len(values_list)


# ### Compute informativeness
# Given cluster size and a list of values extracted from a xpath _Xi_ returns the informativeness of _Xi_

def compute_informativeness(M, values_list):

    values_set = set(values_list)
    Ti = len(values_set)
    
    sum_F_Xi = compute_frequency(values_list)

    return 1 - sum_F_Xi/(M*Ti)
    


# ### xpath weight
# Given a list of values extracted from a xpath _Xi_ returns the weight of _Xi_

def xpath_weight(cluster_size, list_of_values):
    return compute_frequency(list_of_values)*compute_informativeness(cluster_size, list_of_values)


# ### xpath_to_weight
# Arguments:
# - **xpath_to_values_map**: dictionary where keys are xpath and values are values retrieved from the xpath
# - **cluster_size**
#
# Returns a dictionary where keys are xpaths and values are their weights

def xpath_to_weight(xpath_to_values_map, cluster_size):
    
    result = {}
    for xpath in xpath_to_values_map:
        list_of_values = xpath_to_values_map[xpath]
        weight = xpath_weight(cluster_size, list_of_values)
        result.update({xpath: weight})
    
    return result


# ### page_weight
# Arguments:
# - **list of xpath**: list of xpath of a given page
# - **xpath_to_weight_map**: dictionary where keys are xpath and values are their weights
# - **cluster_size**
# - **intersection** (optional): if None nothing happens. Otherwise only xpath in **list of xpath** $\cap$ **intersection** will be considered in computing weight
#
# Returns page's weight

def page_weight(list_of_xpath, xpath_to_weight_map, cluster_size, intersection = None):
        
    weight = 0
    
    if intersection is None:
        intersection = list_of_xpath
        
    for xpath in list_of_xpath:
        if xpath in intersection:
            weight_of_xpath = xpath_to_weight_map[xpath]
            weight += weight_of_xpath
    
    return weight


# ### Max weight page
# Arguments:
# - **url_to_xpaths_map**: dictionary where keys are urls and values are xpaths extracted from urls
# - **xpath_to_weight_map**: dictionary where keys are xpath and values are their weights
# - **cluster_size**
# - **intersection** (optional): if None nothing happens. Otherwise only xpath in **list of xpath** $\cap$ **intersection** will be considered in computing weight
#
# Output: 
# - the URL of the page with the highest weight value

def max_weight_page(url_to_xpaths_map, xpath_to_weight_map, cluster_size, intersection = None):
        
    max_weight = 0
    max_weight_page = None
    
    for url in url_to_xpaths_map:
        
        xpaths = url_to_xpaths_map[url]
        weight = page_weight(xpaths, xpath_to_weight_map, cluster_size, intersection)
        
        if weight > max_weight:
            max_weight = weight
            max_weight_page = url
            
    print("INFO\tMax weight url is  {}".format(max_weight_page))
    print("INFO\tMax weight is {}".format(max_weight))
    
    return max_weight_page


# ### coverage
# Returns cluster's page coverage. TODO: add more explanations

def coverage(X, sample_pages_urls, cluster_pages_urls, url_to_xpaths_map, xpath_to_weight_map):
    covered = 0
    cluster_size = len(cluster_pages_urls)
    for url in cluster_pages_urls:
        if url not in sample_pages_urls:
            xpaths = url_to_xpaths_map[url]
            weight = page_weight(xpaths, xpath_to_weight_map, cluster_size, X)
            if weight == 0:
                covered = covered + 1
    
    return (covered + len(sample_pages_urls))/cluster_size


#another metric to evaluate sample coverage
def coverage2(samplePagesUrl,urlToXpathsMap,XpathNumber):
    sampleXpathList=[]
    for url in samplePagesUrl:
        xpaths=urlToXpathsMap[url]
        sampleXpathList=sampleXpathList+xpaths
    sampleXpathSet=set(sampleXpathList)
    return (len(sampleXpathSet)/XpathNumber)


# ## 3. Sampling algorithm
# ---

# +
from copy import copy

def sampling(url_to_html_map, k = 20):
        
    cluster_size = len(url_to_html_map)
    
    cluster_pages_urls = list(url_to_html_map)
    
    url_to_xpaths_map, xpath_to_values_map = get_data_structures(url_to_html_map)
    url_to_xpaths_map_copy=copy(url_to_xpaths_map)
    
    xpath_to_weight_map = xpath_to_weight(xpath_to_values_map, cluster_size)
    xPathsSize=len(xpath_to_weight_map)
    X = list(xpath_to_values_map) #insert dictionary keys into a list
    
    result = []
    
    iteration_no = 1
    
    while X and len(result) < k:
        print("-------------------")
        print("INFO\tIteration {}".format(iteration_no))
        
        max_weight_url = max_weight_page(url_to_xpaths_map, xpath_to_weight_map, cluster_size, X)
        result.append(max_weight_url)
        X = [xpath for xpath in X if xpath not in url_to_xpaths_map[max_weight_url]]
        url_to_xpaths_map.pop(max_weight_url)
        
        coverage_value = coverage(X, result, cluster_pages_urls, url_to_xpaths_map_copy, xpath_to_weight_map)
        coverage2_value= coverage2(result, url_to_xpaths_map_copy, xPathsSize)
        print("INFO\tWeight based Coverage is {}".format(coverage_value))
        print("INFO\tXpath based Coverage is {}".format(coverage2_value))
        iteration_no = iteration_no +1
    
    return result


# -

# ## 4. Testing

# %matplotlib inline
# Importing libraries
import matplotlib.pyplot as plt
import pandas as pd

df = pd.read_csv('datasets/books_dataset.csv', nrows = 100)

df.head()

df.describe()


def create_dict(df):
    result = {}
    for index, row in df.iterrows():
        key = row['url']
        value = row['src']
        result.update({key: value})
    return result


cluster = create_dict(df)
sample_pages = sampling(cluster)

StarcoderdataJupyterScriptsDedupFiltered