Come si crea un checksum paragonabile di una sequenza numerica?

Question

Come si crea un checksum paragonabile di una sequenza numerica?

#1 da (2 voti)

1

Scusa se il titolo è confuso, ma ecco un esempio per illustrare ciò che sto cercando di realizzare.

Vorrei creare un "checksum" o un raggruppamento di ID di sequenze di numeri simili, in modo che quando si confronta una sequenza con un'altra, si possa vedere se sono simili o meno. Le sequenze "simili" qui sono sequenze che vengono spostate a destra o a sinistra, ma mantengono il loro schema. Questa è una sequenza simile:

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

Come puoi vedere in ogni serie di numeri, la sequenza viene spostata a sinistra. Quindi in questo esempio:

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

Ma

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

Un altro modo per dirlo è:

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

Vorrei che la funzione sumof () crei un valore alfanumerico della somma / somma di controllo della sequenza (preferibilmente un numero intero, ma può contenere anche caratteri). Come gli hash, voglio che questo valore sia abbastanza robusto da prevenire qualsiasi collisione con sequenze non corrispondenti.

Spero di averlo descritto abbastanza bene. Se hai bisogno di chiarimenti, chiedi nei commenti.

math sequence

posta green sammich 18.05.2018 - 00:28

fonte

1 risposta

Leggi altre domande sui tag math sequence

Come modellare le mie classi child senza violare i principi OO Come dichiarare la necessità del plug-in jquery per la pubblicazione di polyfill (e specialmente per gli utenti di webpack)?

score 2 · Answer 1

Ricava una forma canonica (virtuale) della sequenza.

/**
  * 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;
}

Potrebbe benissimo essere che un altro ordine dia un risultato migliore, ad esempio in ogni passo del ciclo che confronta le somme fino all'indice, e in un livello decrescente, in modo che le montagne di dati con valori alti vicini vieni prima.

Quindi implementa un checksum progressivo sulla sequenza ciclica:

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);

Il checksum sopra è la parte problematica. Mascherando i bit, lo stesso CRC può contenere anche cicli completamente diversi.

I checksum 0x12345678 e 0x12A45678 potrebbero essere simili, hanno solo 1 valore diverso. A causa dello spostamento di 4 bit, un confronto di esagono sarebbe facile.

Esistono numerose varianti immaginabili e probabilmente necessarie anche per il tuo scenario. Eppure ci sono alcuni aspetti interessanti menzionati qui.

La somma associativa perderebbe le informazioni sugli ordini, ma sarebbe adatta anche a loro, ad esempio la somma di tutti gli elementi divisi per dire 4.