[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] O presente trabalho consiste em um estudo em torno de Verdade e Método, principal obra do filósofo alemão Hans-Georg Gadamer. Ao tomar o fenômeno da compreensão (Verstehen) como objeto de sua reflexão, Gadamer nos esclarece de antemão que a hermenêutica que ele pretende desenvolver constitui uma tentativa de entender a verdade que é própria das ciências humanas, para além de sua autoconsciência metodológica, bem como o que liga tais ciências ao conjunto de nossa experiência de mundo. Um dos temas centrais desenvolvidos nesta obra, e que se encontra diretamente articulado com a questão da compreensão, é o conceito de jogo (Spiel), entendido como um acontecimento que se dá para além das subjetividades que nele se encontram envolvidas. Para Gadamer o alcance universal e a dimensão ontológica do jogo não devem ser ignorados. Portanto, tentaremos mostrar neste estudo, que jogar e compreender são elementos intercambiáveis em seu pensamento, na medida em que pensar o entrelaçamento jogo-compreensão é realizar que a estrutura da compreensão exige um certo entregar-se à situação em que a subjetividade não é tida mais como instância determinadora em relação ao momento da compreensão. / [en] The present paper is a study on Truth and Method, the main work of the German philosopher Hans-Georg Gadamer. When it comes to the phenomenom of understanding (Verstehen) as the object of his thought, Gadamer explains us that the hermeneutics he intends to develop constitutes an attempt to understand the truth of human sciences, beyond their methodological self-consciousness, as well as, what links such sciences to the whole of our world experience. One of the central themes developed in this work, straightly linked to the question of understanding, is the concept of play (Spiel), known as an event that happens beyond the subjectivities involved in it. According to Gadamer, the universal scope and the ontological dimension of play should not be ignored. Therefore, we will try to show in this work that to play and to understand are interchangeable elements in Gadamer´s thought, inasmuch as to think about the connectedness of play-understanding is to realize that the structure of understanding demands one to surrender oneself to the situation in which the subjectivity is no longer the determinant instance regarding the moment of understanding.

[pt] Neste trabalho é investigada uma técnica de compressão de imagens empregando a Transformada Wavelet Discreta em conexão com o código de compressão mLLZ/d, que é baseado no algoritmo de Lempel-zig com perdas. Primeiramente é apresentada a teoria das wavelets e são discutidos diversos códigos para compactação e compressão baseados no algoritmo de Lempel-Ziv. Em seguida, são apresentados os resultados de diversas simulações realizadas com quatro imagens comumente empregadas neste tipo de análise, de forma a avaliar o desempenho do método em termos de qualidade objetiva e subjetiva. Finalmente, os resultados foram analisados e comparados aos obtidos com outras técnicas de compressão, publicadas em dissertações de mestrado anteriores. / [en] In this work an image compression method employing the Discrete Wavelet Tranform in connection with the Lossy Lempel-Ziv code mLLZ/d is investigated. At first, the wavelet theory as well as several lossy and lossless codes based on the Lempel-ziv algorithm are discussed. Afterwards, simulations are implemented using four images, which are commonly used as a standard for this type of analysis, in order to evaluate the performance of the method in terms of both objective and subjective quality. Finally, the results are analyzed and compared to the ones obtained with other compression techniques, already published in former thesis.

