Partie-Deduplizierung

Wie Duplikate aus den PGN-Dateien entfernt werden

Eine Kurzübersicht

Dieses System zur Deduplizierung von Schachpartien verarbeitet PGN-Dateien in mehreren Phasen, um Duplikate zu identifizieren und die Datenqualität zu optimieren. Zuerst werden PGN-Dateien eingelesen, wichtige Daten extrahiert und bereinigt, Hashes berechnet und Metadaten erkannt. Anschließend werden Spielerpaar-Gruppen über Fuzzy-Namensvergleiche konsolidiert. Darauf folgt die exakte Deduplizierung basierend auf Zugfolgen-Hashes, wobei der Header der besten Partie als Master gewählt wird. Spiele mit subsumierten Zugfolgen werden ebenfalls markiert. Eine weitere Phase nutzt Fuzzy-Matching für textuelle Ähnlichkeiten der Zugfolgen. Zum Schluss werden die einzigartigen Partien sowie optional die markierten Duplikate exportiert, wobei die Header-Qualität durch Integration von FIDE-Daten und eine detaillierte Bewertung optimiert wird, um die besten verfügbaren Informationen im Master-Spiel zu gewährleisten.

Du kannst gerne einen Kommentar unter diesem Artikel hinterlassen.

1. Phase: Import von PGN-Dateien

Diese Phase ist für das Einlesen und die Vorverarbeitung der PGN-Schachspiele zuständig, bevor sie in die Datenbank importiert werden.

Dateiverarbeitung: Das Skript liest PGN-Dateien aus der Quelle. Es kann große Dateien mithilfe von pgn-extract in kleinere, besser handhabbare „Chunks“ aufteilen. Vorhandene Chunks im temporären Verzeichnis werden priorisiert wiederverwendet, es sei denn, das Überschreiben wird erzwungen.
Datenextraktion: Für jedes Spiel werden wichtige Header-Informationen (wie Spieler, Datum, Ereignis, Ort) und die Zugsequenz extrahiert.
Bereinigung und Normalisierung:
- Chessbase EVAL-Kommentare ([%evp...]) werden automatisch entfernt.
- Leerzeilen im PGN-Text werden normalisiert.
- Spielernamen werden umfassend normalisiert und bereinigt, einschließlich der Entfernung von Titeln (GM, IM, etc.) und Ländercodes.
- Es werde FIDE-Spielerdaten (ID, Namen, Titel) aus der fide_players-Tabelle integriert, um Header anzureichern und die Spielerzuweisung zu präzisieren.
Hash-Berechnung: Eindeutige Hashes werden für verschiedene Aspekte des Spiels berechnet:
- Ein Hash für das gesamte Spiel (game_hash).
- Ein Hash für Spielerpaare (player_pair_hash).
- Ein Hash für die vollständige Zugsequenz (moves_hash_full).
- Partielle Zug-Hashes (alle 10 Halbzüge) und End-FENs zu bestimmten Halbzuganzahlen (moves_san_segment_hashes und end_fens_at_ply).
Metadaten-Erkennung: Es wird erkannt und gespeichert, ob der PGN-Text des Spiels Kommentare oder Variationen enthält.
Datumshandhabung: Das Skript versucht, flexible Datumsformate zu parsen und eine Qualitätsbewertung für das Datum zu berechnen. Es kann auch das EventDate bevorzugen, wenn es eine höhere Qualität aufweist.
FEN-Generierung: Die End-FEN des Spiels wird berechnet und ein Hash davon gespeichert.

2. Phase: Konsolidierte Spielerpaar-Gruppierung

Diese Phase ist ein entscheidender Vorverarbeitungsschritt, der Spiele basierend auf der Ähnlichkeit von Spielernamen gruppiert.

