Information Retrieval

Beim Information Retrieval geht es darum, aus einer potentiell riesigen Menge von Dokumenten (en. corpus) diejenigen herauszufinden, die einer Suchanfrage (en. query) am besten entsprechen. Die am besten bekannte Anwendung ist die Internet-Such, die uns für eine Suchanfrage meist die richtige Seite aus Billionen von Webseiten herausfindet.

Es gibt dabei zwei Probleme zu lösen:

• Die Dokumente identifizieren, die der Suche entsprechen (en. selection).
• Die Resultat-Liste der Relevanz entsprechend sortieren (ranking).

Um diese Aufgaben schnell zu lösen, ist es im allgemeinen nicht möglich, den ganzen Korpus für jede Anfrage zu durchsuchen. Stattdessen bauen wir einen Index, der es erlaubt, effizient die geforderten Dokumente zu finden.

Wir verwenden Jupyter Notebooks, um Code zu schreiben und dokumentieren. Erstelle ein neues Github-Repo mit einen Jupyter Notebook, um darin die Aufgaben zu lösen.

Haben unsere Elemente einen eindeutigen Schlüssel (key), der uns für die Suchanfrage genügt, so können wir beispielsweise ein Dictionary verwenden. Der Lookup dauert mit Binärsuche $\mathcal{O}(\log{}n)$, mit einer Hashtable sogar nur konstante (von der Korpusgrösse unabhängige) Zeit, also $\mathcal{O}(1)$.

In der Datenbank-Sprache nennen wir einen eindeutigen Schlüssel auch primary key.

Für die Entwicklung benötigen wir ein kleines Toy-Dataset. Zum Beispiel dieses hier:

thurgau = {
    0: {'name': 'Romanshorn', 'population': 11556, 'latitude': 47.56586, 'longitude': 9.37869},
    1: {'name': 'Amriswil', 'population': 14313, 'latitude': 47.54814, 'longitude': 9.30327},
    2: {'name': 'Arbon', 'population': 15459, 'latitude': 47.51360, 'longitude': 9.42999},
    3: {'name': 'Weinfelden', 'population': 11893, 'latitude': 47.56638, 'longitude': 9.10588},
    4: {'name': 'Frauenfeld', 'population': 26093, 'latitude': 47.55856, 'longitude': 8.89685},
    5: {'name': 'Kreuzlingen', 'population': 22788, 'latitude': 47.645837,'longitude': 9.178608},
    6: {'name': 'Egnach', 'population': 4897, 'latitude': 47.54565, 'longitude': 9.37864},
}

Der Zugriff auf einen Eintrag mit bekanntem key ist trivial: thurgau[6] liefert Egnach blitzschnell zurück - und das täte es auch, wenn das Dataset 6 Millionen Einträge hätte. Nun möchten wir den Korpus aber nach den Ortsnamen durchsuchen können.

Schreibe eine Funktion def linear_search(dataset, attribute, query), die einen beliebigen Korpus (=Dataset) durchsucht nach allen Einträgen, die ein Attribut attribute mit dem exakten Wert query haben.

linear_search(thurgau, 'name', 'Egnach') soll also alle Einträge für Egnach liefern:

for result in linear_search(thurgau, 'name', 'Egnach'):
    print(result)

Die einfachste Möglichkeit sammelt alle Resultate in einer Liste und gibt diese zurück. Das kann aber teuer werden, wenn das Resultset gross ist.

Eine schönere Variante sind Python Generators: statt die Resultate zu sammeln, verwenden wir das yield Keyword, um jedes Suchresultat zurückzugeben. Unsere Funktion wird damit zu einem Generator, über den wir mit for iterieren können. Statt auf einmal alle Resultate zu berechnen, wird immer nur das nächste berechnet.

Mit dem tqdm Modul lassen sich lange Schleifen mit einem Progress-Monitor versehen.

%pip install tqdm
%pip install ipywidgets
 
from tqdm.auto import tqdm
 
def linear_search(dataset, attribute, query):
    """Linear search through dataset, looking for entities with an attribute equal to query."""
    for town in tqdm(dataset.values()):
        if town[attribute] == query:
            yield town

Die lineare Suche für das Toy-Dataset dauert nicht lange - aber was, wenn unser Dataset grösser ist? In dieser Aufgabe erstellst du ein (oder zwei) grössere Datasets. Nach dem einlesen sollen sie ein ähnliches Format haben wie das Toy-Dataset: ein Dictionary mit int Keys und für jeden Eintrag einem weiteren Dictionary als Value.

Lade die Datenbank aller Ortschaften der Welt von http://download.geonames.org/export/dump/ herunter und lies sie als Dictionary places in Python ein. Du kannst entweder cities500.zip (ca. 140k Ortschaften) oder allCountries.zip (12M Features) verwenden - je nachdem, wie mutig du bist… Achtung, das zweite Dataset enthält nicht nur Ortschaften, sondern auch Quartiere, Parks, Länder und Kontinente.

