Подпрограммы сжатых разреженных графов (scipy.sparse.csgraph)#
Пример: Word Ladders#
A Word Ladder это словесная игра, изобретенная Льюисом Кэрроллом, в которой игроки находят пути между словами, меняя по одной букве за раз. Например, можно связать «ape» и «man» следующим образом:
Обратите внимание, что каждый шаг включает изменение только одной буквы слова. Это всего лишь один возможный путь от "ape" до "man", но является ли он кратчайшим возможным путем? Если мы хотим найти кратчайший путь лестницы слов между двумя заданными словами, подмодуль разреженных графов может помочь.
Сначала нам нужен список допустимых слов. Во многих операционных системах такой список встроен. Например, в Linux список слов часто можно найти по одному из следующих адресов:
/usr/share/dict
/var/lib/dict
Еще один простой источник слов — списки слов для Scrabble, доступные на различных сайтах в интернете (поищите с помощью вашей любимой поисковой системы). Сначала мы создадим этот список. Системные списки слов состоят из файла, в котором каждое слово находится на отдельной строке. Следующее следует изменить, чтобы использовать конкретный список слов, который у вас есть:
>>> with open('/usr/share/dict/words') as f:
... word_list = f.readlines()
>>> word_list = map(str.strip, word_list)
Мы хотим рассмотреть слова длиной 3, поэтому выберем только слова правильной длины. Мы также исключим слова, начинающиеся с заглавной буквы (имена собственные) или содержащие небуквенно-цифровые символы, такие как апострофы и дефисы. Наконец, мы приведем все к нижнему регистру для последующего сравнения:
>>> 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
Теперь у нас есть список из 586 допустимых трёхбуквенных слов (точное число может меняться в зависимости от используемого конкретного списка). Каждое из этих слов станет узлом в нашем графе, и мы создадим рёбра, соединяющие узлы, соответствующие каждой паре слов, которые отличаются только одной буквой.
Есть эффективные способы сделать это и неэффективные способы сделать это. Чтобы сделать это максимально эффективно, мы будем использовать некоторые сложные манипуляции с массивами numpy:
>>> import numpy as np
>>> word_list = np.asarray(word_list)
>>> word_list.dtype # these are unicode characters in Python 3
dtype('
>>> word_list.sort() # sort for quick searching later
У нас есть массив, где каждая запись состоит из трёх символов Unicode. Мы хотим найти все пары, где ровно один символ отличается. Начнём с преобразования каждого слова в 3-мерный вектор:
>>> 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
Теперь мы будем использовать Расстояние Хэмминга между каждой точкой, чтобы определить, какие пары слов связаны. Расстояние Хэмминга измеряет долю различающихся элементов между двумя векторами: любые два слова с расстоянием Хэмминга, равным \(1/N\), где \(N\) это количество букв, связанных в словесной лестнице:
>>> 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))
При сравнении расстояний мы не используем равенство, так как это может быть неустойчиво для значений с плавающей точкой. Неравенство даёт желаемый результат, пока никакие две записи в списке слов не идентичны. Теперь, когда наш граф настроен, мы используем поиск кратчайшего пути, чтобы найти путь между любыми двумя словами в графе:
>>> i1 = word_list.searchsorted('ape')
>>> i2 = word_list.searchsorted('man')
>>> word_list[i1]
'ape'
>>> word_list[i2]
'man'
Нам нужно проверить, что они совпадают, потому что если слова нет в списке, это будет не так. Теперь всё, что нужно — найти кратчайший путь между этими двумя индексами в графе. Мы будем использовать Алгоритм Дейкстры, потому что это позволяет нам найти путь только для одного узла:
>>> from scipy.sparse.csgraph import dijkstra
>>> distances, predecessors = dijkstra(graph, indices=i1,
... return_predecessors=True)
>>> print(distances[i2])
5.0 # may vary
Таким образом, мы видим, что кратчайший путь между «ape» и «man» содержит только пять шагов. Мы можем использовать предшественников, возвращаемых алгоритмом, для восстановления этого пути:
>>> 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
Это на три связи меньше, чем в нашем первоначальном примере: путь от "ape" до "man" составляет всего пять шагов.
Используя другие инструменты модуля, мы можем ответить на другие вопросы. Например, существуют ли трёхбуквенные слова, не связанные в словесной лестнице? Это вопрос о связных компонентах графа:
>>> from scipy.sparse.csgraph import connected_components
>>> N_components, component_list = connected_components(graph)
>>> print(N_components)
15 # may vary
В этой конкретной выборке трехбуквенных слов есть 15 связных компонент: то есть 15 различных наборов слов без путей между наборами. Сколько слов в каждом из этих наборов? Мы можем узнать это из списка компонент:
>>> [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
Есть одно большое связное множество и 14 меньших. Давайте посмотрим на слова в меньших множествах:
>>> [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']]
Это все трёхбуквенные слова, которые не соединяются с другими через словесную лестницу.
Нас также может заинтересовать, какие слова максимально разделены. Какие два слова требуют наибольшего количества связей для соединения? Мы можем определить это, вычислив матрицу всех кратчайших путей. Обратите внимание, что по соглашению расстояние между двумя несвязанными точками считается бесконечностью, поэтому нам нужно будет удалить их перед поиском максимума:
>>> distances, predecessors = dijkstra(graph, return_predecessors=True)
>>> max_distance = np.max(distances[~np.isinf(distances)])
>>> print(max_distance)
13.0 # may vary
Итак, существует как минимум одна пара слов, для перехода между которыми требуется 13 шагов! Давайте определим, какие это слова:
>>> 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')]
Мы видим, что есть две пары слов, которые максимально отделены друг от друга: ‘imp’ и ‘ump’ с одной стороны, и ‘ohm’ и ‘ohs’ с другой. Мы можем найти соединяющий список тем же способом, что и выше:
>>> 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
Это дает нам желаемый путь.
Словесные лестницы — лишь одно из потенциальных применений быстрых графовых алгоритмов SciPy для разреженных матриц. Теория графов появляется во многих областях математики, анализа данных и машинного обучения. Инструменты для разреженных графов достаточно гибки, чтобы справляться со многими из этих ситуаций.