Method of inputting name

[0002] 1. Field of the Invention

[0003] The present invention relates to a method of inputting a name and, more particularly, to a method of inputting one of predetermined names through a key pad input image.

[0004] 2. Description of the Related Art

[0005] In a navigation apparatus provided in a motor vehicle or the like to perform vehicle travel guidance to a selected destination, the current position of the vehicle is detected and map data about places around the vehicle position is read out from a map storage medium (e.g., a compact disc read only memory (CD-ROM) or a digital versatile disc (DVD)) to display a map on a display screen with a vehicle position mark superposed on the corresponding portion of the map. As the vehicle travels and the current position changes, the vehicle position mark on the screen is moved or the map is scrolled while the vehicle position mark is fixed at a predetermined position, e.g., at a center of the screen, thereby enabling a driver to have map information at a glance about places around the vehicle position.

[0006] Such an on-vehicle navigation apparatus has a function of inputting a name of a place or a point formed of letters of, for example, the Japanese or English language presented in the order of the kana syllabary or in alphabetical order, and displaying a map containing the point corresponding to the input name. To input a point name, a key pad input image (letter pallet) formed of kana letters or alphabetical letters is displayed on a monitor screen in the order of the kana syllabary or in alphabetical order, and necessary letters are successively designated in the displayed letters to be input.

[0007] The function of displaying a map showing places around a selected point by only inputting a name of the point based on this place input method is convenient. However, in the process of inputting a point name from the letters in the order of the kana syllabary or in alphabetical order, it is necessary to search out each of letter keys (kana or alphabet keys) corresponding to the point name and to input the letters one by one. Thus, troublesome inputting operations are required and there is a considerable possibility of an input error.

[0008] An object of the present invention is to provide a method which enables a point name to be input by a simple operation while reducing the necessary memory capacity.

[0009] To achieve this object, according to one aspect of the present invention, there is provided a method of inputting one of predetermined names through a key pad input image, the method including the steps of (1) preparing a name list in which a plurality of names formed of alphabetical letters, kana letters, or like characters are registered in alphabetical order or in the order of the kana syllabary, and a table formed by storing sequences of n leading characters and data related to each sequence of n leading characters, the data representing information as to whether some of the registered names in the name list have the corresponding sequence of n leading characters, (2) making, when one of the sequences of n leading characters is input, an examination as to whether some of the registered names in the name list have the same sequence of characters as the input sequence of n characters by referring to the table, (3) searching, according to an affirmative result of the examination step, the name list for some of the registered names whose leading characters correspond to the input sequence of n leading characters, (4) identifying, from the names searched out in the searching step, characters each probable to be input as (n+1)th character and characters improbable to be input as (n+1)th character, and displaying the probable characters and the improbable characters so that the probable characters and the improbable characters are discriminable from each other, and (5) displaying, each time a character is input thereafter, characters each probable to be next input and characters improbable to be next input so that the probable characters and the improbable characters are discriminable from each other.

[0010] According to another aspect of the present invention, there is provided a method including forming a table in which (1) each of parent, child and grandchild record is formed by setting characters and bit positions in a one-to-one relationship and by setting a flag at each of the bit positions corresponding to some of the characters each probable to be input in the process of inputting a name, (a) one parent record being formed as a record designating the probability of each of the characters being input as a first character, (b) child records corresponding to the number of the characters being formed, each child record designating the probability of each of the characters being input as a second character subsequent to one of the characters selected as a first character, (c) grandchild records corresponding to the number of possible combinations of first and second characters being formed, each grandchild record designating the probability of each of the characters being input as a third character subsequent to one of the combinations of first and second characters, and in which (2) each of the bits “1” or “0” of all the grandchild records designates the existence or non-existence in the name list of some registered names whose three leading characters correspond to the predetermined sequence of three characters corresponding to the grandchild record bit.

[0011] According to still another aspect of the present invention, when the number of names searched out is reduced to one, the one remaining name is displayed and is input by a predetermined key operation.

[0012] These and other advantages and embodiments of the present invention will become apparent with reference to the following detailed specification, claims, and accompanying drawings.

[0013] FIG. 1 is a block diagram showing the configuration of a navigation apparatus having a name inputting function;

[0014] FIG. 2 is a diagram showing a place name list;

[0015] FIG. 3 is a diagram for explaining a skip table;

[0016] FIG. 4 is a more detailed diagram for explaining the skip table;

[0017] FIG. 5 is a flowchart of place name input control processing; and

[0018] FIGS. 6A and 6B are diagrams showing a key pad input image (letter pallet).

[0019] (a) Configuration

