Σ΄αυτή τη διπλωματική εργασία μελετάμε κάποιους αλγορίθμους συμπίεσης δεδομένων και τους υλοποιούμε. Αρχικά, αναφέρονται βασικές αρχές της κωδικοποίησης και παρουσιάζεται το μαθηματικό υπόβαθρο της Θεωρίας Πληροφορίας. Παρουσιάζονται, επίσης διάφορα είδη κωδικών. Εν συνεχεία αναλύονται διεξοδικά η κωδικοποίηση Huffman και η αριθμητική κωδικοποίηση. Τέλος, οι δύο προαναφερθείσες κωδικοποιήσεις υλοποιούνται σε υπολογιστή με χρήση γλώσσας προγραμματισμού C και χρησιμοποιούνται για τη συμπίεση αρχείων κειμένου. Τα αρχεία που προκύπτουν συγκρίνονται με αρχεία που έχουν συμπιεστεί με χρήση προγραμμάτων του εμπορίου, αναλύονται τα αίτια των διαφορών στην αποδοτικότητα και εξάγονται χρήσιμα συμπεράσματα. / In this thesis we study some data compression algorithms and implement them. The basic principles of coding are mentioned and the mathematical foundation of information theory is presented. Also different types of codes are presented. Then the Huffman coding and arithmetic coding are analyzed in detail. Finally, the two codings are implemented on a computer using the C programming language in order to compress text files. The resulting files are compared with files that are compressed using commercial programmes, the causes of differences in the efficiency are analyzed and useful conclusions are drawn.

Huffman coding is a good method for statistically compressing test data with high compression rates. Unfortunately, the on-­‐chip decoder to decompress that encoded test data after it is loaded onto the chip may be too complex. With limited die area, the decoder complexity becomes a drawback. This makes Huffman coding not ideal for use in scan data compression. Selectively encoding test data using Huffman coding can provide similarly high compression rates while reducing the complexity of the decoder. A smaller and less complex decoder makes Alternate Huffman Coding a viable option for compressing and decompressing scan test data. / text

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2015. / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2016-06-21T16:35:22Z No. of bitstreams: 1 2015_PatríciaHelenaMaiaAlvesdeAndrade.pdf: 1873437 bytes, checksum: a2adfff14b4d48fc3555bc507bfd23ed (MD5) / Approved for entry into archive by Marília Freitas(marilia@bce.unb.br) on 2016-07-26T11:22:23Z (GMT) No. of bitstreams: 1 2015_PatríciaHelenaMaiaAlvesdeAndrade.pdf: 1873437 bytes, checksum: a2adfff14b4d48fc3555bc507bfd23ed (MD5) / Made available in DSpace on 2016-07-26T11:22:23Z (GMT). No. of bitstreams: 1 2015_PatríciaHelenaMaiaAlvesdeAndrade.pdf: 1873437 bytes, checksum: a2adfff14b4d48fc3555bc507bfd23ed (MD5) / A Controladoria Geral da União é o órgão do Poder Executivo responsável pelas atividadesde controle interno, auditoria pública, correição, prevenção e combate à corrupçãoe ouvidoria dos gastos públicos do Poder Executivo. Por meio do menu “Denuncias eManifestações“, no portal da CGU, se tem acesso a um formulário para apresentaçãode denúncias por parte da sociedade. Após cadastradas pelo cidadão as mesmas devemser triadas e encaminhadas para a coordenação temática da CGU com competência pararealizar a apuração. Atualmente essa triagem é feita de forma manual e a denúnciaencaminhada para uma dentre as 91 opções de destino pré-determinadas. Essa grandequantidade de categorias é um fator que dificulta a classificação automática de textos.Considerando o acúmulo de denúncias existentes na base atualmente e a chegada de novasdenúncias, aliadas ao tempo gasto com a triagem manual, torna-se cada vez maisdifícil a análise tempestiva das ocorrências reportadas. Esse contexto pode causar prejuízosfinanceiros para a Administração Pública Federal além de desmotivar a utilizaçãodo canal pelo cidadão. As denúncias cadastradas são provenientes de municípios presentesem todas as Unidades da Federação gerando assim um grande impacto em todoo território nacional. Esta pesquisa tem como objetivo elaborar uma prova de conceitopara um modelo para a triagem automática de denúncias na CGU, utilizando mineração de textos. Os melhores resultados foram alcançados utilizando classificação por rankingbaseada em Árvore de Huffman. Esta prova de conceito demonstrou a viabilidade deuma triagem de denúncias de forma automática na CGU, sem perda de qualidade emcomparação à triagem manual. / The Office of the Comptroller General (CGU) is the agency of the Federal Governmentin charge of assisting the President of the Republic in matters related to internal controlactivities, public audits, corrective and disciplinary measures, corruption prevention andcombating and coordinating ombudsman’s activities. Through a complaints link of theCGU site, citizens have access to a form to file their complaints. These complaints must bescreened and delivered to the coordination of CGU by subject. Nowadays the complaintsscreening is done manually and they are delivered to one of the 91 coordinating units ofCGU. This large amount of categories is more complex in automatic text classification.Considering the complaints storage on the database now and the arrival of new complaints,combined with the time spent on manual sorting, the timely analysis of the reportedoccurrences it becomes increasingly difficult. This context can cause financial losses toFederal Public Administration as well as discouraging the use of the channel by the citizen.Complaints registered origins are municipalities present in all Brazilian states, generatinga great impact on the entire national territory. This research intends to develop a proofof concept for an automatic model of complaints screening, using text mining. The bestresults were achieved using ranking based on the Huffman Tree algorithm. This proofof concept demonstrated the feasibility of automatical sorting without the loss of qualitycompared to manual sorting.

