Как найти отношения между объектами

Ответ 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
}

EDIT: Это не делает то, что вы просили, потому что это не делает связь между "пакетом" и "кошкой", поскольку пакет не представлен фактическим объектом слова, и я определил метод для получения слова2 как объект (просто отработав ваш пример). Вместо этого я мог бы сделать эту строку, чтобы она могла проверить "пакет" в массиве синонимов "набора" перед возвратом, но идея такая же, тем не менее... Здесь объяснение алгоритма высокого уровня.

Итерации синонимов, если это не совпадение, найти этот объект Word в исходной коллекции и вызвать себя с ним в качестве первого аргумента. Это будет рекурсивно исчерпывать каждый путь до тех пор, пока не найдет совпадение, или нет никого в этом случае, если вы находитесь за пределами цикла, возвращающего false. Вышеприведенный код работает на игровой площадке go и правильно возвращает true\nfalse. Обратите внимание, что рекурсивный вызов выполняется в if, чтобы защитить от преждевременного возврата false (также повышение производительности, потому что мы возвращаемся, как только вернется истина, а не продолжаем повторять пути).

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

Ответ 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"))

Вывод:

True
True
False
False

Ответ 3

Прежде всего, неясно, как вы определяете отношения здесь. Если ваш "cat" имеет синонимы: [ "feline", "kitten", "mouser" ], означает ли это, что "mouser" имеет синоним "cat".

На основании моего понимания ответ - нет. Итак, вот решение в 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

Итак, что мы здесь делаем? Сначала у вас есть свой график, который является просто словарем (map in go), который показывает ваши отношения (я в основном взял ваш фрагмент).

Наш алгоритм растет как форма, поддерживая набор проверенных элементов и текущую границу. Если граница пуста (ничего не исследовать, элементы не связаны). Мы извлекаем один элемент за раз с границы и проверяем всех соседей. Если какой-либо из них является элементом, который мы ищем - тогда есть соединение. В противном случае проверьте, видел ли мы такой элемент (а если не добавляем его на границу и в набор отмеченных).

Обратите внимание: если ваши отношения работают несколько иначе, все, что вам нужно, это изменить график.

Последнее слово, если вы ищете нормальный способ поиска синонимов, посмотрите слово на векторный алгоритм и приятный в python. Это позволит вам найти действительно сложную взаимосвязь даже между словами, такими как поиск того, что California и Golden Gate связаны даже без указания указанной связи.

Ответ 4

Здесь приведен пример рекурсивного алгоритма, написанного на 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>

Ответ 5

Вы смотрите на отношения второй степени (в отличие от "простого" примера 1-го места, который вы уже знаете, как найти), что означает, что вам нужно сделать одну из двух вещей:

(1) Решение для хранения данных требует поддержки отдельного списка отношений 2-й степени, а затем просто выполняет поиск в этом (более длинном) списке - для этого требуется поддерживать (потенциально MUCH) больше данных о словарных связях. Например, если у вас есть 10000 слов, и у каждого есть примерно 10 синонимов, то сохраняется 100 000 отношений первой степени. Но тогда у вас будет нечто вроде миллиарда отношений 2-й степени. Так что, конечно, это быстро становится громоздким.

В этом случае каждая запись выглядит следующим образом: {text: "cat" синонимы: [ "кошачий", "котенок", "mouser" ] секунд: [ "pack",...]} ... и вы просто пишете отдельную функцию, которая будет проверять отношения в синонимах "или" секунд ".

(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
}

ПРИМЕЧАНИЕ. Я заметил, что в ваших образцовых данных "кошка" была связана с "котенком", но "котенок" не был обратно связан с "кошкой".