[pt] Os codificadores universais via recorrência de padrões
surgiram nos anos 70, quando foram propostos os
codificadores lz77 e lz78. Devido a baixa complexidade
computacional e ao bom desempenho, quando aplicados na
compressão de arquivos de dados, estes codificadores se
tornaram extremamente populares. Embora estes
codificadores sejam universais, i.e., possuam taxas de
compressão que convergem para entropia, recentemente foi
mostrado que as taxas de compressão não convergem da forma
mais rápida possível, nem mesmo para a classe de fontes
sem memória. A redundância de um codificador universal C,
dada por R, mede a rapidez com que a taxa de compressão
converge para a entropia. Para fontes com número de
estados finito, enquanto os melhores resultados de
codificadores universais via recorrência de padrões
apresentam uma redundância da ordem de 1/{log n}, existem
codificadores que atingem uma redundancia de {log n} /n.
Portanto, os codificadores via recorrência de padrões não
são ótimos. Embora seja conhecido codificadores ótimos
segundo o critério da redundância, tais codificadores
possuem uma alta complexidade computacional e são pouco
úteis na prática. Dentre os codificadores via recorrência
de padrões, o codificador lz78 possui uma das mais baixas
redundâncias para a classe de fontes com número de estados
finito. De fato, não existe outro codificador desta
classe, tal que a redundância seja melhor que a do lz78.
Tomando como base o lz78, este trabalho propõe novas
técnicas para acelerar a convergência da taxa de
compressão (diminuir a redundância) dos codificadores
universais via recorrência de padrões, para fontes com
número de estados finito. Estas técnicas dão origem a
novas versões do lz78. As redundâncias das novas versões
são estabelecidas, considerando a classe de fontes com
número de estados finito. Estas versões são aplicadas na
compressão de arquivos de dados, e os resultados obtidos
são comparados com os resultados de versões anteriores. / [en] The string matching encoders were proposed about 20 years
ago, when the lz77 and lz78 were introduced. They became
extremely popular because of the relationship between
their low complexity and their good performance. Although
these encoders are universal, that is, their compression
rates converge to the source entropy, it was shown,
recently, that those rates do not converge as fast as
possible, even for the class of memoryless source. The
redundancy of an unversal encoder C, denoted by Rc,
measures how fast the compression rate converge to the
entropy. In the class of Finite State Machine (FSM)
source, while the best result of the string matching
encoders is O 1/ {log n}, there are encoders which achieve
a redundancy of O {log n}/n. Therefore, the string
matching encoders are not optimal. Even though optimal
encoders are known, in general, those encoders have a high
complexity and are not useful in practice. Considering the
class of string matching encoders, the lz78 has one of the
best results over the class of FSM source. In fact, there
is no encoder based on the string matching, which archives
a better redundancy. This work makes use of the lz78
encoder to propose new techniques to improve the
performance of sting matching encoders over the class of
FSM. These techniques bring up new versions of the lz78.
For the class of FSM, the redundancies of this versions
are stablished. These versions are used to compress data
files, and their perfoermances are compared to the
performances of older versions.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:7555 |
| Date | 01 December 2005 |
| Creators | MARCELO DA SILVA PINHO |
| Contributors | WEILER ALVES FINAMORE, WEILER ALVES FINAMORE |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.002 seconds