Fuzzy-Namensvergleiche: Spiele, die von den logisch gleichen Spielerpaaren gespielt wurden, werden gruppiert. Dies geschieht durch fuzzy Namensvergleiche unter Verwendung von Algorithmen wie Jaro-Winkler und Monge-Elkan.
Kanonische ID-Zuweisung: Eine canonical_player_pair_id wird zugewiesen, um anzuzeigen, dass diese Spiele von denselben Spielerpaaren stammen, auch wenn die Namen leicht variieren. Weichen die Namen zu sehr voneinander ab, kann hier allerdings keine Zuordnung getroffen werden und die Partie wir während der Duplikatserkennung mit hoher Wahrscheinlichkeit ignoriert.
Parallele Verarbeitung: Die anfängliche Zuweisung temporärer IDs erfolgt parallel in Workern. Die finale Konsolidierung und Zuweisung der globalen IDs findet im Hauptprozess statt, um die Qualität zu sichern. Worker identifizieren Äquivalenzklassen von Spielernamen und senden diese Beziehungen an den Hauptprozess, der sie global konsolidiert.

3. Phase: Exakte Zugfolgen-Deduplizierung

Diese Phase identifiziert und markiert Spiele, die exakt gleiche Zugfolgen aufweisen.

Hash-Vergleich: Spiele werden anhand ihres moves_hash_full verglichen. Wenn dieser Hash identisch ist, gelten die Spiele als exakte Duplikate.
Master-Auswahl: Für eine Gruppe von exakten Duplikaten wird der „beste“ Header ausgewählt. Der Header-Qualitätsscore wird basierend auf der Vollständigkeit und Qualität der Header-Informationen (Spielernamen, Datum, Elo, Ereignis, Ort) berechnet. Siehe auch Prozess der Header-Optimierung im PGN
Markierung: Das Master-Spiel erhält den duplicate_status NULL, während die anderen Duplikate als exact_dupe markiert werden. Die optimierten Header des Masters werden in der Datenbank gespeichert.

4. Phase: Subsumptions-Deduplizierung

Diese Phase findet Spiele, deren Zugfolgen eine exakte Teilmenge der Zugfolgen eines anderen Spiels sind.

Teilfolgen-Erkennung: Das Skript sucht nach Spielen, bei denen die Zugfolge eines kürzeren Spiels am Anfang der Zugfolge eines längeren Spiels exakt übereinstimmt.
Markierung: Solche Spiele werden als subsumed_dupe markiert. Auch hier wird der „beste“ Header für die Master-Spiele in der Duplikatgruppe ausgewählt und angewendet.

5. Phase: Textuelle Fuzzy-Deduplizierung

Diese Phase verwendet fortgeschrittene Fuzzy-Matching-Algorithmen, um ähnliche, aber nicht identische Spiele zu identifizieren.

Algorithmen: Jaro-Winkler und Monge-Elkan werden auf den normalisierten Zugfolgen angewendet.
Dynamische Schwellenwerte: Die Schwellenwerte für die Ähnlichkeit können dynamisch basierend auf der Zuganzahl angepasst werden, um die Sensibilität der Erkennung zu steuern.
Vorfilter: Es gibt Filter basierend auf der Mindestanzahl von Zügen und der maximalen prozentualen Zugdifferenz, um die Anzahl der Vergleiche zu reduzieren.
Markierung: Spiele, die diese Fuzzy-Kriterien erfüllen und noch nicht als Duplikate markiert sind (d.h. duplicate_status IS NULL), werden als textual_fuzzy_dupe markiert. Der Master-Header wird ebenfalls optimiert.

6. Phase: Export

Die letzte Phase ist für den Export der deduplizierten und normalisierten Spiele in PGN-Dateien zuständig.

Einzigartige Spiele: Einzigartige Spiele (die Master-Spiele der Duplikatgruppen, also duplicate_status IS NULL) können in eine separate PGN-Datei exportiert werden. Dabei wird eine Mindest-Header-Qualität berücksichtigt.
Duplikatspiele: Optional können als Duplikate markierte Spiele (exact_dupe, subsumed_dupe, textual_fuzzy_dupe) in eine separate PGN-Datei exportiert werden. Dabei werden die Site– und Event-Tags modifiziert, um den Duplikatstatus und die Duplikatgruppe widerzuspiegeln.
Header-Optimierung: Während des Exports wird die Header-Optimierung angewendet, um sicherzustellen, dass die besten verfügbaren Header-Informationen in den exportierten Spielen enthalten sind.

