Spaces:
Sleeping
Sleeping
File size: 4,885 Bytes
9f135d5 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 | // Rolling hash for efficient string matching (Rabin fingerprint)
// Used in rsync, plagiarism detection, and data deduplication
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TEXT_SIZE 100000
#define WINDOW_SIZE 100
#define NUM_SEARCHES 10000
#define BASE 256
#define MOD 1000000007
typedef struct {
unsigned long long hash;
int window_size;
unsigned long long base_power;
} RollingHash;
void init_rolling_hash(RollingHash *rh, int window_size) {
rh->hash = 0;
rh->window_size = window_size;
rh->base_power = 1;
// Compute BASE^(window_size-1) % MOD
for (int i = 0; i < window_size - 1; i++) {
rh->base_power = (rh->base_power * BASE) % MOD;
}
}
unsigned long long compute_hash(const char *str, int len) {
unsigned long long hash = 0;
for (int i = 0; i < len; i++) {
hash = (hash * BASE + (unsigned char)str[i]) % MOD;
}
return hash;
}
void roll_hash(RollingHash *rh, char old_char, char new_char) {
// Remove old character
rh->hash = (rh->hash + MOD - (rh->base_power * (unsigned char)old_char) % MOD) % MOD;
// Shift and add new character
rh->hash = (rh->hash * BASE + (unsigned char)new_char) % MOD;
}
int rolling_hash_search(const char *text, int text_len, const char *pattern, int pattern_len) {
if (pattern_len > text_len) return 0;
RollingHash rh;
init_rolling_hash(&rh, pattern_len);
unsigned long long pattern_hash = compute_hash(pattern, pattern_len);
rh.hash = compute_hash(text, pattern_len);
int matches = 0;
// Check first window
if (rh.hash == pattern_hash) {
if (strncmp(text, pattern, pattern_len) == 0) {
matches++;
}
}
// Roll through the text
for (int i = pattern_len; i < text_len; i++) {
roll_hash(&rh, text[i - pattern_len], text[i]);
if (rh.hash == pattern_hash) {
if (strncmp(text + i - pattern_len + 1, pattern, pattern_len) == 0) {
matches++;
}
}
}
return matches;
}
// Chunking for data deduplication
typedef struct {
unsigned long long hash;
int offset;
int length;
} Chunk;
int chunk_data(const char *data, int data_len, int window_size, Chunk *chunks, int max_chunks) {
RollingHash rh;
init_rolling_hash(&rh, window_size);
rh.hash = compute_hash(data, window_size);
int chunk_count = 0;
int last_boundary = 0;
for (int i = window_size; i < data_len; i++) {
roll_hash(&rh, data[i - window_size], data[i]);
// Use low bits to determine chunk boundaries
if ((rh.hash & 0xFF) == 0 && chunk_count < max_chunks) {
chunks[chunk_count].hash = compute_hash(data + last_boundary, i - last_boundary);
chunks[chunk_count].offset = last_boundary;
chunks[chunk_count].length = i - last_boundary;
chunk_count++;
last_boundary = i;
}
}
// Add final chunk
if (last_boundary < data_len && chunk_count < max_chunks) {
chunks[chunk_count].hash = compute_hash(data + last_boundary, data_len - last_boundary);
chunks[chunk_count].offset = last_boundary;
chunks[chunk_count].length = data_len - last_boundary;
chunk_count++;
}
return chunk_count;
}
void generate_text(char *text, int size) {
unsigned int seed = 42;
for (int i = 0; i < size - 1; i++) {
seed = seed * 1103515245 + 12345;
text[i] = 'a' + (seed % 26);
}
text[size - 1] = '\0';
}
int main() {
char *text = (char*)malloc(TEXT_SIZE);
char *pattern = (char*)malloc(WINDOW_SIZE + 1);
generate_text(text, TEXT_SIZE);
clock_t start = clock();
int total_matches = 0;
// Pattern searching
for (int i = 0; i < NUM_SEARCHES; i++) {
int pos = (i * 137) % (TEXT_SIZE - WINDOW_SIZE);
strncpy(pattern, text + pos, WINDOW_SIZE);
pattern[WINDOW_SIZE] = '\0';
total_matches += rolling_hash_search(text, TEXT_SIZE, pattern, WINDOW_SIZE);
}
// Data chunking for deduplication
Chunk *chunks = (Chunk*)malloc(1000 * sizeof(Chunk));
int chunk_count = chunk_data(text, TEXT_SIZE, 32, chunks, 1000);
clock_t end = clock();
double time_spent = (double)(end - start) / CLOCKS_PER_SEC;
printf("Rolling hash: text=%d, window=%d, %d searches, %.6f seconds\n",
TEXT_SIZE, WINDOW_SIZE, NUM_SEARCHES, time_spent);
printf("Total matches: %d, Chunks: %d\n", total_matches, chunk_count);
free(text);
free(pattern);
free(chunks);
return 0;
}
|