如何查找对象之间的关系

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个单词的示例：

^{pr2}$

我的挑战是写一个方法来测试两个单词之间的关系。当然，在上面的例子中，在两个单词之间进行测试，比如“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不是由一个实际的word对象表示的，我定义了将word2作为对象接收的方法（只是完成您的示例）。我可以把它改为一个字符串，这样它就可以在返回之前检查“kit”的同义词数组中的“pack”，但是想法还是一样的。。。下面是算法的高级解释。在

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

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

Answer 2

Python解决方案：

class Word:

   # Dictionary of Words, keyed by name.
   word_dict = {}

   def __init__(self, name, synonyms):
      self.name = name
      self.synonyms = synonyms

      # Update the dictionary.
      Word.word_dict[name] = self
      for s in synonyms:
         if not s in Word.word_dict:
            Word.word_dict[s] = Word(s, [])

   def isAncestor(self, other):
      if other in self.synonyms:
         return True
      for s in self.synonyms:
         if Word.word_dict[s].isAncestor(other):
            return True
      return False

def areWordsRelated(word1, word2):
   if not word1 in Word.word_dict or not word2 in Word.word_dict:
      return False
   return Word.word_dict[word1].isAncestor(word2) or Word.word_dict[word2].isAncestor(word1)

words = []
words.append(Word("cat", ["feline", "kitten", "mouser"]))
words.append(Word("kitten", ["kitty", "kit"]))
words.append(Word("kit", ["patck", "bag", "gear"]))
words.append(Word("computer", ["electronics", "PC", "abacus"]))

print(areWordsRelated("cat", "kit"))
print(areWordsRelated("kit", "cat"))
print(areWordsRelated("cat", "computer"))
print(areWordsRelated("dog", "computer"))

输出：

^{pr2}$

Answer 3

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

根据我的理解，答案是否定的。下面是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

那我们在这里干什么？首先你有你的图表，这只是字典（地图在go）显示你的关系（我基本上采取了你的切片）。在

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

请注意，如果您的关系以稍微不同的方式工作，则只需修改图形。在

---

最后一句话，如果您正在寻找一种普通的方法来查找同义词，请看一下word to vector algorithm和一个漂亮的implementation in python。这将允许您找到非常复杂的关系，即使在没有指定关系的情况下，也可以发现California和{}是相关联的。在