Method and system for compressing data and a geographic database formed therewith and methods for use thereof in a navigation application program
First Claim
1. A data compression technique comprising:
- from a first position in an input stream of data characters, searching in a preceding portion of said input stream of data characters from said first position for a sequence of a plurality of data characters that matches a sequence of a plurality of data characters at said first position; and
at said first position, replacing the sequence of a plurality of data characters for which a matching sequence of a plurality of data characters was found in said preceding portion of said input stream with a reference to said matching sequence of a plurality of data characters in said preceding portion of said input stream;
wherein said reference comprises an offset from said first position to a position in said preceding portion of said input stream at which said matching sequence of a plurality of data characters is located and a size of said matching sequence.
4 Assignments
0 Petitions
Accused Products
Abstract
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.
-
Citations
29 Claims
-
1. A data compression technique comprising:
-
from a first position in an input stream of data characters, searching in a preceding portion of said input stream of data characters from said first position for a sequence of a plurality of data characters that matches a sequence of a plurality of data characters at said first position; and
at said first position, replacing the sequence of a plurality of data characters for which a matching sequence of a plurality of data characters was found in said preceding portion of said input stream with a reference to said matching sequence of a plurality of data characters in said preceding portion of said input stream;
wherein said reference comprises an offset from said first position to a position in said preceding portion of said input stream at which said matching sequence of a plurality of data characters is located and a size of said matching sequence. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method of compressing a geographic database comprising:
-
advancing through a portion of the geographic database;
identifying matching substrings of data in said portion; and
when a substring of data is encountered that matches a previous substring in said portion, replacing the substring with a substitution code, wherein said substitution code comprises a backwards offset from said position at which said substitution code replaces said substring to the previous substring.. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A method of forming a geographic database comprising:
-
separating a first plurality of data records into a plurality of groupings of data records, wherein each grouping includes a separate plurality of data records that are accessed together as a group when using the geographic database;
with respect to each of said groupings, identifying matching substrings of data within said grouping; and
when a substring of data is encountered at a position in a grouping that matches a previous substring in said grouping, replacing the substring with a substitution code. - View Dependent Claims (20, 21, 22, 23, 24)
-
-
25. A compression format for storing a collection of data on a medium, wherein said data are required to be decompressed to an uncompressed form in order to use the data for performing functions, the compression format comprising:
-
an arrangement of said collection of data wherein said collection is separated into a plurality parcels each of which includes a plurality of data items which form at least part of said collection, wherein said plurality of data items in each parcel are accessed together as a group in a given sequence; and
a plurality of substitution codes included among said arrangement of a plurality of data items, each of said plurality of substitution codes including an offset from a position in said arrangement of a plurality of data items at which said substitution code is located into a position sequentially backwards therefrom. - View Dependent Claims (26, 27)
-
-
28. A method for decompressing a compressed data stream comprising:
-
starting at a first end of the compressed data stream, advancing through a portion of the data stream until encountering a substitution code that indicates a substitution substring length and an offset backwards into said data stream toward said first end; and
forming an uncompressed output from said compressed data stream, wherein said uncompressed output comprises the portion of the data stream up to said substitution code and a substitution substring appended thereto, wherein said substitution substring corresponds to that part of said portion of said substitution substring length located at said offset from said substitution code within said portion. - View Dependent Claims (29)
-
Specification