[pt] Os códigos de prefixo têm importância fundamental na comprenssão e transmissão de dados. Estes códigos também apresentam relações com problemas de busca. Neste tese, apresentamos novos resultados estruturais e algorítimos sobre a classe dos códigos de prefixo. Explicamos teoricamente as boas taxas de compressão observadas para alguns métodos utilizados na prática. Propomos também algoritmos eficientes para construção de códigos de prefixo ótimos e variantes. Os principais resultados aqui descritos são os seguintes: - um novo algoritmo paralelo para construção de códigos de prefixos ótimos: - uma cota superior para a perda de compressão introduzida pela restrição de comprimento nos códigos de prefixo: - uma cota superior para a perda de compressão introduzida pela restrição de comprimento nos códigos de prefixo alfabéticos: - um algoritmo aproximativo e linear para construção de códigos de prefixo com restrição de comprimento: - um algoritmo aproximativo com complexidade 0(n log n) para construção de códigos de prefixo alfabéticos com restrição de comprimento: - uma nova versão de algoritmo WARM-UP com complexidade fortemente polinomial: - um algoritmo linear para reconhecer códigos de prefixo ótimos com restrição de comprimento: - uma prova afirmativa da conjectura de Vitter sobre o desempenho dos códigos de Huffmann dinâmicos construídos pelo algoritmo FGK (Faller, Gallanger e Knuth) / [en] The prefix codes play an important role in data compression and data communication. These codes also present relation with search problems. In this thesis, we present new structural and algorithmic results concerning the prefix code class. We theoretically explain results related to the high compression rates of some methods that have been used for pratical purposes. We also propose efficient algorthims for constructing optimal prefix codes and some variants. The major results are listed below: -a new parallel algorithm for constructing optimal prefix codes: -a sharp upper bound for the compression loss introduced due usage of length restricted prefix codes: -an upper bound for the compression loss introduced due the usage of length restricted alphabetic prefix codes: -an 0(n log n) time approximative algorithm for constructing lenght restricted prefix code: -a 0(n log n) time approximative algorithm for constructing lenght restricted alphabetic prefix code: -a strongly polinomial version for the WARM-UP algorithm: -a linear time algorithm for recognizing optimal length restricted prefix codes: -a proof for Vitter´s conjecture about the perfomance of the Dynamic Huffman Codes constructed by FGK (Faller, Gallager and Knuth) algorithm.

[pt] Este trabalho apresenta uma análise comparativa de algoritmos rápidos de estimação de movimento para codificações de vídeo, os quais visam reduzir a complexidade computacional do algoritmo Força Bruta. Os dois primeiros ( LOGD e 3 PASSOS) reduzem extremamente a complexidade, contudo, apresentam os mais baixos desempenhos. Dois deles Eliminação Sucessiva (ES I) e Adaptativo da Força Bruta (AFB) são técnicas recentes apresentadas na literatura. O dois últimos algoritmos (ES II e ES III) são modificações propostas nesta tese, com base nas técnicas ES I e AFB. Todos os algoritmos implementados neste trabalho são analisados isoladamente e em ambiente MPEG. / [en] This work presents a comparative analysis of fast motion compensation algorithms for vídeo compression, whitch aim at reducing the computacional complexity of the Full Search block matching tchnique. The first two ( LOG 2D and 3 Step) extremely reduce the complexity. However, they present the lowest performace. Two of them - Sucessive Elimination I ( ES I) and Adaptative Block Matching (AFB) - are schemes recently proposed in the literature. The last two algorithms (ES II and ES III) are modifications proposed in this thesis and are based on the ES I and AFB techniques. The algorithms are examined isolatedly an when operating in the MPEG environment.

[pt] O tamanho das provas formais possui algumas importantes implicações teóricas na área da complexidade computacional. O problema de determinar se uma fórmula é uma tautologia da Lógica Proposicional Intuicionista e do fragmento puramente implicacional da Lógica Minimal (M(contém)) é PSPACE- Completo. Qualquer lógica proposicional com um sistema de dedução natural que satisfaça o princípio da subfórmula possui o problema de determinar tautologias em PSPACE. Saber se qualquer tautologia em M(contém) admite provas de tamanho polinomialmente limitado está relacionado com saber se NP = PSPACE. Técnicas de compressão de provas reportadas na literatura utilizam duas abordagens principais para comprimir provas: gerar provas já compactadas; comprimir uma prova já gerada. Proposta por Gordeev e Haeusler (6), a Compressão Horizontal é uma técnica de compressão de provas em dedução natural da M(contém) que utiliza grafos direcionados para representar as provas. Dada a prova de uma tautologia qualquer da M(contém), que pode possuir tamanho exponencial em relação ao tamanho da conclusão, o objetivo da Compressão Horizontal é que a prova resultante da compressão possua tamanho polinomialmente limitado em relação ao tamanho da conclusão. Nosso trabalho apresenta a primeira implementação da Compressão Horizontal, juntamente com os primeiros resultados da aplicação da técnica sobre provas de tautologias da M(contém), além disso, compara as taxas de compressão obtidas com técnicas tradicionais de compressão de dados. / [en] The size of formal proofs has some important theoretical implications in computational complexity theory. The problem of determining if some formula of Intuitionistic Propositional Logic and the purely implicational fragment of Minimal Logic (M(contains)) is a tautology is PSPACE-Complete. Any propositional logic with a natural deduction system that satisfies the sub- formula principle is PSPACE. To know if any tautology in M(contains) admits polynomially sized proof is related to whether NP = PSPACE. Proof compression techniques reported in literature use two main approaches to proof compressing: generating already compressed proofs; compressing an already generated proof. Proposed by Gordeev and Haeusler (6), the Horizontal Compression is a natural deduction proof compression technique that uses directed graphs to represent proofs. Given a tautology proof in M(contains), which may have an exponential size in relation to conclusion length, the goal of Horizontal Compression is that the compressed proof has a polynomially limited size in relation to conclusion length. Our work presents the first implementation of Horizontal Compression, together with the first results of the execution of the technique on proofs of M(contains) tautologies.

