在Python中生成有向词图

Question

从一系列句子中，我想生成一个有向图以根据以下属性生成子句：

假设有三个句子：

• 我喜欢糖果
• 我爱你
• 我非常喜欢糖果

每当成对出现时，图中将具有1的权重值，即每个连续单词之间都有边缘。

然后我找到具有最大权重的路径在图中。这里返回'I love candy very much'，其权重为3+2+1+1。

str1 = """Man who run in front of car, get tired.
Man who run behind car, get exhausted."""
# create a list of words separated at whitespaces
wordList1 = str1.split(None)
# strip any punctuation marks and build modified word list
# start with an empty list
wordList2 = []
for word1 in wordList1:
# last character of each word
lastchar = word1[-1:]
# use a list of punctuation marks
if lastchar in [",", ".", "!", "?", ";"]:
    word2 = word1.rstrip(lastchar)
else:
    word2 = word1
# build a wordList of lower case modified words
wordList2.append(word2.lower())

现在 wordList2 已经是一组连续的单词了。如何将其转换为图形呢？我正在使用networkx库，但对它不太熟悉。

如何继续制作带有边权重的图形呢？

- R1234

---

一个字典的字典对于你的任务是否足够？当我做类似的图表时，我只是这样做的：graph[word1][word2] = count（你可以非常复杂并使用默认字典，这样它将返回未见过的值为0 的对）。 - BostonJohn

Answer 1

这是一个使用networkX解决问题的方案。

代码将生成一个有向图dG。每个单词将作为一个节点，其中“count”属性表示该单词出现的次数。每个相邻二元组将作为有向边连接起来，其中“weight”属性表示该二元组出现的次数。

import networkx as nx
import string
from sys import maxint

str1 = """Man who run in front of car, get tired.
Man who run behind car, get exhausted."""

wordList1 = str1.split(None)

wordList2 = [string.rstrip(x.lower(), ',.!?;') for x in wordList1]

dG = nx.DiGraph()

for i, word in enumerate(wordList2):
    try:
        next_word = wordList2[i + 1]
        if not dG.has_node(word):
            dG.add_node(word)
            dG.node[word]['count'] = 1
        else:
            dG.node[word]['count'] += 1
        if not dG.has_node(next_word):
            dG.add_node(next_word)
            dG.node[next_word]['count'] = 0

        if not dG.has_edge(word, next_word):
            dG.add_edge(word, next_word, weight=maxint - 1)
        else:
            dG.edge[word][next_word]['weight'] -= 1
    except IndexError:
        if not dG.has_node(word):
            dG.add_node(word)
            dG.node[word]['count'] = 1
        else:
            dG.node[word]['count'] += 1
    except:
        raise

要查看图表的内容，您可以打印节点和边。

for node in dG.nodes():
    print '%s:%d\n' % (node, dG.node[node]['count'])

for edge in dG.edges():
    print '%s:%d\n' % (edge, maxint - dG.edge[edge[0]][edge[1]]['weight'])

请注意，二元组边的权重不是从零开始计数，而是从maxint开始倒数计数。这是因为networkX的最短路径工具将使用权重值作为每条边的代价。通过将我们的最高计数变为最小的权重，我们可以使用这些工具找到具有最高边计数的路径。

例如，我们可以在单词“man”和单词“exhausted”之间获取具有最高计数的路径：

>>>shortest_path = nx.shortest_path(dG, source='man', target='exhausted', weight='weight')
>>>print shortest_path
['man', 'who', 'run', 'behind', 'car', 'get', 'exhausted']

或者，我们可以获取单词“man”和所有其他单词之间计数最高的路径：

>>>shortest_paths = nx.shortest_path(dG, source='man', weight='weight')
>>>print shortest_paths
{'run': ['man', 'who', 'run'], 
'get': ['man', 'who', 'run', 'behind', 'car', 'get'], 
'exhausted': ['man', 'who', 'run', 'behind', 'car', 'get', 'exhausted'], 
'car': ['man', 'who', 'run', 'behind', 'car'], 
'who': ['man', 'who'], 
'behind': ['man', 'who', 'run', 'behind'], 
'of': ['man', 'who', 'run', 'in', 'front', 'of'], 
'in': ['man', 'who', 'run', 'in'], 
'front': ['man', 'who', 'run', 'in', 'front'], 
'tired': ['man', 'who', 'run', 'behind', 'car', 'get', 'tired'], 
'man': ['man']}

如上所述，像这样的图可能存在循环，我不确定networkx最短路径算法在处理这种情况时是否能很好地处理。

祝好运！

- brentlance

---

在Python3x中，请使用sys.maxsize而不是sys.maxint :) - SummerEla

Answer 2

使用字典存储二元组，每次遇到二元组时将值加1。获取字典值的最大值以生成起始点，然后递归调用一个函数，该函数获取以前一个二元组中最后一个单词开头的值最高的二元组，直到不存在以最后一个单词开头的二元组为止。要注意可能存在循环图的情况，例如I love that I love that I love无限循环（设置递归限制）。

我从未专门使用过networkx，但在浏览主页后，上述仍然适用。

- kreativitea