An on-line variable-length binary encoding of text

TitleAn on-line variable-length binary encoding of text
Publication TypeJournal Articles
Year of Publication1996
AuthorsAcharya T, JaJa JF
JournalInformation Sciences
Pagination1 - 22
Date Published1996/10//
ISBN Number0020-0255

We present a methodology for on-line variable-length binary encoding of a dynamically growing set of integers. Our encoding maintains the prefix property that enables unique decoding of a string of integers from the set. In order to develop the formalism of this on-line binary encoding, we define a unique binary tree data structure called the “phase in binary tree.” To show the utility of this on-line variable-length binary encoding, we apply this methodology to encode the pointers generated by the LZW algorithm. The experimental results obtained illustrate the superior performance of our algorithm compared to the most widely used algorithms. This on-line variable-length binary encoding can be applied in other dictionary-based text compression schemes as well to effectively encode the output pointers to enhance the compression ratio.