Das Dictionary sollte als Schlüssel die geonameid verwenden und als Wert wiederum ein Dictionary von den Spaltennamen (Attributen) zu den Werten jedes Ortes. Obige URL beschreibt auch das Datenformat und die Spalten. Verzichte dabei auf Pandas - wir wollen in diesem Block herausfinden, wie Datenbanken funktionieren und nicht eine benutzen!

Du hast alles richtig gemacht, wenn dein Code ungefähr das folgende ausgibt:

print(places[2658985])

{'geonameid': '2658985', 'name': 'Romanshorn', 'asciiname': 'Romanshorn', 'alternatenames': 'Romanshorn,Romanskhorn,luo man si huo en,Романсхорн,羅曼斯霍恩', 'latitude': '47.56586', 'longitude': '9.37869', 'feature class': 'P', 'feature code': 'PPLA3', 'country code': 'CH', 'cc2': '', 'admin1 code': 'TG', 'admin2 code': '2011', 'admin3 code': '4436', 'admin4 code': '', 'population': '8956', 'elevation': '', 'dem': '401', 'timezone': 'Europe/Zurich', 'modification date': '2013-04-02'}

Hinweise:

def read_geonames(filename):
    from io import TextIOWrapper  # to convert the binary stream into unicode
    import zipfile
    import csv
 
    result = {}
    with zipfile.ZipFile(f'data/{filename}.zip') as myzip:    # open the zip archive
        with myzip.open(f'{filename}.txt', 'r') as csv_file:  # open a single file in the archive
            reader = csv.DictReader(TextIOWrapper(csv_file, 'utf-8'), delimiter='\t', fieldnames=['geonameid', 'name', 'asciiname', 'alternatenames', 'latitude', 'longitude', 'feature class', 'feature code', 'country code', 'cc2', 'admin1 code', 'admin2 code', 'admin3 code', 'admin4 code', 'population', 'elevation', 'dem', 'timezone', 'modification date'])
            for data in tqdm(reader, desc=filename):
                result[int(data['geonameid'])] = data
 
    return result
 
cities = read_geonames('cities500')  # Use this if you don't want to wait too long...
places = read_geonames('allCountries')

Wie lange dauert die lineare Suche nach Ortschaften mit dem Namen London? Wieviele Londons gibt es?

In Jupyter Notebooks lässt sich die Zeit einer Operation sehr einfach mit dem %%time Magic messen:

%%time
for result in linear_search(places, 'name', 'London'): print(result)

Lineare Suche dauert uns zulange - wie können wir die Suche beschleunigen? Diskutiert und implementiert!

Lösungsidee

index = {
    'Romanshorn' : {2658985, 11963382},
    # ...
}

Das Erstellen des Index dauert ziemlich lange und lohnt sich natürlich nur, wenn wir mehr als einmal suchen. Wie oft müssen wir suchen, damit wir die Indexerstellung kompensiert haben?

Tipp: Mit dem tqdm-Modul lässt sich der Fortschritt bequem darstellen. Das Modul muss einmalig z.B. mit %pip install tqdm installiert werden.

from tqdm.auto import tqdm
 
def build_attribute_index(dataset, attribute):
    index = dict()
    for id, entity in tqdm(dataset.items()):
        pass  # Your code here: add the entity to the index
    return index

Probiert zuerst mit dem Toy-Dataset, bevor ihr euch an die grossen Datasets wagt!

from tqdm.auto import tqdm
 
def build_attribute_index(dataset, attribute):
    index = dict()
    for id, entity in tqdm(dataset.items()):
        # setdefault retrieves the value for key or adds
        # the given default value if the key does not exist.
        index.setdefault(entity[attribute], set()).add(id)
    return index
 
def query_index(dataset, idx, query):
    """Search using the secondary index 'idx', then look up the entity in the dataset."""
    for id in idx[query]:
        yield dataset[id]
 
%time name_idx = build_attribute_index(places, 'name')

%%time
for result in query_index(places, name_idx, 'London'):
    print(result)

In der Ortsdatenbank möchten wir alle Orte finden, deren Bevölkerung grösser oder kleiner als ein beliebiger Schwellenwert ist. Wir wollen einen Index erstellen, der für alle möglichen Schwellenwerte funktioniert und schnell ist.

Wie stellen wir das am besten an, so dass die Abfrage nach einem Bereich effizient ist? Können wir etwas ähnliches machen wie oben mit Dictionaries? Diskutiert in Gruppen!

Implementiert eine effiziente Abfrage für Range Queries. In allCountries.zip gibt es 95 Entitäten, die zw. 10M-15M Einwohner haben, davon 12 Städte.

Hinweise

%%time
for place in query_numeric_index(places, population_idx, 10e6, 15e6):
    print(place['name'], place['population'])

from tqdm.auto import tqdm
 
