[pt] Mesmo com a evolução dos dispositivos de armazenamento e
comunicação, mantém-se crescente a demanda por mecanismos
de compressão de dados mais eficientes. Entre os
compressores baseados na freqüência de símbolos, destacam -
se os códigos livres de prefixo, que são executados por
vários métodos compostos de diferentes algoritmos e também
apresentam bom desempenho em uso isolado.
Muitas pesquisas trouxeram maior eficiência aos códigos de
prefixo, centradas, sobretudo, na redução do espaço de
memória necessário e tempo gasto durante a descompressão. O
presente trabalho abrange códigos de prefixos e respectivas
técnicas de descompressão visando propor um novo
codificador, o compressor LTL, que utiliza códigos com
restrição de comprimento para reduzir o espaço de memória
da tabela Look-up, eficiente método de decodificação.
Devido ao uso de códigos restritos, é admitido um pequeno
decréscimo nas taxas de compressão para possibilitar uma
decodificação mais rápida. Os resultados obtidos indicam
perda de compressão inferior a 11 por cento para um modelo baseado
em caracteres, com velocidade média de decodificação cinco
vezes maior que a de um decodificador canônico. Embora,
para um modelo de palavras, o ganho médio de velocidade
seja de 3,5, constata-se que, quando o número de símbolos é
muito grande, o tamanho da tabela look-up impossibilita uma
utilização eficiente da memória cache. Assim, o LTL é
indicado para substituir quaisquer códigos de prefixo
baseados em caracteres cuja aplicação requer agilidade no
processo de descompressão. / [en] Even with the evolution of communication and storage
devices, the use of complex data structures, like video and
hypermedia documents, keeps increasing the demand for
efficient data compression mechanisms. Prefix codes are one
of the most known compressors, since they are executed by
some compression methods that group different algorithms,
besides presenting a good performance when used separately.
A lot of approaches have been tried to improve the
decoding speed of these codes. One major reason is that
files are compressed and updated just a few times, whereas
they have to be decompressed each time they are accessed.
This work presents prefix codes and their decoding
techniques in order to introduce a new coding scheme. In
this scheme length-restricted codes are used to control the
space requirements of the Look-up table, an efficient and
fast prefix codes decoding method. Since restricted
codewords are used, a small loss of compression efficiency
is admitted. Empirical experiments indicate that this
loss in the coded text is smaller than 11 percent if a character
based model is used, and the observed average decoding
speed is five times faster than the one for canonical
codes. For a word based model, the average decoding speed
is 3,5 times faster than a canonical decoder, but it
decreases when a large number of symbols is used. Hence,
this method is very suitable for applications where a
character based model is used and extremely fast decoding
is mandatory.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:4117 |
| Date | 12 November 2003 |
| Creators | LORENZA LEAO OLIVEIRA MORENO |
| Contributors | RUY LUIZ MILIDIU |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0023 seconds