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

• US 6,393,149 B2
• Filed: 09/17/1998
• Issued: 05/21/2002
• 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): Boudreau, Leo
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US09/153,996
• Publication Number:
  US 20010043745A1
• Time in Patent Office: 1,342 Days
• Field of Search: 382/232, 382/233, 382/245, 382/246, 382/305, 382/239, 382/173, 341/51, 341/55, 341/67, 701/200, 701/201-215, 701/23, 701/25, 701/26, 701/211, 707/1-4, 707/100, 707/101, 707/102, 340/995
• US Class Current: 382/173
• 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 used in an automobile navigation system, wherein the geographic database includes data entities that represent individual road segments that form a road network upon which an automobile that uses the automobile navigation system travels, the method comprising:

providing an initial collection of data entities that represent road segments that form the road network;

separating the initial collection of data entities into a plurality of groupings, wherein each of the groupings includes data entities that represent road segments located in a separate rectangular area and further wherein each of the groupings has a data size which is larger than a predetermined target size;

applying a compression method to each of the groupings so that each of the groupings has a data size which is not greater than the predetermined target size; and

storing the groupings to form the geographic database.

2. The method of claim 1 wherein the compression method comprises:

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 thereby forming a compressed version of the portion of the geographic database that includes substitution codes that occupy less space than the prior substrings referenced thereby.

3. The method of claim 2 wherein said substitution code further comprises a data component that indicates the length of the matching substring.

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

forming a compressed version of said geographic database that includes substitution codes replacing substrings of data for which matching substrings were identified.

5. The method of claim 4 further comprising:

prior to forming a compressed version of the geographic database, inserting literal length codes in at least said portion of said geographic database, wherein each of said literal length codes indicates a number of immediately following consecutive characters that are not substitution codes.

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

replacing literal length codes with Huffman encoded representations thereof.

7. The method of claim 2 wherein said geographic database is comprised of data records that represent physical features in a geographic region and wherein the method further comprises the step of:

separating said geographic database into a plurality of parcels wherein each parcel includes a plurality of data records, wherein the pluralities of data records in the plurality of parcels together comprise the geographic database, and wherein each of said plurality of parcels comprises a separate portion of the geographic database which is examined to find matching substrings.

8. The method of claim 7 wherein a previous matching substring is constrained to occur within the same parcel as the substitution code that refers thereto.

9. The method of claim 2 further comprising the step of:

replacing literal characters in said portion with Huffman codes.

10. The method of claim 2 further comprising the step of:

replacing backwards offsets with Huffman codes.

11. The method of claim 2 further comprising the step of:

replacing data components that indicate lengths of matching substrings with Huffman codes.

12. The method of claim 2 further comprising the step of:

encoding characters in said portion of the geographic database with compressed representations thereof; and

storing an index in another portion of the database apart from the portion in which substrings were replaced by substitution codes, wherein said index associates each of said encoded characters with said compressed representations.