How to create a lookup table with noise in Python?

Question

Say I have a dictionary in Python {1:'a', 100:'b', 1024:'c'}

I want to build a function that can look for not only the exact value of the key, but also approximated values. For instance, the function can return b if the input is 99 or 101.

Could you suggest me some approaches?

Answer 1

If you have a finite range for the values of the keys that is known in advance something like this indexing with tuples

>>> d={(0,2):'a', (99,101):'b', (1023,1025):'c'}

To find the value of a key:

Find 1024.01:

>>> d={(0,2):'a', (99,101):'b', (1023,1025):'c'}
>>> next(v for (k,v) in d.iteritems() if k[0]<=1024.01<=k[1])
'c'

Find 1025.01:

>>> next(v for (k,v) in d.iteritems() if k[0]<=1025.01<=k[1])
# throws an error because key is not found

Answer 2

You can make your own lookup function as follows:

import sys

def lookup(value, dict):
  nearest = sys.maxint
  result = ""

  for k,v in dict.iteritems():
    if abs(value - k) < nearest:
      nearest = abs(value - k)
      result = v

  return result

print lookup(101, {1:'a', 100:'b', 1024:'c'})

Answer 3

You can search for values within 2% range (configurable) with something like this:

data = {1:'a', 100:'b', 1024:'c'}

def get_approx(data, key):
    return [elem[1] for elem in data.iteritems() if elem[0]*0.98 <= key <= elem[0]*1.02]

get_approx(data, 99)  # outputs ['b']

Answer 4

If you want to keep the speed advantage of a dict, you could bin your keys, e.g. by rounding them to the nearest multiple of 10:

>>> data = {1:'a', 100:'b', 1024:'c'}
>>> fuzzy = { ((k + 5) // 10) * 10:v for k,v in data.items() }
>>> fuzzy
{0: 'a', 100: 'b', 1020: 'c'}

When you want to check if a values is close to a key in data, you simply apply the same transformation:

>>> fuzzy.get(((98+5)//10)*10)
'b'
>>> fuzzy.get(((97+5)//10)*10)
'b'
>>> fuzzy.get(((100+5)//10)*10)
'b'
>>> fuzzy.get(((101+5)//10)*10)
'b'
>>> fuzzy.get(((1022+5)//10)*10)
'c'