]> mj.ucw.cz Git - libucw.git/blob - lib/bitsig.c
Added license notices to all library files which are not specific
[libucw.git] / lib / bitsig.c
1 /*
2  *      Bit Array Signatures -- A Dubious Detector of Duplicates
3  *
4  *      (c) 2002 Martin Mares <mj@ucw.cz>
5  *
6  *      Greatly inspired by: Faloutsos, C. and Christodoulakis, S.: Signature files
7  *      (An access method for documents and its analytical performance evaluation),
8  *      ACM Trans. Office Inf. Syst., 2(4):267--288, Oct. 1984.
9  *
10  *      This data structure provides a very compact representation
11  *      of a set of strings with insertion and membership search,
12  *      but with a certain low probability it cheats by incidentally
13  *      reporting a non-member as a member. Generally the larger you
14  *      create the structure, the lower this probability is.
15  *
16  *      How does it work: the structure is just an array of M bits
17  *      and each possible element is hashed to a set of (at most) L
18  *      bit positions. For each element of the represented set, we
19  *      set its L bits to ones and we report as present all elements
20  *      whose all L bits ar set.
21  *
22  *      Analysis: Let's assume N items have already been stored and let A
23  *      denote L/M (density of the hash function). The probability that
24  *      a fixed bit of the array is set by any of the N items is
25  *      1 - (1-1/M)^(NL) = 1 - ((1-1/M)^M)^NA = approx. 1 - e^-NA.
26  *      This is minimized by setting A=(ln 2)/N (try taking derivative).
27  *      Given a non-present item, the probability that all of the bits
28  *      corresponding to this item are set by the other items (that is,
29  *      the structure gives a false answer) is (1-e^-NA)^L = 2^-L.
30  *      Hence, if we want to give false answers with probability less
31  *      than epsilon, we take L := -log_2 epsilon, M := 1.45*N*L.
32  *
33  *      Example: For a set of 10^7 items with P[error] < 10^-6, we set
34  *      L := 20 and M :=  290*10^6 bits = cca 34.5 MB (29 bits per item).
35  *
36  *      We leave L and an upper bound for N as parameters set during
37  *      creation of the structure. Currently, the structure is limited
38  *      to 4 Gb = 512 MB.
39  *
40  *      This software may be freely distributed and used according to the terms
41  *      of the GNU Lesser General Public License.
42  */
43
44 #include "lib/lib.h"
45 #include "lib/bitsig.h"
46 #include "lib/md5.h"
47
48 #include <string.h>
49 #include <stdlib.h>
50
51 struct bitsig {
52   uns l, m, n, maxn, max_m_mult;
53   u32 hash[4];
54   uns hindex;
55   byte array[0];
56 };
57
58 struct bitsig *
59 bitsig_init(uns perrlog, uns maxn)
60 {
61   struct bitsig *b;
62   u64 m;
63   uns mbytes;
64
65   m = ((u64) maxn * perrlog * 145 + 99) / 100;
66   if (m >= (u64) 1 << 32)
67     die("bitsig_init: bitsig array too large (maximum is 4 Gb)");
68   mbytes = (m + 7) >> 3U;
69   b = xmalloc(sizeof(struct bitsig) + mbytes);
70   b->l = perrlog;
71   b->m = m;
72   b->n = 0;
73   b->maxn = maxn;
74   b->max_m_mult = (0xffffffff / m) * m;
75   bzero(b->array, mbytes);
76   log(L_DEBUG, "Initialized bitsig array with l=%d, m=%u (%u KB), expecting %d items", b->l, b->m, (mbytes+1023)/1024, maxn);
77   return b;
78 }
79
80 void
81 bitsig_free(struct bitsig *b)
82 {
83   xfree(b);
84 }
85
86 static void
87 bitsig_hash_init(struct bitsig *b, byte *item)
88 {
89   struct MD5Context c;
90
91   MD5Init(&c);
92   MD5Update(&c, item, strlen(item));
93   MD5Final((byte *) b->hash, &c);
94   b->hindex = 0;
95 }
96
97 static inline uns
98 bitsig_hash_bit(struct bitsig *b)
99 {
100   u32 h;
101   do
102     {
103       h = b->hash[b->hindex];
104       b->hash[b->hindex] *= 3006477127U;
105       b->hindex = (b->hindex+1) % 4;
106     }
107   while (h >= b->max_m_mult);
108   return h % b->m;
109 }
110
111 int
112 bitsig_member(struct bitsig *b, byte *item)
113 {
114   uns i, bit;
115
116   bitsig_hash_init(b, item);
117   for (i=0; i<b->l; i++)
118     {
119       bit = bitsig_hash_bit(b);
120       if (!(b->array[bit >> 3] & (1 << (bit & 7))))
121         return 0;
122     }
123   return 1;
124 }
125
126 int
127 bitsig_insert(struct bitsig *b, byte *item)
128 {
129   uns i, bit, was;
130
131   bitsig_hash_init(b, item);
132   was = 1;
133   for (i=0; i<b->l; i++)
134     {
135       bit = bitsig_hash_bit(b);
136       if (!(b->array[bit >> 3] & (1 << (bit & 7))))
137         {
138           was = 0;
139           b->array[bit >> 3] |= (1 << (bit & 7));
140         }
141     }
142   if (!was && b->n++ == b->maxn+1)
143     log(L_ERROR, "bitsig: Too many items inserted, error rate will be higher than estimated!");
144   return was;
145 }
146
147 #ifdef TEST
148
149 #include <stdio.h>
150 #include <stdlib.h>
151
152 int main(int argc, char **argv)
153 {
154   struct bitsig *b = bitsig_init(atol(argv[1]), atol(argv[2]));
155   byte buf[1024];
156
157   while (fgets(buf, 1024, stdin))
158     printf("%d\n", bitsig_insert(b, buf));
159
160   return 0;
161 }
162
163 #endif