[pt] As Técnicas de visualização volumétrica apresentam dois clássicos problemas computacionais: necessidade de longo tempo de execução e grande consumo de memória. A popularização das aplicações distribuídas tem despertado um crescente interesse no tratamento dos problemas de grande consumo de memória. Esse problema é fundamental também para garantir o acesso às técnicas de visualização volumétrica em máquinas com pequena capacidade de memória. Nesta tese, propomos um método para a compressão de dados volumétricos baseado na utilização da transformada do cosseno local.Esse método é apropiado ao desenvolvimento de técnicas de visualização volumétrica basedas na estrutura do dado comprimido.A transformada do cosseno local apresenta a capacidade de possibilitar altas taxas de compressão com a minimização do erro de reconstrução, possibilitando a reconstrução local do volume. Neste trabalho, são apresentados os resultados obtidos com a compressão de volumes reais, estimando a influência dos parâmetros dométodo de compressão, investigando as possibilidades de adptação da partição do volume às suas características de frequencias e estimando a capacidade de compressão e os erros introduzidos neste processo.

[pt] Neste trabalho é estudado o problema da compressão de dados por codificadores de estado finito e sem perda de informação. O problema é dividido em três partes: compressão de seqüências individuais, compressão de pares de seqüências e compressão de imagens. A principal motivação do trabalho é o estudo da compressão de pares de seqüências, como um passo intermediário para o entendimento do problema da compressão de dados bidimensionais. Para cada um dos casos é definido um limitante inferior para a taxa de compressão de qualquer codificador de estado finito e sem perda de informação. Para os três casos, codificadores universais são propostos e seus desempenhos são analisados. Os codificadores propostos foram implementados em software e aplicados à compressão de seqüências finitas, pares de seqüências finitas e imagens finitas. Os resultados de simulação obtidos são analisados. / [en] In this work the problem of data compression by finite- state and information lossless encorders is studied. The problem is divided in three parts: compression of individual sequences, compression of pairs of sequences and compression of images. For each of these, a lower bound is defined which sets a limit on the smaller compression rate that can be achieved by any finite-state and information lossless enconders. Universal encorders are proposed and their performance compared to the optimal attainable. The proposed encoders were implemented in software and used to compress finite sequences, pairs of finite sequences and finite images. The simulation results are analysed.

[pt] A tese de mestrado, aqui resumida, tem a meta de propor novos algoritmos para a compressão de dados, em especial imagens, apresentando aplicações e resultados teóricos. Como o título sugere, estes dados serão originados de fontes com alfabeto contínuo, podendo ser particularizado para os casos discretos. O algoritmo a ser proposto (LLZ para o caso contínuo) é baseado no codificador universal Lempel-Ziv, apresentando a característica de admitir a introdução de perdas, mas que conduza a um maior aproveitamento do poder de compressão deste algoritmo. Desta forma, o LLZ se mostra vantajoso em dois pontos: integrar compactador e quantizador, e ser um quantizador universal. / [en] This dissertation introduces new data compression algorithms, specially for images, and presents some applications and theoretical results related to these algorithms. The data to be compressed will be originated from sources with continuos alphabet, and can be stated for discrete sources. The proposed algorithms (LLZ for continuos case), which is based on the universal Lempel-Ziv coder (LZ), accepts losses, taking advantage of LZ s compression power. As such, the LIZ is an innovating proposal in two ways: first, it couples compaction and quantization in one step; and second, it can be seeing as an universal quantizer.

