JPS62274366A - Dictionary retrieving device - Google Patents

Abstract

PURPOSE:To shorten the processing time required for comparing a character, by retrieving only a candidate word which has been limited at a stage of retrieving a dictionary. CONSTITUTION:A character-string which has been delivered from an analysis control part is held in a retrieval character-string buffer 212. A state storage 211 holds a back connection category of a word which has been retrieved immediately before. An index 213 holds a pointer to such a tree structure directory as a word beginning with each character becomes a path extending from a tree root nodal point to a nodal point for showing a terminal of one word. Each nodal point on the tree structure directory has a character corresponding to its nodal point, a succeeding point selecting part, and a pointer to a succeeding nodal point. The nodal point having a symbol for showing a terminal of a word is followed by word information of its word. A retrieval control part 210 obtains an appropriate tree structure directory by the index 213 from the first character in the buffer 212, compares a character in the buffer 212 with a character being attendant on the nodal point of the tree structure directory, and when it reaches a terminal symbol of the word by following the nodal point, it becomes a fact that the word has been found out.

Description

DETAILED DESCRIPTION OF THE INVENTION Detailed Description of the Invention (Field of Industrial Application) The present invention relates to a dictionary search device for natural language analysis.

(Prior Art) Conventionally, in a directory with this structure for a dictionary,
One node of the tree represents one character, and words that have a common string of characters from the left end of the word have some nodes in common. For example, the coined word ``you'', the auxiliary verb ``you'' of will/inference, the auxiliary verb ``yoda''/[yottesu] of comparison, and their conjugated forms (for example, ``you'', ``yona'', ``you'') ) is defined by two common nodes [
yo] and ``u'' ([Acoustical Society of Japan Speech Study Group Materials J 882-82649-654
page).

(Problem to be Solved by the Invention) However, for example, when using a dictionary search device having a directory with this structure to perform morphological analysis of an input character string such as "...depending on how you look at it..." using the longest match method, If you think about it, once you have identified the word up to ``mi'', the possible candidates for the next word include the above-mentioned coined word component ``you'', the auxiliary verb ``you'' of will/inference, and the auxiliary verb ``you'' of comparison. The conjugated form of ``da'' is now also included, and the conjugated form of the auxiliary verb ``yoda'' of the metaphorical auxiliary verb ``yoda'' is used as a word candidate, and then refer to the table that describes the connection possibilities between words. death,
It was necessary to determine whether it could be connected to the previous word. Moreover, in order to determine that "Yo desu", "Yo na", "Yo deshi", etc. are not candidates for the next word, the input character string and "Yo desu", [Yo na], [Yo deshi], etc. It was necessary to compare with This increases the need for backtracking when performing morphological analysis using the longest match method, and increases the processing time required to compare characters.

An object of the present invention is to provide a dictionary search device that solves this problem.

(Means for Solving the Problems) The present invention provides a dictionary search device that searches for a word while tracing a directory with this structure in which each symbol constituting a word is a node, at least a backward connection of a word searched immediately before. a state memory that holds categories; a subsequent node selection means that selects, for each branching node, a subsequent node that is reachable from the backward connected category of the immediately preceding word held in the state memory; and a group of pointers to the subsequent nodes. It is characterized by having a directory part having this structure.

(Operation) In the present invention, the successor node selection section of each branch node on the tree structure directory uses the backward connection category of the word searched immediately before, which is stored in the state memory, to select Limit the reachable successor nodes. This allows you to avoid backtracking by first selecting word candidates from categories that cannot be forward-connected, and to avoid backtracking between the symbols currently being input and the main structure directory when tracing from a node in a tree structure directory to a subsequent node. This makes it possible to reduce the number of comparisons between nodes and symbols.

(Example) Hereinafter, an example of the present invention will be described using FIGS. 1 to 4. FIG. 1 is a block diagram showing an example of a morphological analysis device using a dictionary search device of the present invention. FIG. 2 shows the configuration of a dictionary search device according to the present invention. Third
The figure shows the structure of the nodes of the book structure directory in FIG. 2. FIG. 4 shows the function of the subsequent node selection section in FIG. 3, taking the subsequent node selection section for node 202 in FIG. 2 as an example.

Input text storage 101 holds input text.

The analysis control unit 102 reads a partial character string from the input text storage 101 and passes the character string to the dictionary search device 103 to perform dictionary lookup while proceeding with the morphological analysis of the input text.

In FIG. 2, a search string buffer 212 holds the string received from the analysis control unit 102. The state memory 211 holds the backward connection category of the most recently searched word. Index 213 holds, for each letter, a pointer to a book structure directory in which words starting with that letter are paths from the root node of the tree to the nodes representing the end of a word.

Each node on this structural directory corresponds to one character that makes up a word, and a branch from one node to another indicates that the two nodes are on the path that leads to the word. For example, the adnominal form of the auxiliary verb ``yoda'' in the metaphorical situation ``like J'' is represented by a path passing through the nodes 201, 202, 206, and 208.

Each node on this structure directory has a character corresponding to the node, a subsequent node selection section, and a pointer to the subsequent node, as described in FIG.

A node with a symbol ■ indicating the end of a word is followed by the word information of that word.

The search control unit 210 uses the index 213 to obtain an appropriate tree-structured directory from the first character in the search string buffer 212, and searches for the search character while tracing the characters in the search string buffer 212 one by one from left to right. The characters in the column buffer 212 are compared with the characters associated with nodes in the tree structure directory, and the nodes in the tree structure directory are traced.

When you reach the end of a word between the symbols, you have found a word.

For example, consider the case where an input text such as "...depending on how you look at it..." is morphologically analyzed from left to right, giving priority to the longest match. It is now assumed that the identification of words up to ``mi'' has been completed, and a backward connection category of the word rJLJ, 22, as shown in FIG. 4 has been set in the state memory 211. The analysis control unit 102 performs a dictionary lookup by passing the partial character string ``Yo Yakuwa'' to the dictionary search device 103 since up to ``J'' in the text has been identified.

The passed character string "Yoyowa" is held in the search character string buffer 212 of the dictionary search device. The search control unit 210 uses the index 213 to obtain a main structure directory with the node 201 as the root node from the first character [yo] of the search character string "Yo Yakuha". When a node 201 with "yo" is traced to a node 202 with "u", the nodes that may follow the node 202 include a node 203 with a symbol that marks the end of a word,
Node 204 with the character “da”, node 2 with the character “de”
05, a node 206 with the character "na", a node 207 with the character [ni], etc. However, since the backward connection force degory in the current state memory is 22, the node 202 shown in FIG. Due to the function of the subsequent node selection unit, only the node that marks the end of the word, i.e., node 203, is selected as the next possible node, and the word "yo" is selected as a word candidate at the current position in the input text. Then, the word information for [YoJ] is returned to the analysis control unit 102 as the output of the dictionary search device. At this time, there is no need to perform a comparison operation between the character "ni" in the input text and the nodes [da], "de", "na", and "niJ in the main structure directory. In this way, the analysis control unit 102 inputs Proceed to the next position in the text, ``ni'', and proceed with the analysis process.

On the other hand, conventionally, when prioritizing the longest word as a candidate, if there was no function that preliminarily limits the subsequent node from the subsequent category of the immediately preceding word, the conjunctive form of the auxiliary verb "yoda" ] is selected as a word candidate first, so more unnecessary calculation steps are required than in the dictionary search device of the present invention. Note that the dictionary search device of the present invention can be used not only for morphological analysis of sentences containing kanji and kana, but also, for example, for the language processing section of a speech recognition device.

