# 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)
  * [[indexing]]
  * [[spatial]]

## Build Your Own Google

<nodisp 0>
++++Repo|
https://github.com/tkilla77/ksr_talit_indexing
++++
</nodisp>


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.

### Jupyter
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.

## Direkter Schlüssel

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 [[gf_informatik:daten:processing:dictionaries_tutorial|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_.

### Toy-Dataset

Für die Entwicklung benötigen wir ein kleines Toy-Dataset. Zum Beispiel dieses hier:
<code python>
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},
}
</code>

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.

### Aufgabe 1 - Lineare Suche

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:

<code python>
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)
</code>

#### Python Generators
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 [[generators|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.

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

<nodisp 0>
++++Lösung|
<code python>
%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
</code>
++++
</nodisp>

### Aufgabe 2 - Ernsthafte Datasets

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:

<code python>
print(places[2658985])
</code>
<code bash>
{'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'}
</code>

++++Hinweise:|
  * https://docs.python.org/3/library/zipfile.html
  * https://docs.python.org/3/library/io.html#io.TextIOWrapper
++++

<nodisp 0>
++++Lösung|
Zuerst muss die Datei in `data/cities500.zip` bzw. `data/allCountries.zip` gespeichert werden.

<code python>
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')
</code>
++++
</nodisp>

## Separater Index

### Aufgabe 3a
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:

<code python>
%%time
for result in linear_search(places, 'name', 'London'): print(result)
</code>

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

++++Lösungsidee|
Wir speichern einen zusätzlichen _Index_, zum Beispiel als Dictionary vom gewünschten Such-Kriterium zum einem [[https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset|Set]] von passenden `geonameids`:

<code python>
index = {
    'Romanshorn' : {2658985, 11963382},
    # ...
}
</code>

Der Lookup passiert dann zweistufig: zuerst werden die Ids der Resultate im Index gesucht, anschliessend werden die Dokumente aus dem Dataset geladen.
++++

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?

<code python>
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
</code>

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

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

`name_idx` ist ein Dictionary vom `name` Attribut auf die Menge der passenden `geonameid`s. Erweiterungsidee: Statt `name` verwenden wir das `alternatenames` Attribut - Achtung, dieses enthält alle möglichen Namen mit Kommas getrennt.

<code python>
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')
</code>

<code python>
%%time
for result in query_index(places, name_idx, 'London'):
    print(result)
</code>
++++
</nodisp>