Título: | PREFIX CODES: ALGORITHMS AND BOUNDS | ||||||||||||
Autor: |
EDUARDO SANY LABER |
||||||||||||
Colaborador(es): |
RUY LUIZ MILIDIU - Orientador |
||||||||||||
Catalogação: | 26/JUN/2009 | Língua(s): | PORTUGUESE - BRAZIL |
||||||||||
Tipo: | TEXT | Subtipo: |
THESIS
![]() |
||||||||||
Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
||||||||||||
Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=13809&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=13809&idi=2 |
||||||||||||
DOI: | https://doi.org/10.17771/PUCRio.acad.13809 | ||||||||||||
Resumo: | |||||||||||||
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.
|
|||||||||||||
|