How to uniquely identify a set of strings using an integer

Question

Here my problem statement:

• I have a set of strings that match a regular expression. let's say it matches [A-Z][0-9]{3} (i.e. 1 letter and 3 digits).
• I can have any number of strings between 1 and 30. For example I could have:
  • {A123}
  • {A123, B456}
  • {Z789, D752, E147, ..., Q665}
  • ...
• I need to generate an integer (actually I can use 256 bits) that would be unique for any set of strings regardless of the number of elements (although the number of elements could be used to generate the integer)

What sort of algorithm could I use?

My first idea would be to convert my strings to number and then do operations (I thought of hash functions) on them but I am not sure what formula would be give me could results.

Any suggestion?

Answer 1

You have 2^333 possible input sets ((26 * 10^3) choose 30).

This means you would need a 333 bit wide integer to represent all possibilities. You only have a maximum of 256 bits, so there will be collisions.

This is a typical application for a hash function. There are hashes for various purposes, so it's important to select the right type:

• A simple hash function for use in bucket based data structures (dictionaries) must be fast. Collisions are not only tolerated but wanted. The hash's size (in bits) usually is small. Due to collisions this type of hash is not suited for your purpose.

• A checksum tries to avoid collisions and is reasonably fast. If it's large enough this might be enough for your case.

• Cryptographic hashes have the characteristic that it's not possible (or very hard) to find a collision (even when both input and hash are known). Also they are not invertible (from the hash it's not possible to find the input). These are usually computationally expensive and overkill for your use case.

• Hashes to uniquely identify arbitrary inputs, like CityHash and SpookyHash are designed for fast hashing and collision free identification.

SpookyHash seems like a good candidate for your use case. It's 128 bits wide, which means that you need 2^64 differing inputs to get a 50% chance of a single collision.

It's also fast: three bytes per cycle is orders of magnitude faster than md5 or sha1. SpookyHash is available in the public domain (see link above).

To apply any hash on your use case you could convert the items in your list to numbers, but it seems easier to just feed them as strings. You have to settle for an encoding in this case (ASCII would do).

I'm usually using UTF8 or so, when I18N is an issue. Then it's sometimes important to care for canonicalization. But this does not apply to your simple use case.

Answer 2

A hash is not going to work, since it could produce collisions. Every significant input bit must be mapped to an output bit.

For the letter, you have 90 - 65 = 25 different values, so you can use 5 bits to represent the letter.

The 3-digit number has 1000 different values, so you need 10 bits for this.

If you combine these bits, you have a unique mapping from the input to a 15-bit number.

---

This approach is simple, but it could wastes some bits. If the output must be as short as possible, you could map as follows:

output = (L - 'A')*1000 + N

where L is the letter value, 'A' is the value of the letter A, N is the 3-digit number. Then you can use as few bits as are necessary to represent the complete range of output, which is 25*1000 - 1 = 24999. Here it is 15 bits again, so the simple approach does not waste space.

---

If there are fewer output bits than input bits, a hash function is needed. I would strongly recommend to map the strings to binary data like above, and use a simple function to map the input to the output, for this reason:

A general-purpose hash function can not differentiate the input bits, because it knows nothing about their meaning.
For 256 output bits, after hashing 5.7e38 values, the chance of a collision is 75%. Source: Birthday Attack.

5.7e38 seems huge, but it corresponds to only 129 bits (2^129 = 6.8e38). In this case it means that there is a chance of over 75% that there is a pair of strings with 9 (129/15 = 8.6) elements that collide.

On the other hand, if you use a very simple mapping function like:

• truncate the input to 256 bits (use the first 17 elements of 15 bits each)
• make a 256 bit xor value of all the 15-bit elements

you can guaratee there is no collision between any two strings with at most 17 elements.

The hash functions wich are optimized for generating unique IDs likely perform better than a general-purpose hash as compared here, but I would doubt that they can guarantee collision-free hashing of all 256-bit values.

Conclusion: If most of the input strings have less than 17 elements, I would prefer this to a hash.