Wer schon einmal gelangweilt an einem Rechner mit Zugang zu Wikipedia gesessen hat kennt vielleicht das Spiel Wikispeedia: Man startet auf einem zufälligen Artikel und muss sich mittels möglichst weniger Verlinkungen innerhalb des Artikels zu Adolf Hitler oder Jesus durchklicken; wer die wenigsten Klicks gebraucht hat gewinnt.

Doch wie kann man sichergehen, dass man tatsächlich den kürzesten Pfad von A nach B gefunden hat? Kann man dafür vielleicht eine Art Suchmaschine konstruieren?

Ja, man kann. In diesem Artikel wird es darum gehen, eine derartige Auswertung rechnergestützt vorzunehmen.

Voraussetzungen

Im folgenden wird angenommen dass sich der Nutzer auf einem Linux-System befindet und folgende Software-Pakete installiert hat:

• python > 3.7
• gzip
• wget
• grep
• sed
• pv

Für Python wird zusätzlich noch tqdm-Paket gebraucht, um aufschlussreiche Fortschrittsanzeigen darzustellen. Alles in allem sollte auf einem Arch-System folgendes ausreichen:

$ sudo pacman -S python gzip wget sed grep pv python-tqdm

Daten-Konvertierung

Bevor man überhaupt irgendeine Art von Auswertung vornehmen kann, benötigt man selbstverständlich die passenden Daten.

Glücklicherweise gibt es von Wikipedia eine Seite auf der regelmäßige sogenannte Database-Dumps veröffentlicht werden: dumps.wikimedia.org/dewiki. Dort gibt es neben den ganzen Artikeln (dewiki-latest-pages-articles.xml.bz2) auch Tabellen mit Metadaten. Für dieses Projekt sind vorallem die page und die pagelinks Tabellen interessant. In der Dokumentation von MediaWiki findet man ihren Aufbau:

Pages-Tabelle

Link zur Doku

Hier stehen also die IDs, Titel und Namensräume der Einträge auf Wikipedia drin. Relevant ist hier eigentlich nur der Namensraum 0, in diesem sich alle Artikel befinden. Nutzerseiten und Diskussionen befinden sich in anderen Namensräumen, sind aber für unsere Belange nicht wichtig.

Pagelinks-Tabelle

Link zur Doku

Die pagelinks-Table enthält alle Verlinkungen der Artikel untereinander. Dabei wird der Quell-Artikel über seine ID spezifiziert (pl_from), der Ziel-Artikel aber mit seinem Namen (pl_title). Warum diese Inkonsistenz bezüglich der Referenzierung von Artikeln besteht ist mir unverständlich, da sie die Auswertung lediglich erschwert: wir müssen die Artikel nämlich doppelt indizieren, einmal per String und einmal per Ganzzahl.

Präparation

Zuerst gilt es die Dateien runterzuladen:

$ wget \
https://dumps.wikimedia.org/dewiki/latest/dewiki-latest-page.sql.gz \
https://dumps.wikimedia.org/dewiki/latest/dewiki-latest-pagelinks.sql.gz

Eigentlich sind die SQL-Dateien dazu gedacht, sie in eine MySQL-Datenbank zu laden. Im folgenden werden wir sie aber mittels einfacher Unix-Tools in eine CSV-Datei umwandeln und dann mittels Python in eine In-Memory-Datenstruktur einlesen.

Der relevante Teil der SQL-Dateien besteht aus dem INSERT-Befehl. Der grundlegende Aufbau ist dabei so: INSERT INTO 'page' VALUES (...),(...); In den Klammern stehen dann Komma-separiert die eigentlichen Werte.

Zur Umwandlung wird folgendes Kommando benutzt. Es sieht sehr unübersichtlich aus, ist aber eigentlich relativ simpel gestrickt:

$ pv dewiki-latest-page.sql.gz | zcat \
  | grep INSERT \
  | sed -E 's/INSERT INTO .+ VALUES //g;s/\)[,;]/\n/g;s/^\(//gm' \
  | grep -vE '^\s*$' \
  > dewiki-latest-page.csv
 
 240MiB 0:01:43 [2,32MiB/s] [============================>] 100%            

