如何找到对象之间的关系

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 FalseareWordsRelated(G, "cat", "pack") #trueareWordsRelated(G, "cat", "computer") #false那么我们在这里做什么呢？起初你有你的图表，它只是字典（地图），它显示了你的关系（我基本上拿了你的切片）。我们的算法像模具一样增长，维护一组检查元素和当前边界。如果 frontier 是空的（没有什么可探索的，那么元素没有连接）。我们一次从边界中提取一个元素并检查所有邻居。如果它们中的任何一个是我们正在寻找的元素 - 那么就存在联系。否则检查我们是否已经看到了这样的元素（如果没有，则将其添加到边界和已检查的集合中）。请注意，如果您的关系以稍微不同的方式运作，您需要的只是修改图表。最后一句话，如果您正在寻找一种正常的方法来查找同义词，请查看word to vector 算法和python 中的一个很好的实现。这将允许您找到真正复杂的关系，即使是在没有指定这种关系的情况下，California也Golden Gate可以找到相关的词。