Re: Distribution of longest common hash prefixes

On Mon, Apr 02, 2007 at 04:58:57PM +0200, Peter Eriksen wrote: ...

... and here is the nonbroken version, which is neither sparse nor strange. Thanks to chris on #git for the nice programming lesson. More correct output and program bellow.

Peter

 0:  1
 1:  2
 2:  4
 3:  8
 4: 16
 5: 32
 6: 64
 7: 128
 8: 256
 9: 512
10: 1024
11: 2048
12: 4096
13: 8192
14: 16384
15: 32685
16: 60921
17: 86511
18: 84426
19: 61518
20: 37450
21: 20728
22: 11035
23: 5562
24: 2812
25: 1467
26: 738
27: 355
28: 191
29: 83
30: 49
31: 27
32: 10
33:  3
34:  1
35:  2
36:  0
37:  1
38:  0
39:  0
40:  0
41:  0
42:  0
43:  0
44:  0
45:  0
46:  0
47:  0
48:  0
49:  0
50:  0
51:  0
52:  0
53:  0
54:  0
55:  0
56:  0
57:  0
58:  0
59:  0
60:  0
61:  0
62:  0
63:  0

#include <stdio.h> #include <string.h>

int h2d(char c)
{
	if ('a' <= c && c <= 'f')
		return c-'a'+10;
	else
		return c-'0';
}

int lcprefix(char *a, char *b)
{
	int i = 0;
	int j = 4;
	while (a[i] == b[i])
		i++;

	while ((h2d(a[i])<<j & 128) == (h2d(b[i])<<j & 128))
		j++;
	
	return i*4 + j - 4;
}

int max(int a, int b)
{
	return a < b ? b : a;
}

int main(int argc, char **argv)
{
	FILE *fp;
	char old[41];
	char cur[41];
	int lcp = 0;
	int table[64];
	int i;
	int tmp;

	memset(table, 0, 64*sizeof(int));
	memset(old, '0', 40);
	old[40] = '\0';

	fp = fopen(argv[1], "r");
	fscanf(fp, "%s\n", cur);

	tmp = lcprefix(old, cur);
	table[tmp]++;
	lcp = max(lcp, tmp);

	while (fscanf(fp, "%s\n", cur) != EOF) {
		tmp = lcprefix(old, cur);
		table[tmp]++;
		lcp = max(lcp, tmp);
		if (lcp < tmp) {
			printf("%s\n%s\n", old, cur);
			lcp = lcprefix(old, cur);
			printf("lcprefix = %d\n", lcp);
		}
		memcpy(old, cur, 40);
	}

	for(i = 0; i < 64; i++) {
		printf("%2d: %2d\n", i, table[i]);
	}
	
	return 0;
}