Recognition system

0001The invention relates to a detection system according to the preamble of claim 1.

0002A preferred application of such a detection system For example, the voice input of place names in a voice-activated navigation system in a vehicle. the Navigation system is a closed list of place names based, for example, on a removable disk is present and a reading device in a Memory of the recognition system is transmitted.

0003For such a system can a Verarbeitungstotzeit result from the fact that, after a change of the data carrier after a shutdown of a volatile memory as the main memory etc. until the data in the main memory must be transmitted. Due to cost and cost reasons the transfer is preferably not interactive with selective access to selected areas of the data carrier, but for example, as an entire dataset without substantive interpretation during transmission. At low Transmission rates, as in data bus systems in Vehicles occur, the transfer process may some take time, the user, which in this No reaction of the recognition system on a voice input learns is considered to be disadvantageous.

0004The present invention is therefore based on the object, to provide a detection system of the type mentioned, which When transmitting a data set from the read-only memory in memory more responsive to an input.

0005The invention is described in the patent claim. 1 The sub-claims advantageous configurations and Developments of the invention.

0006In the detection system according to the invention is already after a very short time in the form of the partial data of the first Structural levels before a dataset, the still incomplete is and only a small fraction of the circumference of the constitutes the entire data set, but already a partial Execution of the recognition process and therefore a response to the user allows. The invention this case makes use of the fact tHe data amounts of Partial data to the first structural levels comparatively low is.

0007In some applications it may be advantageous for the characters in a structure level not only individual Symbols of a symbol supply, in particular a allow alphanumeric symbol supply but also receive symbol sequences as characters, especially those Symbol sequences within which the strings of the data set have no branch. During the application, the Place names from a list of names can be characterized for many, especially longer place name recognition time considerably be reduced.

0008A for low memory requirements and thus lower Transmission time advantageous embodiment of the invention provides for the storage of the partial data of a structural level In addition to the mark itself is not explicitly permitted the Subsequent characters but only the number of each save permissible subsequent characters. to find the subsequent characters to a character is Totaling all intervening characters a determined distance within the data stream as a relative address and the present after this data stream distance Characters are used for the further processing of the current Input string is evaluated. If the mark are not only individual but also symbols symbol sequences can, is advantageously even the number of symbols each character stored as information, and the above specified relative addressing additional consideration the number of characters used.

0009The data structure described above is also regardless of the present invention advantageous for displayable in a branching structure strings for transmission and / or storage. Known advantageous Techniques of data storage, such as interleaving, redundant coding with error correction etc. remain unaffected and are usually also usable.

0010The input device is in particular for voice input formed and this has, for example a microphone and a speech on. Speech are numerous Forms from the state of the art, wherein both word recognizer for input connected speech and preferably Einzelsymbolerkenner for buchstabierende Voice input come into question.

0011The invention is described below with reference to preferred embodiments yet thoroughly explained. In which:<dl tsize="7"><dt>Fig. 1</dt><dd>a schematic structure of a data record</dd><dt>FIG. 2</dt><dd>a first embodiment</dd><dt>Fig. 3</dt><dd>a second embodiment</dd></dl>

0012In the sketched in Fig. 1 configuration of a branching network starting from a root node as a neutral R Start node from which permissible paths to a A plurality of nodes first branch level lead E1. The nodes of the first level E1 represent example First letter of the name. Typically The data set to most or all of the nodes the first level several permissible subsequent characters, that from each node of the first level multiple paths to Branching to continue to the second level. Also in the second plane E2 and enter the following node levels more branches, so the branching structure results that because of their appearance as a tree structure referred to as. The arrangement of the record forming amount of data in the form of information about the individual carried nodes of successive node level now in such a way that in a first data block B1, the data grouped contiguously to the nodes of the node level E1 be and on this first frame, a second Data block B2 follows, in which in turn the data to the nodes of the node level E2 grouped contiguously are. This grouping in data blocks and stringing together of the data blocks is continued until the last node plane. In a coding of place names rises Typically, the size of the data blocks from the first Nodal plane with 29 different first letter within the next level steeply to some node levels to remain at a high level and then clear again fall.

0013In the sketched in Fig. 2 embodiment of the View a list of place names in a tree-like branching structure are for each character, ie, for each Nodes of node levels, a letter from the predetermined Symbol stock provided. The icons are in particular the letters of the alphabet including umlauts. The symbol library can also comprise special characters as -, /, or numbers. When a node associated Information is always the this node associated Characters stored. The behind this number of characters information on the number of branches, of this exit node and as to permissible successor mark leading next-level nodes KE2. The entry on the top Nodes of the first layer KE1 therefore means that these Node the first letter A represents and this letter 22 different subsequent characters are permitted. mutandis to the other initials the other nodes are usually other numbers given of permissible successors. Special cases here forming the letter Q, which in the German language only the letter u can follow, and the letter X, to which in a assumed example of a list of place names just a place name is contained. Both characters therefore have the successor number 1. The data block DB1 to the first data level KE1 contiguous contains then the Entries A22, B11, ... to UE12 as information about the Nodes of this data level.

0014From the number of nodes in the first node layer, which is included in the information R29 of the root node and the position of the current character A in the first place this node level results in a distance of 28 entries (B11 to UE12) until the beginning of the next frame to the node level KE2. From the entry to the current A22 Node further stipulates tHe the first 22 entries to allowable information to this distance in the data stream Successor characters. Decides the speech at a second input character on the Presence of the letter A, which in the node level E2 an acceptable replacement for the letter A in the first represents layer, then the path from this node continue to the letter A in the second plane. at this node to the letter A in the second node level KE2 is as an additive, the number 3, which is expressed, that to this node three permissible subsequent characters exist, in turn, by nodes in the third node level are represented. The branching structure has therefore the node A3 three further in the second node level Way on to nodes in the third node level KE 3.

