Efficient mapping from 2^24 values to a 2^7 index

I have a data structure that stores amongst others a 24-bit wide value. I have a lot of these objects.

To minimize storage cost, I calculated the 2^7 most important values out of the 2^24 possible values and stored them in a static array. Thus I only have to save a 7-bit index to that array in my data structure.

The problem is: I get these 24-bit values and I have to convert them to my 7-bit index on the fly (no preprocessing possible). The computation is basically a search which one out of 2^7 values fits best. Obviously, this tak开发者_开发知识库es some time for a big number of objects.

An obvious solution would be to create a simple mapping array of bytes with the length 2^24. But this would take 16 MB of RAM. Too much.

One observation of the 16 MB array: On average 31 consecutive values are the same. Unfortunately there are also a number of consecutive values that are different.

How would you implement this conversion from a 24-bit value to a 7-bit index saving as much CPU and memory as possible?

Hard to say without knowing what the definition is of "best fit". Perhaps a kd-tree would allow a suitable search based on proximity by some metric or other, so that you quickly rule out most candidates, and only have to actually test a few of the 2^7 to see which is best?

This sounds similar to the problem that an image processor has when reducing to a smaller colour palette. I don't actually know what algorithms/structures are used for that, but I'm sure they're look-up-able, and might help.

As an idea... Up the index table to 8 bits, then xor all 3 bytes of the 24 bit word into it. then your table would consist of this 8 bit hash value, plus the index back to the original 24 bit value.

Since your data is RGB like, a more sophisticated hashing method may be needed.

 bit24var        & 0x000f gives you the right hand most char.
(bit24var >> 8)  & 0x000f gives you the one beside it.
(bit24var >> 16) & 0x000f gives you the one beside that.

Yes, you are thinking correctly. It is quite likely that one or more of the 24 bit values will hash to the same index, due to the pigeon hole principal.

One method of resolving a hash clash is to use some sort of chaining.

Another idea would be to put your important values is a different array, then simply search it first. If you don't find an acceptable answer there, then you can, shudder, search the larger array.

How many 2^24 haves do you have? Can you sort these values and count them by counting the number of consecutive values.

Since you already know which of the 2^24 values you need to keep (i.e. the 2^7 values you have determined to be important), we can simply just filter incoming data and assign a value, starting from 0 and up to 2^7-1, to these values as we encounter them. Of course, we would need some way of keeping track of which of the important values we have already seen and assigned a label in [0,2^7) already. For that we can use some sort of tree or hashtable based dictionary implementation (e.g. std::map in C++, HashMap or TreeMap in Java, or dict in Python).

The code might look something like this (I'm using a much smaller range of values):

import random

def make_mapping(data, important):
    mapping=dict() # dictionary to hold the final mapping
    next_index=0 # the next free label that can be assigned to an incoming value
    for elem in data:
        if elem in important: #check that the element is important
            if elem not in mapping: # check that this element hasn't been assigned a label yet
                mapping[elem]=next_index
                next_index+=1 # this label is assigned, the next new important value will get the next label 
    return mapping

if __name__=='__main__':
    important_values=[1,5,200000,6,24,33]
    data=range(0,300000)
    random.shuffle(data)
    answer=make_mapping(data,important_values)
    print answer

You can make the search much faster by using hash/tree based set data structure for the set of important values. That would make the entire procedure O(n*log(k)) (or O(n) if its is a hashtable) where n is the size of input and k is the set of important values.

Another idea is to represent the 24BitValue array in a bit map. A nice unsigned char can hold 8 bits, so one would need 2^16 array elements. Thats 65536. If the corresponding bit is set, then you know that that specific 24BitValue is present in the array, and needs to be checked.

One would need an iterator, to walk through the array and find the next set bit. Some machines actually provide a "find first bit" operation in their instruction set.

Good luck on your quest. Let us know how things turn out.

Evil.