# Create the index.
def build_integer_range_index(dataset, attribute):
    index = []
    for id, entity in tqdm(dataset.items()):
        # Only include entities that specify a population (no mountains and lakes, please)
        try:
            value = int(entity[attribute])
            if value > 0:
                index.append((value, id))
        except ValueError:
            pass
    index.sort()  # Sort first by population, then id
    return index
 
 
def query_numeric_index(dataset, idx, lower, upper):
    # Use bisect instead of implementing binary search ourselves:
    import bisect
    # Use operator.itemgetter(0) to extract the population from the (pop, id) tuple.
    import operator
 
    # The index of the smallest entity in idx greater or equal than lower.
    lower_index = bisect.bisect_left(idx, lower, key=operator.itemgetter(0))
    # The index of the smallest entity in population_idx greater than upper.
    upper_index = bisect.bisect_right(idx, upper, key=operator.itemgetter(0))
    for index_key in range(lower_index, upper_index):
        yield dataset[idx[index_key][1]]
 
%time population_idx = build_integer_range_index(places, 'population')

Statt Binärsuche könnten wir auch einen Binären Suchbaum (Binary Search Tree - BST) verwenden. Jeder Knoten (Node) des Baums speichert eine Stadt mit ihrer Bevölkerungszahl als Schlüssel (Key) und der dazugehörigen geonameid als Wert (Value). Dazu hat jeder Knoten noch zwei Unterknoten: Im Knoten left werden alle Knoten mit kleineren Keys gespeichert, im Knoten right werden alle Knoten mit grösseren Keys gespeichert.

Ein Knoten sieht in Python zum Beispiel so aus:

class Node:
    """A tree node, also represents an entire (sub-)tree."""
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

Aufgabe: Schreibe eine Funktion def build_tree(sorted_tuples, left_idx, right_idx), die aus einer sortierten Liste von Tupeln (population, geonameid) einen Baum baut, der den obigen Bedingungen genügt.

Hinweise

node.left = build_tree(sorted_tuples, left_idx, ...)
node.right = build_tree(sorted_tuples, ..., right_idx)

Lösung

Suche im BST Wie können wir im Suchbaum ein Element finden? Wir steigen im Baum vom Wurzelknoten her ab, und wenden uns jeweils links oder rechts, je nachdem, ob der Key kleiner oder grösser als der gewünschte Wert ist.

Schreibe eine Funktion bst_search(node, key), die den Value des gewünschten Knotens zurückgibt. Wie sieht die rekursive Variante davon aus?

Wie könnte eine (rekursive) Funktion aussehen, die alle Values zurückgibt, die zwischen zwei Grenzen stehen (range query)?

Hinweise:

Visualisiere einen von dir gebauten Baum mit Graphviz. Experimentiere zuerst mit dem Online-Editor, um ein Gefühl dafür zu kriegen, wie ein Baum aussehen könnte. Verwende anschliessend das graphviz Package in Python wie folgt.

Beachte:

• Einen neuen Graph erzeugen wir mit graph = graphviz.Digraph('Graph Title').
• In Graphviz werden zuerst Knoten (nodes) erstellt
  • graph.node('A')
  • graph.node('B')
• Kanten (edges) werden zwischen zwei Knoten eingefügt, diese werden über ihre Id identifiziert:
  • graph.edge('A', 'B')
• Rekursion wäre wieder mal hilfreich…

#### Christmas Challenge Style deinen BST als Christmas Tree!

Ideen:

• Node Shapes
  • Mcircle anyone?
  • es gibt auch Custom Shapes…
• color Attribut
• Background Image…

Idee

Lösung:

def render_tree(graph, node, nuller=""):
    """Renders the tree in graphviz."""
    if node is None:
        # In order to have separate Nil-nodes, we need to create artificially
        # named nodes with unique names. We use the 'nuller' parameter to create
        # these, which is the left/right-path down from the root.
        graph.node(nuller, "", shape="point")
        return nuller
 
    id = str(node.key)
    graph.node(id, f"< <B>key:</B> {id}<BR/><B>id:</B> {str(node.value)}<BR/><B>town:</B> {towns[node.value]['name']} >")
    left_key = render_tree(graph, node.left, nuller + "l")
    graph.edge(id, left_key)
    right_key = render_tree(graph, node.right, nuller + "r")
    graph.edge(id, right_key)
    return id
 
dot = graphviz.Digraph("Population Search Tree")
render_tree(dot, tree)
dot

Bevölkerungszahl, Geburtstage etc. sind einfach, weil die Bevölkerungszahl und Zeit skalare, also eindimensionale Grössen sind. Aber wie können wir einen zweidimensionalen Index schaffen, der uns alle Elemente liefert, die innerhalb eines Rechtecks von Längen- und Breitengraden liegen?

• Quadtree
• Range Tree
• K-d_tree
• S2 Library

Versuche, einen K-d-Tree zu bauen. Clone dazu das https://github.com/tkilla77/ksr_talit_indexing Jupyter Notebook und entwickle es weiter.