0015The data block DB2 of the second node level KE2 contains then as entries the node information of the subsequent nodes for the node A22 of the first node level, so for example, A3, B8, ..., Z2, where the information about 11 permissible Subsequent characters in the second node level KE2 to the follow node B11 of the first node level KE1, so for example, A8 to U13. Thereafter, the child nodes follow the second node level KE2 to the node C11 of the first node level KE 1 and so on until all nodes of the node level KE2 the complete data block DB2 form for this node level. After this data block DB2, the information coming to the Node, the node level KE 3. The relative distance from the node A3 of the second node level KE2 to its permissible followers in the data block DB3 results from the sum of the intervening entries that present from the hitherto Information derivable therefrom already that the node A3 of the second node level, the first position within the permitted successor to the node A22 of the first Node level forms and thus still 21 children nodes to be skipped to A22. The skipped and thus contributing to the distance to the subsequent nodes for A3 Entries include all subsequent nodes for the by A22 following node of the first node level KE2, wherein their number from the letter-supplied figures (B) 11, (C) 11, ..., (B) 12 gives cumulative. The after this distance in the data stream occurring three entries be as a possible successor to the node A3 of the second Level and thus further treated total to the string AA. Within the permissible followers C, L and S decide the speech on the existence of the letter S as the third character of the input string and the path from the child node S, for which in the example given case be 2 subsequent characters allowed to the present and therefore the total entry S2, continued. For the distance to the two permissible subsequent nodes in the plane KE4 to that node 2 in the plane KE 3 are next to the following entries in the node level KE 3 even in the node level KE4 overlying entries counting in the example H3 and E1.

0016By run by the speech progression within the branching structure is in the ninth node level a node L reaches, which as the end of a name characterized is in that the item provided number of permissible followers equals zero. The entered Place name is now fully established. To this end had the Example case, the partial data from the new node levels from the Read memory are transferred into the main memory, so that the full name of construction completed until quite late is. The early start of the recognizer and the gradual pursuit of the path through the branch network but can already after loading less Levels, for example, of four levels by building a Display the first character associated with the input string to one of the stored strings the Users are signaled that his voice input processed becomes. Further, the user may upon detection of a misclassification of an input character, the more Cancel processing and start a new entry.

0017The sketched in Fig. 3 embodiment differs of the sketched in Fig. 2 embodiment is substantially characterized in that the characters in a node of a node level not only a single symbol from the symbol library but also a symbol sequence can be contained. These Summary of several consecutive symbols in a single node is particularly advantageous, when a built in detail in FIG. 2 branching network between two or more in different planes includes successive knots no branching. This applies in the place names described in FIG. 2 in detail Aasbüttel for string BÜTTEL whose path Reaching the node B1 in the fourth node level FIG. 2 up to the letter L and in this example, thus also to the end of a word is already certain. Since in this example FIG. 2, the node levels 5 to 9 no decision path are offering more in the embodiment of Fig. 3, all characters of this partial sequence Büttel already in a node of the fourth node level KE4 summarized. Upon reaching the node lackey of the fourth node level can already be conclusively checked with whether the Total string Aasbüttel for an assignment of the input string due to cumulative probabilities the speech or comparable criteria it can be assumed. A similar situation arises for the place name AALEN in the sketched branching network, wherein the symbol sequence LEN, which in Fig. 2 is spread over three node levels KE 3 to KE5, according to FIG. 3 are combined in a node LEN node level KE 3 can. The zusammenfaßbaren symbol sequences are not necessary at the end of the place names but can also intermediate portions in central regions of the name or the beginning account. Typical symbol sequences, which often result summarized a unique detailed path read, are CH or CK, necessarily meets the symbol sequence QU and of a beginning with the letter X Input string would remain the example of German Place names only the name XANTEN, the order already in the first node level completely housed and identified can be.

0018For effective storage, transmission and processing of such a modified branching network with the Admissibility of symbol sequences in a network node can advantageously the entries on each node to another number, which in the number of symbols this node indicates supplemented. That figure the to Fig. 2 have already been explained in detail to an entry Node prefixed. The entry 1A22 at a node then means that this node contains a symbol that This symbol is the letter A, and that at this node 22 permissible subsequent nodes in the hierarchy next Node level are available. A node entry 2QU4 means in this illustration that the node contains two symbols, that these symbols be successively Q and U, and that to this node in the next node level 4 permissible subsequent nodes exist. The entry means 6XANTEN0 then, that to the node a six-digit sequence of symbols XANTEN belongs and the name thus is already fully and has no feasible successor more.

0019To determine the relative position of the group of items the permissible successor is then over in Amendment the determination by the example of FIG. 2 still the length of the entries for each intervening Node considered.

0020To the extent of the place name recognizer not already using the Information on each node the number of already transmitted data blocks can be determined, this data block numbers can also be specified with. with regard the number of transmitted blocks, the place-name recognition in step with the transfer of data from continue reading the memory. It can, for example, the partial data from four node levels KE1 to KE4 in transmit a relatively short time and on this basis, with the Detecting an input and buffered input string be started. Once the part of the data next node level are transmitted, the detector may go a step further, until the entire name is recognized is. While in a data structure according to Fig. 2 long City going through many node levels and thus also require the transmission of large data quantities, in the data structure sketched in Fig. 3 Art for many Entries in the list of names to significantly reduce the Detection time can be expected. For other problems Again, the data structure of the sketched in Fig. 2 be kind advantageous.

0021The invention is not limited to the described embodiments limited but expert under Skills in many ways it may be modified and in particular in other problems as the detection of Place names from a list of names advantageously applicable.