Análise da Partição Ótima do LZ78

Marcelo Da Silva Pinho, Weiler A. Finamore

DOI: 10.14209/sbrt.2001.06300038

Evento: XIX Simpósio Brasileiro de Telecomunicações (SBrT2001)

Keywords: codificação de fonte codificação universal compressão de dados codificadores via recorrência de padrões

Abstract

"O Lempel-Ziv’78 (LZ78) é um codificador universal que tem inspirado vários esquemas práticos de compressão de dados. Embora ele seja assintoticamente ótimo, i.e., sua taxa de compressão converge para a entropia da fonte, o procedimento de partição da seqüência de entrada não é ótimo. Encontrar a partição ótima de uma seqüência de entrada para o LZ78 é um problema NP-completo e por esta razão pouco se sabe sobre o ganho que uma partição mais eficiente produziria no LZ78. Neste trabalho, a partição ótima do LZ78 é analisada. É apresentado um resultado que mostra que o ganho da partição ótima não é significativo, no sentido de que o número de segmentos produzidos por esta partição tem o mesmo comportamento assintótico do número de segmentos produzidos pela partição original do LZ78. Este trabalho ainda apresenta um algoritmo que calcula um limitante inferior para o número de segmentos gerados pela partição ótima, para uma seqüência de entrada arbitrária. Este algoritmo é utilizado para medir o desempenho de dois métodos de partição diferentes."

Download