[pt] Cifragem e compressão de dados são funcionalidades essencias quando dados digitais são armazenados ou transmitidos através de canais inseguros. Geralmente, duas operações sequencias são aplicadas: primeiro, compressão de dados para economizar espaço de armazenamento e reduzir custos de transmissão, segundo, cifragem de dados para prover confidencialidade. Essa solução funciona bem para a maioria das aplicações, mas é necessário executar duas operações caras, e para acessar os dados, é necessário primeiro decifrar e depois descomprimir todo o texto cifrado para recuperar a informação. Neste trabalho são propostos algoritmos que realizam tanto compressão como cifragem de dados. A primeira contribuição desta tese é o algoritmo ADDNULLS - Inserção Seletiva de Nulos. Este algoritmo usa a técnica da esteganografia para esconder os símbolos codificados em símbolos falsos. É baseado na inserção seletiva de um número variável de símbolos nulos após os símbolos codificados. É mostrado que as perdas nas taxas de compressão são relativamente pequenas. A segunda contribuição desta tese é o algoritmo HHC - Huffman Homofônico-Canônico. Este algoritmo cria uma nova árvore homofônica baseada na árvore de Huffman canônica original para o texto de entrada. Os resultados dos experimentos são mostrados. A terceira contribuição desta tese é o algoritmo RHUFF - Huffman Randomizado. Este algoritmo é uma variante do algoritmo de Huffman que define um procedimento de cripto-compressão que aleatoriza a saída. O objetivo é gerar textos cifrados aleatórios como saída para obscurecer as redundâncias do texto original (confusão). O algoritmo possui uma função de permutação inicial, que dissipa a redundância do texto original pelo texto cifrado (difusão). A quarta contribuição desta tese é o algoritmo HSPC2 - Códigos de Prefixo baseados em Substituição Homofônica com 2 homofônicos. No processo de codificação, o algoritmo adiciona um bit de sufixo em alguns códigos. Uma chave secreta e uma taxa de homofônicos são parâmetros que controlam essa inserção. É mostrado que a quebra do HSPC2 é um problema NP- Completo. / [en] Data compression and encryption are essential features when digital data is stored or transmitted over insecure channels. Usually, we apply two sequential operations: first, we apply data compression to save disk space and to reduce transmission costs, and second, data encryption to provide confidentiality. This solution works fine for most applications, but we have to execute two expensive operations, and if we want to access data, we must first decipher and then decompress the ciphertext to restore information. In this work we propose algorithms that achieve both compressed and encrypted data. The first contribution of this thesis is the algorithm ADDNULLS - Selective Addition of Nulls. This algorithm uses steganographic technique to hide the real symbols of the encoded text within fake ones. It is based on selective insertion of a variable number of null symbols after the real ones. It is shown that coding and decoding rates loss are small. The disadvantage is ciphertext expansion. The second contribution of this thesis is the algorithm HHC - Homophonic- Canonic Huffman. This algorithm creates a new homophonic tree based upon the original canonical Huffman tree for the input text. It is shown the results of the experiments. Adding security has not significantly decreased performance. The third contribution of this thesis is the algorithm RHUFF - Randomized Huffman. This algorithm is a variant of Huffman codes that defines a crypto-compression algorithm that randomizes output. The goal is to generate random ciphertexts as output to obscure the redundancies in the plaintext (confusion). The algorithm uses homophonic substitution, canonical Huffman codes and a secret key for ciphering. The secret key is based on an initial permutation function, which dissipates the redundancy of the plaintext over the ciphertext (diffusion). The fourth contribution of this thesis is the algorithm HSPC2 - Homophonic Substitution Prefix Codes with 2 homophones. It is proposed a provably secure algorithm by using a homophonic substitution algorithm and a key. In the encoding process, the HSPC2 function appends a one bit suffx to some codes. A secret key and a homophonic rate parameters control this appending. It is shown that breaking HSPC2 is an NP-Complete problem.