Prozess der Header-Optimierung im PGN

Der Header-Optimierungsprozess zielt darauf ab, die bestmögliche Qualität der Header-Daten für jedes Spiel zu gewährleisten, insbesondere für das „Master“-Spiel innerhalb einer Duplikatgruppe. Dies beinhaltet mehrere Schritte der Bereinigung, Bewertung und Zusammenführung, wobei FIDE-Spielerdaten stark genutzt werden.

1. Initialisierung und FIDE-Datenintegration (während des Imports)

Beim initialen Import eines PGN-Spiels werden Spielernamen transformiert und mit FIDE-Daten angereichert:

Spielernamen (`White` und `Black`) werden bereinigt, indem gebräuchliche Titel (GM, IM, etc.) und Ländercodes entfernt werden.
Eine „normalisierte“ Zeichenkette wird für Hashing und allgemeine Vergleiche erstellt, typischerweise durch Entfernen aller nicht-alphanumerischen Zeichen und Konvertierung in Kleinbuchstaben.
Das Skript versucht, Spieler mit FIDE-Daten zu verknüpfen:
- Wenn ein normalisierter Spielername eindeutig mit dem `main_name` eines FIDE-Spielers in den geladenen FIDE-Daten übereinstimmt, wird der Header des Spiels mit dem `main_name`, der `FideId` und dem `Title` des FIDE-Spielers aktualisiert (falls verfügbar). Dies geschieht nur, wenn der FIDE-Name eine ausreichende Länge hat. Dies reichert den Header des Spiels frühzeitig mit autoritativen FIDE-Informationen an.

2. Laden der FIDE-Spielerdaten

Bevor Deduplizierungs- oder Header-Optimierungsphasen beginnen, lädt das Skript FIDE-Spielerdaten aus der `fide_players`-Tabelle. Diese Daten sind entscheidend für den robusten Spieler-Namensabgleich und die Header-Verbesserung:

Die Daten werden in zwei Hauptstrukturen gespeichert:
- `fide_data_by_id`: Ein Dictionary, das FIDE-IDs den vollständigen Spielerdaten (Hauptname, alternative Namen, Land, Titel, etc.) zuordnet.
- `fide_data_by_normalized_name`: Ein Dictionary, das verschiedene normalisierte Namensvarianten (Hauptnamen und alternative Namen) einer Liste von entsprechenden FIDE-IDs zuordnet. Dies ermöglicht flexible Suchvorgänge basierend auf unterschiedlichen Schreibweisen oder Formaten eines Spielernamens.
Sowohl der `main_name` als auch alle `alternative_names` aus den FIDE-Daten werden normalisiert und der `fide_data_by_normalized_name`-Map hinzugefügt. Dies stellt sicher, dass verschiedene Arten, wie ein Spielername in einem PGN erscheinen könnte, immer noch mit seinem offiziellen FIDE-Eintrag verknüpft werden können.
Namen werden im PGN nur ersetzt, wenn eine eindeutige Zuordnung zu einer einzigen Person in der `fide_players`-Tabelle erfolgt.

3. Bewertung der Header-Qualität

Um den „besten“ Header unter Duplikaten zu bestimmen, wird jedem Spiel-Header ein Qualitätsscore zugewiesen. Dieser Score setzt sich aus verschiedenen Header-Feldern zusammen:

Spielernamen: Werden basierend auf Länge und dem Vorhandensein problematischer Zeichen bewertet (`score_player_name`). Ein signifikanter Bonus wird hinzugefügt, wenn ein Spielername eindeutig mit einer FIDE-ID verknüpft werden kann (`score_single_player_name_with_fide`).
Ereignis/Ort: Werden basierend auf Länge und dem Vorhandensein aussagekräftiger Daten bewertet (`score_generic_header`).
Datum: Werden basierend auf der Präzision des Datums bewertet (volles Datum > Monat-Jahr > nur Jahr). Ein Bonus wird vergeben, wenn das Datum nicht geändert werden musste (`score_date`).
Elo-Zahlen: Werden basierend auf dem numerischen Wert bewertet (`score_elo`).
Ergebnis: Ein Ergebnis wie „1-0“, „0-1“ oder „1/2-1/2“ erhält einen hohen Score. Fehlende Ergebnisse („*“ oder „?“) erhalten einen negativen Score.
Weitere Header: Allgemeine Header-Felder erhalten einen Score basierend auf ihrer Länge.

