It's not about primes, it's about big numbers, with distributions 1, 1000, 10000000, the first char will contribute to the LSBs, the second char to more significant bits and so on. The higher the ratio between those numbers, the more distance between the bit your chars can change. You see collisions when there is an overlap. For example with 26 values and weights of 1, 8, and 64, each char will directly affect a range of 8 bits, and each range will be at a distance of 3 bits from the next, with an overlap of 5. But with weights 1, 32 and 1024, you'll get no overlap in the range of bits each char can affect (so no carry).

Actually the perfect list of weights in your example with chars a..z is 1, 26, 26^2, 26^3 .... But this will not fit into your integers as soon as 26^L > 2^64 with L the maximum length of your string.

The general best distribution (no collisions, ignoring the limitation of 64 bits) is the list of K^N with K the number of possible characters. And I'm pretty sure the list of K^(N/C) should give you an average collision close to C (C strings for each value), but would require an integer with C times less bits.

Actually the perfect list of weights in your example with chars a..z is 1, 26, 26^2, 26^3 .... But this will not fit into your integers as soon as 26^L > 2^64 with L the maximum length of your string.

Yes. That is what I was attempting to describe in the OP when I said: "I could calculate the positional power of the maximum number of characters and generate a guaranteed unique number, but the number of unique items in my collection is ~2e5, the subsets can be hundreds of elements each, so the signature values would rapidly become so huge as to be unmanageable.".

Using this schema on simple character data with an alphabet of just 26 chars means I would run over the limit of my 64-bit ints after only 13 characters.

But as I said above, in a typical example of the type of problem I am trying to cater for, the 'alphabet' could be as large as 200,000 or even larger; and size of my subsets (aka. length of the strings), is frequently multiple hundreds or even low thousands. As such, there can be no "perfect set of weights".

However, those numbers do hide some good news. With numbers this large, the number of combinations is ludicrously large, so even if I need to signature hundreds of billions of them, I will still only be processing a tiny, miniscule percentage of the total, so the likelihood that I would encounter a collision without it being an exact duplicate -- assuming even distributions -- is very slim indeed.

To try and put some flesh on that assertion. Let's say my 'alphabet' is 200,000 (N) unique things; and my subsets each consist of some combination of 1000 (K) of those things, then the formula for the total number of combinations is (N+K-1)! / (K! * (N-K)!), which for those example numbers comes out at: 1.414e8029

So even if I need to process one trillion of those, that's still only 0.00000000...{8000 zeros}...00000007%. False collisions are unlikely.

Of course, totally even distributions in real world data are few and far between, but still it means that using a less than perfect signature mechanism is very likely to detect actual duplicates and rarely detect false ones.

It's not about primes,

Perhaps not mathematically, but practically it is. In part because I'm making it so. It is easy to demonstrate (with small subsets) that if I used powers of 2 weights, the incidence of collisions is vastly reduced:

C:\test>weightedPrimeSumProduct -K=6 -M=16
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131
+072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432
736000  Ave. collisions: 7.091558; Max. collisions:79.000000
[download]

But that limits me to 'alphabets' of 63 chars at most; and practically to far less once sum of products plays out.

I might consider trying to stretch the alphabet by assigning each power of two to two or more items in my collection, but that causes a vary rapid climb in the false positives:

C:\test>weightedPrimeSumProduct -K=6 -M=16
1 1 2 2 4 4 8 8 16 16 32 32 64 64 128 128 256 256 512 512 1024 1024 20
+48 2048 4096 4096
736000  Ave. collisions: 81.936457; Max. collisions:671.000000

C:\test>weightedPrimeSumProduct -K=6 -M=16
1 1 1 2 2 2 4 4 4 8 8 8 16 16 16 32 32 32 64 64 64 128 128 128 256 256
736000  Ave. collisions: 414.806197; Max. collisions:2931.000000
[download]

Almost back to monotonic sequential weightings. And this is where the idea of using primes to expand the alphabet size that could be handled whilst reducing the chances of arithmetic collisions. The sum of multiples of unique primes is less likely to collide. And by using every second, third or fourth prime, the collisions reduce further. There is no real surprise in any of that.

What did surprise me was the effect that shuffling the primes had on reducing the collision rates. And that bring me back to my questions in the OP regarding how to determine the best ordering of the chosen set of primes.

I am quite convinced that a GA is the only game in town for arriving at a good, if not necessarily optimal ordering; but I'm still trying to wrap my head around a suitable mutation algorithm to allow the GA to arrive at a good solution within a reasonable time frame.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.

In the absence of evidence, opinion is indistinguishable from prejudice.
i

With ~2e5, you'll have to do something beside the simple weighted sum (like a modulus) if you want to avoid the bell shape, which tends to be a thing with the sum of independant variables (with identical probability distribution - not your case with the weights - you'd actually get close to a gaussian distribution, a perfect bell)

The sum of multiples of unique primes is less likely to collide.

That's not a property of primes I know. The reason primes gives you better result is because their progression is close enough to an exponential one.

What did surprise me was the effect that shuffling the primes had on reducing the collision rates.

I actually believed this couldn't be true until I realized you are not working with fixed length input. If you were, you'd just have to apply the same permutation to the string as the one applied to the primes to obtain the same result:

 a  b  c  d
 3  7 17 29
[download]

Is the same as:

 b  d  a  c
 7 29  3  17
[download]

