An on-line variable-length binary encoding of text

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.