[pt] Esta Dissertação destina-se ao desenvolvimento de novas técnicas de realce aplicadas no domínio da transformada. O estudo das transformadas bidimensionais motivaram o desenvolvimento de técnicas baseadas nestas ferramentas matemáticas. Análises comparativas entre os métodos de realce no domínio espacial e no domínio da transformada logo revelaram as vantagens do uso das transformadas. É proposta e analisada uma nova técnica de realce no domínio da Transformada Cosseno Discreta (DCT). Os resultados mostraram que esta nova proposta é menos afetada por ruído e realça mais a imagem que as técnicas apresentadas na literatura. Adicionalmente, considera-se uma estratégia com o objetivo de eliminar o efeito de escurecimento da imagem processada pelo Alpha-rooting. É também apresentada uma nova proposta de realce no domínio da Transformada Wavelet Discreta (DWT). As simulações mostraram que a imagem resultante possui melhor qualidade visual que a de técnicas relatadas na literatura, além de ser pouco afetada pelo ruído. Além disso, a escolha do parâmetro de realce é simplificada. / [en] This Dissertation is aimed at the development of new enhancement techniques applied in the transform domain. The study of the bidimensional transforms motivated the development of techniques based on these mathematical tools. The comparative analysis between the enhancement methods in the spatial domain and in the transform domain revealed the advantages of the use of transforms. A new proposal of enhancement in the Discrete Cosine Transform (DCT) domain is analysed. The results showed that this new proposal is less affected by noise and enhances more the image than other techniques reported in the literature. In addition, a strategy to eliminate the darkening effect of enhancement by Alpha-rooting is considered. A new proposal of enhancement in the Discrete Wavelet Transform (DWT) domain is also presented. Simulation results showed that the enhanced images have better visual quality than other ones presented in the literature and is less affected by noise. Moreover, the choice of the enhancement parameter is simplified.

[pt] Para transmissão da informação de maneira confiável, em canais com apagamento, foram criados os códigos LT (Luby Transform), uma das principais classes de códigos fontanais. Estes códigos não têm uma taxa fixa, em outras palavras, eles têm taxa versátil. Esta dissertação aborda o estudo da transmissão de imagens através de canal ruidoso, AWGN (Aditive White Gaussian Noise), com o uso de Códigos LT. Investigou-se o desempenho usando uma modulação BPSK, dois esquemas foram testados: Um esquema para canal que inclui apagamento (BESC) e um outro que foi proposto usando um código Hamming em série com um código LT. O esquema LT-Hamming apresentou um ganho de código maior que o esquema BESC e o código convolucional de semelhantes características. Foi testado o esquema LT-Hamming para diferentes tipos de imagens em um canal AWGN usando a técnica SPIHT para a compressão das imagens. Para obter uma medida objetiva da qualidade da imagem recuperada foi usado o parâmetro PSNR (Peak Sinal to Noise Ratio) e foram apresentadas algumas imagens com o objetivo de analisar sua qualidade através de uma inspeção visual. Dado que o código LT é versátil para o que diz respeito à taxa de código, foi proposto um método para método para atribuir diferentes níveis de proteção da informação codificada, UEP (Unequal Error Protection). / [en] To transfer reliably information in erasure channels, LT (Luby Transform) codes were created, they are part of the main class of fountain codes, this codes don’t have fixed rate, in other words, they have a versatile code rate. This thesis address to the study of images transmission through noisy channel, AWGN (Aditive White Gaussian Noise) using LT codes. We investigated the performance using a BPSK modulation, two schemes were tested: A scheme of channel that includes deletion (BESC) and another that was proposed, using a Hamming code in series with a LT code. The LT-Hamming scheme present a gain code larger than BESC scheme and convolutional codes of similar characteristics. Was tested LT-Hamming scheme for different types of images on AWGN channel using the SPIHT technique for images compression. To obtain an objective measure of image quality was used the PSNR (Peak Signal Noise Ratio) and some images were presented in order to analize its quality through visual inspection given that LT code is a versatile for what concern the code rate it was proposed a method to assign different protection levels to the code information, UEP (Unequal Error Protection).

