Реализовать алгоритм рекурсивного хеширования

Question

Допустим, файл A имеет байты:

2
5
8
0
33
90
1
3
200
201
23
12
55

, и у меня есть простой алгоритм хеширования, в котором я храню сумму трех последних последовательных байтов так:

2   
5   
8   - = 8+5+2 = 15
0   
33  
90  - = 90+33+0 = 123
1   
3   
200 - = 204
201 
23  
12  - = 236

такЯ смогу представить файл A как 15, 123, 204, 236

. Допустим, я копирую этот файл на новый компьютер B, и я сделал несколько небольших изменений, и байты файла B:

255 
2   
5   
8   
0   
33  
90  
1   
3   
200 
201 
23  
12
255
255 

"обратите внимание, что разница - это дополнительный байт в начале файла и 2 дополнительных байта в конце, но остальные очень похожи"

, поэтому я могу выполнить тот же алгоритм, чтобы определить, являются ли некоторые частифайл одинаков.Помните, что файл A был представлен хэш-кодами 15, 123, 204, 236, давайте посмотрим, даст ли файл B некоторые из этих хэш-кодов!

, поэтому для файла BI придется делать это каждые 3 последовательных байта

int[] sums; // array where we will hold the sum of the last bytes


255 sums[0]  =          255     
2   sums[1]  =  2+ sums[0]    = 257     
5   sums[2]  =  5+ sums[1]    = 262     
8   sums[3]  =  8+ sums[2]    = 270  hash = sums[3]-sums[0]   = 15   --> MATHES FILE A!
0   sums[4]  =  0+ sums[3]    = 270  hash = sums[4]-sums[1]   = 13
33  sums[5]  =  33+ sums[4]   = 303  hash = sums[5]-sums[2]   = 41
90  sums[6]  =  90+ sums[5]   = 393  hash = sums[6]-sums[3]   = 123  --> MATHES FILE A!
1   sums[7]  =  1+ sums[6]    = 394  hash = sums[7]-sums[4]   = 124
3   sums[8]  =  3+ sums[7]    = 397  hash = sums[8]-sums[5]   = 94
200 sums[9]  =  200+ sums[8]  = 597  hash = sums[9]-sums[6]   = 204  --> MATHES FILE A!
201 sums[10] =  201+ sums[9]  = 798  hash = sums[10]-sums[7]  = 404
23  sums[11] =  23+ sums[10]  = 821  hash = sums[11]-sums[8]  = 424
12  sums[12] =  12+ sums[11]  = 833  hash = sums[12]-sums[9]  = 236  --> MATHES FILE A!
55  sums[13] =  55+ sums[12]  = 888  hash = sums[13]-sums[10] = 90
255 sums[14] =  255+ sums[13] = 1143    hash = sums[14]-sums[11] =  322
255 sums[15] =  255+ sums[14] = 1398    hash = sums[15]-sums[12] =  565

поэтому, глядя на эту таблицу, я знаю, что файл B содержит байты из файла A плюс дополнительные, потому что хэш-коды совпадают.

причина, по которой я показываю этот алгоритм, заключается в том, что он был порядка nДругими словами, я смог вычислить хэш последних 3 последовательных байтов без необходимости перебирать их!

Если у меня есть более сложный алгоритм, такой как выполнение md5 из последних 3 байтов, он будетбыть порядка n ^ 3, потому что, поскольку я перебираю файл BI, у меня должен быть внутренний цикл for, который будет вычислять хэш последних трех байтов.

Поэтому мой вопрос:

Как я могу улучшить алгоритм, сохраняя его порядка n.Это вычисляет хэш только один раз.Если я использую существующий алгоритм хеширования, такой как md5, мне придется поместить внутренний цикл внутри алгоритма, который значительно увеличит порядок алгоритма.

Обратите внимание, что то же самое можно сделать с умножением вместо сложения.но счетчик значительно растет очень быстро.Может быть, я могу комбинировать умножение, сложение и вычитание ...

Редактировать

Кроме того, если я гуглю для:

рекурсивные функции хеширования в граммах

появляется много информации, и я думаю, что эти алгоритмы очень трудно понять ...

Я должен реализовать этот алгоритм для проекта, поэтому я заново изобретаю колесо ... Я знаю, что есть многоалгоритмы там.

