Geek asks and answers

Synonym dictionary?

How do I approach this problem? I basically need to implement a dictionary of synonyms. Some “word / synonym” pairs are taken as input, and I should be able to “request” it for a list of all synonyms of the word.

For instance:


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

I will write C ++ code, but I'm interested in the general idea of ​​implementation, so the question is not language specific.

PS: The basic idea is to have several groups of words (synonyms). In the above example, there would be two such groups:

{"car", "auto equipment", "car", "car"} {"bicycle", "car"}

“vehicle” refers to both the “bicycle” and the second; the rest refers only to the first

+3
2

Graph + hash table/search tree Vertex, .
- node ( ). - node / BFS/DFS . ( , )

: O (E (d) + V (d)) (d = ) (E (d) = , V (d))
O (1) ( node, )
O (logn)/O (1) node ( /-)
O (logn)/O (1) tree/hash O (1)
P.S. : , , .
, ...

+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 ++ .

+1

More articles:


All Articles