CÓDIGOS DE PREFIXO: ALGORITMOS E COTAS

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)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