Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- talit:spatial [2023-12-18 18:53] – [Christmas Challenge] hof
+++ talit:spatial [2024-09-23 11:49] (aktuell) – hof
@@ Zeile 1: / Zeile 1: @@
-# Information Retrieval
-## Build Your Own Google
-<nodisp 1>
-++++Repo|
-https://github.com/tkilla77/ksr_talit_indexing
-++++
-</nodisp>
-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.
-### 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 $\mathcal{O}(\log{}n)$, mit einer [[gf_informatik:daten:processing:dictionaries_tutorial|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_.
-### Toy-Dataset
-Für die Entwicklung benötigen wir ein kleines Toy-Dataset. Zum Beispiel dieses hier:
-<code python>
-thurgau = {
-: {'name': 'Romanshorn', 'population': 11556, 'latitude': 47.56586, 'longitude': 9.37869},
-: {'name': 'Amriswil', 'population': 14313, 'latitude': 47.54814, 'longitude': 9.30327},
-: {'name': 'Arbon', 'population': 15459, 'latitude': 47.51360, 'longitude': 9.42999},
-: {'name': 'Weinfelden', 'population': 11893, 'latitude': 47.56638, 'longitude': 9.10588},
-: {'name': 'Frauenfeld', 'population': 26093, 'latitude': 47.55856, 'longitude': 8.89685},
-: {'name': 'Kreuzlingen', 'population': 22788, 'latitude': 47.645837,'longitude': 9.178608},
-: {'name': 'Egnach', 'population': 4897, 'latitude': 47.54565, 'longitude': 9.37864},
-}
-</code>
-### 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>
-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 [[https://docs.python.org/3/tutorial/classes.html#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 lassen sich lange Schleifen mit einem Progress-Monitor versehen.
-<nodisp 1>
-++++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 1>
-++++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
-    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')
-</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?
-**Tipp:**
-Mit dem `tqdm`-Modul lässt sich der Fortschritt bequem darstellen. Das Modul muss einmalig z.B. mit `%pip install tqdm` installiert werden.
-<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 1>
-++++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>
 ## Range Queries
@@ Zeile 261: / Zeile 62: @@
 ++++
 </nodisp>
 ### Aufgabe 4c
@@ Zeile 282: / Zeile 84: @@
 ++++Hinweise|
-  * Das Wurzel-Element is idealerweise das Element in der Mitte zwischen `left_idx` und `right_idx` (Median), dann sind beide Subtrees ungefähr gleich gross, der Baum ist _balanciert_.
+  * Das Wurzel-Element ist idealerweise das Element in der Mitte zwischen `left_idx` und `right_idx` (Median), dann sind beide Subtrees ungefähr gleich gross, der Baum ist _balanciert_.
   * Rekursion ist praktisch: Schaffe einen neuen Knoten `node = Node(key, value)`, anschliessend rufe die Funktion für den linken und rechten Subtree auf:
 <code python>
@@ Zeile 291: / Zeile 93: @@
 ++++Lösung|
-<nodisp 2>
+<nodisp 1>
 <code python>
 def build_tree(sorted_tuples, left=None, right=None):
@@ Zeile 355: / Zeile 157: @@
 ++++
 </nodisp>
 ### Graph Visualization ###
@@ Zeile 406: / Zeile 210: @@
 [[http://magjac.com/graphviz-visual-editor/?dot=graph%20%7B%0A%20%20%20%20bgcolor%3Dlightblue%0A%20%20%20%20node%20%5Bstyle%3Dfilled%2C%20color%3Dtransparent%2C%20style%3Dradial%5D%0A%20%20%20%20A%20%5Bshape%3Dstar%2C%20fillcolor%3D%22gold%3Abrown%22%5D%3B%0A%20%20%20%20node%20%5Bshape%3Dtriangle%2C%20fillcolor%3D%22green%3Adarkgreen%22%5D%0A%20%20%20%20A%20--%20B%3B%0A%20%20%20%20A%20--%20C%3B%0A%20%20%20%20node%20%5Bshape%3Dcircle%2C%20fillcolor%3D%22red%3Adarkred%22%5D%0A%20%20%20%20B%20--%20D%3B%0A%20%20%20%20B%20--%20E%3B%0A%20%20%20%20C%20--%20F%3B%0A%20%20%20%20C%20--%20G%3B%0A%7D|Idee]]
-Yes:
+Yes (courtesy of Laurin):
-{{:talit:spatial:pasted:20231218-185336.png}}
+{{:talit:spatial:pasted:20231218-185336.png?nolink&800}}
 ## Spatial Algorithms