Сравнение деревьев парсеров: общий подсписок в двух списках - PullRequest
Новая
       46

Сравнение деревьев парсеров: общий подсписок в двух списках

0 голосов
/ 11 декабря 2018

Моя цель - определить, дублируются ли два предложения.

Я пытаюсь сравнить деревья синтаксического анализатора двух предложений.Я извлек теги из деревьев синтаксического анализатора в следующем формате 

['ROOT', 'SBARQ', 'WHADVP', 'WRB', 'SQ', 'VP', 'VBP', 'ADJP', 'RB', 'JJ', 'NP', 'NNP', 'NP', 'NP', 'NNS', 'VP', 'VBG', 'NP', 'NP', 'NNS', 'SBAR', 'WHNP', 'WDT', 'S', 'VP', 'VBP', 'ADVP', 'RB', 'VP', 'VBN', 'PP', 'IN', 'NP', 'NNP', '.']
['ROOT', 'SBARQ', 'WHADVP', 'WRB', 'SQ', 'VBP', 'NP', 'NNS', 'VP', 'VB', 'NP', 'NP', 'NNP', 'NNS', 'SBAR', 'WHNP', 'WDT', 'S', 'VP', 'MD', 'VP', 'VB', 'VP', 'VBN', 'ADVP', 'RB', 'PP', 'IN', 'NP', 'NNP', '.']

Я хочу получить длину общих подсписков двух списков.В приведенном выше случае результаты будут 4 («ROOT», «SBARQ», «WHADVP», «WRB») + 5 («SBAR», «WHNP», «WDT», «S», «VP»)+2 ('ADVP', ​​'RB') + 5 ('PP', 'IN', 'NP', 'NNP', '.').

Или у вас есть другие решения, которые можно сделатьиспользование дерева разбора для сходства двух предложений.Еще один вопрос, какой самый быстрый способ получить дерево разбора?Так как у меня есть более 300 000 пар предложений для сравнения ...

Заранее спасибо!

Ответы [ 3 ]

0 голосов
/ 11 декабря 2018

Python stdlib включает в себя модуль difflib для выполнения различий, что-то вроде этого (хотя результаты немного отличаются от ожидаемых): 

pos1 = ['ROOT', 'SBARQ', 'WHADVP', 'WRB', 'SQ', 'VP', 'VBP', 'ADJP', 'RB', 'JJ', 'NP', 'NNP', 'NP', 'NP', 'NNS', 'VP', 'VBG', 'NP', 'NP', 'NNS', 'SBAR', 'WHNP', 'WDT', 'S', 'VP', 'VBP', 'ADVP', 'RB', 'VP', 'VBN', 'PP', 'IN', 'NP', 'NNP', '.']
pos2 = ['ROOT', 'SBARQ', 'WHADVP', 'WRB', 'SQ', 'VBP', 'NP', 'NNS', 'VP', 'VB', 'NP', 'NP', 'NNP', 'NNS', 'SBAR', 'WHNP', 'WDT', 'S', 'VP', 'MD', 'VP', 'VB', 'VP', 'VBN', 'ADVP', 'RB', 'PP', 'IN', 'NP', 'NNP', '.']

from difflib import SequenceMatcher

sm = SequenceMatcher(a=pos1, b=pos2)
for diff in sm.get_opcodes():
    # uncomment this to see all the diffs
    # print(diff)
    op, f1_from, f1_to, f2_from, f2_to = diff
    if op == 'equal':
        print("{}{}".format(f1_to-f1_from, tuple(pos1[f1_from:f1_to])))

дает: 

5('ROOT', 'SBARQ', 'WHADVP', 'WRB', 'SQ')
1('VBP',)
3('NP', 'NNS', 'VP')
2('NP', 'NP')
6('NNS', 'SBAR', 'WHNP', 'WDT', 'S', 'VP')
2('ADVP', 'RB')
5('PP', 'IN', 'NP', 'NNP', '.')
0 голосов
/ 24 декабря 2018

Я думаю, что у меня может быть такая же проблема, как и у вас.

Ваша цель - вычислить сумму общих узлов двух деревьев и затем получить сходство двух предложений?

0 голосов
/ 11 декабря 2018

Я рекомендую вам прочитать о Самая длинная общая проблема подпоследовательности

, и здесь у вас есть оба примера, использующие рекурсивное и динамическое программирование, оба пишущие на python

https://rosettacode.org/wiki/Longest_common_subsequence#Python

...