4. Auswahl des besten Spielernamens aus einem Pool

Innerhalb einer Duplikatgruppe, die mehrere Spiele mit potenziell unterschiedlichen Spielernamen-Schreibweisen enthält, wählt das Skript den „besten“ Spielernamen aus. Dieser Prozess ist entscheidend für die Konsistenz der Daten:

Alle Spielernamen (Weiß und Schwarz) aus allen Spielen der Duplikatgruppe werden gesammelt.
Jeder dieser Kandidatennamen wird individuell bewertet (`score_single_player_name_with_fide`), wobei die Verknüpfung mit einer FIDE-ID einen erheblichen Bonus gibt.
Die Kandidaten werden nach ihrem Score, ihrer Länge (längere, vollständigere Namen werden bevorzugt) und ihrer `game_id` (als Tie-Breaker) sortiert.
Der Name mit dem höchsten Score wird als „bester“ Name ausgewählt. Wenn dieser beste Name mit einer eindeutigen FIDE-ID verknüpft ist und der FIDE-Hauptname die minimale Längenanforderung erfüllt, wird der FIDE-Hauptname als der endgültige beste Spielername verwendet, zusammen mit der FIDE-ID und dem Titel. Dies stellt sicher, dass die offiziellste und qualitativ hochwertigste Namensform bevorzugt wird.

5. Zusammenführung der Header-Daten

Nachdem der Master eines Duplikatssatzes identifiziert wurde, werden die Header-Informationen aller Spiele in dieser Gruppe zusammengeführt, um den optimalen Header für den Master zu erstellen. Dies geschieht feldweise:

Für Spielernamen (`White`, `Black`): Es wird der zuvor ermittelte „beste“ Spielername aus dem Pool aller Kandidaten der Gruppe übernommen, inklusive der zugehörigen FIDE-ID und des Titels, falls zutreffend.
Für Datum (`Date`): Das Skript wählt das Datum mit dem höchsten Qualitätsscore aus allen Spielen der Gruppe. Bei gleichem Score wird das spätere Datum bevorzugt.
Für andere Tags (z.B. `Event`, `Site`, `Result`, `WhiteElo`, `BlackElo`, `PlyCount`): Für jedes dieser Felder werden alle Werte aus allen Spielen der Gruppe gesammelt. Jeder Wert erhält einen eigenen Score (z.B. `score_generic_header`, `score_elo`). Der Wert mit dem höchsten Score wird für den Master-Header ausgewählt. Bei Gleichstand wird der längere Wert bevorzugt.
Nicht relevante oder leere Tags werden aus dem optimierten Header entfernt.

6. Aktualisierung des Master-Spiels

Schließlich werden die optimierten Header in der Datenbank für das Master-Spiel aktualisiert. Das Master-Spiel wird auch als „header_optimized“ markiert und sein `duplicate_status` wird auf `NULL` gesetzt, um anzuzeigen, dass es der kanonische Eintrag für diese Duplikatgruppe ist.

Letzte Bereinigung mit Scid

Zuletzt wird noch eine Bereinigung mit Scid durchgeführt. Scid findet hier immer noch einige Duplikate, was hauptsächlich an zwei Dingen liegt:

Bildung der Spielerpaar-Gruppierungen: Wenn die Namen der Spieler so unterschiedlich geschrieben sind, dass sie nicht in die Gruppierung mit aufgenommen werden, können sie auch nicht als Duplikate erkannt werden.
Der maximale Unterschied in der Partielänge von 30%: Überschreitet der Unterschied in der Ply-Anzahl den Wert von 30%, werden die Partien auch nicht über die Deduplizierung erkannt.

Durch diese Bereinigung werden ca. 1500 bis 2000 zusätzliche Duplikate erkannt.

Scriptversion: 3.2

Schreibe einen Kommentar Antworten abbrechen