Реализация словаря синонимов?

Question

Как мне подойти к этой проблеме?Мне в основном нужно реализовать словарь синонимов.Он принимает в качестве входных данных некоторые пары "слово / синоним", и я должен иметь возможность "запросить" его для получения списка всех синонимов слова.

Например:

Dictionary myDic;

myDic.Add("car", "automobile");
myDic.Add("car", "autovehicle");
myDic.Add("car", "vehicle");
myDic.Add("bike", "vehicle");

myDic.ListOSyns("car") // should return {"automobile","autovehicle","vehicle" ± "car"}
                       // but "bike" should NOT be among the words returned

Я напишу это на C ++, но меня интересует общая идея реализации, поэтому вопрос не является специфичным для конкретного языка.

PS: Основная идея состоит в том, чтобы иметь несколько групп слов (синонимы).В приведенном выше примере таких групп будет две:

{"автомобиль", "автомобиль", "автомобиль", "автомобиль"} {"велосипед", "автомобиль"}

"транспортное средство "принадлежит обоим", "велосипед" только второму, остальные только первому

Answer 1

Я бы реализовал это как Graph + hash table / search tree
каждое ключевое слово было бы вершиной, а каждое соединение между двумя ключевыми словами было бы ребром.
хеш-таблица или дерево поиска будут соединяться от каждого слова к его узлу (и наоборот).
при отправке запроса - вы находите узел с вашим хешем / деревом и выполняете BFS / DFS необходимой глубины. (то есть вы не можете продолжить после определенной глубины)

сложность: O (E (d) + V (d)) для поиска графа (d = глубина) (E (d) = количество ребер на соответствующей глубине, то же самое для V (d))
O (1) для создания ребра (не включая поиск узла, подробно под его поиском)
O (logn) / O (1) для поиска узла (для дерева / хеш-таблицы)
O (logn) / O (1) для добавления ключевого слова в дерево / хэш-таблицу и O (1) для добавления вершины
p.s. как упомянуто: проектировщик должен иметь в виду, нуждается ли он в направленном или косвенном Графике, как упомянуто в комментариях к вопросу.
надеюсь, что это поможет ...

Answer 2

С пояснениями в комментариях к вопросу это относительно просто, поскольку вы не храните группы взаимных синонимов, а скорее отдельно определяете приемлемые синонимы для каждого слова. Очевидным контейнером является либо:

std::map<std::string, std::set<std::string> >

или

std::multi_map<std::string, std::string>

если вас не волнует вставка дубликатов, например:

myDic.Add("car", "automobile");
myDic.Add("car", "auto");
myDic.Add("car", "automobile");

В случае multi_map используйте функцию-член equal_range, чтобы извлечь синонимы для каждого слова, например, так:

struct Dictionary {
    vector<string> ListOSyns(const string &key) const {
        typedef multi_map<string, string>::const_iterator constit;
        pair<constit, constit> x = innermap.equal_range(key);
        vector<string> retval(x.first, x.second);
        retval.push_back(key);
        return retval;
    }
};

Наконец, если вы предпочитаете структуру, подобную хеш-таблице, древовидной структуре, тогда unordered_multimap может быть доступно в вашей реализации C ++, и в основном работает тот же код.