如何在给定单词映射的情况下检查两组语句是否为及物性和反身性

Question

给定两个句子，以及单词与其同义词的映射，我想编写一个程序来确定这些句子是否相似。两个句子相似的条件是它们有相同的单词数量，并且每个对应的单词都是同义词。一定要处理同义词之间的对称和传递关系。例如，同义词映射是：

[(“a”, “b”), (“a”, “c”), (“a”, “d”), (“b”, “e”), (“f”, “e”), (“g”, “h”)]

那么句子“a e g”和“f c h”就是同义词。示例：

Input S1: “a e g” S2: “f c h” 
Map: [(“a”, “b”), (“a”, “c”), (“a”, “d”), (“b”, “e”), (“f”, “e”), (“g”, “h”)]
Output: True 

说明：“a”和“f”是同义词，因为“a”和“b”是同义词，“f”和“e”是同义词，“b”和“e”是同义词。类似地，“c”和“e”是同义词，“g”和“h”是同义词。

我已经尝试过这组代码：

synonyms = [('a','b'), ('a','c'),('a','d'),('b','e'), ('f','e'), ('g','h')]

def transitive(sequence):
    for a,b in sequence:
        for c,d in sequence:
            if b==c and (a,d) not in sequence:
                return True

    return False

def symmetric(sequence):
    for x,y in sequence:
        for a,z in sequence:
            if y == a and x == z:
                return True
    return False

def main(input1, input2):

    if len(input1) == len(input2):
        for a in input1:    
            for b in input2:
                if transitive(synonyms) and symmetric(synonyms):
                    c = "True"
                else:
                    c = "False"

        for a in input1 and input2:
        # for b in input2:
            if transitive(synonyms) and symmetric(synonyms):
                c = "True"

            else:
                c = "False"
        print(c)

    else:
        print("False")                      
first = input("Enter first statement: \n")
second = input("Enter second statement: \n")
main(first,second)

我想不出逻辑来比较这两个字符串

Answer 1

这里有一种可能性。因为您有一个equivalence relation，所以您可以考虑从它形成的equivalence classes。基本上，您可以创建集合，使彼此同义词的所有单词都在一起。或者，如果您更喜欢用图的形式来考虑它，您可以将您的元组视为无向图的边，并找到connected components。

你可以这样做：

def make_word_classes(synom):
    # List of classes
    word_classes = []
    for w1, w2 in synom:
        # Go through existing classes
        for wcls in word_classes:
            # If one of the words is already in the current class
            if w1 in wcls or w2 in wcls:
                # Add both words and continue to next pair of words
                wcls.add(w1)
                wcls.add(w2)
                break
        else:  # Note this else goes with the for loop, not the if block
            # If there was no matching class, add a new one
            word_classes.append({w1, w2})
    return word_classes

synom = [("a", "b"), ("a", "c"), ("a", "d"), ("b", "e"), ("f", "e"), ("g", "h")]
word_classes = make_word_classes(synom)
print(word_classes)
# [{'a', 'c', 'b', 'd', 'f', 'e'}, {'h', 'g'}]

有了这些，就很容易判断两个句子是否相等。您只需检查每对单词是否相等或属于相同的等价类：

def sentences_are_equivalent(s1, s2, word_classes):
    # Split into words
    l1 = s1.split()
    l2 = s2.split()
    # If they have different sizes they are different
    if len(l1) != len(l2):
        return False
    # Go through each pair of corresponding words
    for w1, w2 in zip(l1, l2):
        # If it is the same word then it is okay
        if w1 == w2:
            continue
        # Go through list of word classes
        for wcls in word_classes:
            # If both words are in the same class it is okay
            if w1 in wcls and w2 in wcls:
                # Continue to next pair of words
                break
        else:  # Again, this else goes with the for loop
            # If no class contains the pair of words
            return False
    return True

s1 = "a e g"
s2 = "f c h"
print(sentences_are_equivalent(s1, s2, word_classes))
# True