synonym data structure for searching

I'm looking for a data structure to keep synonyms. I would like to keep synonyms in bucket like "North America", "USA", "United States".

Search content can be tagged with any of "North America", "USA", "United States".

For example, Content_1 is tagged "USA" Content_2 is tagged "North America" Content_3 is tagged "United States" 

If User search for "USA", search result should return all three contents not just Content_1. To do get this, I have to get all synonyms of USA and then do a search.

How can I store synonyms where I look for a one of the synonyms and get all others ?

One way to do this is through HashMap like below

USA -> North America,United States United States -> USA, North America North America -> USA,United States 

This one does not look that good. Please suggest a good data structure to store synonyms.

thanks.

2 Answers

Access is O(1). But building a data structure looks like generating duplicate items. A better data structure where only one entry is stored.

You can use two data structures. One for storing them and one for lookup. One vector of vectors that contains all the synonyms of a word. And a hashmap that points to the container with all of the synonyms for O(1) lookup.

So you would store your synonyms in a data structure like this (a list of lists of strings):

{{"USA","North America","United States"},{"Tiny","Small"},{"Great","Good"}} 

And then you would have a hashmap, so if you search for "USA" you will get the first list. If you search for "Small" you will get the second list.

"USA"->{"USA","North America","United States"} "Small"->{"Small","Tiny"} 

The data in the hashmap is only a reference to the list of synonyms that you saved in the other data structure.

Build a datatype Synonym which has a Set<String> containing all synonyms for one word (in your case "North America", "USA", "United States"). Then map with a Map<String, Synonym> all your words to the corresponding Synonym.