Patent Publication Number: US-6035299-A

Title: Mapping system with house number representation

Description:
FIELD OF THE INVENTION 
     The present invention relates to a mapping and to a vehicle navigation system and, more particularly, to a method for storing house numbers for use in a mapping/navigation system. 
     DESCRIPTION OF THE RELATED ART 
     Vehicle navigation systems are well known, see e.g. Yamada et al., U.S. Pat. No. 4,926,336; Link et al., U.S. Pat. No. 5,270,937; and Ichikawa, U.S. Pat. No. 5,410,485, all incorporated by reference. Such navigation systems generally perform two major functions. One function is to identify the optimum route from the present location to a desired destination, a process which is generally referred to as route guidance. The other function is to display a map of both the present location and of the identified route. 
     A database containing a digitized map of the road network, house numbers, etc. is provided to a vehicle navigation system. To be useful, such a database must be flexible enough so as to allow for inclusion of all address numbering systems that have been adopted by different states. One such address numbering system, common in most of the United States, calls for house numbers that contain numeric characters only and have a predefined range of 0 to 999999. In other locations a hyphen or an alphabetic character is disposed among numeric characters to represent a house number. Three such cases exist: 
     Case 1 
     An alphabetic character E, N, S or W is disposed among numeric characters. e.g. 3E199, 17N017, 16S001 and 5W200. 
     Case 2 
     A hyphen is disposed among numeric characters. e.g. 10-250, 17-190. 
     Case 3 
     A number of leading zeros is disposed before a hyphen and/or a number of leading zeroes is disposed after a hyphen. e.g. 170-1, 170-001 and 170-002. 
     A data structure used to generate a database of house numbers for use in a mapping system must, therefore, be able to encompass all possible permutations that a house numbering scheme which uses both numeric and alphabetic characters may generate. One such known data structure 100 (devised by SEI Information Technologies, Incorporated) is illustrated in FIG. 1. As can be seen from FIG. 1, depending on the operating system and the type of computer system used, data structure HOUSE --  NUMBER requires from 11 to 24 bytes of data, to store alphanumeric house numbers. Hereinafter, a byte refers to a stream of 8 binary digits; an alphanumeric number refers to a string of numeric, alphabetic as well as special printable characters and a numeric number refers to a string of numeric-only characters. Examples of special printable characters include, &#34;/&#34;, &#34;-&#34;. Examples of numeric numbers include 136457 and 23988. Examples of alphanumeric numbers include 312W786, 017-007. Data structure 100, however, is inadequate for use in a navigation system for the reasons that follow. 
     First, many mapping/navigation systems store house numbers in a memory unit that is only four bytes wide and, as such, must be adapted in order to accommodate the typically twelve bytes wide data structure of FIG. 1. Consequently, data structure 100 is not viable for use in many mapping/vehicle navigation systems. 
     Second, data structure 100 requires an excessively large memory space to store the needed information. 
     Third, data structure 100 does not lend itself to an efficient sorting process. Up to 5 relational operations may be required to complete the sorting of data which have been represented according to data structure 100. Relational operations are well known in the art and comprise the following set 
     &#34;&lt;&#34; designating the operation &#34;less than&#34; 
     &#34;&lt;=&#34; designating the operation &#34;less than or equal to&#34; 
     &#34;&gt;&#34; designating the operation &#34;greater than&#34; 
     &#34;&gt;=&#34; designating the operation &#34;greater than or equal to&#34; 
     &#34;=&#34; designating the operation &#34;equal to&#34; 
     FIG. 2 illustrates the steps required to sort through alphanumeric numbers 100-01 and 100-1 according to data structure 100. In step 1, the sorting routine determines whether the house numbers are numeric or alphanumeric. An alphabetic character present in an alphanumeric number is identified in step 2. In step 3 and 4 the numeric characters preceding and succeeding the alphabetic character are identified respectively. Leading zeroes succeeding an alphabetic character are ignored in step 4. Finally, in step 5, the number of numeric characters, including the number of leading zeroes, succeeding the alphabetic character are determined to complete the sorting process. 
     Fourth, data structure 100 is not backward compatible with numeric numbering systems. Consequently, data structure 100 is ineffective in representing house numbers which contain numeric characters only. 
     Fifth, data structure 100 lacks the capability to represent leading zeroes where they precede any alphabetic and numeric characters. For example, the two leading zeroes appearing before numeric character &#34;1&#34; in number 001-007 cannot be represented by data structure 100. 
     SUMMARY 
     In accordance with the present invention, a data structure which is four bytes (32 bits) stores and represents alphanumeric house numbers for use in a mapping system for e.g. a vehicle navigation system. (&#34;House number&#34; here means generally numerical addresses.) 
     Bit 31 of the data structure designates the presence or the absence of an alphabetic/printable character in a house number. Bits 30-28 provide additional information about the possible type of non-numeric character used in a house number. If the bit stream defined by bit positions 30-28 is either &#34;000&#34; or &#34;100&#34; or 101&#34; or &#34;110&#34; or &#34;111&#34;, then bits 27-14 represent the numeric portion of a house number preceding the alphabetic character, bits 13-4 represent the numeric portion of a house number succeeding the alphabetic character, bits 3-2 represent leading zeroes disposed before any numeric character preceding an alphabetic character and bits 1-0 represent leading zeroes disposed after an alphabetic character and before a succeeding numeric character. If the bit stream defined by bit positions 30-28 is &#34;001&#34;, then bit 27 identifies whether the first character of a house number is numeric or alphabetic, bits 26-22 identify the alphabetic character used in a house number, bits 21-12 represent house numbers larger than 999 or represent characters other than the alphabetic characters, bits 11-2 represent the numeric portion of a house number and bits 1-0 represent leading zeroes. 
     The data structure requires the same field size as that used to represent numeric house numbers and, as such, is backwards compatible with the memory unit of many vehicle navigation systems. Moreover, the structure requires only one relational operation to perform a sorting of numbers. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 defines a known data structure for the array variable HOUSE --  NUMBER, used for representing and storing alphanumeric house numbers. 
     FIG. 2 illustrates the steps necessary to resolve the sorting hierarchy of the array members 100-01 and 100-1 of the array variable HOUSE --  NUMBER as defined in FIG. 1. 
    
    
     DETAILED DESCRIPTION 
     The present invention provides a bit-packed method of storing and representing a substantial combinations of house numbers of the type used in the United States, using an unsigned integer data field which is only four bytes wide. The data structure in accordance with the present invention is described below. 
     Bit 31 
     This is the most significant bit and is used to indicate whether a house number includes a non-numeric character. 
     0=House number includes only numeric characters 
     1=House number includes alphanumeric characters 
     Bits 30-28 
     These three bits identify the non-numeric character that is used in the house numbering system, according to the following table: 
     
         ______________________________________                                    
Bit 30    Bit 29  Bit 28      Numeric Character                           
______________________________________                                    
0         0       0                                                       
(hyphen)                                                                  
0         0       1           *see the definition                         
                              below                                       
0         1       0           undefined                                   
0         1       1           undefined                                   
1         0       0           E                                           
1         0       1           N                                           
1         1       0           S                                           
1         1       1           W                                           
______________________________________                                    
 *The bit stream &#34;001&#34; in bit positions 30-28, respectively, represents   
 house numbers that consist of either an alphabetic character succeeded by
 up to three numeric characters, e.g. A7, G001 or an alphabetic character 
 that is preceded by up to three numeric characters, e.g. 7A, 002G.       
 Hereinafter a house number with bit stream &#34;110&#34; in bit positions 30-28 i
 referred to as a KC type and house numbers with bit streams &#34;000&#34;, &#34;100&#34;,
 &#34;101&#34;, &#34;110 # or &#34;111&#34; in bit positions 30-28 are referred to as a nonKC 
 type. Bits 27 through 0 constitute different meanings depending on whethe
 a house number is of a KC type as defined above. In what follows the     
 representation of bits 27-0 are divided in two groups depending on whethe
 a house number is of a KC or a nonKC type.                               
 
    
     KC TYPE 
     A &#34;1&#34; at bit 27 indicates that a house number begins with an alphabetic character and a &#34;0&#34; at bit 27 indicates that a house number begins with a numeric character. 
     Bits 26-22 
     These five bits determine the alphabetic character used in a house number according to the following table. 
     
         ______________________________________                                    
Bits 26-22     Character                                                  
______________________________________                                    
00000          undefined                                                  
00001          A                                                          
00010          B                                                          
00011          C                                                          
00100          D                                                          
00101          E                                                          
00110          F                                                          
00111          G                                                          
01000          H                                                          
01001          I                                                          
01010          J                                                          
01011          K                                                          
01100          L                                                          
01101          M                                                          
01110          N                                                          
01111          O                                                          
10000          P                                                          
10001          Q                                                          
10010          R                                                          
10011          S                                                          
10100          T                                                          
10101          U                                                          
10110          V                                                          
10111          W                                                          
11000          X                                                          
11001          Y                                                          
11010          Z                                                          
11011-11111    Undefined                                                  
______________________________________                                    
 
    
     Bits 21-12 
     These ten bits are currently not utilized and are set to zero. It is reserved for representing numbers greater than 999 and for representing other non-numeric characters. 
     Bits 11-2 
     These ten bits represent numeric characters present in a house number. 
     Bits 1-0 
     These two bits represent the number of leading zeroes preceding any numeric character according to the following table: 
     
         ______________________________________                                    
Bit 3    Bit 2          result                                            
______________________________________                                    
0        0              no    leading zeroes                              
0        1              1     leading zero                                
1        0              2     leading zeroes                              
1        1              3     leading zeroes                              
______________________________________                                    
 
    
     Bits 27-14 
     These fourteen bits represent numeric characters preceding an alphabetic character. 
     Bits 13-4 
     These ten bits represent numeric characters succeeding an alphabetic character. 
     Bits 3-2 
     These two bits represent the leading zeroes disposed before any numeric character preceding an alphabetic according to the following table: 
     
         ______________________________________                                    
Bit 3    Bit 2          result                                            
______________________________________                                    
0        0              no    leading zeroes                              
0        1              1     leading zero                                
1        0              2     leading zeroes                              
1        1              3     leading zeroes                              
______________________________________                                    
 
    
     Bits 1-0 
     These two bits represent the leading zeroes disposed after an alphabetic character and before a succeeding numeric character according to the following table: 
     
         ______________________________________                                    
Bit 1    Bit 0          result                                            
______________________________________                                    
0        0              no    leading zeroes                              
0        1              1     leading zero                                
1        0              2     leading zeroes                              
1        1              3     leading zeroes                              
______________________________________                                    
 
    
     The data structure, in accordance with the present invention, advantageously requires a substantially smaller amount of memory space to store an alphanumeric house number than those of the prior art. 
     Another advantage of the data structure, in accordance with the present invention, is that it uses the same number of data bytes as those used to represent numeric house numbers and, as such, maintains compatibility with the memory unit of many vehicle navigation systems which can only process data that is four bytes wide. 
     Another advantage of the data structure, in accordance with the present invention, is that it requires only one relational operation to perform a sorting of numbers. The thirty two stream of bits of any given alphanumeric number are evaluated according to their positional dependence to determine their binary value and are compared to those of other numbers to determine the relative positions of the numbers in a hierarchical system. In other words, the magnitude of each number is compared to those of others to resolve the sorting hierarchy. For example, suppose that the following alphanumeric numbers are to be sorted in an increasing order: 
     
         ______________________________________                                    
             G009                                                         
              4-107                                                       
             11E010                                                       
             100-007                                                      
             7A                                                           
             1040                                                         
              11-170                                                      
______________________________________                                    
 
    
     A one step application of a relational operation when applied to a binary representation of the above numbers, in accordance with the data structure of the present invention, will give rise to the following sorted results based on the binary values of the numbers: 
     
         ______________________________________                                    
             1040                                                         
              4-107                                                       
              11-170                                                      
             100-007                                                      
             7A                                                           
             G009                                                         
             114E010                                                      
______________________________________                                    
 
    
     Another advantage of the data structure, in accordance with the present invention, is that it is capable of representing alphanumeric house numbers of up to 8 characters. As was discussed earlier, in a non-KC type house numbers, bits 27-4, represent numeric characters positioned on either side of an alphabetic character. The 14 bits preceding an alphabetic character allow representation of all numbers up to and including 16,383, and the 10 bits succeeding an alphabetic character allow representation of all numbers up to and including 1,023. Adding the alphabetic character represented by bits 30-28, excluding any leading zeroes, it becomes evident that house numbers of up to 8 characters in length may be represented with the data structure, in accordance with the present invention. Including the 6 leading zeroes, up to 14 characters may be stored and represented using the data structure, in accordance with the present invention. 
     This disclosure is illustrative and not limiting; further modification will be apparent to one skilled in the art in light of this disclosure and are intended to fall within the scope of the appended claims.