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-Suche, die uns für eine Suchanfrage meist die richtige Seite aus Billionen von Webseiten herausfindet.

Es bestehen die folgenden Kapitel:

• Information Retrieval (diese Seite)
• Text Indexing
• Range Queries

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 $𝒪(log(n))$, mit einer Hashtable sogar nur konstante (von der Korpusgrösse unabhängige) Zeit, also $𝒪(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 Corpus ist ein Dictionary, dessen Keys gerade die Dokumenten-Ids sind; jedes Dokument ist wiederum ein kleines Dictionary, wobei jedes dieselben Keys (name…) aufweist.

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:

def linear_search(dataset, attribute, query):
    """Returns an iterable (list or generator) of all elements
       in dataset for which the given attribute matches query."""
    pass
 
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 lässt sich der Fortschritt bequem darstellen. Das Modul muss einmalig z.B. mit %pip install tqdm installiert werden.

%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
    from tqdm.auto import tqdm
 
    # Fieldnames from https://download.geonames.org/export/dump/
    fields = ['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']
 
    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=fields)
            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?

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)