<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Assignment 02
Step1:  a) Implement a crawler
Der Crawler wurde mit Hilfe der Bibliothek 'scrapy' geschrieben. Die dazu implementierte Anwendung ist im Verzeichnis ~/sitespider zu finden und der eigentliche Crawler in der Datei ~/sitespider/sitespider/spiders/site_spider.py. Der Code dazu sieht wie folgt aus
Step2:  Importierung der analysierten Seiten
Im folgenden Code-Block werden die resultierenden Dateien einzeln ausgelesen und in der Variablen pages gespeichert.
Step3:  Konstanten
Die folgenden Konstenten sind vorgegeben bzw. müssen zuvor berechnet werden
Step4:  Funktionen
PageRank-Funktion
Die Funktion calculate_page_rank() berechnet den PageRank für die übergebene Seite page_i. Folgende Formel wurde dabei implementiert
Step5:  Hilfe-Funktionen
Die Funktion initialize() initialisiert alle Seiten mit einem Start-PageRank, der sich durch die Division von eins durch die Anzahl aller Seiten berechnet. Zudem setzt sie den folgenden PageRank auf None.
Step6:  Die Funktion termination_condition() gibt einen boolischen Wert zurück, der sagt, ob die Abbruchbedingung erfüllt ist oder nicht. Im Falle, dass es keine zwei Vergleichswerte gibt, also rank+1 gleich None ist, wird False zurückgegeben, ansonsten wird der Rückgabewert mit folgender Formel berechnet
Step7:  Die Funktion set_ranks() setzt, wenn rank+1 nicht None ist, für alle Seiten den älteren PageRank-Wert rank auf den aktuellen PageRank-Wert rank+1.
Step8:  Berechnung der PageRanks für alle Dokumente
Im folgenden Code-Block wird zunächst die Methode initialize() aufgerufen, um alle Seiten mit einem initalen PageRank-Wert zu initialisieren. Anschließend wird so lange die While-Schleife durchlaufen, bis die Abbruchsbedingung erfüllt ist. Innerhalb der While-Schleife wird zunächst die Methode set_ranks() aufgerufen, um alle alten PageRanks auf den aktuellen Stand zu setzen. Anschließend wird jede Seite durchlaufen, wobei jeweils der nächste PageRank für die aktuelle Seite berechnet wird und in der Variablen rank+1 gespeichert wird.
Step9:  Speichern der PageRanks
Die Resultate werden in der Datei rank.txt gespeichert. Dabei steht in der Datei zunächst die Id der Seite und anschließend der eigentliche PageRank-Wert.
Step10:  Überprüfung der Summe aller PageRanks
Als Abschluß wird die Summe aller PageRanks berechnet, um zu prüfen, ob dieser Wert ungefähr 1 entspricht.
Step11:  d) Build a tf-Index for the words contained in the documents
Im folgenden Abschnitt wird ein TF-Index für alle Wörter, die in den Dokumenten (Seiten) auftauchen, berechnet.
Variablen
Folgende Variablen werden verwendet
Step12:  Funktionen
Gewichtete Term-Frequency
Die Funktion get_weighted_tf() brechnet mittels der folgenden Formel die gewichtete Term-Frequency für den übergebenen Term im Bezug auf das Dokument, mit der übergebenen Dokumenten-Id.
$$ w_{t,d} =
  \begin{cases}
    1 + log_{10}(tf_{t,d})       & \quad \text{if } tf_{t,d} > 0\
    0 & \quad \text{otherwise}\
  \end{cases}
