Estudo e desenvolvimento de algoritmos de compressão sem perda sobre dados uniformemente distribuídos

Abstract

The ever-increasing pace of digital information production and consumption is not keeping up with current data storage and transmission offerings, i.e., we produce more digital content than we can store and communicate, and this race will apparently not be easily balanced. Data compression techniques have been developed to optimize storage and communication mechanisms so that information occupies the minimum amount of space in a file management system or the minimum amount of bandwidth in a communication channel. Such techniques are based on the Information Theory proposed by Shannon, in which the statistics of the signal to be compressed play a key role in the efficient representation of the information. Repetition and structure are characteristics fundamentally exploited by compression algorithms. However, sequences of uniformly distributed, independent and identically distributed (i.i.d) data break these two pillars that underlie statistical compression. It is also known that ideally the coded output of a compression algorithm is uniformly distributed, so to study the possibility of compressing uniform distributions is to open up the possibility of recursive compression. The present work aims to explore this possibility by looking at the compression problem outside the statistical field, but from the inherent redundancy of standard binary coding, proposed by the Concatenation algorithm and from the geometric perspective through the SVD-spherical method. The Concatenation algorithm takes advantage of the unused bit fractions in the standard binary representation, having its maximum performance when the alphabet size of the compressed data is 2 N + 1. The experiments were conducted on RAND Corporation data, which is uniform data produced by physical processes with alphabet size 10. The results showed that it is possible to obtain up to 12.5% compression on this set.