How do I create a comparable checksum of a number sequence?

Question

Sorry if the title is confusing, but here's an example to illustrate what I'm trying to accomplish.

I would like to create a 'checksum' or ID grouping of similar number sequences, so that when you compare one sequence to another, it can see if they are similar or not. 'Similar' sequences here are sequences that are shifted to the right or left, but maintain their pattern. This is a similar sequence:

[ 1, 4, 5, 6 ]
[ 4, 5, 6, 1 ]
[ 5, 6, 1, 4 ]
[ 6, 1, 4, 5 ]

As you can see in each set of numbers the sequence is shifted to the left. So in this example:

sumof([ 1, 4, 5, 6 ]) == sumof([ 4, 5, 6, 1 ]);

But

sumof([ 1, 4, 4, 6 ]) != sumof([ 4, 5, 6, 1 ]);

Another way to put it is:

$checksum == sumof([ 1, 4, 5, 6 ]) == sumof([ 4, 5, 6, 1 ]) == sumof([ 5, 6, 1, 4 ]) == sumof([ 6, 1, 4, 5 ])

I would like the function sumof() to create an alphanumeric value of the sum/checksum of the sequence (preferably an integer, but can contain characters too). Like hashes, I want this value to be robust enough to prevent any collisions with non-matching sequences.

I hope I've described this well enough. If you need any clarification please ask in the comments.

Answer 1

Derive a canonical (virtual) form of the sequence.

/**
  * Do a lexical comparison and yield the start index of the
  * lexically first cyclic sequence.
  */
int minCycleStartIndex(int[] seq) {
   int n = seq.length;
   int minI = 0;
   for (int i = 1; i < n; ++i) {
       for (int j = 0; j < n; ++j) {
           int c = seq[(minI + j) % n] - seq[(i + j) % n];
           if (c != 0) {
               if (c > 0) {
                   minI = i;
               }
               break;
           }
       }
   }
   return minI;
}

It might very well be that an other order gives a better result, for instance in every loop step comparing the sums upto the index, and in decreasing level, so that data mountains with neighbouring high values come first.

Then implement a progressive checksum on the cyclic sequence:

int cyclicChecksum(int[] seq, int startI) {
   int checksum = 0;
   for (int i = 0; i < n; ++i) {
       int x = seq[(startI + i) % n];
       x /= 4; // Support similarity by lowering the resolution.
       //checksum = (checksum << 2) + x;
       checksum = (checksum << 4) | (x & 0xF);
   }
   return checksum;
}

int minI = minCycleStartIndex(seq);
int crc = cyclicChecksum(seq, minI);

The checksum above is the problematic part. By masking bits out, the same CRC may also contain wildly different cycles.

Checksums 0x12345678 and 0x12A45678 could be similar, have just 1 different value. Because of the 4 bit shift, a hex comparison would be easy.

There are numerous variations imaginable, and probably even needed for your scenario. Yet there are some interesting aspects mentioned here.

By the way associative summing would loose the ordering info, but would fit too, for instance the sum of all elements divided by say 4.