Таблицы дактилоскопии Рабина

Последние пару дней я изучал дактилоскопию Рабина. Хотя общая идея достаточно проста, у меня возникают серьезные проблемы с пониманием реализаций, циркулирующих в сети. В частности, все они, по-видимому, взяты из оригинальной документа LBFS, а именно из librabinpoly скользящее окно определяется как :

33 static u_int64_t slide8(RabinPoly *rp, unsigned char m) {                       
   34         rp->circbuf_pos++;                                                      
   35         if (rp->circbuf_pos >= rp->window_size) {                               
   36                 rp->circbuf_pos = 0;                                            
   37         }                                                                       
   38         unsigned char om = rp->circbuf[rp->circbuf_pos];                        
   39         rp->circbuf[rp->circbuf_pos] = m;                                       
   40         return rp->fingerprint = append8 (rp, rp->fingerprint ^ rp->U[om], m);  
   41 }                                                                               
   42                                                                                 
   43 static u_int64_t append8(RabinPoly *rp, u_int64_t p, unsigned char m) {         
   44         return ((p << 8) | m) ^ rp->T[p >> rp->shift];                          
   45 }

Где таблицы U/T генерируются из начального полинома. Я не видел ни в одной из статей, касающихся снятия отпечатков пальцев Рабина, обсуждения использования этих двух таблиц и операций XOR. Я чувствую, что это как-то связано с арифметикой по модулю, но я не совсем уверен. исходный код Git также использует отпечатки пальцев Рабина, но вместо получения таблицы динамически у них есть набор заранее вычисленных. Итак, мой вопрос: чего именно достигают эти операции Xor, и код обычно выглядит совершенно иначе, чем «канонический» объяснение алгоритма


c algorithm math fingerprinting rabin-karp
person lrd dsk    schedule 12.08.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

В каноническом объяснении используется скользящий хеш, который не является отпечатком Рабина. Хотя очень похоже. Не вдаваясь слишком глубоко в дебри абстрактной алгебры, скажем, что идея, стоящая за обоими, состоит в том, чтобы вычислить полином, полученный из сообщения в конкретном кольцо, которое имеет 0, 1, сложение, вычитание, умножение, но не деление (целые числа по модулю m для канонического объяснения; GF(2k) для отпечатков пальцев Рабина, то есть многочленов с коэффициентами по модулю 2 по модулю неприводимого многочлена степени k) .

Простейшее кольцо - это целые числа по модулю 2, которое имеет 0, 1 и определяет

+  0 1        -  0 1        *  0 1
------        ------        ------
0  0 1        0  0 1        0  0 0
1  1 0        1  1 0        0  0 1  .

Происходит очень интересная вещь: плюс и минус имеют одинаковое определение, и оба эквивалентны XOR. Используя компьютерное слово для представления многочлена с коэффициентами по модулю 2, мы можем складывать и вычитать многочлены с помощью побитового XOR. Вот почему XOR появляется в rp->fingerprint ^ rp->U[om]: мы вычитаем термин из байта, который только что вышел из окна, используя таблицу U, поскольку для этого термина есть только 256 возможностей.

Другое использование XOR, ((p << 8) | m) ^ rp->T[p >> rp->shift], в выражении, которое модифицируется неприводимым полиномом, то есть эквивалентно моддингу m в каноническом объяснении. Если бы мы сделали это с помощью полиномиального длинного деления (как предположительно вычисляется таблица T в первую очередь), мы бы заметили, что члены, вычитаемые (в кольце) из делимого, определяются только старшими битами ( p >> rp->shift). Немного алгебраических манипуляций позже, мы можем кэшировать сумму (в кольце) и вычесть ее (в кольце, так что побитовое XOR) из делимого (((p << 8) | m)).

Для полноты отметим, что p << 8 эквивалентно полиномиальному умножению на x8.

person David Eisenstat    schedule 12.08.2020