生成蟒蛇

Question

有向詞圖從句子的名單，我想生成有向圖根據以下屬性生成一個子一句：

假設有三句話：

• 我愛糖果
• 我愛你
• 我愛糖果非常

圖形將公頃每一對連續出現的每個連續單詞之間都有重量爲1的邊緣。

然後我找出圖中最大權重的路徑。這將返回「我愛糖果非常好」，重量爲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庫，但不太熟悉它。

如何繼續製作邊緣權重圖？

Answer 1

使用字典存儲雙字母組，每次遇到兩字時加1的值。獲取字典值的最大值以生成起始點，然後遞歸地調用一個函數，該函數獲取以前一個二元詞中的最後一個詞開頭的最高值的bigram，直到不再有以最後一個詞開始的更大格式。警惕圓形圖形的可能性，例如I love that I love that I love ad infinitum（設置遞歸限制）。

我從來沒有與networkx具體工作，而是通過網頁一瞧後，上面仍然適用。

Answer 2

下面是使用networkX解決您的問題的方法。

該代碼將生成一個有向圖dG。 dG每個單詞將有一個節點，其中'count'屬性表示該單詞已被查看過多少次。每個二元組有一個有向邊，其中'weight'屬性表示兩個bigram發生了多少次。

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的最短路徑實用程序將使用權重值作爲每邊的成本。通過使我們的最高計數成爲我們最小的權重，我們可以使用這些實用程序來查找具有最高邊數的路徑。

例如，我們可以得到字「人」與字之間最高計數的路徑「耗盡」：

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

或者，我們可以得到字「的最高計數的路徑男人和所有其他：

>>>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最短路徑算法將如何處理這種情況。

祝你好運！