Также альтернативным решением, которое я думал, было выполнение того же алгоритма плюс еще один, который является сильным.поэтому файл AI будет выполнять один и тот же алгоритм каждые 3 байта плюс md5 из каждых 3 байтов.Во втором файле я просто выполню второй алгоритм, если первый сбудется ....

Answer 1

Редактировать:

Чем больше я думаю о том, что вы имели в виду под "рекурсивным", тем больше я сомневаюсь, что решение, которое я представил ранее, это то, что вы должны реализовать, чтобы сделать что-нибудь полезное.вероятно, вы хотите реализовать алгоритм хеш-дерева , который является рекурсивной операцией.

Для этого вы хэшируете список, делите список на две части и выполняете рекурсию в эти два подсписка.Завершите работу, если ваш список имеет размер 1 или минимальный требуемый размер хеш-функции, поскольку каждый уровень рекурсии удваивает размер вашего общего хеш-вывода.

Псевдокод:

create-hash-tree(input list, minimum size: default = 1):
  initialize the output list
  hash-sublist(input list, output list, minimum size)
  return output list

hash-sublist(input list, output list, minimum size):
  add sum-based-hash(list) result to output list // easily swap hash styles here
  if size(input list) > minimum size:
    split the list into two halves
    hash-sublist(first half of list, output list, minimum size)
    hash-sublist(second half of list, output list, minimum size)

sum-based-hash(list):
  initialize the running total to 0

  for each item in the list:
    add the current item to the running total

  return the running total

Время выполнения всего этого алгоритма, я думаю, составляет O(hash(m)); m = n * (log(n) + 1), при этом hash(m) обычно представляет собой линейное время.

Пространство памяти выглядит как O(hash * s); s = 2n - 1, хэш обычно имеет постоянный размер.

Обратите внимание, что для C # я бы сделал список вывода List<HashType>, но я бы сделал список ввода IEnumerable<ItemType>, чтобы сэкономить место на диске, и использовал Linq, чтобы быстро "разбить" список без выделениядва новых подсписка.

Оригинал:

Я думаю, вы можете получить это O(n + m) время выполнения;где n - размер списка, m - размер текущего подсчета и n < m (в противном случае все суммы будут равны).

С двухсторонней очередью

Потребление памяти будет соответствовать размеру стека плюс размер m для временного хранилища.

Для этого используйте двустороннюю очередь и промежуточный итог.Вставьте вновь обнаруженные значения в список при добавлении к промежуточной сумме, а когда очередь достигнет размера m, выскользните из списка и вычтите из промежуточной суммы.

Вот некоторый псевдокод:

initialize the running total to 0

for each item in the list:
  add the current item to the running total
  push the current value onto the end of the dequeue
  if dequeue.length > m:
    pop off the front of the dequeue
    subtract the popped value from the running total
  assign the running total to the current sum slot in the list

reset the index to the beginning of the list

while the dequeue isn't empty:
  add the item in the list at the current index to the running total
  pop off the front of the dequeue
  subtract the popped value from the running total
  assign the running total to the current sum slot in the list
  increment the index

Это не рекурсивно, это итеративно.

Запуск этого алгоритма выглядит следующим образом (для m = 3):

value   sum slot   overwritten sum slot
2       2          92
5       7          74
8       15         70
0       15         15
33      46
90      131
1       124
3       127
200     294
201     405
23      427
12      436
55      291

С индексированием

Вы можете удалить очередь и переназначить любые слоты, взяв для начала сумму последних значений m и использовав смещение вашего индекса вместо снятия очереди, например array[i - m].

Это не уменьшит ваше время выполнения, так как вам все равно придется иметь два цикла: один для построения счетчика выполнения, а другой для заполнения всех значений.Но это уменьшит использование вашей памяти только для стекового пространства (эффективно O(1)).

Вот некоторый псевдокод:

initialize the running total to 0

for the last m items in the list:
  add those items to the running total

for each item in the list:
  add the current item to the running total
  subtract the value of the item m slots earlier from the running total
  assign the running total to the current sum slot in the list

m slots earlier - сложная часть.Вы можете разделить это на два цикла:

• Тот, который индексирует в конце списка, минус m, плюс i
• Тот, который индексирует от i минус m

Или вы можете использовать арифметику по модулю, чтобы "обернуть" значение, когда i - m < 0:

int valueToSutract = array[(i - m) % n];

Answer 2

