Komprimierte dünnbesetzte Graphenroutinen (scipy.sparse.csgraph)#
Beispiel: Wortleitern#
Eine Wortleiter ist ein von Lewis Carroll erfundenes Wortspiel, bei dem die Spieler Pfade zwischen Wörtern finden, indem sie nacheinander einen Buchstaben ändern. Zum Beispiel kann man "ape" und "man" auf folgende Weise verbinden:
Beachten Sie, dass jeder Schritt nur eine Änderung eines Buchstabens des Wortes beinhaltet. Dies ist nur ein möglicher Pfad von "ape" zu "man", aber ist es der kürzeste mögliche Pfad? Wenn wir den kürzesten Wortleiterpfad zwischen zwei gegebenen Wörtern finden wollen, kann das Untermodul für dünnbesetzte Graphen helfen.
Zuerst benötigen wir eine Liste gültiger Wörter. Viele Betriebssysteme haben eine solche Liste integriert. Zum Beispiel ist unter Linux eine Wortliste oft an einem der folgenden Orte zu finden:
/usr/share/dict
/var/lib/dict
Eine weitere einfache Quelle für Wörter sind die Scrabble-Wortlisten, die im Internet an verschiedenen Stellen verfügbar sind (suchen Sie mit Ihrer bevorzugten Suchmaschine). Wir werden diese Liste zuerst erstellen. Die Systemwortlisten bestehen aus einer Datei mit einem Wort pro Zeile. Das Folgende sollte angepasst werden, um die von Ihnen verfügbare Wortliste zu verwenden.
>>> with open('/usr/share/dict/words') as f:
... word_list = f.readlines()
>>> word_list = map(str.strip, word_list)
Wir möchten Wörter der Länge 3 betrachten, also wählen wir nur diese Wörter der richtigen Länge aus. Wir eliminieren auch Wörter, die mit Großbuchstaben beginnen (Eigennamen) oder nicht-alphanumerische Zeichen wie Apostrophe und Bindestriche enthalten. Schließlich stellen wir sicher, dass alles klein geschrieben ist, um es später vergleichen zu können.
>>> word_list = [word for word in word_list if len(word) == 3]
>>> word_list = [word for word in word_list if word[0].islower()]
>>> word_list = [word for word in word_list if word.isalpha()]
>>> word_list = list(map(str.lower, word_list))
>>> len(word_list)
586 # may vary
Jetzt haben wir eine Liste von 586 gültigen dreibuchstabigen Wörtern (die genaue Zahl kann je nach verwendeter Liste variieren). Jedes dieser Wörter wird zu einem Knoten in unserem Graphen, und wir werden Kanten erstellen, die die Knoten verbinden, die jeweils einem Wortpaar zugeordnet sind, das sich nur durch einen Buchstaben unterscheidet.
Es gibt effiziente und ineffiziente Wege, dies zu tun. Um dies so effizient wie möglich zu tun, werden wir einige ausgeklügelte NumPy-Array-Manipulationen verwenden.
>>> import numpy as np
>>> word_list = np.asarray(word_list)
>>> word_list.dtype # these are unicode characters in Python 3
dtype('<U3')
>>> word_list.sort() # sort for quick searching later
Wir haben ein Array, bei dem jeder Eintrag drei Unicode-Zeichen lang ist. Wir möchten alle Paare finden, bei denen sich genau ein Zeichen unterscheidet. Wir beginnen damit, jedes Wort in einen 3-D-Vektor umzuwandeln.
>>> word_bytes = np.ndarray((word_list.size, word_list.itemsize),
... dtype='uint8',
... buffer=word_list.data)
>>> # each unicode character is four bytes long. We only need first byte
>>> # we know that there are three characters in each word
>>> word_bytes = word_bytes[:, ::word_list.itemsize//3]
>>> word_bytes.shape
(586, 3) # may vary
Nun verwenden wir die Hamming-Distanz zwischen jedem Punkt, um zu bestimmen, welche Wortpaare verbunden sind. Die Hamming-Distanz misst den Anteil der Einträge zwischen zwei Vektoren, die sich unterscheiden: Zwei Wörter mit einer Hamming-Distanz von \(1/N\), wobei \(N\) die Anzahl der Buchstaben ist, sind in der Wortleiter verbunden.
>>> from scipy.spatial.distance import pdist, squareform
>>> from scipy.sparse import csr_matrix
>>> hamming_dist = pdist(word_bytes, metric='hamming')
>>> # there are three characters in each word
>>> graph = csr_matrix(squareform(hamming_dist < 1.5 / 3))
Beim Vergleichen der Distanzen verwenden wir keine Gleichheit, da dies bei Fließkommawerten instabil sein kann. Die Ungleichheit liefert das gewünschte Ergebnis, solange keine zwei Einträge der Wortliste identisch sind. Jetzt, da unser Graph eingerichtet ist, werden wir eine Suche nach dem kürzesten Pfad verwenden, um den Pfad zwischen zwei beliebigen Wörtern im Graphen zu finden.
>>> i1 = word_list.searchsorted('ape')
>>> i2 = word_list.searchsorted('man')
>>> word_list[i1]
'ape'
>>> word_list[i2]
'man'
Wir müssen prüfen, ob diese übereinstimmen, da dies nicht der Fall ist, wenn die Wörter nicht in der Liste enthalten sind. Nun müssen wir nur noch den kürzesten Pfad zwischen diesen beiden Indizes im Graphen finden. Wir werden den Dijkstra-Algorithmus verwenden, da er es uns ermöglicht, den Pfad für nur einen Knoten zu finden.
>>> from scipy.sparse.csgraph import dijkstra
>>> distances, predecessors = dijkstra(graph, indices=i1,
... return_predecessors=True)
>>> print(distances[i2])
5.0 # may vary
Wir sehen also, dass der kürzeste Pfad zwischen "ape" und "man" nur fünf Schritte enthält. Wir können die vom Algorithmus zurückgegebenen Vorgänger verwenden, um diesen Pfad zu rekonstruieren.
>>> path = []
>>> i = i2
>>> while i != i1:
... path.append(word_list[i])
... i = predecessors[i]
>>> path.append(word_list[i1])
>>> print(path[::-1])
['ape', 'apt', 'opt', 'oat', 'mat', 'man'] # may vary
Das sind drei Schritte weniger als in unserem anfänglichen Beispiel: Der Pfad von "ape" nach "man" besteht nur aus fünf Schritten.
Mit anderen Werkzeugen des Moduls können wir weitere Fragen beantworten. Gibt es zum Beispiel dreibuchstabige Wörter, die in einer Wortleiter nicht verbunden sind? Dies ist eine Frage der verbundenen Komponenten im Graphen.
>>> from scipy.sparse.csgraph import connected_components
>>> N_components, component_list = connected_components(graph)
>>> print(N_components)
15 # may vary
In dieser speziellen Auswahl an dreibuchstabigen Wörtern gibt es 15 verbundene Komponenten: Das heißt, 15 unterschiedliche Mengen von Wörtern, zwischen denen keine Pfade existieren. Wie viele Wörter gibt es in jeder dieser Mengen? Das erfahren wir aus der Liste der Komponenten.
>>> [np.sum(component_list == i) for i in range(N_components)]
[571, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] # may vary
Es gibt eine große verbundene Menge und 14 kleinere. Betrachten wir die Wörter in den kleineren Mengen.
>>> [list(word_list[np.nonzero(component_list == i)]) for i in range(1, N_components)]
[['aha'], # may vary
['chi'],
['ebb'],
['ems', 'emu'],
['gnu'],
['ism'],
['khz'],
['nth'],
['ova'],
['qua'],
['ugh'],
['ups'],
['urn'],
['use']]
Dies sind alle dreibuchstabigen Wörter, die über eine Wortleiter nicht mit anderen verbunden sind.
Wir könnten uns auch fragen, welche Wörter maximal getrennt sind. Welche zwei Wörter benötigen die meisten Schritte, um sich zu verbinden? Wir können dies ermitteln, indem wir die Matrix aller kürzesten Pfade berechnen. Beachten Sie, dass per Konvention die Entfernung zwischen zwei nicht verbundenen Punkten als Unendlich angegeben wird, so dass wir diese entfernen müssen, bevor wir das Maximum finden.
>>> distances, predecessors = dijkstra(graph, return_predecessors=True)
>>> max_distance = np.max(distances[~np.isinf(distances)])
>>> print(max_distance)
13.0 # may vary
Es gibt also mindestens ein Wortpaar, das 13 Schritte benötigt, um von einem zum anderen zu gelangen! Lassen Sie uns ermitteln, welche das sind.
>>> i1, i2 = np.nonzero(distances == max_distance)
>>> list(zip(word_list[i1], word_list[i2]))
[('imp', 'ohm'), # may vary
('imp', 'ohs'),
('ohm', 'imp'),
('ohm', 'ump'),
('ohs', 'imp'),
('ohs', 'ump'),
('ump', 'ohm'),
('ump', 'ohs')]
Wir sehen, dass es zwei Wortpaare gibt, die maximal voneinander getrennt sind: 'imp' und 'ump' einerseits und 'ohm' und 'ohs' andererseits. Den verbindenden Pfad können wir auf die gleiche Weise wie oben ermitteln.
>>> path = []
>>> i = i2[0]
>>> while i != i1[0]:
... path.append(word_list[i])
... i = predecessors[i1[0], i]
>>> path.append(word_list[i1[0]])
>>> print(path[::-1])
['imp', 'amp', 'asp', 'ass', 'ads', 'add', 'aid', 'mid', 'mod', 'moo', 'too', 'tho', 'oho', 'ohm'] # may vary
Dies ergibt den gewünschten Pfad.
Wortleitern sind nur eine mögliche Anwendung der schnellen Graphenalgorithmen von SciPy für dünnbesetzte Matrizen. Die Graphentheorie taucht in vielen Bereichen der Mathematik, Datenanalyse und des maschinellen Lernens auf. Die Werkzeuge für dünnbesetzte Graphen sind flexibel genug, um viele dieser Situationen zu bewältigen.