An Example of Representation.

The mechanism named ``Superimposed coding'' [11] allows to store a set of data of variable size into a bit-string of fixed size. It is then possible, with a simple test, to estimate the probability that an element is in the set of data (which depends on the size of the result bit-string and on the number of data). This probability is equal to 0 if the output of the test is ``no''.
More precisely, the result is an $m$-bit string named $B$. We note $B=b_{m-1}\ldots b_{1}b_{0}$ where each $b_{i}\in\{0,1\}$. Initially, $B$ is set to $00\ldots 0$. We have then $k$ elements $y_{1},\ldots,y_{k}$ of various size and we note the set of data $Y=\{y_{1},\ldots,y_{k}\}$. Moreover, let us define $q$ hash functions $h_{1},\ldots,h_{q}$ where each $h_{i}: \{0,1\}^{*}\longrightarrow\{0,1\}^{c}$ with $m=2^c$.
For $j=1..k$ we compute $h_{1}(y_{j}),\ldots,h_{q}(y_{j})$ and for every $l=1..q$ we put to 1 the bit $b_{i}$ where $i=h_{l}(y_{j})$.
To know if the element $y_{R}$ is in the set of data $Y=\{y_{1},\ldots,y_{k}\}$, we compute for every $l=1..q$ $Y_{l}=h_{l}(y_{R})$ and if there is an element $l_{0}\in\{1,\ldots,q\}$ such as $b_{Y_{l_{0}}}=0$ then $y_{R}\notin Y$. If not, then $y_{R}\in Y$ with an error probability of about $\Big( 1-e^{\frac{-kq}{m}}\Big)^{q}$.