[0020] FIG. 1 is a diagram showing the configuration of a navigation apparatus to which the present invention can be applied. The navigation apparatus has a map storage medium 11, e.g., a CD-ROM having map information stored therein, a CD-ROM control section 12 for controlling reading of map information from the CD-ROM, and a position measuring unit 13 for measuring the current position of a vehicle. The position measuring unit 13 includes a vehicle speed sensor which detects the distance traveled, a gyroscope for ascertaining the vehicle heading, and central processing unit (CPU) for calculating the position of the vehicle. The navigation apparatus also has a map information memory 14 for storing map information read out from the CD-ROM, a remote controller 15 for operation via the remote control interface 16 and for performing an operation for selection from a menu, an operation for enlargement/reduction, a manual map scrolling and so on. The apparatus further has a processor (CPU) 17 for overall control of the navigation apparatus, a read only memory (ROM) 18 having various navigation control programs stored therein, a random access memory (RAM) 19 for storing processing results, a display controller 20 for generating map images and menu images, a video RAM 21 for storing map images and menu images generated by the display controller 20, a monitor (display) 22 for displaying a menu image, etc., and a bus 23.

[0021] In the CD-ROM 11, a place name list NLS in which a multiplicity of place names are registered in alphabetical order is stored. A skip table is also stored in the CD-ROM 11 for recognition as to whether some of the places registered in the place name list NLS have a sequence of certain n (e.g., n=3) alphabetical letters as their leading letters.

[0022] (b) Place Name List

[0023] FIG. 2 represents the place name list NLS. Place names are registered in alphabetical order from an initial address 000. For example, place names whose first to third letters correspond to an alphabetical letter sequence “AAA” are registered in alphabetical order from address a_AAA, place names whose first to third letters correspond to an alphabetical letter sequence “AAB” are registered in alphabetical order from address a_AAB. Other place names are successively registered in the same manner. Finally, place names whose first to third letters correspond to an alphabetical letter sequence “ZZZ” are registered from address a_ZZZ.

[0024] (c) Skip Table

[0025] FIG. 3 represents the skip table SKT. A plurality of sequences of n (n=3) alphabetical letters and data items (flags) related to the sequences of alphabetical letters are stored to form the skip table SKT. Each of the data items denotes the existence/non-existence of some place name having the corresponding sequence of n leading alphabetical letters and registered in the place name list NLS.

[0026] FIG. 4 is a more detailed diagram representing the skip table SKT. The skip table SKT has a parent stage using a record R₁which designates a probability or improbability of one of the alphabetical letters being a first letter, a child stage using records R_Ato R_Zeach of which designates a probability or improbability of one of the alphabetical letters being a second letter, and a grandchild stage using records R_AAto R_ZZeach of which designates a probability or improbability of one of the alphabetical letters being a third letter. Through these three stages, a list for some of the place names having three leading letters corresponding to three input letters is designated. Records R₁, R_Ato R_Z, and R_AAto R_ZZin these stages are formed as described below.

[0027] (1) Alphabetical letters each probable to be input as a first letter in a place name input and the other alphabetical letters improbable to be input as a first letter are expressed in a 26-bit record R₁(parent stage). The first bit at the leftmost position in 26-bit record R₁is a letter A position; the second bit, a B position; the third bit, a C position; . . . ; and the twenty-sixth position, a Z position. If it is probable that letter A will be input as a first letter in a place name input, the first bit is set to “1”. If it is improbable that the letter A will be input as a first letter, the first bit is set to “0”. Determination is made in the same manner with respect to the other twenty-five alphabetical letters, thereby setting each bit to “1” or “0”. A pointer to a child record is stored with respect to each of the bit positions in the parent record R₁(bit positions of “1”). A probability of an alphabetical letter being input as a first letter signifies that the alphabetical letter is the first letter of at least one of the registered place names in the place name list.

[0028] (2) Alphabetical letters each probable to be input as a second letter subsequent to a first letter in a place name input and the other alphabetical letters improbable to be input as a second letter are expressed in 26-bit records R_Ato R_Z(child stage). That is, a record R_Ais prepared as a record having “A” as a first letter, and the first bit of the record R_Ais set to “1” if it is probable that letter “A” will be input subsequently to the first letter “A” in a place name input. If it is improbable that letter “A” will be input subsequently to the first letter “A”, the first bit of the record R_Ais set to “0”. If it is probable that letter “B” will be input subsequently to the first letter “A” in a place name input, the second bit of the record R_Ais set to “1”. If it is improbable that letter “B” will be input subsequently to the first letter “A”, the second bit of the record R_Ais set to “0”. Determination is made in the same manner with respect to the other twenty-four alphabetical letters, thereby setting each bit of the record R_Ato “1” or “0”. Then, a record R_Bis prepared as a record having “B” as a first letter. If it is probable that letter “A” will be input subsequently to the first letter “B” in a place name input, the first bit of the record R_Bis set to “1”. If it is improbable that letter “A” will be input subsequently to the first letter “B”, the first bit of the record R_Bis set to “0”. Determination is made in the same manner with respect to the other twenty-five alphabetical letters, thereby setting each bit of the record R_Bto “1” or “0”. Subsequently, records R_Cto R_Zhaving first letters “C” to “Z” are formed in the same manner. A pointer to a grandchild record is stored with respect to each of the bit positions in the records R_Ato R_Z(bit positions of “1”). A probability of an alphabetical letter being input as a second letter subsequent to a first alphabetical letter signifies that these alphabetical letters are the two leading letters of at least one of the registered place names in the place name list.

