如何找到对象之间的关系

Question

对于有类似问题的人(在找到解决方案后编写):

根据下面的答案,您可能会注意到这个问题,有很多不同的解决方案.我只选择了Evan,因为它是我在自己的代码中实现的最简单的方法.但是,根据我的尝试,其他每个答案也都有效.@SalvadorDali链接了这个非常有趣的Kaggle页面,如果你有兴趣,我建议阅读.Prolog也被提出作为一种可能的解决方案,我对它不熟悉,但如果你已经知道它 - 它可能值得考虑.此外,如果您只想获取要使用的代码,请参阅下面的Javascript和Python示例.但是,每个人都有不同的解决方案,我不确定哪个是最有效的(随意自己测试).

进一步的方法/阅读:

http://en.wikipedia.org/wiki/Breadth-first_search

Prolog和祖先的关系

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"之类的2个单词之间进行测试会很容易.我可以查看"猫"的同义词列表并测试它是否包含"小猫".使用这样的代码:

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

如果你给我一些反馈，我可以编辑它，因为它并不完全符合你的要求，但它是要点。我将编辑技术解释，说明必须更改哪些内容才能满足您的确切示例。

package main

import "fmt"

func main() {
    words := []Word{
            {text: "cat", synonyms: []string{"feline", "kitten", "mouser"}},
            {text: "kitten", synonyms: []string{"kitty", "kit"}} ,
            {text: "kit", synonyms: []string{"pack", "bag", "gear"}},
            {text: "computer", synonyms: []string{"electronics", "PC", "abacus"}},
    }

    fmt.Println(areWordsRelated(words, words[0], words[2]))
    fmt.Println(areWordsRelated(words, words[0], words[3]))
}

type Word struct{
     text     string
     synonyms []string
}

func areWordsRelated(words []Word, word1, word2 Word) bool {
    for _, elem := range word1.synonyms{
        if elem == word2.text{
            return true
        } else {
            for _, word := range words {
                if word.text == elem {
                    if (areWordsRelated(words, word, word2)) {
                        return true
                    }
                }
            }
        }
    }
    return false
}

编辑：这并没有完全满足您的要求，因为它没有在“pack”和“cat”之间建立联系，因为 pack 不是由实际的单词对象表示，并且我定义了接收 word2 作为对象的方法（只是解决你的例子）。我可以将其设为一个字符串，以便它可以在返回之前检查“kit”的同义词数组中的“pack”，但想法仍然相同......这是该算法的高级解释。

迭代同义词，如果不匹配，则Word在原始集合中找到该对象并将其作为第一个参数调用我自己。这将递归地耗尽每个路径，直到找到匹配项，或者没有剩余路径，在这种情况下，您在循环之外返回 false。上面的代码在 go Playground 中运行并正确返回true\nfalse。请注意，递归调用是在 if 内进行的，以防止过早返回 false（这也是性能增强，因为我们一旦找到 true 就返回，而不是继续递归路径）。

https://play.golang.org/p/gCeY0SthU1