A data compression method and system that include the substitution of a
substring of data characters located at a first position in a stream of
data characters with a substitution code. The substitution code includes a
reference to a previous position in the stream of data characters at which
is located a substring of data characters that matches the substring of
data characters which are being substituted located at the first position.
The substitution code also includes an indication of the size of the
substituted substring. The reference in the substitution code is a
backwards offset to the previous position relative to the first position.
According to a further aspect, Huffman encoding can be applied to the
backward offsets, the substring lengths, the consecutive literal character
lengths, and the literal characters themselves to reduce the data
requirement size. In an application of the data compression method to
geographic data that has been organized to facilitate access and use by a
navigation application program, the Huffman tree(s) for decoding the
encoded characters are stored in a separate portion of the database from
portions that include the data that have been compressed using the Huffman
coding, thereby facilitating the use of the same Huffman tree(s) for more
than one portion of the data records.