[0029] (3) Alphabetical letters each probable to be input as a third letter subsequent to first and second letters in a place name input and the other alphabetical letters improbable to be input as a third letter are expressed in 26-bit records R_AAto R_AZ, R_BAto R_BZ, . . . , R_ZAto R_ZZ(grandchild stage). That is, a 26-bit record R_AAis prepared as a record having “AA” as first and second letters, and the first bit of the record R_AAis set to “1” if it is probable that letter “A” will be input subsequently to the first and second letters “AA” in a place name input. If it is improbable that letter “A” will be input subsequently to the first and second letters “AA”, the first bit of the record R_AAis set to “0”. If it is probable that letter “B” will be input subsequently to the first and second letters “AA” in a place name input, the second bit of the record R_AAis set to “1”. If it is improbable that letter “B” will be input subsequently to the first and second letters “AA”, the second bit of the record R_AAis set to “0”. Determination is made in the same manner with respect to the other twenty-four alphabetical letters, thereby setting each bit of the record R_AAto “1” or “0”. Then, a record R_ABis prepared as a record having “AB” as first and second letters. If it is probable that letter “A” will be input subsequently to the first and second letters “AB” in a place name input, the first bit of the record R_ABis set to “1”. If it is improbable that letter “A” will be input subsequently to the first and second letters “AB”, the first bit of the record R_ABis set to “0”. Determination is made in the same manner with respect to the other twenty-five alphabetical letters, thereby setting each bit of the record R_ABto “1” or “0”. Subsequently, records R_ACto R_AZ, R_BAto R_BZ, . . . , R_ZAto R_ZZare formed in the same manner with respect to sets of first and second letters “AC” to “AZ”, “BA” to “BZ”, . . . , “ZA” to “ZZ”.

[0030] The existence/non-existence of some place name registered in the place name list can be ascertained according to whether “1” is set at one of the bit positions of the above-described grandchild records R_AAto R_AZ, R_BAto R_BZ, . . . , R_ZAto R_ZZcorresponding to the three leading letters of the place name. For example, if a place name “Atlanta” exists, the bit of the grandchild record R_ATcorresponding to the three leading letters “ATL” is “1”.

[0031] According to an embodiment of the present invention, as can be understood from the above, the number of records for identifying the sets of three letters in the skip table SKT is a total of 1 in the parent stage, 26 in the child stage and 26×26 in the grandchild stage, and a total table is given by

[0032] (Table Size)=(Record Size)×(Number of Records).

[0033] Since one record is formed of 26 bits, the necessary table size is

[0034] (Table Size)=26[1+26+26×26]

[0035] =26 (bits)×703 (records)

[0036] =18278 (bits) or 2285 (bytes).

[0037] That is, it is possible to identify a name having a sequence of certain three leading letters as one registered or not registered in the name list by using a table having a small data size of 2285 bytes.

[0038] (d) Place Name Input Control

[0039] FIG. 5 is a flowchart of place name input control, and FIGS. 6A and 6B are diagrams showing a key pad input image (letter pallet).

[0040] When a power supply for the navigation apparatus is turned on, the processor 17 (shown in FIG. 1) reads out the skip table SKT stored on the recording medium (CD-ROM) 11 and stores the skip table SKT in the RAM 19 based on a booting program. In this state, a user selects an alphabetical place name input process by a menu operation with the remote controller 15. Then, the processor displays a key pad input image (letter pallet) such as shown in FIG. 6A on the monitor 22.

[0041] Next, the user inputs leading letters of a place name one by one by designating alphabetical key pads in the key pad input image (step 100). The processor checks whether three leading letters have been input (step 101). If three leading letters have been input, the processor examines whether the first to third letters at least one of the registered place names in the place name list NLS correspond to the three input letters (step 102). For example, in a case where three letters “AAB” are input, record R₁is first referred to and record R_Ais recognized, from record R₁, as the next record to be referred to with respect to the second letter (the pointer to record R_Ais obtained) since the first letter is “A”. From record R_A, record R_AAis recognized as the next record to be referred to with respect to the third letter (the pointer to record R_AAis obtained) since the second letter is “A”. Then, since the third letter is “B”, the second bit of record R_AAis recognized as “1” or “0” to ascertain whether at least one place name whose first to third letters correspond to the three input letters “AAB” exists as one of the registered place names in the place name list NLS.

