压缩稀疏图例程 (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

另一个容易获取单词的来源是互联网上可用的拼字游戏单词列表（使用你喜欢的搜索引擎搜索）。我们首先创建这个列表。系统单词列表由一个每行一个单词的文件组成。以下内容应根据你可用的特定单词列表进行修改:

>>> 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    # 可能会有所不同

现在我们有了一个包含586个有效三字母单词的列表（确切数量可能因所用列表而异）。这些单词中的每一个都将成为我们图中的一个节点，我们将创建边连接那些仅有一个字母不同的单词对所对应的节点。

有高效的方法来完成这个任务，也有低效的方法。为了尽可能高效地完成这个任务，我们将使用一些复杂的numpy数组操作：

>>> import numpy as np
>>> word_list = np.asarray(word_list)
>>> word_list.dtype   # 这些是Python 3中的Unicode字符
dtype('<U3')
>>> word_list.sort()  # 排序以便稍后快速搜索

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

>>> word_bytes = np.ndarray((word_list.size, word_list.itemsize),
...                         dtype='uint8',
...                         buffer=word_list.data)
>>> # 每个Unicode字符有四个字节长。我们只需要第一个字节
>>> # 我们知道每个单词中有三个字符
>>> word_bytes = word_bytes[:, ::word_list.itemsize//3]
>>> word_bytes.shape
(586, 3)    # 可能会有所不同

现在，我们将使用 汉明距离 来确定哪些单词对是相连的。汉明距离测量两个向量之间不同条目的比例：任何汉明距离等于 \(1/N\) 的单词对，其中 \(N\) 是字母的数量，在单词阶梯中是相连的:

>>> from scipy.spatial.distance import pdist, squareform
>>> from scipy.sparse import csr_matrix
>>> hamming_dist = pdist(word_bytes, metric='hamming')
>>> # 每个单词有三个字符
>>> 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算法 <https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm>`_，因为它允许我们只为一个节点找到路径:

>>> from scipy.sparse.csgraph import dijkstra
>>> distances, predecessors = dijkstra(graph, indices=i1,
...                                    return_predecessors=True)
>>> print(distances[i2])
5.0    # 可能会有所不同

所以我们看到，“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']    # 可能会有所不同

这比我们最初的例子少了三个链接：从“ape”到“man”的路径只有五个步骤。

使用模块中的其他工具，我们可以回答其他问题。例如，是否存在在单词阶梯中不相连的三字母单词？这是一个关于图中连通分量的问题::

>>> from scipy.sparse.csgraph import connected_components
>>> N_components, component_list = connected_components(graph)
>>> print(N_components)
15    # 可能会有所不同

在这个特定的三字母单词样本中，有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]    # 可能会有所不同

有一个大的连通集合和14个较小的集合。让我们看看这些较小集合中的单词:

>>> [list(word_list[np.nonzero(component_list == i)]) for i in range(1, N_components)]
[['aha'],    # 可能会有所不同
 ['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    # 可能会有所不同

因此，至少有一对单词需要13步才能从一个单词到达另一个单词！让我们确定这些单词对:

>>> i1, i2 = np.nonzero(distances == max_distance)
>>> list(zip(word_list[i1], word_list[i2]))
[('imp', 'ohm'),    # 可能会有所不同
 ('imp', 'ohs'),
 ('ohm', 'imp'),
 ('ohm', 'ump'),
 ('ohs', 'imp'),
 ('ohs', 'ump'),
 ('ump', 'ohm'),
 ('ump', 'ohs')]
('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']    # 可能会有所不同

这给了我们想要看到的路径。

单词阶梯只是scipy的稀疏矩阵快速图算法的众多潜在应用之一。图论在许多数学领域、数据分析和机器学习中都有应用。稀疏图工具足够灵活，可以处理许多这些情况。