An Efficient Algorithm for Almost Instantaneous VF Code Using Multiplexed Parse Tree

Almost Instantaneous VF code proposed by Yamamoto and Yokoo in 2001, which is one of the variable-length-to-fixed-length codes, uses a set of parse trees and achieves a good compression ratio. However, it needs much time and space for both encoding and decoding than an ordinary VF code does. In this...

Full description

Saved in:
Bibliographic Details
Main Authors: Yoshida, Satoshi, Kida, Takuya
Format: Conference Proceeding
Language:English
Subjects:
AIVF code
compression pattern matching
Decoding
Encoding
Natural languages
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Almost Instantaneous VF code proposed by Yamamoto and Yokoo in 2001, which is one of the variable-length-to-fixed-length codes, uses a set of parse trees and achieves a good compression ratio. However, it needs much time and space for both encoding and decoding than an ordinary VF code does. In this paper, we proved that we can multiplex the set of parse trees into a compact single tree and simulate the original encoding and decoding procedures. Our technique reduces the total number of nodes into O(2 l k - k 2 ), while it is originally O(2 l k), where l and k are the codeword length and the alphabet size, respectively. The experimental results showed that we could encode and decode over three times faster for natural language texts by using this technique.
ISSN:1068-0314
2375-0359
DOI:10.1109/DCC.2010.27