AVERAGE-CASE ANALYSIS FOR A SIMPLE COMPRESSION ALGORITHM

In this paper we treat the static dictionary problem, very well known in computer science. It consists in storing a set S of m elements in t he range [1 ... n] so that membership queries on S's elements can be h andled in O(1) time. It can be approached as a table compression probl em in which a size n table has m ones and the other elements are zeros . We focus our attention on sparse case (m much less than n). We use a simple algorithm to solve the problem and make an average-case analys is of the total space required when the input derives from uniform pro bability distribution. We also find some conditions able to minimize s torage requirements. We then propose and analyze a new algorithm able to reduce storage requirements drastically to O(m(4/3)).