???item.export.label??? ???item.export.type.endnote??? ???item.export.type.bibtex???

Please use this identifier to cite or link to this item: https://tedebc.ufma.br/jspui/handle/tede/tede/4187
Tipo do documento: Tese
Título: Estudo e desenvolvimento de algoritmos de compressão sem perda sobre dados uniformemente distribuídos
Título(s) alternativo(s): Study and development of lossless compression algorithms on uniformly distributed data
Autor: CARVALHO, Caio Magno Aguiar de 
Primeiro orientador: DUAILIBE FILHO, Allan Kardec Barros
Primeiro membro da banca: DUAILIBE FILHO, Allan Kardec Barros
Segundo membro da banca: SANTANA, Ewaldo Éder Carvalho
Terceiro membro da banca: SOUZA, Francisco da Chagas de
Quarto membro da banca: SIQUEIRA, Hugo Valadares
Resumo: 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.
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.
Palavras-chave: compressão de dados;
Dados uniformes;
teoria da informação;
concatenação.
data compression;
Uniform data;
information theory;
concatenation.
Área(s) do CNPq: Metodologia e Técnicas da Computação
Ciências Exatas e da Terra
Idioma: por
País: Brasil
Instituição: Universidade Federal do Maranhão
Sigla da instituição: UFMA
Departamento: DEPARTAMENTO DE ENGENHARIA DA ELETRICIDADE/CCET
Programa: PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA DE ELETRICIDADE/CCET
Citação: CARVALHO, Caio Magno Aguiar de. Estudo e desenvolvimento de algoritmos de compressão sem perda sobre dados uniformemente distribuídos. 2022. 80 f. Tese (Programa de Pós-Graduação em Engenharia de Eletricidade/CCET) - Universidade Federal do Maranhão, São Luís, 2022.
Tipo de acesso: Acesso Aberto
URI: https://tedebc.ufma.br/jspui/handle/tede/tede/4187
Data de defesa: 16-Sep-2022
Appears in Collections:TESE DE DOUTORADO - PROGRAMA DE PÓS GRADUAÇÃO EM ENGENHARIA DE ELETRICIDADE

Files in This Item:
File Description SizeFormat 
CAIOMAGNOAGUIARDECARVALHO.pdfDissertação de Mestrado854,19 kBAdobe PDFDownload/Open Preview


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.