Programmiertechnik II SS26, Übung 4

Pro Übung gibt es 20 Punkte. Für die Zulassung zur Prüfung müssen in allen Übungen mindestens 50% der Punkte insgesamt sowie mindestens 25% in jeder einzelnen Übung erzielt werden.

Der Code für diese Aufgabe kann als Repository geklont und lokal kompiliert werden. Dafür ist es nötig, die Git-Submodule zu initialisieren und zu aktualisieren (wichtig‼️):

git submodule update --init

Anschließend kann

make tests

im Projektordner ausgeführt werden, um die Tests zu kompilieren. (Der Code kann unabhängig von den Tests mit make all kompiliert werden.)

Hinweis: Hilfestellung zum Setup der Entwicklungsumgebung und des Debuggers finden Sie in Übung 1.

Einleitung

Wiederholtes Suchen in großen Datenmengen ist ein zentrales Problem der Informatik. Typischerweise geht es dabei entweder um Dictionary-Lookups (Schlüssel → Wert) oder um Set-Membership (Ist ein Element enthalten?).

Unser konkreter Use Case: Set-Membership im Genom

In dieser Übung betrachten wir einen realistischen Datensatz:
Das menschliche Y-Chromosom aus dem Human Genome Project (data/Homo_sapiens.GRCh38.dna.chromosome.Y.fa).
Nach Entfernen von Whitespace enthält es ca. 58.2 Millionen Zeichen aus dem Alphabet {C, G, A, T, N}.

Wir fokussieren uns auf folgende Fragestellung:

Ist eine gegebene DNA-Sequenz (der Länge 12) im Genom enthalten?

Diese Information ist biologisch relevant, z. B. bei:

• Mutationsanalyse
• Primer-Design
• Qualitätskontrolle in Sequenzierungsverfahren

Formal handelt es sich um ein Set-Problem: Das Genom definiert eine große Menge von Teilstrings, und wir prüfen, ob ein gegebenes Element dazugehört.

Anmerkung: Sets sind sehr nah verwandt mit dem Dictionary. Ein Set speichert nur Schlüssel, ein Dictionary speichert Schlüssel-Wert-Paare. Fast jede Datenstruktur für Sets lässt sich mit geringem Aufwand zu einer Map/Dictionary erweitern, indem zusätzlich ein Wert gespeichert wird.

Aufgabe 1: Naiver Ansatz (2p)

Relevante Dateien: src/NaiveSearch.h

Implementieren Sie eine naive Substring-Suche zur Beantwortung von Set-Membership-Anfragen.

Die Funktion soll prüfen, ob ein gegebener String pattern im Text text enthalten ist.
Verwenden Sie dafür einen einfachen, zeichenweisen Vergleich ohne Vorverarbeitung oder zusätzliche Datenstrukturen.

Aufgabe 2: Bloom-Filter (8p)

Relevante Dateien: hash.h, BloomFilter.h

Aufgabe 2.1: (2p): Hashfunktionen für Zeichenketten
Implementieren Sie zwei generische Hashfunktionen für Zeichenketten. Gehen Sie davon aus, dass der Template-Typ T iterierbar ist und sich die Elemente als Ganzzahlen auswerten lassen. T könnte also z. B. std::string oder std::vector<int> sein.

• sum_hash (Unit 7, Folie 13, Idee 1)
• rolling_hash (Unit 7, Folie 13, Idee 2) (Wikipedia: Polynomial Rolling Hash)

Führen Sie make tests aus und diskutieren Sie die Kommandozeilen-Ausgabe von TEST CASE: A2.1. Welche Hashfunktion eignet sich besser für Zeichenketten und warum? Inwiefern ist das anhand der Tests erkennbar?

Hinweis: TEST CASE: A2.1 gibt unter anderem das Ergebnis des Chi-Quadrat-Tests an. Dabei wird gemessen, wie gleichmäßig die Hashwerte auf die Buckets verteilt sind. Ein hoher Chi-Quadrat-Wert bedeutet, dass manche Buckets überlastet und andere leer sind. Der p-Wert gibt die Wahrscheinlichkeit an, einen so großen oder größeren Chi-Quadrat-Wert bei einer Gleichverteilung zu beobachten.

Aufgabe 2.2: (2p): Hashfunktionen für den Bloom-Filter
Je nach Bloom-Filter brauchen wir beliebig viele verschiedene Hashes pro Schlüsselwert. Implementieren Sie drei Funktionen, die jeweils $k$ verschiedene Hashes für eine Eingabe generieren:

• hash_keys_iterative: $\forall i \in \set{2\dots k}: h_i(x) = h_1(h_{i-1}(x))$, wobei wir als $h_1$ rolling_hash wählen und die Ausgabe der vorherigen Hashfunktion als String verwenden. Da die Hashfunktionen deterministisch sind, haben alle Hashes die gleichen Kollisionen. Warum verringert dieser Ansatz trotzdem die False-Positive-Rate des Bloom-Filters?
• hash_keys_polynomial: Erzeugt $k$ verschiedene Hashes, indem rolling_hash mit $k$ unterschiedlichen Multiplikatoren aufgerufen wird.
• hash_keys_polynomial_primes: Genau wie hash_keys_polynomial, allerdings sollen die $k$ Multiplikatoren ausschließlich Primzahlen sein.

Hinweis 1: Wenn die Primzahlen innerhalb der Hashfunktion in einer static const-Variable gespeichert werden, müssen sie nur einmal pro Template-Instanz berechnet werden statt bei jedem Aufruf neu. Hinweis 2: hash_keys_polynomial und hash_keys_polynomial_primes bekommen jeweils einen Startwert übergeben und verwenden dann angefangen mit diesem Startwert die jeweils nächstgrößeren $k$ Ganzzahlen (bzw. Primzahlen) als Multiplikatoren.

Aufgabe 2.3 (4p): Generische Bloom-Filter-Implementierung Vervollständigen Sie die BloomFilter-Klasse in BloomFilter.h.

Der Bloom-Filter soll die folgenden Operationen unterstützen:

• add(item): Fügt das Element item dem Bloom-Filter hinzu. Wie berechnen Sie am besten aus arbiträren Hashes einen Tabellenindex? (Hinweis: Modulo)
• contains(item): Überprüft, ob das Element item möglicherweise im Bloom-Filter enthalten ist.
• fill_ratio(): Gibt den Befüllungsgrad des Bloom-Filters zurück (also Summe der gesetzten Bits / Größe des Filters).

Der Bloom-Filter soll die folgenden Eigenschaften aufweisen:

1. konfigurierbare Größe $m$ (über den Konstruktor)
2. konfigurierbare Anzahl $k$ von Indizes pro Element (Template-Parameter N)
3. nicht auf einen bestimmten Datentyp beschränkt sein und generisch implementiert sein (Template-Typ T)
4. unabhängig von der verwendeten Hashfunktion implementiert

Verwenden Sie std::functional, um sicherzustellen, dass die Hashfunktion zur Kompilierzeit oder Laufzeit austauschbar ist und der Bloom-Filter für verschiedene Datentypen und Anwendungsfälle angepasst werden kann.

Aufgabe 3: Tries (8p)

Relevante Dateien: trie.h

Um Set-Membership-Anfragen effizienter zu beantworten, implementieren Sie einen Trie (Präfixbaum).

Ein Trie ist ein Baum, in dem jede Kante ein Zeichen aus dem gegebenen Alphabet (hier {C, G, A, T, N}) repräsentiert und jeder Pfad von der Wurzel zu einem anderen Knoten eine Zeichenfolge bildet, sodass gemeinsame Präfixe zusammengefasst werden. Dadurch lassen sich enthaltene Sequenzen effizient prüfen.
Ein weiterer Vorteil: Wenn alle Sequenzen der Länge k eingefügt wurden, sind auch kürzere Präfixe implizit enthalten.

Operationen

Der Trie soll folgende Methoden unterstützen:

• add: Fügt eine Zeichenfolge ein.
• contains: Prüft, ob ein Pfad für die Zeichenfolge existiert.
• observed: Wie contains, jedoch nur dann true, wenn der letzte Knoten als Ende einer gespeicherten Zeichenfolge markiert ist.