(Effects of the Invention) As described above, according to the present invention, only limited candidate words are searched at the stage of searching a dictionary, so backtracking is achieved by first employing word candidates in categories that cannot be forward connected. It is also possible to reduce the number of unnecessary symbol-to-symbol comparisons.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an example of a morphological analysis device using a dictionary search device of the present invention. FIG. 2 is a diagram showing an example of the structure of a tree-structured directory of the dictionary search device according to the present invention, and FIG.
The figure shows the structure of the main structure directory node in FIG. 2. FIG. 4 is a diagram illustrating the function of the subsequent node selection section, taking the subsequent node selection section of the node 202 in FIG. 2 as an example. In the figure, 101 is an input text storage, 102 is an analysis control unit, 103 is a dictionary search device, 210 is a search control unit, 211
is a state memory, 212 is a search string buffer, 213 is an index, 201, 202, 204, 205, 206
, 207 are nodes of the tree structure directory, 203, 208
is the tree-structured directory Q:X ([Figure 4

Claims (1)

[Scope of Claims] In a dictionary search device that searches for a word while tracing a tree-structured directory in which each symbol constituting a word is a node, (a) a state in which at least the backward connection category of the word searched immediately before is retained; (b) for each branching node, a subsequent node selection means for selecting a subsequent node that is reachable from the backward connection category of the immediately preceding word held in the state memory, and a group of pointers to the subsequent nodes; A dictionary search device comprising: a directory section having a tree structure;