如何在Python中找到两个单词之间的最短依赖路径？

Question

我试图在Python给定的依赖树中找到两个单词之间的依赖路径。

判刑

Robots in popular culture are there to remind us of the awesomeness of unbound human agency.

我使用practnlptools（https://github.com/biplab-iitb/practNLPTools）来获得依赖项分析结果，如：

nsubj(are-5, Robots-1)
xsubj(remind-8, Robots-1)
amod(culture-4, popular-3)
prep_in(Robots-1, culture-4)
root(ROOT-0, are-5)
advmod(are-5, there-6)
aux(remind-8, to-7)
xcomp(are-5, remind-8)
dobj(remind-8, us-9)
det(awesomeness-12, the-11)
prep_of(remind-8, awesomeness-12)
amod(agency-16, unbound-14)
amod(agency-16, human-15)
prep_of(awesomeness-12, agency-16)

也可以可视化为（从https://demos.explosion.ai/displacy/拍摄的照片）

“机器人”和“是”之间的路径长度为1，“机器人”和“敬畏”之间的路径长度为4。

我的问题是上面给出的依赖解析结果，如何得到两个单词之间的依赖路径或依赖路径长度？

从我目前的搜索结果来看，nltk的ParentedTree会有帮助吗？

谢谢！

Answer 1

这个答案依赖于Stanford CoreNLP来获得句子的依赖树。在使用networkx时，它从HugoMailhot的answer中借用了相当多的代码。

在运行代码之前，需要：

1. sudo pip install pycorenlp（斯坦福CoreNLP的python接口）
2. 下载Stanford CoreNLP

3. 启动斯坦福CoreNLP服务器，如下所示：

   java -mx4g -cp "*" edu.stanford.nlp.pipeline.StanfordCoreNLPServer -port 9000 -timeout 50000
   

然后可以运行以下代码来查找两个单词之间的最短依赖路径：

import networkx as nx
from pycorenlp import StanfordCoreNLP
from pprint import pprint

nlp = StanfordCoreNLP('http://localhost:{0}'.format(9000))
def get_stanford_annotations(text, port=9000,
                             annotators='tokenize,ssplit,pos,lemma,depparse,parse'):
    output = nlp.annotate(text, properties={
        "timeout": "10000",
        "ssplit.newlineIsSentenceBreak": "two",
        'annotators': annotators,
        'outputFormat': 'json'
    })
    return output

# The code expects the document to contains exactly one sentence.
document =  'Robots in popular culture are there to remind us of the awesomeness of'\
            'unbound human agency.'
print('document: {0}'.format(document))

# Parse the text
annotations = get_stanford_annotations(document, port=9000,
                                       annotators='tokenize,ssplit,pos,lemma,depparse')
tokens = annotations['sentences'][0]['tokens']

# Load Stanford CoreNLP's dependency tree into a networkx graph
edges = []
dependencies = {}
for edge in annotations['sentences'][0]['basic-dependencies']:
    edges.append((edge['governor'], edge['dependent']))
    dependencies[(min(edge['governor'], edge['dependent']),
                  max(edge['governor'], edge['dependent']))] = edge

graph = nx.Graph(edges)
#pprint(dependencies)
#print('edges: {0}'.format(edges))

# Find the shortest path
token1 = 'Robots'
token2 = 'awesomeness'
for token in tokens:
    if token1 == token['originalText']:
        token1_index = token['index']
    if token2 == token['originalText']:
        token2_index = token['index']

path = nx.shortest_path(graph, source=token1_index, target=token2_index)
print('path: {0}'.format(path))

for token_id in path:
    token = tokens[token_id-1]
    token_text = token['originalText']
    print('Node {0}\ttoken_text: {1}'.format(token_id,token_text))

输出为：

document: Robots in popular culture are there to remind us of the awesomeness of unbound human agency.
path: [1, 5, 8, 12]
Node 1  token_text: Robots
Node 5  token_text: are
Node 8  token_text: remind
Node 12 token_text: awesomeness

注意，斯坦福CoreNLP可以在线测试：http://nlp.stanford.edu:8080/parser/index.jsp

这个答案在windows7sp1x64ultimate上用斯坦福CoreNLP 3.6.0、pycorenlp 0.3.0和python3.5x64进行了测试。