Как найти кратчайший путь зависимости между двумя словами в Python?
Я пытаюсь найти путь зависимости между двумя словами в Python с учетом дерева зависимостей.
Для предложения
Роботы в популярной культуре напоминают нам об удивительной свободе человеческой деятельности.
Я использовал practicenlptools ( 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/) 
Длина пути между "роботами" и "are" равна 1, длина пути между "роботами" и "awesomeness" будет равна 4.
Мой вопрос приведен выше результата анализа зависимости, как я могу получить путь зависимости или длину пути зависимости между двумя словами?
Из моего текущего результата поиска, nltk's ParentedTree поможет?
Спасибо!
3 ответа
Ваша проблема может быть легко воспринята как проблема графа, где мы должны найти кратчайший путь между двумя узлами.
Чтобы преобразовать ваш анализ зависимостей в граф, мы сначала должны иметь дело с тем фактом, что он представлен в виде строки. Вы хотите получить это:
'nsubj(are-5, Robots-1)\nxsubj(remind-8, Robots-1)\namod(culture-4, popular-3)\nprep_in(Robots-1, culture-4)\nroot(ROOT-0, are-5)\nadvmod(are-5, there-6)\naux(remind-8, to-7)\nxcomp(are-5, remind-8)\ndobj(remind-8, us-9)\ndet(awesomeness-12, the-11)\nprep_of(remind-8, awesomeness-12)\namod(agency-16, unbound-14)\namod(agency-16, human-15)\nprep_of(awesomeness-12, agency-16)'
выглядеть так:
[('are-5', 'Robots-1'), ('remind-8', 'Robots-1'), ('culture-4', 'popular-3'), ('Robots-1', 'culture-4'), ('ROOT-0', 'are-5'), ('are-5', 'there-6'), ('remind-8', 'to-7'), ('are-5', 'remind-8'), ('remind-8', 'us-9'), ('awesomeness-12', 'the-11'), ('remind-8', 'awesomeness-12'), ('agency-16', 'unbound-14'), ('agency-16', 'human-15'), ('awesomeness-12', 'agency-16')]
Таким образом, вы можете передать список кортежей в конструктор графа из модуля networkx, который проанализирует список и создаст для вас граф, плюс даст вам аккуратный метод, который дает вам длину кратчайшего пути между двумя заданными узлами.
Необходимый импорт
import re
import networkx as nx
from practnlptools.tools import Annotator
Как получить строку в нужном формате списка кортежей
annotator = Annotator()
text = """Robots in popular culture are there to remind us of the awesomeness of unbound human agency."""
dep_parse = annotator.getAnnotations(text, dep_parse=True)['dep_parse']
dp_list = dep_parse.split('\n')
pattern = re.compile(r'.+?\((.+?), (.+?)\)')
edges = []
for dep in dp_list:
m = pattern.search(dep)
edges.append((m.group(1), m.group(2)))
Как построить график
graph = nx.Graph(edges) # Well that was easy
Как вычислить кратчайшую длину пути
print(nx.shortest_path_length(graph, source='Robots-1', target='awesomeness-12'))
Этот скрипт покажет, что кратчайший путь с учетом анализа зависимостей на самом деле имеет длину 2, так как вы можете получить из Robots-1 в awesomeness-12 пройдя через remind-8
1. xsubj(remind-8, Robots-1)
2. prep_of(remind-8, awesomeness-12)
Если вам не нравится этот результат, вы можете подумать о фильтрации некоторых зависимостей, в этом случае не разрешать xsubj зависимость для добавления в график.
Ответ HugoMailhot отличный. Я напишу что-то похожее для пользователей, которые хотят найти кратчайший путь зависимости между двумя словами (тогда как ответ HugoMailhot основан на PractNLPTools).
Приговор:
Роботы в популярной культуре напоминают нам об удивительной свободе человеческой деятельности.
имеет следующее дерево зависимостей:
Вот код, чтобы найти кратчайший путь зависимости между двумя словами:
import networkx as nx
import spacy
nlp = spacy.load('en')
# https://spacy.io/docs/usage/processing-text
document = nlp(u'Robots in popular culture are there to remind us of the awesomeness of unbound human agency.', parse=True)
print('document: {0}'.format(document))
# Load spacy's dependency tree into a networkx graph
edges = []
for token in document:
# FYI https://spacy.io/docs/api/token
for child in token.children:
edges.append(('{0}-{1}'.format(token.lower_,token.i),
'{0}-{1}'.format(child.lower_,child.i)))
graph = nx.Graph(edges)
# https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.shortest_paths.html
print(nx.shortest_path_length(graph, source='robots-0', target='awesomeness-11'))
print(nx.shortest_path(graph, source='robots-0', target='awesomeness-11'))
print(nx.shortest_path(graph, source='robots-0', target='agency-15'))
Выход:
4
['robots-0', 'are-4', 'remind-7', 'of-9', 'awesomeness-11']
['robots-0', 'are-4', 'remind-7', 'of-9', 'awesomeness-11', 'of-12', 'agency-15']
Чтобы установить spacy и networkx:
sudo pip install networkx
sudo pip install spacy
sudo python -m spacy.en.download parser # will take 0.5 GB
Некоторые тесты, касающиеся анализа зависимостей spacy: https://spacy.io/docs/api/
Этот ответ опирается на Stanford CoreNLP для получения дерева зависимостей предложения. Он использует довольно много кода из ответа HugoMailhot при использовании networkx.
Перед запуском кода необходимо:
sudo pip install pycorenlp(интерфейс Python для Stanford CoreNLP)- Скачать Стэнфордский CoreNLP
Запустите сервер Stanford 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
Обратите внимание, что Stanford CoreNLP можно протестировать в Интернете: http://nlp.stanford.edu:8080/parser/index.jsp
Этот ответ был протестирован с использованием Stanford CoreNLP 3.6.0, pycorenlp 0.3.0 и python 3.5 x64 на Windows 7 SP1 x64 Ultimate.