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

示例：字阶梯

A Word Ladder 是刘易斯·卡罗尔发明的一种文字游戏，玩家通过一次交换一个字母来找到单词之间的路径。例如，人们可以通过以下方式将“猿”和“人”联系起来：

\[{\rm ape\to ait\to bit\to Big\to袋子\to mag\to man}\]

请注意，每个步骤只涉及更改单词的一个字母。这只是从“猿”到“人”的一条可能路径，但这是最短的可能路径吗？如果我们希望找到两个给定单词之间的最短单词梯形路径，稀疏图子模块可以提供帮助。

首先，我们需要一个有效单词列表。许多操作系统都内置了这样的列表。例如，在Linux上，通常可以在以下位置之一找到单词列表：

/usr/share/dict
/var/lib/dict

另一个容易获取单词的来源是互联网上各种站点提供的拼字游戏单词列表(使用您最喜欢的搜索引擎进行搜索)。我们将首先创建此列表。系统单词列表由每行一个单词的文件组成。应修改以下内容以使用您提供的特定单词列表：

>>> word_list = open('/usr/share/dict/words').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字符长度。我们想找出恰好有一个字符不同的所有配对。我们将从将每个单词转换为3-D矢量开始：

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

现在，我们将使用 Hamming distance 在每个点之间确定连接哪些词对。汉明距离衡量两个向量之间不同的条目的分数：任何两个汉明距离等于 \(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's algorithm ，因为它只允许我们找到一个节点的路径：：

>>> from scipy.sparse.csgraph import dijkstra
>>> distances, predecessors = dijkstra(graph, indices=i1,
...                                    return_predecessors=True)
>>> print(distances[i2])
5.0    # may vary

所以我们看到“猿”和“人”之间的最短路径只有五步。我们可以使用算法返回的前置任务来重建此路径：：

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

这比我们最初的例子少了三个环节：从“猿”到“人”的路径只有五步。

使用模块中的其他工具，我们可以回答其他问题。例如，有没有三个字母的单词没有在单词阶梯中链接？这是图表中连接组件的问题：

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

上一页

带ARPACK的稀疏特征值问题

下一页

空间数据结构和算法 (scipy.spatial )