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 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.
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.
61 Citations
16 Claims
-
1. 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 (2, 3)
-
-
4. 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 (5)
after encountering said substitution code, continuing to advance through the data stream to a second end thereof, wherein said second end is opposite from said first end; and
during said step of continuing to advance, as each substitution code is encountered, wherein each substitution code indicates a substitution substring length and an offset backwards into said data stream toward said first end, continuing to form the uncompressed output from said compressed data stream, wherein said uncompressed output comprises the portion of the data stream up to each substitution code and a substitution substring appended thereto, wherein each 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.
-
-
6. A method for using data from a geographic database with a navigation application, wherein the data represent individual segments of roads, and wherein the geographic database includes portions that are in a compressed format, the method comprising:
-
with a software application that provides a navigation-related feature for automobile travel on said roads, identifying a portion of the geographic database that contains data needed for the navigation application;
accessing the portion of the geographic database that had been identified;
decompressing the portion that had been accessed thereby forming an uncompressed version of the portion that had been accessed; and
using the decompressed version of the portion of the geographic database in the navigation application. - View Dependent Claims (7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
advancing through the portion of the database that had been accessed until encountering a substitution code that indicates a substring length and a backwards offset into the portion of the database that had been accessed; and
in the portion of the database being accessed, replacing the substitution code with a substring having the substring length and located at the backwards offset thereby forming the decompressed version of the portion of the geographic database that had been accessed.
-
-
8. The method of claim 6 wherein the step of decompressing further comprises:
replacing Huffman codes in the portion of the geographic database that had been accessed with corresponding decoded representations of the Huffman codes thereby forming the decompressed version of the portion of the geographic database that had been assessed.
-
9. The method of claim 6 wherein the step of accessing obtains the portion of the geographic database from a physical medium upon which the geographic database is stored.
-
10. The method of claim 6 wherein the step of accessing obtains the portion of the geographic database via a wireless communications link.
-
11. The method of claim 6 further comprising:
prior to the step of identifying, using an initialization routine to determine that the geographic database used by the navigation system contains compressed data.
-
12. The method of claim 6 wherein the step of identifying is performed using an index.
-
13. The method of claim 6 further comprising:
after the step of accessing, storing the portion of the geographic database in a cache along with other portions of the geographic database that have been accessed.
-
14. The method of claim 6 wherein the step of decompressing further comprises:
-
(a) starting at a top of the portion, decoding an initial code, wherein the initial code is a Huffman code that, when decoded, indicates an initial run length count for literals;
(b) decoding a subsequent number of Huffman codes as literals, wherein the subsequent number corresponds to the initial run length count indicated by the decoded initial code;
after decoding the subsequent number of Huffman codes, (c) decoding a next Huffman code, wherein the next Huffman code indicates whether subsequent codes are literals or a substitution code;
(d) if the next Huffman code indicates that subsequent Huffman codes are literals, decoding a subsequent number of Huffman codes as literals, but (e) if the next Huffman code indicates that a subsequent Huffman code is a substitution code, decoding the subsequent Huffman code as a substitution code, wherein the decoded substitution code indicates a substitution string length and an offset, and then replacing the substitution code with a string which is identical to the string having a length corresponding to the substitution string length and which is located at the offset into that part of the portion that has already been decoded; and
then(f) performing steps (c)-(e) until a bottom of the portion is reached.
-
-
15. The method of claim 6 wherein the step of decompressing further comprises:
using a Huffman tree located in another portion of the geographic database to decode Huffman codes included in the portion of the geographic database being decompressed.
-
16. The method of claim 6 wherein the portion of the geographic database contains data that represent geographic features located in a separate one of a plurality of rectangular areas into which a region represented by the geographic database is divided.
Specification