壓縮稀疏圖常式 (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    # 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 維向量

>>> 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 快速圖演算法在稀疏矩陣中的一個潛在應用。圖論在數學、資料分析和機器學習的許多領域中都有應用。稀疏圖工具足夠靈活，可以處理許多這些情況。