1. Zuerst wird mit zcat die komprimierte SQL-Datei entpackt.
2. Die Ausgabe wird an grep weitergeleitet, das nach allen INSERT-Befehlen in der Datei sucht.
3. Die Insert-Befehle werden nun durch eine Reihe von regulären Ausdrücken gejagt:
   • s/INSERT INTO .+ VALUES //g entfernt den Prefix des INSERT-Befehls, sodass nur noch die Datensätze übrigbleiben: (…),(…),(…);
   • s/\)[,;]/\n/g ersetzt alle Klammern, die vor einem Semikolon oder Komma stehen, durch einen Zeilenumbruch
   • s/^\(//gm entfernt die führenden Klammern, die übrig geblieben sind
4. Der letzte grep-Befehl verhindert, dass leere Zeilen ausgegeben werden, die von den vorherigen Bearbeitungsschritten stammen.

Das muss dann nochmals für die Pagelink-Tabelle ausgeführt werden. Da diese deutlich größer ist, dauert der Vorgang hier etwas länger.

$ pv dewiki-latest-pagelinks.sql.gz | zcat \
  | grep INSERT \
  | sed -E 's/INSERT INTO .+ VALUES //g;s/\)[,;]/\n/g;s/^\(//gm' \
  | grep -vE '^\s*$' \
  > dewiki-latest-pagelinks.csv

Ja, diese Regex-Lösung ist sehr hacky, sieht nicht schön aus (reines ASCII-Puke), aber sie erledigt den Job und konvertiert die SQL-Datei auf einem alten i3-Laptop in unter einer Minute in ein für Python lesbares CSV. Eine große Einschränkung ist jedoch die Annahme dass keiner der Datensätze (Artikel-Titel etc.) ein ), enthält. Wäre dies der Fall würde das Parsing fehlschlagen und ein korruptes CSV produzieren, allerdings ist das hier glücklicherweise nicht der Fall.

Daten-Import

Zeit die konvertierten CSV-Dateien in Python zu laden. Der folgende Python-Code kann entweder im Terminal (z.B. mit ipython) oder in einem Jupyter Notebook ausgeführt werden. Dabei ist zu beachten, dass sich die oben generierten CSV-Dateien im selben Arbeitsverzeichnis befinden.

Als erstes gilt es, eine passende Datenstruktur zu konstruieren. Hier wird eine Python-3 Data Class verwendet. Für jeden Artikel speichern wir seinen Namen, die Länge des Seitenquelltextes, ob es sich nur um eine Weiterleitung handelt, sowie zwei Listen: einmal die Verlinkungen ausgehend von dem Artikel (links), und auch die Verlinkungen auf den Artikel (backlinks). Warum dies nützlich ist wird sich zu einem späteren Zeitpunkt noch ergeben.

Hier also der Quelltext für die WikiArticle-Klasse, ungekürzt:

from dataclasses import dataclass
from typing import Type, List

ARTICLE_NAMESPACE = 0

@dataclass
class WikiArticle:
    id: int
    name: str
    len: int
    is_redirect: bool
    links: List[Type['WikiArticle']]
    backlinks: List[Type['WikiArticle']]

    def __repr__(self):
        return self.name.replace('_', ' ')

    def __hash__(self):
        return hash((self.id, self.name, self.len, self.is_redirect))

    def __eq__(self, other):
        if type(self) != type(other):
           return False
        if other.id != self.id or \
           other.name != self.name or \
           other.len != self.len or \
           other.is_redirect != self.is_redirect:
            return False
        return True
    	    

articles_by_id = dict()
articles_by_name = dict()

Wie oben im Quelltext leicht zu erkennen ist werden Adjazenz-Listen zur Graph-Repräsentation genutzt, d.h. benachbarte Artikel (zwischen denen eine Verlinkung existiert) speichern eine Referenz. Außerdem werden zwei Hash-Tabellen verwendet, um die Artikel auffindbar zu machen, einmal per Name und einmal per ID.

Nun gilt es die Liste mit den Artikel-Namen und -IDs einzulesen:

import csv
from tqdm import tqdm