Dans cette thèse, nous étudions l'enveloppe convexe des arbres binaires à racine sur n feuilles.Ce sont les arbres de Huffman dont les feuilles sont labellisées par n caractères. à chaque arbre de Huffman T de n feuilles, nous associons un point xT , appelé point de Huffman, dans l'espace Qn où xT est le nombre d'arêtes du chemin reliant la feuille du ième caractère et la racine.L'enveloppe convexe des points de Huffman est appelé Huffmanoèdre. Les points extrêmes de ce polyèdre sont obtenus dans un premier temps en utilisant l'algorithme d'optimisation qui est l'algorithme de Huffman. Ensuite, nous décrivons des constructions de voisinages pour un point de Huffman donné. En particulier, une de ces constructions est principalement basée sur la construction des sommets adjacents du Permutoèdre. Puis, nous présentons une description partielle du Huffmanoèdre contenant en particulier une famille d'inégalités définissant des facettes dont les coefficients, une fois triés, forment une suite de Fibonacci. Cette description bien que partielle nous permet d'une part d'expliquer la plupart d'inégalités définissant des facettes du Huffmanoèdre jusqu'à la dimension 8, d'autre part de caractériser les arbres de Huffman les plus profonds, i.e. une caractérisation de tous les facettes ayant au moins un plus profond arbre de Huffman comme point extrême. La contribution principale de ce travail repose essentiellement sur les liens que nous établissons entre la construction des arbres et la génération des facettes / In this thesis, we study the convex hull of full binary trees of n leaves. There are the Huffman trees, the leaves of which are labeled by n characters. To each Huffman tree T of n leaves, we associate a point xT , called Huffman point, in the space Qn where xT i is the lengths of the path from the root node to the leaf node marked by the ith character. The convex hull of the Huffman points is called Huffmanhedron. The extreme points of the Huffmanhedron are first obtained by using the optimization algorithm which is the Huffman algorithm. Then, we describe neighbour constructions given a Huffman point x. In particular, one of these constructions is mainly based on the neighbour construction of the Permutahedron. Thereafter, we present a partial description of the Huffmanhedron particularly containing a family of inequalities-defining facets whose coeficients follows in some way the law of the well-known Fibonacci sequence. This description allows us, on the one hand, to explain the most of inequalities-defining facets of the Huffmanhedron up to the dimension 8, on the other hand, to characterize the Huffman deepest trees, i.e a linear characterization of all the facets containing at least a Huffman deepest tree as its extreme point. The main contribution of this work is essentially base on the link what we establish between the Huffman tree construction and the facet generation.

