解析器树比较：两个列表中的公共子列表

Question

我的目标是确定两个句子是否重复。你知道吗

我试着比较这两个句子的语法树。 我已经按照以下格式从解析器树中提取了标记

['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', '.']

Answer 1

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', '.')

Answer 2

我想我可能和你有类似的问题。你知道吗

你的目标是计算两棵树的公共节点之和，然后得到两个句子的相似度吗？你知道吗

Answer 3

我建议你阅读Longest common subsequence problem

这里有两个使用递归和动态编程的例子，都是用python编写的

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