Prime casuali e ricerca di sottostringhe Rabin Karp

Aug 17 2020

Sto leggendo l'algoritmo Rabin-Karb di Sedgewick. Il libro dice:

Usiamo un Q primo casuale che prende un valore il più grande possibile evitando l'overflow

Alla prima lettura non ho notato il significato di casuale e quando ho visto che nel codice longviene usato a i miei primi pensieri sono stati:
a) Usa il setaccio di Eratosthene per trovare un grande numero primo che si adatta a long
o
b) cerca da un elenco di innesca qualsiasi numero primo abbastanza grande che è maggiore di inte lo usa come costante.

Ma poi il resto della spiegazione dice:

Useremo un longvalore maggiore di 10^20rendere la probabilità che una collisione avvenga minore di10^-20

Questa parte mi ha confuso dal momento che longnon può adattarsi per 10^20non parlare di un valore maggiore di quello. Quindi, quando ho controllato il calcolo del numero primo, il libro rimanda a un esercizio che ha solo il seguente suggerimento:

Un numero casuale di n cifre è primo con probabilità proporzionale a 1 / n

Cosa significa?

Quindi, fondamentalmente, quello che non ottengo è:
a) qual è il significato di usare un numero primo casuale ? Perché non possiamo semplicemente calcolarlo in anticipo e usarlo come costante?
b) perché è 10^20menzionato poiché è fuori portata long?
c) In che modo questo suggerimento è utile? Cosa significa esattamente?

Risposte

3 DavidEisenstat Aug 17 2020 at 14:09

Ancora una volta , Sedgewick ha cercato di semplificare un algoritmo e ha sbagliato leggermente i dettagli. Primo, come osservi, 10 20 non può essere rappresentato in 64 bit. Anche prendendo un numero primo vicino a 2 63-1 , tuttavia, probabilmente vorresti un po 'di spazio per moltiplicare il modo normale senza traboccare in modo che il modulo successivo sia corretto. La risposta utilizza un numero primo a 31 bit, che lo rende facile ma offre solo probabilità di collisione nell'intervallo 10 −9 .

La versione originale utilizza le impronte digitali di Rabin e un polinomio casuale irriducibile su 𝔽 2 [x], che dal punto di vista della teoria algebrica dei numeri si comporta in modo molto simile a un numero primo casuale sugli interi. Se scegliamo che il polinomio sia di grado 32 o 64, le impronte digitali si adattano perfettamente a una parola del computer della lunghezza appropriata e l'addizione e la sottrazione polinomiale funzionano entrambe in XOR bit per bit, quindi non c'è overflow.

Ora, Presumibilmente Sedgewick non voleva spiegare come funzionano gli anelli polinomiali. Bene. Se dovessi implementare questo approccio, in pratica, mi piacerebbe scegliere un primo p vicino al massimo che era facile da mod per le istruzioni a basso costo (Io ho un debole per 2 il 31 - 2 27 + 1 ; EDIT in realtà 2 il 31 - 1 funziona anche meglio dato che non abbiamo bisogno di un numero primo liscio qui) e quindi scegli un numero casuale in [1, p − 1] per valutare i polinomi a (questo è il modo in cui Wikipedia lo spiega). Il motivo per cui abbiamo bisogno di un po 'di casualità è che altrimenti l'avversario ignaro potrebbe scegliere un input che sarebbe garantito per avere molte collisioni di hash, il che degraderebbe gravemente il tempo di esecuzione.

Sedgewick ha voluto seguire l'originale un po 'più da vicino di quello, tuttavia, che in sostanza valuta i polinomi a un valore fisso di x (letteralmente x nella versione originale che utilizza anelli polinomiali). Ha bisogno di un numero primo casuale in modo che l'avversario ignaro non possa progettare collisioni. Vagliare numeri abbastanza grandi è abbastanza inefficiente, quindi si rivolge al Teorema dei numeri primi (che è la matematica dietro il suo suggerimento, ma vale solo asintoticamente, il che crea un grande pasticcio teoricamente) e un veloce test di primalità (che può essere probabilistico; il i casi in cui fallisce non influenzeranno la correttezza dell'algoritmo e sono abbastanza rari da non influenzare il tempo di esecuzione previsto).

Non sono sicuro di come dimostri un vincolo formale alla probabilità di collisione. La mia idea approssimativa è fondamentalmente, mostrare che ci sono abbastanza numeri primi nella finestra di interesse, usare il Teorema cinese del resto per dimostrare che è impossibile che ci sia una collisione per troppi numeri primi contemporaneamente, concludere che la probabilità di collisione è limitata dal probabilità di scegliere un numero primo cattivo, che è basso. Ma il teorema dei numeri primi vale solo in modo asintotico, quindi dobbiamo fare affidamento su esperimenti al computer riguardanti la densità dei numeri primi negli intervalli di parole della macchina. Non buono.