with open('dewiki-latest-page.csv', 'r') as file:
    reader = csv.reader(file, delimiter=',', quotechar="'", escapechar='\\')

    for page_id, page_namespace, page_title, page_restrictions, \
      page_is_redirect, page_is_new, page_random, page_touched, \
      page_links_updated, page_latest, page_len, \
      page_content_model, page_lang in tqdm(reader):
        if int(page_namespace) != ARTICLE_NAMESPACE:
            continue
                
        article = WikiArticle(int(page_id), page_title,
        int(page_len), page_is_redirect == '1', [], [])
        articles_by_id[int(page_id)] = article
        articles_by_name[page_title] = article

Als letztes fehlt nur noch der Import von den Verlinkungen, dann ist unsere Graph-Repräsentation komplett. Aus irgendeinem Grund ist die ID der Quellartikels gespeichert, aber der Name des Ziel-Artikels, weshalb wir die beiden dicts brauchen. Wir lesen die CSV Zeile für Zeile, prüfen ob es sich um eine Verlinkung zwischen Artikeln handelt die wir kennen und fügen ggf. den Zielartikel zu den Kindern des Quellknotens hinzu. Außerdem speichern wir die Verlinkung auch noch im Zielknoten, um später bei der Breitensuche effizient abfragen zu können welche Artikel auf diesen verlinken.

with open('dewiki-latest-pagelinks.csv', 'r') as file:
    reader = csv.reader(file, delimiter=',', quotechar="'", escapechar='\\')
    
    for pl_from, pl_namespace, pl_title, pl_from_namespace in tqdm(reader):
        if int(pl_from) not in articles_by_id or \
           pl_title not in articles_by_name or \
           int(pl_from_namespace) != ARTICLE_NAMESPACE:
           continue
        	
        source = articles_by_id[int(pl_from)]
        target = articles_by_name[pl_title]
        
        if source == target:
            continue
        
        source.links.append(target)
        target.backlinks.append(source)

Datascience here we come

Nachdem nun alle relevanten Informationen bequem in den Hauptspeicher geladen wurden können wir nun mit der eigentlich Auswertung der Daten beginnen.

Wer hat den längsten Artikel?

Eine ganz simple Aufgabe zu Beginn: wir bestimmen die zehn längsten Artikel. Hierzu nutzen wir die mitgelieferte Sortierfunktion von Python mit einem Lambda, um die Artikellänge als Sortierschlüssel zu spezifizieren.

def print_top_ten_longest_articles():
    sorted_by_length = sorted(articles_by_name.values(),
            key=lambda item: item.len,
            reverse=True
    )
    top_ten = sorted_by_length[:10]

    for rank, article in enumerate(top_ten, start=1):
        print(f"{rank}. {article}")

print_top_ten_longest_articles()

Ein Aufruf von print_top_ten_longest_articles() liefert folgende Liste:

1. Gerth Medien (Musiklabel)/Diskografie
2. Landbuch Karls IV.
3. Liste der Wettbewerbe der olympischen Sommersportarten
4. Liste von Pkw-Marken
5. Liste der Stolpersteine in Berlin-Schöneberg
6. Liste der Schlangenarten
7. Liste der Spieler der Premier League
8. Humanitäre Aspekte der Militärintervention im Jemen seit 2015
9. Sexueller Missbrauch in der römisch-katholischen Kirche
10. Liste der Baudenkmäler in Viersen (A–F)

Dass eine Liste von Pkw-Marken weit oben landet beim Ranking der längsten Artikel verwundert nicht unbedingt, aber dass der Artikel über sexuellen Missbrauch in der römisch-katholischen Kirche auf Platz 9 landet lässt mich durchaus etwas vom Glauben abzukommen…

(Anmerkung: wir lesen hier die Länge des Artikel-Quelltextes, der nicht mit der genauen Wortanzahl im Klartext übereinstimmt, d.h. Artikel mit vielen Links/Tabellen o.ä. erscheinen in diesem Ranking höher)

Ausblick

In diesem Artikel wurde der Import von Wikipedia-Metadaten in Python beschrieben und es wurden bereits kleinere Auswertungen vorgenommen. In nachfolgenden Artikeln wird es darum gehen, tatsächlich kürzeste Verlinkungen zwischen Artikeln ausfindig zu machen.