Statkraft är helägt av Norska staten och är Sveriges fjärde största elproducent. Detta examensarbete syftar till att ta fram en metod för att lösa hur Statkraft Sverige AB ska lagra mjukvarubackuper av sina lokalkontrollssystem. För närvarande finns det ingen homogen lagringsmetod för backuper på företaget och problemet som ska lösas i examensarbetet är hur man kan lagra backuper från ett flertal heterogena system på en gemensam lagringsplattform. I och med att de allra flesta hjälpsystem för konfigurering av styrdatorer (PLC) bygger på Microsoft DOS/Windows så är det relativt enkelt att överföra backuper till en gemensam plattform. För äldre hjälpmedel kan man dock tänka sig att virtualisera hjälpmedlen på en nyare PC-dator med exempelvis VMware för att undvika problem som kan uppstå med äldre hårdvara. Därefter kan man arkivera backuperna i ZIP-format som man kan lagra på en server. Fördelen med att använda sig av ZIP för arkivering är att man får en inbyggd integritetskontroll av backuperna då ZIP har inbyggd cyclic redundancy check (CRC) som använder sig av kontrollsummor för att kontrollera så att filerna är korrekta. Dessutom så får man endast en fil i jämförelse med många filer per backup om man inte använder sig av arkivering. Backuperna ska sedan lagras på en server som ligger inom företagets intranät/kontorsnät som endast behörig personal har tillgång till. Uppladdningen av filerna kan gå till på flera olika sätt, större backupfiler från PC-system kan laddas upp direkt via nätverket och dokumentationen uppdateras manuellt. Mindre backupfiler skulle dock kunna laddas upp genom en webbsida på intranätet där dokumentationen uppdateras automatiskt i samband med uppladdning. Lagringsutrymmet för båda dessa lösningar är dock detsamma så det går även att ladda upp mindre backuper manuellt genom nätverket. Med dessa lösningar har berörda tekniker tillgång till backuperna vart de än befinner sig så länge internetuppkoppling finns genom ett virtuellt privat nätverk (VPN) till företagets intranät/kontorsnät. / Statkraft is the fourth largest electricity producer in Sweden and is fully owned by the Norwegian state. This thesis aims to develop a method for solving how Statkraft Sweden AB will store software backups of their local control systems. Currently there is no uniform method of storage for backups in the company and the problem to be solved in the thesis is how to store backups from multiple heterogeneous systems on a single storage platform. Based on the fact that the vast majority of help systems for configuring Programmable Logic Controllers (PLC) is based on Microsoft DOS / Windows, it is relatively simple to transfer the backups to a common platform. With older help systems it is also possible to virtualize these help systems on newer PC-based computers with for example VMware instances to avoid issues that can arise with older hardware. You can then archive the backups in ZIP-format that can be stored on a server, the advantage of using ZIP-archiving is to get a built-in integrity check of backups as ZIP has built in cyclic redundancy check (CRC) that uses checksums to check that the files are correct. Additionally, you get only one file in comparison to many files per backup if you do not archive in for example ZIP-format. The backups are then stored on a server within the company intranet / office network that is restricted to authorized personnel. The upload of the files can be done in several different ways; large backup files from PC-systems can be uploaded directly via the network, and the documentation is updated manually. Smaller and incremental backup files could however be uploaded through a web page on the Intranet, where documentation is automatically updated during upload. The storage space for both of these solutions is the same so that it is also possible to upload smaller backups manually through the network. With these solutions, the technicians can access the backups wherever they are as long as an Internet connection is available thru a virtual private network (VPN) Connection to the company’s intranet/office network.

No description available.

The genome of an organism contains all hereditary information encoded in DNA.Genome databases are rapidly increasing. This increase in the amount of DNA data demands an increasing need to compress the DNA data in less space for faster transmission and research activities. General text compression algorithms don’t utilize the specific characteristics of a DNA sequence. There are various tools developed using different algorithms and approaches. Many of these tools include the implementation of Huffman encoding to incorporate the characteristics of DNA sequences. Huffman-based techniques center on the idea of selecting repeated sequences to form a skewed Huffman tree. The algorithm also lies around constructing multiple Huffman trees when encoding. These implementations have demonstrated an improvement in the compression ratios compared to the standard Huffman tree. This research suggests few improvements over one of these algorithms to select the repeat sequences to obtain better compression ratios.