[pt] Muitas são as aplicações onde se faz necessário transmitir modelos 3D via Internet. Entre eles merece destaque o compartilhamento de dados entre ambientes colaborativos situados em diferentes localidades. Este compartilhamento permite a sua análise e visualização, porém restrições de largura de banda da rede (Internet/Intranet) assim como o custo de armazenamento limitam a complexidade do modelo a ser transmitido/armazenado. As malhas geométricas são utilizadas em diferentes áreas da computação gráfica e visualização científica, como exemplos podem se citar elementos finitos os quais são utilizados em modelos CAD, jogos, modelagem de terrenos, geometria computacional entre outros. Devido à grande complexidade das malhas, estas são processadas por meios computacionais usando alguma estrutura de dados que represente da melhor forma o modelo em questão. A principal motivãção deste trabalho é verificar a viabilidade do uso de uma nova estrutura de dados para representar e comprimir malhas irregulares (triângulos e quadrângulos). Nesta nova abordagem será apresentada a estrutura de dados CHalfEdge. Ela usa os conceitos e idéias da representação HalfEdge e esta por sua vez possui um baixo custo de armazenamento e mantém um alto poder de expressão. Neste trabalho é desenvolvido tambem um algoritmo de compressão de malhas triangulares e/ou quadrangulares com suporte a alças. Este novo algoritmo proposto é uma extensão da compressão de malhas triangulares EdgeBreaker. / [en] Many applications need to transmit 3D models over the Internet, among those data sharing between collaborative environments situated in different locations. Those data sharing aim to analyze and visualize them but bandwidth constraints and storage costs limit the complexity of models than can be transmitted/stored. Polygonal meshes are used in different areas of Computer Graphics and Scientific Visualization. For instance, finite elements and boundary representations are used in CAD models, games, terrain modelling, etc. Due the great complexity of those meshes, they must be represented by a specific data structure that suits them. The main motivation of this work is to verify the feasibility of the use of a new data structure to represent and to compress irregular meshes (triangles and quads). It is introduced the CHalfEdge data structure based on the ideas of the HalfEdge data structure, which are used to represent models by boundary representation. In this work it is also proposed a new algorithm to compress and decompress irregulars meshes with genus, this new algorithm is an extension of the EdgeBreaker compression for regular meshes.

[pt] Em um sistema de comunicações, procura-se representar a informação gerada de forma eficiente, de modo que a redundância da informação seja reduzida ou idealmente eliminada, com o propósito de armazenamento e/ou transmissão da mesma. Este interesse justifica portanto, o estudo e desenvolvimento de técnicas de compressão que vem sendo realizado ao longo dos anos. Este trabalho de pesquisa investiga o uso de códigos de permutação para codificação de fontes segundo um critério de fidelidade, mais especificamente de fontes sem memória, caracterizadas por uma distribuição uniforme e critério de distorção de erro médio quadrático. Examina-se os códigos de permutação sob a ótica de fontes compostas e a partir desta perspectiva, apresenta-se um esquema de compressão com duplo estágio. Realiza-se então uma análise desse esquema de codificação. Faz-se também uma extensão L- dimensional (L > 1) do esquema de permutação apresentado na literatura. Os resultados obtidos comprovam um melhor desempenho da versão em duas dimensões, quando comparada ao caso unidimensional, sendo esta a principal contribuição do presente trabalho. A partir desses resultados, busca-se a aplicação de um esquema que utiliza códigos de permutação para a compressão de imagens. / [en] In communications systems the information must be represented in an efficient form, in such a way that the redundancy of the information is either reduced or ideally eliminated, with the intention of storage or transmission of the same one. This interest justifies the study and development of compression techniques that have been realized through the years. This research investigates the use of permutation codes for source encoding with a fidelity criterion, more specifically of memoryless uniform sources with mean square error fidelity criterion. We examine the permutation codes under the view of composed sources and from this perspective, a project of double stage source encoder is presented. An analysis of this project of codification is realized then. A L-dimensional extension (L > 1) of permutation codes from previous research is also introduced. The results prove a better performance of the version in two dimensions, when compared with the unidimensional case and this is the main contribution of the present study. From these results, we investigate an application for permutation codes in image compression.