Falls beim Traversieren ein Zeichen nicht im Alphabet liegt oder ein Pfad nicht existiert, geben contains und observed false zurück. add wirft eine std::invalid_argument-Exception, wenn ein Zeichen der Eingabe nicht im Alphabet ist.

Hinweis: Einzelne Funktionen in der Trie-Klasse sind mit einem zusätzlichen Size-Template versehen, das unabhängig von den Template-Parametern der Klasse ist.

Beispiele für den Trie in der Abbildung:

• Für eine gespeicherte Sequenz GAGT:
  contains("GAGT") == true, observed("GAGT") == true
• Für das Präfix GAG:
  contains("GAG") == true, observed("GAG") == false
• Für GAM:
  beide false (M nicht im Alphabet)

---

Eigenschaften des Tries

• Der Trie ist über ein festes Alphabet definiert.
• Jede Zeichenfolge besteht aus Elementen dieses Alphabets.
• Zeichenfolgen müssen nicht notwendigerweise gleiche Länge besitzen.
• Knoten am Ende einer Zeichenkette werden markiert, müssen aber nicht zwangsläufig Blätter sein.
• Jeder Knoten kann bis zu |Alphabet| Kinder haben. (In der Implementierung bestimmt der Index des Kindes sein Zeichen. Nicht vorhandene Kinder werden durch nullptr abgebildet.)
• Eine Wurzel existiert, gehört aber selbst zu keiner Zeichenfolge.

Die Implementierung muss mit std::array-basierten Eingaben kompatibel sein (siehe Tests).

Aufgabe 4: Benchmarking (2p)

Relevante Dateien: bench_cli.cpp

Vergleichen Sie die drei verschiedenen Ansätze für Set-Membership anhand des Genom-Datensatzes mit dem Programm in bench_cli.cpp (vorgegeben):

• Die gesamte Datei data/Homo_sapiens.GRCh38.dna.chromosome.Y.fa wird als zusammenhängender String eingelesen.
• Jeder 12 Zeichen lange Substring wird in die jeweilige Datenstruktur eingefügt.
• Die 12 Zeichen langen Abfragen in data/genome_substr.csv werden anschließend auf Set-Membership überprüft.

Vergleichen Sie die Zeitmessungen, um die jeweiligen Datenstrukturen aufzubauen, Set-Membership zu überprüfen und die Genauigkeit der Resultate zu bewerten.

Führen Sie make bench in der Kommandozeile aus und diskutieren Sie die Resultate.

Vergleichen Sie die verschiedenen Hashfunktionen, indem Sie die folgenden Befehle ausführen:

make bench ARGS="data/Homo_sapiens.GRCh38.dna.chromosome.Y.fa data/genome_substr.csv 64000000 iter"

make bench ARGS="data/Homo_sapiens.GRCh38.dna.chromosome.Y.fa data/genome_substr.csv 64000000 poly"

make bench ARGS="data/Homo_sapiens.GRCh38.dna.chromosome.Y.fa data/genome_substr.csv 64000000 prime"

Notieren Sie die Ausgabe der Befehle in solution.md.

Optional: Vergleichen Sie die Ergebnisse bei variierender Anzahl von Hashfunktionen und Größe des Bloom-Filters. (Das Benchmarking des Tries kann dafür auskommentiert werden.) Sie können zur Berechnung der Kenngrößen für den Bloom-Filter hier Hilfe finden.

Abgabehinweise

• Bearbeiten Sie die mit // TODO markierten Stellen im Code.
• Für die in der Aufgabenstellung beschriebenen Datentypen und Algorithmen sollen die eigenen bzw. vorgegebenen Implementierungen genutzt werden. Davon abgesehen darf die STL verwendet werden. Notieren Sie sich für das Testatgespräch: Welche Teile der STL könnten theoretisch benutzt werden, um die Aufgaben zu implementieren?
• Korrekte Speicherverwaltung (new/delete, new[]/delete[] oder ggf. Initialisierung im Stack) gehört zur Aufgabenstellung :)
• Die Tests sollen alle grün sein (make tests), sind aber in erster Linie eine Hilfestellung und keine Garantie für die volle Punktzahl - dafür gibt es die Testatgespräche.