如何找出对象之间的关系

Question

对于有类似问题的人（在找到解决方案后编写）：

如下面的答案所示，这个问题有很多不同的解决方案。我只选择了Evan的答案，因为它对我来说是最容易实现到我的代码中去的。然而，从我尝试过的结果来看，每个其他的答案也都起作用。@SalvadorDali 链接了这个Kaggle页面，非常有趣，如果你感兴趣，我建议你阅读一下。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也可以），伪代码或解释都将非常棒。

- Maximilian Sun

---

按照你的构建方式，基本上会有多个相关单词的有限集合（一个集合可能是{计算机、电子、个人电脑、算盘}，另一个可能是{猫科动物、小猫、猫、捕鼠器、袋子、齿轮、包等等等等}）。为什么不编写代码预先定义所有这些集合，然后测试这两个单词是否都是任何一个集合的成员呢？ - Rick

这似乎很适合 Prolog。 - DiogoDoreto

Prolog具有声明性语法来构建关系，并允许您查询这些关系...很抱歉我不能给您展示一个例子，因为我学习它已经有几年了。如果没有好的答案出现，也许值得去了解一下。 - DiogoDoreto

这里，我在Prolog中找到了一个相关的问题，你可以根据你的问题进行调整：https://dev59.com/4F_Va4cB1Zd3GeqPUpFE - DiogoDoreto

@DiogoDoreto，Progol是一种声明式语言，而Go、Python和JavaScript都是命令式的...所以我不建议除了出于好奇之外使用这种解决方案。 - icza

Answer 1

一个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"))

输出：

True
True
False
False

- R Sahu

---

我该如何构建这棵树？ - Maximilian Sun

Answer 2

如果您对此提供一些反馈，我可以进行编辑，因为它并不完全符合您的要求，但这是主旨。我将编辑带有技术解释的内容，以满足您的确切示例。

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”之间的连接表示为实际的单词对象，并且我定义了该方法接收word2作为对象（只是根据您的示例工作）。我可以改为将其作为字符串，以便在返回之前检查“kit”的同义词数组中是否有“pack”，但是无论如何想法都是相同的......以下是算法的高级解释。

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

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

- evanmcdonnal

---

有没有一种方法可以让它在离起始单词X个单词后超时？我可以向该方法添加一个参数来跟踪迭代次数，对吗？ - Maximilian Sun

@MaximilianSun，这很容易，只需在循环中添加一个计数器并进行检查。如果达到边缘限制或您所称的任何其他限制，则返回false。 - evanmcdonnal

我认为你关于“pack”与“kit”无关的注释，主要是因为我的示例有问题，而不是你的代码。 - Maximilian Sun

@MaximilianSun 是的，这个例子不太一致，所以我选择了那种方式。如果你把 word2 改为一个字符串，然后按需要修改函数体使其能够编译，你就可以传入 words[0] 和 "pack"，它将返回 true。 - evanmcdonnal

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中为map），显示您的关系（我基本上采用了您的切片）。

我们的算法像霉菌一样生长，维护一组已检查的元素和当前边界。如果边界为空（没有要探索的内容），则元素不相连。我们从边界中逐个提取元素并检查所有邻居。如果其中任何一个是我们正在寻找的元素，则存在连接。否则，请检查我们是否已经看到了这样的元素（如果没有，则将其添加到边界和已检查的集合中）。

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

---

最后一点，如果您正在寻找一种正常的方法来查找同义词，请查看单词向量算法和一个不错的Python实现。这将使您能够找到复杂的关系，甚至在单词之间找到像找到加利福尼亚和金门大桥这样的相关性，即使没有明确指定这种关系。

- Salvador Dali

Answer 4

您正在查看2度关系（与您已经知道如何查找的“简单”1度关系示例相反），这意味着您需要做以下两件事之一：

（1）存储量大的解决方案需要维护一个2度关系的单独列表，然后在该列表中进行搜索（较长的列表）- 这需要维护关于单词关系的（可能非常多）更多数据。例如，如果您有10000个单词，并且每个单词大约有10个同义词，则存储了100,000个1度关系。但是，然后您将拥有大约十亿个2度关系。因此，当然会很快变得难以控制。

在这种情况下，每个条目看起来像这样： {text: "cat" synonyms: ["feline", "kitten", "mouser"] seconds:["pack",...]} … 然后，您只需编写一个单独的函数，该函数将检查'synonyms'或'seconds'中的关系。

（2）程序化解决方案仍将仅存储1度关系，然后执行嵌入式循环。

在这种情况下：

//// This checks for 1st degree relationship
areWordsRelated1(word1 Word, word2 Word) bool{
    for _, elem := range word1.synonyms{
         if elem == word2.text{
             return true
         }
    }
    return false
}

//// This checks for 2nd degree by checking 1st and then, if not, 
//// then trying the 1st degree function on the children of word2
//// before giving up and returning false
areWordsRelated2(word1 Word, word2 Word) bool{
    for _, elem1 := range word1.synonyms{
         if elem1 == word2.text{
             return true
         } else {
         for _, elem2 := range elem1.synonyms{
             if areWordsRelated1(word1, elem2) {
                 return true
             }
         }
    }
    return false
}

注意：我注意到在你的样本数据中，“cat”与“kitten”相关，但是“kitten”并没有相反地与“cat”相关。

- Jonathan Tweedy

Answer 5

这里是一个用JavaScript编写的递归算法示例，其中还加入了一些jQuery以使搜索数组更容易。它可能需要进行优化，但应该可以为您提供一个开始。

$(function() {
  var words = [{
    text: "cat",
    synonyms: ["feline", "kitten", "mouser"]
  }, {
    text: "kitten",
    synonyms: ["kitty", "kit"]
  }, {
    text: "kit",
    synonyms: ["pack", "bag", "gear"]
  }, {
    text: "computer",
    synonyms: ["electronics", "PC", "abacus"]
  }];

  console.log(areWordsRelated('cat', 'pack', words));
  console.log(areWordsRelated('cat', 'rack', words));
});

function areWordsRelated(parentWord, childWord, list) {
  var parentWordItems = $.grep(list, function(element) {
    return element.text === parentWord;
  });

  if (parentWordItems.length === 0) {
    return false
  } else {
    var parentWordItem = parentWordItems[0];
    var remainingItems = $.grep(list, function(element) {
      return element.text !== parentWord;
    });
    if (parentWordItem.synonyms.indexOf(childWord) >= 0) {
      return true;
    } else {
      for (var i = 0; i < parentWordItem.synonyms.length; i++) {
        var synonym = parentWordItem.synonyms[i];
        if (areWordsRelated(synonym, childWord, remainingItems)) {
          return true;
        }
      }
      return false;
    }
  }
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>

- Dave