$$
Step13:  Initalisierung der Stopwörter
Im folgenden Code-Block werden die Stopwörter aus der Datei stop_words.txt ausgelesen und in der Variablen stopwords gespeichert.
Step14:  Berechnung aller vorkommenden Wörter
Um alle vorkommenden Wörter zu berechnen, werden alle Texte der Dokumente durchlaufen und mittels des nltk-Wörter-Tokinisierers tokinisiert. Jedes resultierende Wort wird anschließend analysiert und sofern es kein Zeichen oder ein Stopwort ist, dem term_set hinzugefügt.
Step15:  Berechnung des Term-Frequency-Indexes
Um den Term-Frequency-Indexes aufzustellen, wird jedes Dokument durchlaufen, wobei zunächst für jedes Wort aus dem term_set ein Wert von 0 initialisiert wird. Anschließend wird jedes Wort innherhalb des Dokumentes analysiert und, sofern es sich um kein Zeichen oder Stopwort handelt, der passende Zähler um eins erhöht.
Step16:  Speichern des Term-Frequency-Indexes
Das Resultat wird in der Datei index.txt gespeichert. Dabei stellt jede Zeile ein Wort und jede Spalte ein Dokument dar.
Step17:  e) Implement a function search to search for documents containing given words
Folgend wird ein TF-Index für alle Wörter innerhalb der Dokumente (Seiten) berechnet.
Variablen
Folgende Variablen werden verwendet
Step18:  Funktionen
Gewichtete Inverse-Document-Frequency
Die Funktion get_weighted_idf() berechnet mittels der folgenden Formel die gewichtete Inverse-Document-Frequency für den übergebenen Term.
$$ w_t =
  \begin{cases}
    log_{10}( \frac{N}{df_t})       & \quad \text{if } df_t > 0\
    0 & \quad \text{otherwise}\
  \end{cases}
