Алгоритм формирования списка смежности с вложенными соседями - PullRequest
Новая
       59

Алгоритм формирования списка смежности с вложенными соседями

1 голос
/ 28 апреля 2020

Мне трудно придумать хороший алгоритм для формирования списка смежности, когда дан список синонимов.

Список синонимов представлен в виде вектора векторов. Внутренний вектор имеет размер 2 и состоит из 2 слов, которые являются синонимами.

например, 

std::vector<std::vector<std::string>> synonyms{{"joy", "happy"}, {"happy", 
"ecstatic"}, {"cheerful, ecstatic"}, {"big", "giant"}, {"giant", "gigantic"}};

Итак, у нас есть 2 набора синонимичных слов: {joy, happy, ecstatic, cheerful} и {big, giant, gigantic}

Я хочу создать список смежности из списка ребер, используя std::unordered_map<std::string, std::set<std::string>>. Значение set, потому что соседи должны быть отсортированы. В качестве альтернативы, значение может быть вектором, а затем мы отсортируем вектор в конце. Как лучше всего составить этот список смежности с учетом ребер?

Для этого списка смежности мне нужна запись для каждого слова. Так что в приведенном выше примере у меня будет 7 записей. И для каждой записи я хотел бы сопоставить ее со всеми словами, с которыми она является синонимом. Что-то вроде: 

{happy} -> {cheerful, ecstatic, joy}
{joy} -> {cheerful, ecstatic, happy}
{ecstatic} -> {cheerful, happy, joy}
{cheerful} -> {ecstatic, happy, joy}
{giant} -> {big, gigantic}
{big} -> {giant, gigantic}
{gigantic} -> {big, giant}

1 Ответ

0 голосов
/ 28 апреля 2020

Предположим две изолированные окрестности слов: Na и Nb. Каждое слово в окрестности знает все другие слова в окрестности (синонимы). Затем мы указываем, что слово из Na, называемое Wa, и слово из Nb, называемое Wb, объявлены как синонимы. У нас должно быть Wa и каждый сосед Wa (т.е. каждое слово в Na) добавляет Wb и каждый сосед Wb (т.е. каждое слово в Nb) к его списку соседей (синонимов). И мы должны иметь каждое слово в Nb добавить каждое слово в Na в свой список соседей (синонимов).

В конце этой операции все слова знают все другие слова в новой комбинированной окрестности, что делает эту новую окрестность допустимым входным сигналом для другой итерации вышеуказанного алгоритма.

Одно слово без добавления синонимов - это окрестность 1, что делает его корректным входом в алгоритм.

Не думайте о комбинировании слов. Думайте о соединении окрестностей. Каждое слово отображается в его полную окрестность, чтобы начать. Это облегчает переполнение кварталов. Позже мы можем удалить каждое слово из его собственного соседства. 

std::unordered_map<std::string, std::set<std::string>> al;

for (auto const & syns : synonyms)
  for (auto const & word : syns)
  {
    al[word].insert(word);
    for (auto const & syn : syns)
    {
      al[syn].insert(syn);
      if (word != syn)
      {
        // add the entire neighborhood of word to
        // the entire neighborhood of syn, and vice versa
        for (auto const & neighbor_word : al[word])
          for (auto const & neighbor_syn : al[syn])
          {
            al[child_word].insert(child_syn);
            al[child_syn].insert(child_word);
          }
      }
    }
  }

// remove each word's mapping to itself as a synonym:
for (auto & words : al)
  words.second.erase(words.first);

Грязно, черт возьми, и я не хочу оценивать сложность, но выполняет свою работу. Я думаю?

В ожидании экспертной оценки ...

...