压缩稀疏图例程 (scipy.sparse.csgraph)

示例：文字梯子

文字梯子是由刘易斯·卡罗尔发明的文字游戏，玩家通过一次改变一个字母的方式在单词间寻找路径。例如，可以按以下方式将“ape”和“man”联系起来

\[{\rm ape \to apt \to ait \to bit \to big \to bag \to mag \to 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('<U3')
>>> word_list.sort()  # sort for quick searching later

我们有一个数组，其中每个条目都是三个 unicode 字符长。我们希望找到所有正好有一个字符不同的对。我们将首先把每个单词都转换为 3D 向量

>>> 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'

我们需要检查这些匹配，因为如果单词不在列表中，情况并非如此。现在，我们需要做的就是找到这两个索引在图中的最短路径。我们将使用Dijkstra 的算法，因为它允许我们仅找到一个节点的路径

>>> 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 的稀疏矩阵快速图算法的一个潜在应用。图论出现在数学、数据分析和机器学习的许多领域。稀疏图工具足够灵活，可以处理许多此类情况。