Average-Case Analysis for a Simple Compression Algorithm |
| |
Authors: | D Merlini R Sprugnoli M C Verri |
| |
Affiliation: | (1) Dipartimento di Sistemi e Informatica, via Lombroso 6/17, 50134 Firenze, Italy., IT |
| |
Abstract: | 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 the range 1 . . . n ] so that membership queries on S 's elements can be handled in O(1) time. It can be approached as a table compression problem in which a size n table has m ones and the other elements are zeros. We focus our attention on sparse case (m
n ). We use a simple algorithm to solve the problem and make an average-case analysis of the total space required when the
input derives from uniform probability distribution. We also find some conditions able to minimize storage requirements. We
then propose and analyze a new algorithm able to reduce storage requirements drastically to O(m
4/3
) .
Received December 1, 1997; revised March 1, 1998. |
| |
Keywords: | , Static dictionary problem, Table compression, Average case analysis, |
本文献已被 SpringerLink 等数据库收录! |
|