Hinweise:

• Besonders schöne Klickpfade mit dem -Button als Text oder als URL in die Zwischenablage kopieren und in den Kommentaren hinterlassen!
• Wenn mehrere kürzeste Pfade existieren wählt der Code einen zufällig aus. Man kann also durch wiederholte Klicks auf Los! verschiedene Antworten bekommen.
• Fehler werden mit einem roten Warndreieck angezeigt. Erscheint es neben einem Eingabefeld so zeigt es an, daß die Start- oder Zielseite in Wikipedia nicht existiert.
• Wird eine Seite nicht gefunden, so prüfen Sie die Schreibweise exakt. Am besten suchen Sie den Begriff zuerst in der Wikipedia und kopieren dann den Titel der Seite in das Eingabefeld.
• Ein rotes Warndreieck im Ausgabebereich zeigt einen anderen Fehler an. Entweder es existiert kein Klickpfad zwischen den beiden Seiten oder Server oder Graphdatenbank sind nicht zu erreichen.
• Wird kein Pfad gefunden, so kann das unter anderem daran liegen, daß die Zielseite eine reine Weiterleitungsseite ist. Diese haben nur einen ausgehenden Link und sind nie Ziel eines Links, deswegen gibt es auch keinen Klickpfad der zu ihnen führt. Ein Beispiel ist der Artikel Mozart, welcher auf Wolfgang Amadeus Mozart weiterleitet. Prüfen sie das Ziel in der Wikipedia und verwenden Sie den Titel der Hauptseite (Wolfgang Amadeus Mozart) statt den der Weiterleitungsseite (Mozart).
• Der Datenbestand ist ein Dump vom 7.4.2017, die aktuelle deutsche Wikipedia kann andere Seiten und andere Links enthalten.

Wie funktioniert das?

Das Verfahren ist ein klassischer ETL-Prozess bei dem Daten beschafft (Extraction), formal umgebaut (Transformation), und in ein geeignetes Zielsystem geladen werden (Load) um dann dort ausgewertet werden zu können.

Der Extraktionsschritt ist einfach, denn Wikipedia bietet den Download ihrer Daten in Form einer großen XML-Datei an (https://dumps.wikimedia.org/dewiki/latest/). Die Datei heißt dewiki-latest-pages-articles.xml.bz2 und beim Schreiben dieser Zeilen ca. 4.5GB groß), sie enthält alle Seiten und für jede Seite den jeweils aktuellsten Wikitext.

Aus dem XML-Dump macht ein Python-Skript zwei CSV-Dateien. Die erste, pages.csv, enthält zu jeder Seite nur die numerische ID und den Titel der Seite, diese beiden Elemente stehen direkt als XML-Elemente zur Verfügung. Die zweite, links.csv, enthält alle Links. Für jeden Link stehen in einer Zeile die numerische ID der Seite auf der er steht, und der Titel der Seite auf die der Link zeigt.

Wie parst man eine XML-Datei von 4.5GB? Ganz sicher nicht indem man sie komplett als DOM in den Hauptspeicher schaufelt. Das Extraktionsskript verwendet lxm.etree.iterparse, eine Bibliothek die das Beste aus der SAX- und der DOM-Welt vereint: Mit iterparse wird die Datei sequenziell geparst und SAX-ig für jedes Tag Ereignisse ausgelöst. Die Ereignishandler bekommen jeweils Teilbäume DOM-ig als Objekte geliefert. Das Skript kann also auf die end-Ereignisse von <page>-Elementen warten, jede einzelne Seite, eine überschaubare Datenmenge, bequem mit einer DOM-artigen API verarbeiten und das DOM-ige Fragment danach sofort verwerfen.

Ein weiterer kleiner Trick ist, daß die bz2-komprimierte XML-Datei nur ein einziges Mal sequenziell gelesen werden muss, also wird sie mit BZ2File nur on-the-fly dekomprimiert.

Die Links, auf die eine Wikiseite verweist, stehen im XML-Format leider nicht als separate Elemente zur Verfügung, sondern sind in der WikiText-Notation eingebettet. Sie werden vom Skript mit einem regulären Ausdruck extrahiert und nach Wiki-Namensräumen sortiert. Alle internen Links die tatsächlich in die deutsche Wikipedia zeigen werden dann nach links.csv herausgeschrieben.

Am Ende des Extraktionsprozesses liegen pages.csv mit ca. 4Millionen Zeilen und links.csv mit ca. 82Millionen Zeilen vor. Es wäre nun denkbar diese Daten zu lesen, eine geeignete Datenstruktur im RAM aufzubauen und zum Beispiel mit dem Dijkstra-Algorithmus den kürzesten Weg zwischen zwei Seiten zu finden. Interessanter ist es aber, dafür ein allgemeineres Werkzeug zu verwenden und dann mehr Fragen als nur die nach dem shortest path beantworten zu können. Ein solches Werkzeug ist die Graph-Datenbank neo4j

Mit nur vier Kommandos in der neo4j-Sprache Cypher werden pages.csv und links.csv eingelesen:

USING PERIODIC COMMIT 
LOAD CSV WITH HEADERS FROM \"file:///pages.csv\" AS row 
CREATE (:Page {id: row.id, title: row.title, imported: true});

CREATE INDEX ON :Page(id);");
CREATE INDEX ON :Page(title);");

USING PERIODIC COMMIT
LOAD CSV WITH HEADERS FROM "file:///links.csv" AS row
MATCH (source:Page {id: row.source_id})
MATCH (target:Page {title: row.target_title})
CREATE (source)-[l:Link]->(target);
									

Die Frage nach dem Weg von Kolbermoor nach Pinneberg beantwortet der in neo4j eingebaute Client auf sehr hohem Abstraktionsniveau. Konfrontiert mit der Cypher-Abfrage:

MATCH 
	(source:Page { title: "Kolbermoor" }),
	(target:Page { title: "Pinneberg" }), 
	p = allShortestPaths((source)-[*]->(target)) 
RETURN p LIMIT 3;
									

Liefert er folgendes Ergebnis (SVG-Grafik, das Original ist interaktiv!):

 

Man braucht also mindestens drei Klicks von Kolbermoor nach Pinneberg, und neo4j zeigt hier drei verschiedene Routen dafür. Auch die zusätzlichen Links zwischen den Seiten sind ausgegeben, so daß man sehen kann, daß manche von den Listen nicht nur auf ihre Elementseiten verweisen, sondern die Seiten auch einen Rückverweis enthalten.

Bleiben nur noch eine Schnittstelle vom Browser zu dieser neo4j-Datenbank und ein wenig Präsentation.

Die Rolle der Schnittstelle übernimmt ein PHP-Skript. Neo4j bietet eine REST-Schnittstelle mit JSON als Transport-Format und PHP ist auf dem Webserver ohnehin in Betrieb, also ist das trivial zu implementieren. Die Hauptaufgabe ist die Sicherung gegen SQL-, äh, Cypher-Injection, ansonsten werden Abfrage und Ergebnis von dem Skript nur zwischen Client und neo4j-Server weitergereicht.

Die Präsentationsschicht ist diese Seite. Sie hat im Wesentlichen Eingabefelder für Start und Ziel und jQuery bildet den Klebstoff zwischen dem PHP-Skript und dem DOM und sorgt für hübsche Animationen.

Ich wünsche viel Spaß bei der Erforschung der Wege durch die Wikipedia und freue mich über Feedback.