Árvores Pares: Um Esquema para Detecção de Erros em Árvores Tipo Huffman
Autores
|
4564 |
416,6,221
|
|
|
4565 |
416,6,221
|
|
|
4566 |
416,6,221
|
Informações:
Publicações do PESC
Árvores pares correspondem a códigos de prefixos baseados em Huffman, onde todas as codificações têm paridade par. Esses códigos têm a propriedade de detectar a ocorrência de um número ímpar de erros de 1-bit em uma mensagem codificada. Sua definição foi motivada por um problema proposto por Hamming, em 1980. Neste trabalho caracterizamos árvores pares ótimas considerando duas situações: probabilidades uniformes e probabilidades arbitrárias. Árvores pares ótimas podem ser construídas por um algoritmo O(n^3) em tempo, ao passo que códigos quase-ótimos podem ser construídos por uma heurística O(n log n), cuja árvore resultante tem custo aproximadamente 5% maior que a correspondente árvore de Huffman, para grande número de símbolos. É desenvolvido um modelo probabilístico para avaliar a capacidade de detecção de erros de árvores pares e são apresentados resultados experimentais com a compressão de vários conjuntos de dados, incluindo linguagem natural. Finalmente, árvores pares são estendidas para árvores alfa-pares , que podem ter um aumento expressivo na capacidade de detecção de erros, baseado em um parâmetro alfa. É também dado um algoritmo para obter árvores alfa-pares ótimas e resultados experimentais com essas árvores.
Even trees correspond to Huffman-based prefix codes where a11 encodings have even parity. They have the property of being able to detect the occurrence of an odd number of I-bit errors introduced in a coded message. Its definition was motivated by a problem posed by Hamming in 1980. In this work we characterize optimal even trees considering two situations: uniform probabilities and arbitrary probabilities. Optimal even trees can be constructed by an O(n3) time algorithm, whereas nearly optimal even codes can be constructed by an O(n1ogn) heuristics whose resulting tree has a cost in practice 5% greater than the cost of the corresponding Huffman tree, for a large number of symbols. It is developed a probabilistic model to evaluate the error detection capability of even trees. The work includes experimental results with the compression of different sets of data, including natural language. Finally, even trees are extended to a-even trees, that can have an increased capacity of error detection, based on a parameter a. It is also given an algorithm to obtain optimal a-even trees and various experimental results with these trees.