[pt] Esta tese aborda os problemas de compressão para os seguintes tipos de dados: sequência de bits e grafos web. Para o problema de compressão de sequência de bits, demonstramos a relação entre algoritmos de intercalação e codificadores de fonte binária. Em seguida, mostramos que os algoritmos de intercalação binária (Hwang e Lin, 1972), recursivo (Dudzinski, 1981) e probabilístico (Vega, 1993), geram respectivamente os codificadores de entropia baseado em comprimentos de carreiras codificados com o código de Rice, o codificador de intercalação binária (Moffat, 2000) e o codificador de Rice aleatório, na qual é um novo variante do código de Rice. Para o problema de compressão de grafos web, propomos uma nova representa ção compacta para grafos web, intitulada árvore-w, construída especificamente para memória externa (disco), sendo a primeira nesse gênero. Propomos também um novo tipo de layout projetado especificamente para grafos web, intitulado layout escalado. Além disso, mostramos como construir um layout cache-oblivious para explorar a hierarquia de memórias, sendo a primeira desse tipo. Apresentamos vários tipos de consultas que podem ser executadas e é a primeira representação a suportar execução de consulta de leitura aleatória em lote e a otimização de consultas avançadas, inclusive em memória principal. Por fim, executamos uma série de experimentos que mostra que a árvore-w apresenta taxas de compressão e de tempo de execução competitivas com outras representações compactas em memória principal. Assim, demonstramos empiricamente a viabilidade de uma representação compacta para memória externa na prática, contrariando a afirmação de vários pesquisadores (Suel, 2001) (Buehrer, 2008). / [en] This thesis addresses the problems of compression for the following data types: numbers, sequence of bits and webgraphs. For the problem of compression of a sequence of bits, we demonstrate the relationship between merge algorithms and binary source coders. Then, we show that the algorithms binary merge (Hwang and Lin, 1972), recursive merge (Dudzinski, 1981) and probabilistic merge (Vega, 1993), generate respectively an entropy coder based runlengths encoded with the Rice code, the interpolative binary coder (Moffat, 2000) and the random Rice coder, which is a new variant of the Rice code. For the problem of webgraph compression, we propose a new compact representation for webgraphs, entitled w-tree, built specifically for external memory (disk), being the first one in this genre. We also propose a new type of layout designed specifically for webgraphs, entitled scaled layout. In addition, we show how to build a cache-oblivious layout to explore the hierarchy of memories, being the first of its kind. We offer several types of queries that can be performed and it is the first representation to support batched random read query execution and advanced query optimization, including in main memory. Finally, we performed a series of experiments showing that the w-tree provides compression rates and running times competitive with other compact representations for main memory. Therefore, we demonstrate empirically the feasibility of a compact representation for external memory in practice, contrary to the assertion of several researchers (Suel, 2001) (Buehrer, 2008).

[pt] A transformada de Burrows-Wheeler, baseada na ordenação de contextos, transforma uma seqüência de caracteres em uma nova seqüência mais facilmente comprimida por um algoritmo que explore grandes seqüências de repetições de caracteres. Aliado a recodificação do MoverParaFrente e seguida de uma codificação para os inteiros gerados, eles formam uma nova família de compressores, que possuem excelentes taxas de compressão, com boas performances nos tempos de compressão e descompressão. Este trabalho examina detalhadamente essa transformada, suas variações e algumas alternativas para os algoritmos utilizados em conjunto com ela. Como resultado final, apresentamos uma combinação de estratégias que produz taxas de compressão para texto melhores do que as oferecidas pelas implementações até aqui disponíveis. / [en] The Burrows-Wheeler Transform, based on sorting of contexts, transforms a sequence of characters into a new sequence easier to compress by an algorithm that exploits long sequences of repeted characters. Combined with the coding provided by the MoveToFront Algorithm and followed by a codification for the generated integers, they propose a new family of compressors, that achieve excellent compression rates with good time performances in compression and decompression. This work examines detaildedly this transform, its variations and some alternatives for the algorithms used together with it. As a final result, we present a combination of strategies that producescompression rates for text data that are better than those offered by implementations available nowadays.

[pt] Esta dissertação apresenta uma estratégia para desenvolver mecanismos de compressão de dados adquiridos por sensores, seguindo como inspiração o processo utilizado no formato JPG2000. A estratégia adota a abordagem das séries históricas dos dados sob o ponto de vista do processamento de sinais. Dada à natureza instável dos sensores é natural que ruídos sejam adicionados ao sinal original. Estes ruídos são detectados e tratados enquanto o sinal é suavizado e limpo, facilitando a análise, ao passo que em que componentes pouco relevantes são removidos ou aproximados, permitindo que o sinal seja comprimido com pouca perda de informação. / [en] This dissertation introduces a strategy to develop a compression method for sensor data inspired on the JPG2000 techniques. The strategy adopted processes data streams much in the same way as signal processing. Due to the unstable nature of sensor data, noise is added to the original signal. This noise is detected and treated while the signal is cleaned and smoothed, making it easier to analyze the data stream. Less relevant signal components are removed or approximated allowing the signal to be compressed with few information loss.