Method and system for compressing data and a geographic database formed therewith and methods for use thereof in a navigation application program

• US 6,600,841 B1
• Filed: 03/22/2002
• Issued: 07/29/2003
• Est. Priority Date: 09/17/1998
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Meek, James A., Friederich, Matthew
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US10/104,947
• Time in Patent Office: 494 Days
• Field of Search: 382/173, 382/232, 382/245, 382/246, 382/305, 382/233, 701/200, 701/201, 701/202, 701/203, 701/205, 701/206, 701/208, 701/210, 701/213, 701/214, 707/1-4, 707/100, 707/101, 707/102, 341/51, 341/55, 341/67, 340/995
• US Class Current: 382/305
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. The method of claim 4 further comprising the step of:

storing said index in said geographic database.

6. The method of claim 4 further comprising the step of:

storing said index in a global portion of said geographic database.