Many-to-one mapping (creating equivalence classes)

Question

I have a project of converting one database to another. One of the original database columns defines the row's category. This column should be mapped to a new category in the new database.

For example, let's assume the original categories are:parrot, spam, cheese_shop, Cleese, Gilliam, Palin

Now that's a little verbose for me, And I want to have these rows categorized as sketch, actor - That is, define all the sketches and all the actors as two equivalence classes.

>>> monty={'parrot':'sketch', 'spam':'sketch', 'cheese_shop':'sketch', 
'Cleese':'actor', 'Gilliam':'actor', 'Palin':'actor'}
>>> monty
{'Gilliam': 'actor', 'Cleese': 'actor', 'parrot': 'sketch', 'spam': 'sketch', 
'Palin': 'actor', 'cheese_shop': 'sketch'}

That's quite awkward- I would prefer having something like:

monty={ ('parrot','spam','cheese_shop'): 'sketch', 
        ('Cleese', 'Gilliam', 'Palin') : 'actors'}

But this, of course, sets the entire tuple as a key:

>>> monty['parrot']

Traceback (most recent call last):
  File "<pyshell#29>", line 1, in <module>
    monty['parrot']
KeyError: 'parrot'

Any ideas how to create an elegant many-to-one dictionary in Python?

Check out this elegant [answer](http://stackoverflow.com/a/11105962/355230) to a similar question. — martineau, Jun 24 '12 at 01:54

score 18 · Accepted Answer · answered Dec 17 '09 at 11:32

18

It seems to me that you have two concerns. First, how do you express your mapping originally, that is, how do you type the mapping into your new_mapping.py file. Second, how does the mapping work during the re-mapping process. There's no reason for these two representations to be the same.

Start with the mapping you like:

monty = { 
    ('parrot','spam','cheese_shop'): 'sketch', 
    ('Cleese', 'Gilliam', 'Palin') : 'actors',
}

then convert it into the mapping you need:

working_monty = {}
for k, v in monty.items():
    for key in k:
        working_monty[key] = v

producing:

{'Gilliam': 'actors', 'Cleese': 'actors', 'parrot': 'sketch', 'spam': 'sketch', 'Palin': 'actors', 'cheese_shop': 'sketch'}

then use working_monty to do the work.

answered Dec 17 '09 at 11:32

Ned Batchelder

364,293
75
561
662

4

+1 Thanks a lot. I assume there's no python native type for this job; Do you think there should be one? – Adam Matan Dec 17 '09 at 11:38
can't we have some reference as the value in the (key, value) pair rather than storing the actual string? Since the no. of keys are significantly larger than the no. of values, this would save a lot of space. Is there a way to do this? – ishan3243 Mar 25 '14 at 18:29
Old question, but regarding @ishan3243's observation, I am pretty sure Python will intern these strings, since they are being defined explicitly as constants. Furthermore, even if the values are read in at run-time, because of how this code loops and assigns the same variable to each index, it should cause string interning. – Spencer D Dec 30 '18 at 07:11

score 5 · Answer 2 · answered Dec 17 '09 at 11:28

You could override dict's indexer, but perhaps the following simpler solution would be better:

>>> assoc_list = ( (('parrot','spam','cheese_shop'), 'sketch'), (('Cleese', 'Gilliam', 'Palin'), 'actors') )
>>> equiv_dict = dict()
>>> for keys, value in assoc_list:
    for key in keys:
        equiv_dict[key] = value


>>> equiv_dict['parrot']
'sketch'
>>> equiv_dict['spam']
'sketch'

(Perhaps the nested for loop can be compressed an impressive one-liner, but this works and is readable.)

Not for the faint of heart: equiv_dict = dict( sum([[(k, v) for k in ks] for (ks, v) in assoc_list], []) ) — Vladimir Gritsenko, Dec 17 '09 at 11:37

score 3 · Answer 3 · answered Dec 17 '09 at 11:20

3

>>> monty={ ('parrot','spam','cheese_shop'): 'sketch', 
        ('Cleese', 'Gilliam', 'Palin') : 'actors'}

>>> item=lambda x:[z for y,z in monty.items() if x in y][0]
>>>
>>> item("parrot")
'sketch'
>>> item("Cleese")
'actors'

But let me tell you, It will be slow than normal one to one dictionary.

answered Dec 17 '09 at 11:20

YOU

120,166
34
186
219

Slow-ish, but on the plus side doesn't require a persistent secondary data structure. Could be sped up a certain degree by not being written as a lambda and using a list comprehension. – martineau Jun 24 '12 at 01:52

score 2 · Answer 4 · answered Jul 24 '16 at 02:27

If you want to have multiple keys pointing to the same value, i.e.

m_dictionary{('k1', 'k2', 'k3', 'k4'):1, ('k5', 'k6'):2} and access them as,

`print(m_dictionary['k1'])` ==> `1`.

Check this multi dictionary python module multi_key_dict. Install and Import it. https://pypi.python.org/pypi/multi_key_dict

Many-to-one mapping (creating equivalence classes)

4 Answers4

Linked