http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm использует обновляемую хеш-функцию, которую он вызывает http://en.wikipedia.org/wiki/Rolling_hash.. Это будет намного легче вычислить, чем MD5 / SHA, и может быть не хуже.

Вы можете доказать некоторые вещи об этом: это многочлен степени d от выбранной константы a. Предположим, что кто-то предоставляет два фрагмента текста, а вы выбираете случайным образом. Какова вероятность столкновения? Хорошо, если значение хеша одинаково, вычитая их, вы получите многочлен с корнем. Поскольку существует не более d корней ненулевого полинома и случайное выбрано a, вероятность не превышает модуль / d, который будет очень мал для больших модулей.

Конечно, MD5 / SHA является безопасным, но см. http://cr.yp.to/mac/poly1305-20050329.pdf для безопасного варианта.

Answer 3

это то, что я получил до сих пор.Я просто пропускаю шаги, которые не должны занимать время, такие как сравнение массива хэшей и открытие файлов для чтения.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RecursiveHashing
{
    static class Utilities
    {

        // used for circular arrays. If my circular array is of size 5 and it's
        // current position is 2 if I shift 3 units to the left I shouls be in index
        // 4 of the array.
        public static int Shift(this int number, int shift, int divisor)
        {
            var tempa = (number + shift) % divisor;
            if (tempa < 0)
                tempa = divisor + tempa;
            return tempa;
        }

    }
    class Program
    {
        const int CHUNCK_SIZE = 4; // split the files in chuncks of 4 bytes

        /* 
         * formula that I will use to compute hash
         * 
         *      formula =  sum(chunck) * (a[c]+1)*(a[c-1]+1)*(a[c-2]+1)*(-1^a[c])
         *      
         *          where:
         *              sum(chunk)  = sum of current chunck
         *              a[c]        = current byte
         *              a[c-1]      = last byte
         *              a[c-2]      = last last byte
         *              -1^a[c]     = eather -1 or +1  
         *              
         *      this formula is efficient because I can get the sum of any current index by keeping trak of the overal sum
         *      thus this algorithm should be of order n
         */

        static void Main(string[] args)
        {
            Part1(); // Missing implementation to open file for reading
            Part2();
        }



        // fist part compute hashes on first file
        static void Part1()
        {
            // pertend file b reads those bytes
            byte[] FileB = new byte[]{2,3,5,8,2,0,1,0,0,0,1,2,4,5,6,7,8,2,3,4,5,6,7,8,11,};

            // create an array where to store the chashes
            // index 0 will use a fast hash algorithm. index 1 will use a more secure hashing algorithm
            Int64[,] hashes = new Int64[(FileB.Length / CHUNCK_SIZE) + 10, 2];


            // used to track on what index of the file we are at
            int counter = 0;
            byte[] current = new byte[CHUNCK_SIZE + 1]; // circual array  needed to remember the last few bytes
            UInt64[] sum = new UInt64[CHUNCK_SIZE + 1]; // circual array  needed to remember the last sums
            int index = 0; // position where in circular array

            int numberOfHashes = 0; // number of hashes created so far


            while (counter < FileB.Length)
            {
                int i = 0;
                for (; i < CHUNCK_SIZE; i++)
                {
                    if (counter == 0)
                    {
                        sum[index] = FileB[counter];
                    }
                    else
                    {
                        sum[index] = FileB[counter] + sum[index.Shift(-1, CHUNCK_SIZE + 1)];
                    }
                    current[index] = FileB[counter];
                    counter++;

                    if (counter % CHUNCK_SIZE == 0 || counter == FileB.Length)
                    {
                        // get the sum of the last chunk
                        var a = (sum[index] - sum[index.Shift(1, CHUNCK_SIZE + 1)]);
                        Int64 tempHash = (Int64)a;

                        // conpute my hash function
                        tempHash = tempHash * ((Int64)current[index] + 1)
                                          * ((Int64)current[index.Shift(-1, CHUNCK_SIZE + 1)] + 1)
                                          * ((Int64)current[index.Shift(-2, CHUNCK_SIZE + 1)] + 1)
                                          * (Int64)(Math.Pow(-1, current[index]));


                        // add the hashes to the array
                        hashes[numberOfHashes, 0] = tempHash;
                        numberOfHashes++;

                        hashes[numberOfHashes, 1] = -1;// later store a stronger hash function
                        numberOfHashes++;

                        // MISSING IMPLEMENTATION TO STORE A SECOND STRONGER HASH FUNCTION

                        if (counter == FileB.Length)
                            break;
                    }

                    index++;
                    index = index % (CHUNCK_SIZE + 1); // if index is out of bounds in circular array place it at position 0
                }
            }
        }


        static void Part2()
        {
            // simulate file read of a similar file
            byte[] FileB = new byte[]{1,3,5,8,2,0,1,0,0,0,1,2,4,5,6,7,8,2,3,4,5,6,7,8,11};            

            // place where we will place all matching hashes
            Int64[,] hashes = new Int64[(FileB.Length / CHUNCK_SIZE) + 10, 2];


            int counter = 0;
            byte[] current = new byte[CHUNCK_SIZE + 1]; // circual array
            UInt64[] sum = new UInt64[CHUNCK_SIZE + 1]; // circual array
            int index = 0; // position where in circular array



            while (counter < FileB.Length)
            {
                int i = 0;
                for (; i < CHUNCK_SIZE; i++)
                {
                    if (counter == 0)
                    {
                        sum[index] = FileB[counter];
                    }
                    else
                    {
                        sum[index] = FileB[counter] + sum[index.Shift(-1, CHUNCK_SIZE + 1)];
                    }
                    current[index] = FileB[counter];
                    counter++;

                    // here we compute the hash every time and we are missing implementation to 
                    // check if hash is contained by the other file
                    if (counter >= CHUNCK_SIZE)
                    {
                        var a = (sum[index] - sum[index.Shift(1, CHUNCK_SIZE + 1)]);

                        Int64 tempHash = (Int64)a;

                        tempHash = tempHash * ((Int64)current[index] + 1)
                                          * ((Int64)current[index.Shift(-1, CHUNCK_SIZE + 1)] + 1)
                                          * ((Int64)current[index.Shift(-2, CHUNCK_SIZE + 1)] + 1)
                                          * (Int64)(Math.Pow(-1, current[index]));

                        if (counter == FileB.Length)
                            break;
                    }

                    index++;
                    index = index % (CHUNCK_SIZE + 1);
                }
            }
        }
    }
}