$$
Step19:  Gewichteter TF-IDF-Wert
Die Funktion get_weighted_tf_idf() brechnet mittels der folgenden Formel den gewichteten TF-IDF-Wert für den übergebenen Term im Bezug auf das Dokument mit der übergebenen Dokumenten-Id.
$$ \text{tf-idf}{t,d} = tf{t,d} \times idf_t $$
Step20:  Search
Die Funktion search() brechnet für jede Seite einen Wert, der aussagt, wie gut die jeweilge Seite zu den gesuchten Termen passt. Dabei berechnet sich der Wert ohne Einbeziehung des PageRanks wie folgt
Step21:  Berechnung der Document-Frequency für jedes Wort
Zur Berechnung der Document-Frequency werden alle Seiten durchlaufen, wobei jedes Wort des Textes der Seite betrachtet wird. Sofern das Wort kein Zeichen oder Stopwort ist und noch nicht im df_dict vorkommt, wird es neu mit der  Document-Frequency 1 und der Dokumenten-Id angelegt. Existiert das Wort bereits im df_dict, wird nur dann die Document-Frequency um eins erhöht, wenn die aktuelle Dokumenten-Id noch nicht existiert.
Step22:  Suche mit TF-IDF und anschließende Speicherung
Gesucht wird nach folgenden Termen
Step23:  Im folgenden Code-Block wird jeder Such-Term durchgegangen und der jeweilige Wert für jedes Dokument berechnet. Der Wert setzt sich aus dem TF-IDF-Wert zusammen. Anschließend wird das Ergebnis in der Datei pageranke_search.txt gespeichert.
Step24:  f) Extend your search function and include PageRank to score the documents
Suche mit TF-IDF und PageRank und anschließende Speicherung
Gesucht wird nach folgenden Termen
Step25:  Im folgenden Code-Block wird jeder Such-Term durchgegangen und der jeweilige Wert für jede Seite berechnet. Der Wert setzt sich aus dem TF-IDF-Wert und PageRank zusammen. Anschließend wird das Ergebnis in der Datei pageranke_search.txt gespeichert.
<ASSISTANT_TASK:>
Python Code:
import json
import os
import nltk
import string
import re
import pandas as pd
from IPython.display import display
import numpy as np
import math
Explanation: Assignment 02
End of explanation
directory = 'sitespider/sites'
files = [x[2] for x in os.walk(directory)][0]
pages = []
Explanation: a) Implement a crawler
Der Crawler wurde mit Hilfe der Bibliothek 'scrapy' geschrieben. Die dazu implementierte Anwendung ist im Verzeichnis ~/sitespider zu finden und der eigentliche Crawler in der Datei ~/sitespider/sitespider/spiders/site_spider.py. Der Code dazu sieht wie folgt aus:
```python
-- coding: utf-8 --
import scrapy
import re
import json
class SiteSpiderSpider(scrapy.Spider):
    name = 'site_spider'
start_urls = [
    'http://people.f4.htw-berlin.de/~zhangg/pages/teaching/pages/d01.html',
    'http://people.f4.htw-berlin.de/~zhangg/pages/teaching/pages/d06.html',
    'http://people.f4.htw-berlin.de/~zhangg/pages/teaching/pages/d08.html'
]
def parse(self, response):
    id = response.url.split('/')[-1].split('.')[0]
    with open("sites/%s.json" % id, 'w') as f:
        data = {'id': id,
                'text': "".join(line for line in response.css('body::text').extract()),
                'url': response.url,
                'back_links': [link.split('.')[0] for link in response.css('a::attr(href)').extract()]
                }
        json.dump(data, f)
    for next_page in response.css('a::attr(href)').extract():
        yield response.follow(next_page, callback=self.parse)
```
Die Klasse SiteSpiderSpider erbt von der Klasse scrapy.Spider. So kann die geschriebene Klasse später als Crawler benutzen werden.
Das Attribut name identifizieren den Crwaler und wird dazu benutzt, den Crawler später über die Konsole aufzurufen. Das Attribut start_urls legt fest, welche URLs vom Crawler initial angefragt werden sollen. Die Methode parse() nimmt dann anschließend die Rückgabe jeder Anfrage entgegen und bearbeitet diese. Da die Methode parse() die default Callback-Methode ist, muss diese nicht explizit angegeben werden.
Die parse()-Methode erzeugt einen String, der die Anfrage eindeutig beschreibt. Dieser Wert wird anschließend als Dateiname für die Datei verwendet, in der die Daten der Anfrage gespeichert werden. Gewähltes Fromat ist hierbei JSON. In der Datei selber wird die Id der Anfrage, der eigentliche Text ohne HTML-Tags, die URL und alle auf der Seite gefundenen Links als Array gespeichert. Anschließend wird für alle auf der Seite gefundenen Links derselbe Prozess mittels der Methode response.follow() angestoßen.
b) Crawl all reachable documents starting from the following URLs
Der implementierte Crawler kann mittels des Konsolen-Befehls 'scrapy crawl site_spider' in dem Verzeichniss ~/sitespider aufgerufen werden. Die resultierenden Dateien sind in dem Unterordner ~/sitespider/sites/* zu finden
c) Calculate the PageRanks of the downloaded pages
Folgend werden die PageRanks der heruntergeladenen Seiten berechnet.
Variablen
Folgende Variablen werden verwendet:
* directory: Ordner, in dem die resultierenden Dateien liegen
* files: resultierende Dateien
* pages: Dictionary-Array, wobei jedes Dictionary jeweils eine Seite repräsentiert
End of explanation
for file in files:
    with open("%s/%s" % (directory, file)) as json_data:
        pages += [json.load(json_data)]
Explanation: Importierung der analysierten Seiten
Im folgenden Code-Block werden die resultierenden Dateien einzeln ausgelesen und in der Variablen pages gespeichert.
End of explanation
n = len(pages)
t = 0.05
d =  1 - t
δ = 0.04 
Explanation: Konstanten
Die folgenden Konstenten sind vorgegeben bzw. müssen zuvor berechnet werden:
* n = Anzahl der betrachteten Seiten
* t = Teleportationsrate
* d = Dämpfungsfaktor
* δ = Abbruchswert
End of explanation
def calculate_page_rank(page_i):
    sum_result = 0  
    for page_j in pages:
        if page_i['id'] in page_j['back_links']:
            sum_result += page_j['rank'] / len(page_j['back_links'])
        if len(page_j['back_links']) == 0:
            sum_result += page_j['rank'] / n
    return d * sum_result + t / n
Explanation: Funktionen
PageRank-Funktion
Die Funktion calculate_page_rank() berechnet den PageRank für die übergebene Seite page_i. Folgende Formel wurde dabei implementiert:
$$ r_{k+1}(p_i) = d * \bigg ( \displaystyle\sum_{p_j \in B_{pi}} \frac{r_k(p_j)}{|p_j|} + \displaystyle\sum_{p_j,|p_j|=0} \frac{r_k(p_j)}{N} \bigg ) + \frac{t}{N} $$
End of explanation
def initialize():
    for page in pages:
        page['rank'] = 1/n
        page['rank+1'] = None
Explanation: Hilfe-Funktionen
Die Funktion initialize() initialisiert alle Seiten mit einem Start-PageRank, der sich durch die Division von eins durch die Anzahl aller Seiten berechnet. Zudem setzt sie den folgenden PageRank auf None.
End of explanation
def termination_condition():
    delta = 0
    for page in pages:
        if page['rank+1'] is None:
            return False
        else:
            delta += abs(page['rank+1'] - page['rank'])
    return  delta <= δ
Explanation: Die Funktion termination_condition() gibt einen boolischen Wert zurück, der sagt, ob die Abbruchbedingung erfüllt ist oder nicht. Im Falle, dass es keine zwei Vergleichswerte gibt, also rank+1 gleich None ist, wird False zurückgegeben, ansonsten wird der Rückgabewert mit folgender Formel berechnet:
$$ \sum_{p_i,i \in 1,...,N} abs(r_{k+1}(p_i) - r_k(p_i)) <= \delta $$
End of explanation
def set_ranks():
    for page in pages:
        if  page['rank+1'] is not None:
            page['rank'] = page['rank+1']
Explanation: Die Funktion set_ranks() setzt, wenn rank+1 nicht None ist, für alle Seiten den älteren PageRank-Wert rank auf den aktuellen PageRank-Wert rank+1.
End of explanation
initialize()
while not termination_condition():
    set_ranks()
    for page in pages:
        page['rank+1'] = calculate_page_rank(page)
Explanation: Berechnung der PageRanks für alle Dokumente
Im folgenden Code-Block wird zunächst die Methode initialize() aufgerufen, um alle Seiten mit einem initalen PageRank-Wert zu initialisieren. Anschließend wird so lange die While-Schleife durchlaufen, bis die Abbruchsbedingung erfüllt ist. Innerhalb der While-Schleife wird zunächst die Methode set_ranks() aufgerufen, um alle alten PageRanks auf den aktuellen Stand zu setzen. Anschließend wird jede Seite durchlaufen, wobei jeweils der nächste PageRank für die aktuelle Seite berechnet wird und in der Variablen rank+1 gespeichert wird.
End of explanation
with open('rank.txt', 'w') as f:
    for page in pages:
        f.write("%s: %s\n" % (page['id'], page['rank+1']))
Explanation: Speichern der PageRanks
Die Resultate werden in der Datei rank.txt gespeichert. Dabei steht in der Datei zunächst die Id der Seite und anschließend der eigentliche PageRank-Wert.
End of explanation
rank_sum = 0
for page in pages:
    rank_sum += page['rank+1']
print(rank_sum)
Explanation: Überprüfung der Summe aller PageRanks
Als Abschluß wird die Summe aller PageRanks berechnet, um zu prüfen, ob dieser Wert ungefähr 1 entspricht.
End of explanation
tf_dict = {}
term_set = set()
stopwords = []
exclude = set(string.punctuation)
porter = nltk.PorterStemmer()
Explanation: d) Build a tf-Index for the words contained in the documents
Im folgenden Abschnitt wird ein TF-Index für alle Wörter, die in den Dokumenten (Seiten) auftauchen, berechnet.
Variablen
Folgende Variablen werden verwendet:
* tf_dict: Dictionary, das den TF-Index repräsentiert
* term_set: Set, bestehend aus allen vorkommenden Begriffen innerhalb der Dokumente 
* stopwords: Liste von Stopwörtern
* exclude: Set von Zeichen, die entfernt werden sollen
* porter: Stemmer, der zum Finden der Wortstämme verwendet werden soll; in dem Fall der nltk-Porter-Stemmer
End of explanation
def get_weighted_tf(doc_id, term):
    if term in tf_dict[doc_id]:
        if tf_dict[doc_id][term] == 0:
            return 0
        else:
            return 1 + math.log10(tf_dict[doc_id][term])
    else:
        return 0
Explanation: Funktionen
Gewichtete Term-Frequency
Die Funktion get_weighted_tf() brechnet mittels der folgenden Formel die gewichtete Term-Frequency für den übergebenen Term im Bezug auf das Dokument, mit der übergebenen Dokumenten-Id.
$$ w_{t,d} =
  \begin{cases}
    1 + log_{10}(tf_{t,d})       & \quad \text{if } tf_{t,d} > 0\
    0 & \quad \text{otherwise}\
  \end{cases}
$$
End of explanation
with open('stop_words.txt') as line:
    stopwords += re.sub('[^a-zA-Z0-9,]', '', line.read()).split(',')
Explanation: Initalisierung der Stopwörter
Im folgenden Code-Block werden die Stopwörter aus der Datei stop_words.txt ausgelesen und in der Variablen stopwords gespeichert.
End of explanation
for page in pages:
    for term in nltk.word_tokenize(page['text']):
        if term not in exclude and term not in stopwords:
            term_set.add(porter.stem(term).lower())
Explanation: Berechnung aller vorkommenden Wörter
Um alle vorkommenden Wörter zu berechnen, werden alle Texte der Dokumente durchlaufen und mittels des nltk-Wörter-Tokinisierers tokinisiert. Jedes resultierende Wort wird anschließend analysiert und sofern es kein Zeichen oder ein Stopwort ist, dem term_set hinzugefügt.
End of explanation
for page in pages:
    tf_dict[page['id']] = {}
    for term in term_set:
        tf_dict[page['id']][term] = 0
    for term in nltk.word_tokenize(page['text']):
        if term not in exclude and term not in stopwords:
            tf_dict[page['id']][porter.stem(term).lower()] += 1
Explanation: Berechnung des Term-Frequency-Indexes
Um den Term-Frequency-Indexes aufzustellen, wird jedes Dokument durchlaufen, wobei zunächst für jedes Wort aus dem term_set ein Wert von 0 initialisiert wird. Anschließend wird jedes Wort innherhalb des Dokumentes analysiert und, sofern es sich um kein Zeichen oder Stopwort handelt, der passende Zähler um eins erhöht.
End of explanation
tf_df = pd.DataFrame(tf_dict)
tf_df.to_csv('index.txt', header=True, index=True, sep=';')
Explanation: Speichern des Term-Frequency-Indexes
Das Resultat wird in der Datei index.txt gespeichert. Dabei stellt jede Zeile ein Wort und jede Spalte ein Dokument dar.
End of explanation
df_dict = {}
Explanation: e) Implement a function search to search for documents containing given words
Folgend wird ein TF-Index für alle Wörter innerhalb der Dokumente (Seiten) berechnet.
Variablen
Folgende Variablen werden verwendet:
* df_dict: Dictionary, das für jedes Wort die Anzahl festhält, in wie vielen Dokumenten das Wort vorkommt und die Dokumenten, in denen es vorkommt.
End of explanation
def get_weighted_idf(term):
    if term in df_dict:
        if df_dict[term]['count'] == 0:
            return 0
        else:
            return math.log10( n / df_dict[term]['count'])
    else:
        return 0
Explanation: Funktionen
Gewichtete Inverse-Document-Frequency
Die Funktion get_weighted_idf() berechnet mittels der folgenden Formel die gewichtete Inverse-Document-Frequency für den übergebenen Term.
$$ w_t =
  \begin{cases}
    log_{10}( \frac{N}{df_t})       & \quad \text{if } df_t > 0\
    0 & \quad \text{otherwise}\
  \end{cases}
$$
End of explanation
def get_weighted_tf_idf(doc_id, term):
    return get_weighted_tf(doc_id, term) * get_weighted_idf(term)
Explanation: Gewichteter TF-IDF-Wert
Die Funktion get_weighted_tf_idf() brechnet mittels der folgenden Formel den gewichteten TF-IDF-Wert für den übergebenen Term im Bezug auf das Dokument mit der übergebenen Dokumenten-Id.
$$ \text{tf-idf}{t,d} = tf{t,d} \times idf_t $$
End of explanation
def search(terms, page_rank=False):
    result = {}
    for page in pages:
        result[page['id']] = 0
        for term in terms:
            result[page['id']] += get_weighted_tf_idf(page['id'], porter.stem(term).lower())
            if page_rank:
                result[page['id']] *= page['rank+1']
    return result
Explanation: Search
Die Funktion search() brechnet für jede Seite einen Wert, der aussagt, wie gut die jeweilge Seite zu den gesuchten Termen passt. Dabei berechnet sich der Wert ohne Einbeziehung des PageRanks wie folgt:
$$ \text{Score}(q, d) = \sum_{t \in q} \text{tf-idf}_{t,d}$$
Mit Einbeziehung des PageRanks berechnet sich der Wert wie folgt:
$$ \text{Score}(q, d) = \sum_{t \in q} \text{tf-idf}_{t,d} \times PageRank_d $$
End of explanation
for page in pages:
    for term in nltk.word_tokenize(page['text']):
        if term not in exclude and term not in stopwords:
            if porter.stem(term).lower() in df_dict and page['id'] not in df_dict[porter.stem(term).lower()]['documents']:
                df_dict[porter.stem(term).lower()]['count'] += 1
                df_dict[porter.stem(term).lower()]['documents'] += [page['id']]
            elif porter.stem(term).lower() not in df_dict:
                df_dict[porter.stem(term).lower()] = {'count': 1,
                                                      'documents': [page['id']]
                                                     }          
Explanation: Berechnung der Document-Frequency für jedes Wort
Zur Berechnung der Document-Frequency werden alle Seiten durchlaufen, wobei jedes Wort des Textes der Seite betrachtet wird. Sofern das Wort kein Zeichen oder Stopwort ist und noch nicht im df_dict vorkommt, wird es neu mit der  Document-Frequency 1 und der Dokumenten-Id angelegt. Existiert das Wort bereits im df_dict, wird nur dann die Document-Frequency um eins erhöht, wenn die aktuelle Dokumenten-Id noch nicht existiert.
End of explanation
search_terms = [['token'],['index'],['classification'],['classification', 'token']]
Explanation: Suche mit TF-IDF und anschließende Speicherung
Gesucht wird nach folgenden Termen:
* token
* index
* classification
* classification, token
End of explanation
with open('tfidf_search.txt', 'w') as f:
    for search_term in search_terms:
        f.write('Suchwort: %s\n\n' % ', '.join(search_term))
        result = search(search_term)
        for key in result:
            f.write("%s: %s\n" % (key, result[key]))
        f.write('\n\n')
Explanation: Im folgenden Code-Block wird jeder Such-Term durchgegangen und der jeweilige Wert für jedes Dokument berechnet. Der Wert setzt sich aus dem TF-IDF-Wert zusammen. Anschließend wird das Ergebnis in der Datei pageranke_search.txt gespeichert.
End of explanation
search_terms = [['token'],['index'],['classification'],['classification', 'token']]
Explanation: f) Extend your search function and include PageRank to score the documents
Suche mit TF-IDF und PageRank und anschließende Speicherung
Gesucht wird nach folgenden Termen:
* token
* index
* classification
* classification, token
End of explanation
with open('pageranke_search.txt', 'w') as f:
    for search_term in search_terms:
        f.write('Suchwort: %s\n\n' % ', '.join(search_term))
        result = search(search_term, page_rank=True)
        for key in result:
            f.write("%s: %s\n" % (key, result[key]))
        f.write('\n\n')
Explanation: Im folgenden Code-Block wird jeder Such-Term durchgegangen und der jeweilige Wert für jede Seite berechnet. Der Wert setzt sich aus dem TF-IDF-Wert und PageRank zusammen. Anschließend wird das Ergebnis in der Datei pageranke_search.txt gespeichert.
End of explanation
<END_TASK>