En raison de l'expansion des données, les algorithmes de compression sont désormais cruciaux. Nous abordons ici le problème de trouver des algorithmes de compression optimaux par rapport à une source de Markov donnée. A cet effet, nous étendons l'algorithme de Huffman classique. Pour se faire premièrement on applique Huffman localement à chaque état de la source Markovienne, en donnant le résultat de l'efficacité obtenue pour cet algorithme. Mais pour bien approfondir et optimiser quasiment l'efficacité de l'algorithme, on donne un autre algorithme qui est toujours appliqué localement à chaque états de la source Markovienne, mais cette fois ci en codant les facteurs partant de ces états de la source Markovienne de sorte à ce que la probabilité du facteur soit une puissance de 1/2 (sachant que l'algorithme de Huffman est optimal si et seulement si tous les symboles à coder ont une probabilité puissance de 1/2). En perspective de ce chapitre on donne un autre algorithme (restreint à la compression de l'étoile) pour coder une expression à multiplicité, en attendant dans l'avenir à coder une expression complète / Due to the expansion of datas, compression algorithms are now crucial algorithms. We address here the problem of finding an optimal compression algorithm with respect to a given Markovian source. To this purpose, we extend the classical Huffman algorithm. The kernels are popular methods to measure the similarity between words for classication and learning. We generalize the definition of rational kernels in order to apply kernels to the comparison of languages. We study this generalization for factor and subsequence kerneland prove that these kernels are defined for parameters chosen in an appropriate interval. We give different methods to build weighted transducers which compute these kernels

En raison de l'expansion des données, les algorithmes de compression sont désormais cruciaux. Nous abordons ici le problème de trouver des algorithmes de compression optimaux par rapport à une source de Markov donnée. A cet effet, nous étendons l'algorithme de Huffman classique. Pour se faire premièrement on applique Huffman localement à chaque état de la source Markovienne, en donnant le résultat de l'efficacité obtenue pour cet algorithme. Mais pour bien approfondir et optimiser quasiment l'efficacité de l'algorithme, on donne un autre algorithme qui est toujours appliqué localement à chaque états de la source Markovienne, mais cette fois ci en codant les facteurs partant de ces états de la source Markovienne de sorte à ce que la probabilité du facteur soit une puissance de 1/2 (sachant que l'algorithme de Huffman est optimal si et seulement si tous les symboles à coder ont une probabilité puissance de 1/2). En perspective de ce chapitre on donne un autre algorithme (restreint à la compression de l'étoile) pour coder une expression à multiplicité, en attendant dans l'avenir à coder une expression complète / Due to the expansion of datas, compression algorithms are now crucial algorithms. We address here the problem of finding an optimal compression algorithm with respect to a given Markovian source. To this purpose, we extend the classical Huffman algorithm. The kernels are popular methods to measure the similarity between words for classication and learning. We generalize the definition of rational kernels in order to apply kernels to the comparison of languages. We study this generalization for factor and subsequence kerneland prove that these kernels are defined for parameters chosen in an appropriate interval. We give different methods to build weighted transducers which compute these kernels

<p>As integrated circuits get smaller, faster and can fit more functionality, more problems arise with wire delays and cross-talk. Especially when using global clock signals distributed over a large chip area. This thesis will briefly discuss a solution to this problem using the Globally Asynchronous Locally Synchronous (GALS) design path.</p><p>The goal of this thesis was to test the solution by modelling and partially implementing an MPEG-2 video decoder connected as a GALS system, using synchronous design tools. This includes design of the system in Simulink, implementing selected parts in VHDL and finally testing the connected parts on an FPGA. Presented in this thesis is the design and implementation of the system as well as theory on the MPEG-2 video decoding standard and a short analysis of the result.</p>