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.
A method of forming a geographic database comprising: separating a first plurality of data records into a plurality of groupings of data records, wherein the data records represent individual segments of roads located in a geographic region, and further 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 thereby forming the geographic database that includes a plurality of groupings each of which includes substitution codes that occupy the prior substrings referenced thereby.
Claim 2
Independent Claim
129 words
A method of forming a geographic database comprising: separating a first plurality of data records into a plurality of groupings of data records, wherein the data records represent individual segments of roads located in a geographic region, and further 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 thereby forming the geographic database that includes a plurality of groupings each of which includes substitution codes that occupy the prior substrings referenced thereby.
Claim 3
Dependent Claim
25 words
The method of claim 1 wherein each substitution code comprises a backwards offset from the position of said substitution code to said previous matching substring.
Claim 4
Dependent Claim
101 words
The method of claim 1 further comprising: prior to separating at least the first plurality of data records into a plurality of groupings, forming separate types of data records, wherein each type includes a separate plurality of data records; then, with respect to each type, separating the plurality of data records within the type into a plurality of groupings, each of which includes a separate plurality of data records of the given type which are accessed together as a group; and then further within each of said groupings, identifying matching substrings of data and replacing the substring with a substitution code.
Claim 5
Dependent Claim
54 words
The method of claim 1 further comprising the step of: determining character occurrence frequencies within at least part of said geographic database; forming an index that associates characters with coded representations thereof based upon said occurrence frequencies; and replacing those characters within said at least part of said geographic database with said coded representations.
Claim 6
Dependent Claim
17 words
The method of claim 4 further comprising the step of: storing said index in said geographic database.
Claim 7
Dependent Claim
21 words
The method of claim 4 further comprising the step of: storing said index in a global portion of said geographic database.