[0042] If “0” is recorded as the bit of the grandchild record corresponding to the three input leading letters, no place name having the corresponding three leading letters exists, and the processor therefore requests the user to again input letters through the image on the display (step 103). Processing through steps 100 to 102 is then repeated.

[0043] If “1” is recorded as the bit of the grandchild record corresponding to the three input leading letters, the processor recognizes the existence of some place names having the three leading letters in step 102, makes a binary search for the place names having the corresponding three leading letters in the place name list NLS, reads out the place names searched out, and stores them in the RAM 19 (step 104). Thereafter, the processor sets i to 4 (step 105) and recognizes, in the place names stored in the RAM, alphabetic letters each probable to be input as ith letter and the other alphabetic letters improbable to be input as ith letter (step 106) The processor then reduces the luminance of lighting (shades) for the alphabet keys (key pads) improbable to be operated to input an ith letter while maintaining the luminance of lighting for the key pads probable to be operated for inputting (step 107). FIG. 6B illustrates a case where “TORRANCE” is input as a place name and alphabetic letters each probable to be input after “TORRANCE” are brightly displayed while the other alphabetical letters improbable to be input are shaded. The user can select an ith letter from the bright key pads. Thus, the facility of the ith letter inputting operation is improved and the possibility of occurrence of an input error is reduced.

[0044] After the user has input an ith letter (step 108), the processor checks whether there is only one place name whose first to ith letters correspond to the above-described sequence of input letters (whether the input letter sequence has become unique) (step 109). If the input letter sequence is not unique, the processor increments i by one (i+1→i) (step 110) to repeat processing through steps 106 to 108.

[0045] If only one place name is searched out whose first to ith letters correspond to the input letter sequence even before being completely input, it is displayed in an upper image section on the monitor screen (step 111), and the user operates a FIND key referring to the display if the displayed name coincides with the name that the user intends to input, thereby completing the place name inputting process (step 112). The arrangement may alternatively be such that processing through steps 106 to step 110 is repeated to input all the alphabetical letters of the target name without performing steps 111 and 112.

[0046] Place names each probable to be input by the user are reduced as the inputting process progresses, so that the processor can recognize a reduced number of place names (candidate place names) each of which is probable to be equal to the place name that the user intends to input. The arrangement may therefore be such that, when several candidate place names remain, they are successively displayed at a user's request or automatically, and the user selects and inputs one of the candidate place names.

[0047] The present invention has been described with respect to the case of inputting a place name from letters presented in alphabetical order. However, the inputting process of the present invention is not limited to this. For example, the present invention can also be applied to a system for inputting a place name from letters in the kana syllabary or like characters. Also, the present invention is not limited to inputting of place names. The present invention can be applied to a system for inputting many other kinds of names. Furthermore, in the process of the invention, the number n is not limited to 3.

[0048] The present invention has been described with respect to what is presently considered to be a preferred embodiment. However, the present invention can be modified and changed on various ways without departing from the scope of the invention set forth in the appended claims, and is to be construed to encompass such modifications and changes.

[0049] According to an embodiment of the present invention, as described above, each of a plurality of letters is recognized as probable or improbable to be next input by a user in the process of inputting a place name or the like, and keys corresponding to the letters probable to be input are displayed so as to be discriminable from other keys corresponding to the letters improbable to be input, thereby enabling the user to input the place name by a simple operation with a reduced possibility of an input error.

[0050] According to an embodiment of the present invention, each of parent, child and grandchild records is formed by setting letters (alphabetical letters or kana letters) and bit positions in a one-to-one relationship and by setting a flag (“1”) at each of the bit positions corresponding to some of the letters each probable to be input in the process of inputting a name, (1) one parent record being formed as a record designation the probability of each of the letters being input as a first letter, (2) child records corresponding to the number of the letters being formed, each child record designating the probability of each of the letters being input as a second letter subsequent to one of the letters selected as a first letter, (3) grandchild records corresponding to the number of possible combinations of first and second letters being formed, each grandchild record designating the probability of each of the letters being input as a third letter subsequent to one of the combinations of first and second letters, (4) each of the bits “1” or “0” of the grandchild records designating the existence/non-existence in a name list of some registered names whose three leading letters correspond to the predetermined sequence of three letters corresponding to the grandchild record bit. From these records forming a table of a small size, it is possible to ascertain whether a registered name having certain three leading letters exists in the name list. If a name not registered in the name list is input by a user, the user is requested to again input a name. Therefore, even if the user makes an error in inputting letters, he or she can immediately recognize the error and can input the necessary name correctly and promptly.

[0051] According to another embodiment of the present invention, when the number of names probable to be input is reduced to one, the one remaining name is displayed and input by a predetermined key operation before completing the process of inputting all the letters of the name.