те же файлы, представленные в таблице с использованием того же алгоритма

                        hashes
bytes       sum Ac  A[c-1]  A[c-2]  -1^Ac   sum * (Ac+1) * (A[c-1]+1) * (A[c-2]+1)
2       2                   
3       5                   
5       10  5   3   2   -1  
8       18  8   5   3   1   3888
2       20  2   8   5   1   
0       20  0   2   8   1   
1       21  1   0   2   -1  
0       21  0   1   0   1   6
0       21  0   0   1   1   
0       21  0   0   0   1   
1       22  1   0   0   -1  
2       24  2   1   0   1   18
4       28  4   2   1   1   
5       33  5   4   2   -1  
6       39  6   5   4   1   
7       46  7   6   5   -1  -7392
8       54  8   7   6   1   
2       56  2   8   7   1   
3       59  3   2   8   -1  
4       63  4   3   2   1   1020
5       68  5   4   3   -1  
6       74  6   5   4   1   
7       81  7   6   5   -1  
8       89  8   7   6   1   13104
11      100 11  8   7   -1  -27648






file b                          
                            rolling hashes
bytes       0   Ac  A[c-1]  A[c-2]  -1^Ac   sum * (Ac+1) * (A[c-1]+1) * (A[c-2]+1)
1       1                   
3       4                   
5       9   5   3   1   -1  
8       17  8   5   3   1   3672
2       19  2   8   5   1   2916
0       19  0   2   8   1   405
1       20  1   0   2   -1  -66
0       20  0   1   0   1   6
0       20  0   0   1   1   2
0       20  0   0   0   1   1
1       21  1   0   0   -1  -2
2       23  2   1   0   1   18
4       27  4   2   1   1   210
5       32  5   4   2   -1  -1080
6       38  6   5   4   1   3570
7       45  7   6   5   -1  -7392
8       53  8   7   6   1   13104
2       55  2   8   7   1   4968
3       58  3   2   8   -1  -2160
4       62  4   3   2   1   1020
5       67  5   4   3   -1  -1680
6       73  6   5   4   1   3780
7       80  7   6   5   -1  -7392
8       88  8   7   6   1   13104
11      99  11  8   7   -1  -27648