如何找到对象之间的关系

Question

对于有类似问题的人（找到解决方案后写的）：根据下面的答案，您可能会注意到这个问题有很多不同的解决方案。我只选择了 Evan 的，因为它是我在自己的代码中实现的最简单的方法。但是，根据我的尝试，其他所有答案也都有效。@SalvadorDali链接了这个Kaggle 页面，这绝对很有趣，如果您有兴趣，我建议您阅读。Prolog 也被提出作为一种可能的解决方案，我不熟悉它，但如果您已经知道它 - 可能值得考虑。此外，如果您只是想使用代码，下面有可用的 Javascript 和 Python 示例。但是，每个人都有不同的解决方案，我不确定哪种方法最有效（请自行测试）。进一步的方法/阅读：http://en.wikipedia.org/wiki/Breadth-first_search序言和祖先关系https://www.kaggle.com/c/word2vec-nlp-tutorial/details/part-2-word-vectors对不起，标题令人困惑，我想不出一种方法来正确地表达我的问题——欢迎任何更好的想法。因为我很难描述我的问题，所以我会尽量解释我的目标和代码：注意：我这里的代码是 Go，但我也很乐意提供其他语言的答案，如果您有任何问题，我会尽快回答基本上，我有一组“Word”对象，如下所示：type Word struct{     text     string     synonyms []string}这是数组中 4 个单词的示例：  []Word{      {text: "cat" synonyms: ["feline", "kitten", "mouser"]}      {text: "kitten" synonyms: ["kitty", "kit"]}       {text: "kit" synonyms: ["pack", "bag", "gear"]}      {text: "computer" synonyms: ["electronics", "PC", "abacus"]}   }我的挑战是编写一种方法来测试两个词之间的关系。当然，使用上面的示例可以很容易地在“cat”和“kitten”等两个词之间进行测试。我可以检查“猫”的同义词列表并测试它是否包含“小猫”。用这样的代码：areWordsRelated(word1 Word, word2 Word) bool{    for _, elem := range word1.synonyms{         if elem == word2.text{             return true         }    }    return false}但是，我不知道如何测试更远的关系。例如：areWordsRelated("cat","pack") //should return true //because "cat" is related to "kitten" which is related to "pack"areWordsRelated("cat", "computer") //should return false我试图递归地做，但我所有的尝试似乎都不起作用。任何示例代码（我的代码是 Go，但 Python、Java 或 Javascript 也可以）、伪代码或只是解释都非常棒。

Answer 1

首先，这里不清楚你如何定义关系。如果你的“猫”有同义词：[“猫”，“小猫”，“鼠标”]，这是否意味着“鼠标”有一个同义词“猫”。

根据我的理解，答案是否定的。所以这是python中的解决方案：

G = {

    "cat": ["feline", "kitten", "mouser"],

    "kitten": ["kitty", "kit"],

    "kit": ["pack", "bag", "gear"],

    "computer": ["electronics", "PC", "abacus"]

}

def areWordsRelated(G, w1, w2):

    if w1 == w2:

        return True

    frontier = [w1]

    checked = set()

    while len(frontier):

        el = frontier.pop()

        if el in G:

            neighbors = G[el]

            for i in neighbors:

                if i == w2:

                    return True

                if i not in checked:

                    frontier.append(i)

                    checked.add(i)

    return False

areWordsRelated(G, "cat", "pack") #true

areWordsRelated(G, "cat", "computer") #false

那么我们在这里做什么呢？起初你有你的图表，它只是字典（地图），它显示了你的关系（我基本上拿了你的切片）。

我们的算法像模具一样增长，维护一组检查元素和当前边界。如果 frontier 是空的（没有什么可探索的，那么元素没有连接）。我们一次从边界中提取一个元素并检查所有邻居。如果它们中的任何一个是我们正在寻找的元素 - 那么就存在联系。否则检查我们是否已经看到了这样的元素（如果没有，则将其添加到边界和已检查的集合中）。

请注意，如果您的关系以稍微不同的方式运作，您需要的只是修改图表。

最后一句话，如果您正在寻找一种正常的方法来查找同义词，请查看word to vector 算法和python 中的一个很好的实现。这将允许您找到真正复杂的关系，即使是在没有指定这种关系的情况下，California也Golden Gate可以找到相关的词。