UNIVERSAL STRING MATCHING ENCODERS BY RECURRENCE OF STANDARDS FOR SOURCES WITH FINITE NUMBER OF STATES / CODIFICADORES UNIVERSAIS VIA RECORRÊNCIA DE PADRÕES PARA FONTES COM NÚMERO DE ESTADOS FINITO

AUTOR(ES)
DATA DE PUBLICAÇÃO

2000

RESUMO

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.

ASSUNTO(S)

codificacao de fonte source coding recurrence of standards codificacao universal universal codification recorrencia de padroes

ACESSO AO ARTIGO

Documentos Relacionados