Study and development of lossless compression algorithms on uniformly distributed data

Autor: CARVALHO, Caio Magno Aguiar de
Přispěvatelé: DUAILIBE FILHO, Allan Kardec Barros, SANTANA, Ewaldo Éder Carvalho, SOUZA, Francisco da Chagas de, SIQUEIRA, Hugo Valadares
Jazyk: portugalština
Rok vydání: 2022
Předmět:
Zdroj: Biblioteca Digital de Teses e Dissertações da UFMA
Universidade Federal do Maranhão (UFMA)
instacron:UFMA
Popis: Submitted by Jonathan Sousa de Almeida (jonathan.sousa@ufma.br) on 2022-10-18T11:07:31Z No. of bitstreams: 1 CAIOMAGNOAGUIARDECARVALHO.pdf: 874689 bytes, checksum: 40bf64143db20d5d05f9662c49892e31 (MD5) Made available in DSpace on 2022-10-18T11:07:31Z (GMT). No. of bitstreams: 1 CAIOMAGNOAGUIARDECARVALHO.pdf: 874689 bytes, checksum: 40bf64143db20d5d05f9662c49892e31 (MD5) Previous issue date: 2022-09-16 CAPES 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. A alta produção e consumo de informação digital em ritmo cada vez mais acelerado não acompanha as atuais ofertas de armazenamento e transmissão de dados, ou seja, produzimos mais conteúdo digital do que podemos armazenar e comunicar, e essa corrida aparentemente não será equilibrada facilmente. As técnicas de compressão de dados foram desenvolvidas afim de otimizar os mecanismos de armazenamento e comunicação de forma que a informação ocupe o mínimo de espaço em um sistema de gerenciamento de arquivos ou o mínimo de largura de banda em um canal de comunicação. Tais técnicas estão baseadas na Teoria da Informação proposta por Shannon, nas quais as estatísticas do sinal a ser comprimido desempenham papel fundamental na representação eficiente da informação. Repetição e estrutura são características fundamentalmente exploradas por algoritmos de compressão. Entretanto sequências de dados uniformemente distribuídos, independentes e identicamente distribuídos (i.i.d) rompem esses dois pilares que fundamentam a compressão estatística. É sabido também que idealmente a saída codificada de um algoritmo de compressão é uniformemente distribuída, portanto, estudar a possibilidade de compressão de distribuições uniformes é abrir a possibilidade de compressão recursiva. O presente trabalho tem como objetivo explorar essa possibilidade através da observação do problema da compressão fora do campo estatístico, mas a partir da redundância inerente da codificação binária padrão, proposta pelo algoritmo da Concatenação e da perspectiva geométrica através do método SVD-esfera-espiral. O algoritmo da Concatenação aproveita as frações de bits não utilizadas na representação binária padrão, tendo o seu desempenho máximo quando o tamanho do alfabeto dos dados comprimidos é 2 N + 1. Os experimentos foram conduzidos sobre os dados da RAND Corporation, os quais são dados uniformes produzidos por processos físicos com alfabeto de tamanho 10. Os resultados mostraram que é possível obter até 12,5% de compressão sobre esse conjunto.
Databáze: OpenAIRE
Externí odkaz: