Реализовать алгоритм рекурсивного хеширования
Допустим, файл 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 некоторые из этих хеш-кодов!
так что по файлу B I придется делать это каждые 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, потому что при выполнении итерации по файлу B I потребуется внутренний цикл for, который будет вычислять хэш последние три байта.
Итак, мой вопрос:
как я могу улучшить алгоритм, сохраняя его порядка n. Это вычисляет хэш только один раз. Если я использую существующий алгоритм хеширования, такой как md5, мне придется поместить внутренний цикл внутри алгоритма, который значительно увеличит порядок алгоритма.
Обратите внимание, что можно сделать то же самое с умножением вместо сложения. но счетчик значительно растет очень быстро. Может быть, я могу сочетать умножение и сложение и вычитание...
редактировать
Кроме того, если я Google для:
рекурсивные хеширующие функции в граммах
появляется много информации, и я думаю, что эти алгоритмы очень трудно понять...
Я должен реализовать этот алгоритм для проекта, поэтому я заново изобретаю колесо... Я знаю, что существует множество алгоритмов.
Также альтернативным решением, о котором я думал, было выполнение того же алгоритма плюс еще один сильный. поэтому файл AI будет выполнять один и тот же алгоритм каждые 3 байта плюс md5 из каждых 3 байтов. Во втором файле я просто выполню второй алгоритм, если первый сбудется....
3 ответа
Редактировать:
Чем больше я думаю о том, что вы имели в виду под "рекурсивным", тем больше я сомневаюсь, что решение, которое я представил ранее, это то, что вы должны реализовать, чтобы сделать что-нибудь полезное.
Вы, вероятно, хотите реализовать алгоритм хеш-дерева, который является рекурсивной операцией.
Для этого вы хэшируете список, делите список на две части и повторяете эти два подсписка. Завершите работу, если ваш список имеет размер 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 это сложная часть. Вы можете разделить это на два цикла:
- Тот, который индексирует от конца списка, минус м, плюс я
- Тот, который индексирует от я минус м
Или вы можете использовать арифметику по модулю, чтобы "обернуть" значение вокруг, когда i - m < 0:
int valueToSutract = array[(i - m) % n];
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 для безопасного варианта.
Это то, что я получил так далеко. Я просто пропускаю шаги, которые не должны занимать время, как сравнение массива хешей и открытие файлов для чтения.
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