javascript - 如何找到对象之间的关系

Question

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

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

更多方法/阅读:

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

Prolog and ancestor relationship

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" 之类的两个词之间进行测试会很容易。我可以检查“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

如果你给我一些反馈，我可以编辑它，因为它没有完全按照你的要求做，但它是 jist。我将通过技术解释对必须进行更改以符合您的确切示例进行编辑。

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