# Text Indexing

<nodisp 1>
++++Repo|
https://github.com/tkilla77/ksr_talit_indexing/blob/main/04_text_indexing.ipynb
++++
</nodisp>

Nachdem wir in [[retrieval]] ein einzelnes Attribut indexiert haben, möchten wir dasselbe für einen ganzen Text erreichen. Statt der Geodatenbank verwenden wir dafür Artikel von Wikipedia.

Natürlich benötigen wir auch wieder ein Toy-Dataset:

<code python>
documents = {
    1: "Ein Film über Sterne, mit Harrison Ford.",
    2: "Ein Film über Sterne von Antoine de Saint-Exupéry.",
    3: "In diesem Film gewinnt James Bond gegen Dr. No.",
}
</code>

Anders als bei der Geodatenbank müssen wir hier noch den Text in einzelne Wörter (_en_. Tokens) zerlegen.
### Aufgabe 1 - Tokenizer

Schreibe eine Funktion `def tokenize(text)` die einen Text in einzelne Wörter zerlegt und diese Tokens mit `yield` zurückgibt.

Die Funktion soll im folgenden Text-Indexing-Code aufgerufen werden, der ganz ähnlich funktioniert wie der [[retrieval#aufgabe_3b|Attribut-Indexing-Code]]:

<code python>
from tqdm.auto import tqdm
 
def build_text_index(dataset, index=None):
    """Builds and returns full-text index for all documents in a dataset. Adds to an existing index if one is given."""
    if index is None:
        index = dict()
    for id, document in tqdm(dataset):
        for token in tokenize(document):
            index.setdefault(token, set()).add(id)
    return index

toy_index = build_text_index(documents.items())
</code>

Anschliessend sollten wir unseren Index durchsuchen können:

<code python>
def query_index(index, query):
    return index.get(query, set())

query_index(toy_index, "James")
</code>

#### Fragen
  - Findet dein System einen Film über `'bond` (Kleinbuchstaben)?
  - Findet dein System einen Film über `'Ford'` (ohne Satzzeichen)?
  - Wieviele Filme über `'Sterne'` findest du?

Passe deinen Tokenizer so an, dass er sinnvoll mit Satzzeichen umgeht. Zudem möchten wir alle Texte in Kleinbuchstaben umwandeln. Der Index sollte anschliessend etwa so aussehen:

<code python>
{'ein': {1, 2},
 'film': {1, 2, 3},
 'über': {1, 2},
 'sterne': {1, 2},
 'mit': {1},
 'harrison': {1},
 'ford': {1},
 'von': {2},
 'antoine': {2},
 'de': {2},
 'saint': {2},
 'exupéry': {2},
 'in': {3},
 'diesem': {3},
 'gewinnt': {3},
 'james': {3},
 'bond': {3},
 'gegen': {3},
 'dr': {3},
 'no': {3}}
</code>

<nodisp 1>
++++Lösung|
<code python>
def tokenize(text):
    import re, string
    text = text.lower()
    # Solution with split/strip
    for token in text.split():
        yield token.strip(string.punctuation)
    # Alternative solution using regular expressions
    #yield from re.findall("\w+", text, )
</code>
++++
</nodisp>

Wir sehen bereits: Einige Wörter (`antoine`) sind _wertvoller_ als andere (`film`), um eine Frage richtig zu beantworten. Im obigen Beispiel liefert das Token `film` überhaupt keine Information darüber, welches Dokument am besten zur Query passt, da es in jedem Dokument vorkommt. Wir werden das Problem später mit _Stop Wording_ behandeln.


## Moar Data
Um unser System zu testen, müssen wir es natürlich auf eine grösseres Dataset loslassen. Dazu indexieren wir Film-Artikel aus wikipedia.de.

Als Start nehmen wir alle {{:talit:movies_1985.csv.zip|Wikipedia-Artikel über Filme von 1985}} (387 Filme, 0.7MB). Das CSV hat nur zwei Spalten:
  - Wikipedia-Url (was auch gut als Identifier taugt)
  - Artikel-Text

Grössere Datasets gibt es auf https://if.ksr.ch/talit/indexing (nur KSR-intern).

### Aufgabe 2 - Movie Index
Erstelle einen Index aller WP-Artikel über Filme von 1985. Schreibe dazu eine Generator-Funktion, um die WP-Artikel-Tupel aus dem ''.csv.zip'' zu yielden.

<nodisp 1>
++++Lösung|
<code python>
def read_movie_csv(filename):
    import csv
    with open(filename, 'r', encoding='utf-8') as csvfile:
        reader = csv.reader(csvfile)
        for url, text in reader:
            yield url, text
</code>
++++
</nodisp>

Wieviele Filme mit `'harrison'` gibt es? Und wieviele mit einem `'delorean'`?
## Stop Wording
Wenn du den erstellten Index untersuchst, wirst du Wörter wie ''der'' oder ''ein'' finden, die in praktisch allen Artikeln vorkommen. Entsprechend benötigen die sehr viel Platz im Index, und liefern auch kaum interessante Resultate.

Normalerweise werden solche _Stop Words_ bereits bei der Indexierung ignoriert. Natürlich könnten wir eine Stop-Word-Liste aus dem Internet laden - aber eigentlich haben wir ja alle Informationen selber bereits zur Hand, um eine solche zu erstellen: Wir kennen die Häufigkeit jedes Wortes, also in wie vielen Artikeln es vorkommt. Wörter, die in mehr als der Hälfte der Artikel vorkommen, dürften kaum interessant sein. Mehr als an der _absoluten_ Häufigkeit sind wir also interessiert an der _relativen_ Dokumentenhäufigkeit (_en._ document frequency): $\frac{frequency}{n}$.

### Aufgabe 3 - Stop Words
Erstelle eine Liste aller Wörter in unserem Index, absteigend sortiert nach relativer Dokumentenhäufigkeit.

Erstelle daraus eine Stop-Word-Liste (mit einem Cut-off bei 50%) und modifiziere `tokenize` so, dass die Funktion zusätzlich alle stop-words unterdrückt.

<nodisp 1>
++++Lösung|
<code python>
n = sum(1 for _ in read_movie_csv('data/movies_1985.csv'))
cutoff = 0.5
freqs = [(word, len(docs) / n) for word, docs in movie_idx.items() if len(docs) / n > cutoff]
import operator
freqs.sort(reverse=True, key=operator.itemgetter(1))
</code>

<code python>
stop_words = {freq[0] for freq in freqs}

def tokenize(text, stop_words=stop_words):
    import re
    for token in re.findall("\w+", text):
        if not token in stop_words:
            yield token.lower()
    
</code>
++++
</nodisp>
## Ranking
Beim Information Retrieval geht es nicht nur darum, welche Dokumente zur Query passen, sondern welche _am besten_ dazu passen. Ranking ist eine komplexe und manchmal undurchsichtige Wissenschaft, die von vielen gegenläufigen Interessen getrieben ist: Beispielsweise möchten ganz viele Webseitenbetreiber zuoberst in den Suchresultaten von Google landen - andererseits möchten die Benutzer die wirklich relevante Webseite zuoberst haben. Und Google möchte irgendwie Geld verdienen, indem es die obersten Plätze verkauft.

Nehmen wir folgendes Beispiel: Wir indexieren alle Film-Artikel der 1980er Jahre und wollen möglichst gute Suchresultate für folgende Queries:
  * ''michael fox delorean''
  * ''michael fox''
  * ''michael fox wortdasesnichtgibt''

Unsere Query-Funktion muss erstens mit mehreren Wörtern umgehen können - es bietet sich an, die `tokenize` Funktion auch hier anzuwenden und eine Suchanfrage für jedes Token in der Query durchzuführen. Die Frage ist allerdings, wie wir die einzelnen Resultatlisten kombinieren... 


### Aufgabe 4 - Multiple Query Tokens

Schreibe eine neue Query-Funktion, die mehrere Wörter kombinieren kann. Welche Kombinationsmethode wählst du?

<nodisp 1>
++++Lösung|

Mit der Vereinigung (_en_: union):

<code python>
def query_index(index, query):
    result_set = set()
    for token in tokenize(query):
        results = index.get(token, set())
        result_set = result_set.union(results)
    return result_set
</code>

Mit der Schnittmenge (_en_: intersection):

<code python>
def query_index(index, query):
    result_set = None
    for token in tokenize(query):
        results = index.get(token, set())
        result_set = results if result_set is None else result_set.intersection(results)
    return result_set
</code>
++++
</nodisp>

### Numerisches Ranking
Die Schnittmenge scheint für die Query ''michael fox delorean'' gut zu funktionieren, weil ''delorean'' ein ziemlich spezifisches Wort ist, das nur in wenigen Filmen vorkommt - aber was, wenn in der Query ein Wort vorkommt, das nicht im Index ist?

Die Vereinigungsmenge hingegen liefert sehr viele Resultate für eine Query wie ''michael fox delorean''.

#### Wortfrequenzen
Zuerst werden die Inverse Document Frequencies in ein Dictionary überführt, das einfach auszulesen ist:

<code python>
word_frequencies = {word: freq for word, freq in freqs}

table = [['Term', 'Relative Document Frequency']]
for token in tokenize("michael fox delorean"):
    table.append([token, word_frequencies[token]])

%pip install tabulate
from tabulate import tabulate
tabulate(table, headers="firstrow", floatfmt=".2%", tablefmt='html')
</code>

#### Inverse Document Frequency

Die erste Idee wäre, die Tokens nach ihrer _document frequency_ zu gewichten: Ein Wort, das nur in einem Dokument vorkommt, ist ein guter Hinweis dafür, dass dieses in die Resultatliste gehört. Ein Allerweltswort (soweit es noch nicht durch Stopwording herausgefiltert worden ist) ist hingegen kein sehr gewichtiges Indiz, dass ein es enthaltendes Dokument wichtig ist.

Wenn wir die Document Frequency plotten, sehen wir aber, dass die Frequenzen sehr ungleich verteilt sind:

<code python>
#!pip install matplotlib

def plot_terms(terms):
    import matplotlib.pyplot as plt
    import matplotlib as mpl
    import math

    labels = [x for x, y in terms.items()]
    values = [y for x, y in terms.items()]
    fig, ax = plt.subplots() 
    #ax.set_yscale('log')
    label_count = 10
    label_multiple = len(terms) // label_count
    ax.xaxis.set_major_locator(mpl.ticker.MultipleLocator(label_multiple, 0))
    ax.set_xticklabels([None] + labels[0:-1:label_multiple], rotation=90)
    #print(labels[0:-1:label_multiple])
    ax.plot(values)

plot_terms(word_frequencies)
</code>

{{:talit:indexing:pasted:20240830-143037.png?nolink&400}}

Das sieht nach einer exponentiellen Funktion aus ([[wpde>Zipfsches_Gesetz]]). Um die Werte näher zueinander zu bringen, hilft uns eine Logarithmus-Transformation - zudem invertieren wir die Werte, so dass seltene Wörter einen höheren Score haben als häufige:

<code python>
import math
log_terms = {term: math.log(1/weight) for term, weight in word_frequencies.items()}
print(f"Michael: {log_terms['michael']:.2g}, Fox: {log_terms['fox']:.2g}, delorean: {log_terms['delorean']:.2g}")

plot_terms(log_terms)
</code>

{{:talit:indexing:pasted:20240830-143300.png?nolink&400}}

#### Aufgabe 5: Ranking mit log IDF
Statt eine strikte AND-Verknüpfung aller Suchterme möchten wir ein Ranking erstellen, das alle Dokumente einschliesst, die mindestens einen Suchterm enthält. Jeder Such-Begriff soll entsprechend seiner _Inverse-Document-Frequency_ (IDF) zum Rang beitragen. Das bedeutet, dass das Auftreten des seltenen Begriffs ''delorean'' mehr zum Rang beiträgt als ein häufiges Wort wie ''michael''. Trotzdem sollte ein einzelnes seltenes Wort nicht alles andere ausblenden dürfen.

<nodisp 1>
++++Lösung|
<code python>
def query_index_weighted(index, query, k=10):
    """Returns the top k search results matching query."""
    result_set = dict()
    for term in tokenize(query):
        idf = log_terms[term]
        results = index.get(term, set())
        for result in results:
            result_set[result] = result_set.get(result, 0) + idf
    return dict(sorted(result_set.items(), reverse=True, key=lambda item: item[1])[:k])
</code>
++++
</nodisp>