0

I am trying to implement an (Language1 - Language2) dictionary. I want to make an search algorithm in both direction that speed is faster than O(n)

For example, if (hello, hola) is one pair,

SEARCH_SPANISH_BY_ENGLISH (hello) = "hola", and

SEARCH_ENGLISH_BY_SPANISH (hola) = "hello"

If you have an idea for an algorithm, can you tell me how to set up an dictionary and implement an search algorithm? It seems like I have to use an divide and conquer but I am not sure how. Thanks.

The side of dictionary should be singular, which means I cannot build both English-Spanish and Spanish-English dictionary.

YoYoYOOOO
  • 3
  • 2
  • you can have a look at bidirectional dictionary by Jon Skeet. https://stackoverflow.com/questions/255341/getting-key-of-value-of-a-generic-dictionary#255630 – Gauravsa Sep 21 '18 at 01:42
  • 1
    Where does the rather arbitrary limitation on not having two dictionaries come from? That makes things rather difficult so you should examine its absolute necessity. In other words, what's the actual *reason* for it? – paxdiablo Sep 21 '18 at 01:51
  • still need another container to achieve less than O(n) complexity.. – Gauravsa Sep 21 '18 at 04:13
  • https://codereview.stackexchange.com/questions/132900/concurrent-bidirectional-dictionary – Gauravsa Sep 21 '18 at 05:07

2 Answers2

0

Any balanced tree, or sorted array, or hashtable data structure will give you better than O(n) when searching.

For the bidirectionality, you can just have two data structures, one for English-Español the other for Español-English. That doesn't necessarily mean two complete dictionaries, just that you need a search index of some description for either direction.

However, since you appear to have a one-to-one mapping of words, you can just maintain one dictionary as persistent and build the reverse one at run time.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • Sorry I forgot to add the instruction, I cannot make two dictionaries. Just one is allowed. – YoYoYOOOO Sep 21 '18 at 01:42
  • 1
    @YoYoYOOOO, regardless of how you do it, you will need two "dictionaries", that's the only way to get sub-O(n) performance in both directions. Note that I've quoted that word since you don't need to *maintain* both dictionaries, one can be built from the other. – paxdiablo Sep 21 '18 at 01:49
0

You can have two dictionary as the search time will remain constant. However, if you still wish to have two way dictionary, then Jon Skeet's version is here:

Getting key of value of a generic Dictionary?

Gauravsa
  • 6,330
  • 2
  • 21
  • 30