and so on. But with variable length input, the coefficients on the left are more likely to be used. So you obtain better result by having coefficients that are more distant in the front and the "less efficient" ones at the end. You can start by 1, and then add your coefficient by maximazing the ratio (the distance between the bits two characters will affect is log(K1)-log(K2), so an increasing function of (K1/K2)). Taking the powers of two up to 2^16 that could be: 2^0, 2^16, 2^8, 2^12, 2^4, 2^10, 2^6, 2^14, 2^2, 2^15, 2^1, 2^13, 2^3, 2^11, 2^5, 2^9, 2^7 The biggest ratio you can get with those numbers is of course 2^16. Then you take number that's halfway (in terms of ratio) between: 2^16. 2^12 and 2^4 both have a minimum ratio with one of the previous number of 2^4 (I put 2^12 first because it's the further away from 2^0, which is the coefficient with the highest probability to be used). Then 2^10, 2^6, 2^14 and 2^2. All the remaining order introduce two new 2^0 ratios.

I hadn't been able to figure out why the shuffling helped you, either. Before Eily's post, I was going to lean down the road of suggesting comparing your monotonically increasing ramp of weights with a monotonically decreasing ramp of weights, and see whether collisions were affected. And then recommend trying a list of weights which was half ramp + half random (actually, three sets of half-ramp: #1:first half increasing, #2:middle half increasing (quarter random on each side), #3: final half increasing. (And compare all those to one of your fully-shuffled weight setes.) If you saw that the down-ramp and the the half-ramps all had worse collisions than your shuffle, then I would suggest trying a mutator that tried to get rid of rampy-segments: if you found a sequence of weights that were strictly increasing (or generally increasing, with occasional excursions), I would suggest having the mutator pick new random primes or just re-shuffle the rampy section.

Also, I have found that histograms can hide some critical information. With your ordered set of 736000 combinations from the first example, you might want to comapre the time-series of the generated signatures -- probably with the multiple weight lists: ramp up, ramp down, 3 half ramps, and one or two completely random weights, to see if any patterns jump out and give you a hint for what your mutator could do.

Finally, as a last thought: as Eily said, sums of primes don't approach uniqueness. However, products of primes do. I know that purely multiplying primes is unique. I spent some time while I couldn't sleep last night trying to come up with a reasonable way to use that, since you'd obviously quickly overrun your 64bit integer with a product of K=1000 primes. :-) I think I came up with something (after looking up a few primey facts today) that would be a product of two primes.

• To fit in 64bits, each prime would have to be less than 2**32. The biggest 32bit prime number ⁽¹⁾ is 4_294_967_291, which is the 203_280_221^{st (2)} prime.
• That number of multiplyable-primes is bigger than your expected N≥200_000, so in theory, we could assign two primes (or 1000) to each of your N things, and multiple two primes together.
• If you didn't want to just start doling out primes randomly, you could do something like
  • @prime[1 .. 200_000] = import_from_list_of_first_million_primes()
  • generate two 1000-weight lists @wa and @wb, using your randomly shuffled primes
  • for each $comb, generate two sigs $sa and $sb in your sig function
    • even if one of your sigs had a collsion, the chances that both collide at the same time are significanlty smaller
    • return $product = $prime[$sa] * $prime[$sb]

Is there some reason you don't want to use an existing algorithm like CRC or MD5?

In order to reduce the collision rate, it will help if you spread out the signature values over a larger output set. To keep from overflowing, you can choose a big modulus $M.

It's common to choose $M to be a power of two, so "% $M" becomes "& ($M - 1)". Choosing $M prime has some mathematical advantages, but as long as none of the @P values has any common factors with $M it works ok. If you set $P[$_] to $K**$_ for some $K, you won't even have to store @P.

Is there some reason you don't want to use an existing algorithm like CRC or MD5?

Yes. Whilst in my examples I'm using strings of letters for simplicity and conciseness; the actual collection could be pretty much anything. Eg. Instead of letters in a word; in might be the existence of and ordering of words in a sentence, or the existence of phrases, regardless of ordering in a document; or literally any other combinatorial subset of attributes of some datasets.

In order to use crc or MD5 for these other kinds of subset collections, it would require two passes: one to encode (say hash lookup mapping) the collection subset into a 'string' digestible by those algorithms; and a second pass over that string to arrive at the signature.

If I can accumulate the signature whilst iterating the first pass, I can save a substantial amount of time. In a previous attempt at a similar problem I came up with an algorithm -- very specific to the data being processed -- that proved to be almost 50 times faster than first stringifying then MD5. With a dataset measured in terabytes, that was a substantial saving.

To keep from overflowing, you can choose a big modulus $M.

That's a good suggestion, but there is a problem with it. With a pure (non-modulo) arithmetic signature, the values tend to group like-near-like in a nearly continuous ordering. It isn't a collating order that anyone would recognise, but similar subsets tend to be collate close to each other and transition gradually from one end of the spectrum to the other.

However, once you start wrapping the signatures back on themselves using modulo arithmetic, that useful artifact of the non-modulo arithmetic disappears. It's not always needed or useful, but if I can avoid it, it might allow a more generic solution with additional useful properties.

It is certainly something for me to keep in mind if another solution doesn't present itself. Thankyou.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.

In the absence of evidence, opinion is indistinguishable from prejudice.

Actually, both CRC and MD5 can be calculated incrementally without having to stringify the entire dataset at once. That's what the MD5 context object is for. I don't know of a CRC module that provides that functionality, but it's easy to implement.

But yeah, coming up with a function that has the "nonrandom" behavior you're looking for is going to be very tricky and data-dependent.