JP5258631B2 - Dictionary search device - Google Patents

Description

  The present invention relates to a dictionary search apparatus that performs a dictionary search using a double array.

  In a conventional dictionary search using a double array, a trie structure is realized by two arrays called Base and Check, and a high-speed dictionary search and a common prefix search are performed (for example, see Non-Patent Document 1). In addition, in a dictionary search using a trie structure, a method has been proposed in which a character string search including a wild card and a regular expression is performed at a high speed by a reverse trie (see, for example, Patent Document 1).

Japanese Patent No. 2683870

Aoe: Double-sequence high-speed digital search algorithm, IEICE Transactions, J71-D, No. 9, pp. 1592-1600 (1987)

  In the conventional search method, transition is made character by character based on the input character, and it is confirmed whether the transition destination is correct each time. For this reason, a common prefix search that determines whether the leading part of the input character string is registered as a word in the dictionary, such as a dictionary search in a morphological analyzer, can be realized at high speed. There is a problem that the forward matching search for searching for a word including this at the beginning from the dictionary cannot be performed at high speed.

Hereinafter, in order to clarify the problems of the conventional method, a simple word search using a double array will be described.
The double array represents a trie structure on two arrays, and FIG. 15 shows an example of a double array in which {“aaa”, “abc”, “abcd”, “abfgh”, “afghhi”} are registered. It is a thing. The double array includes a Base array and a Check array, and State indicates an index of the array and corresponds to a node of a tri structure. FIG. 16 illustrates the trie structure represented by this double array. The State in FIG. 15 corresponds to the node number in FIG. Trie transition (node movement) by the double array is performed with reference to the Base array and the Check array.

Hereinafter, the character set is S _c = {'#', 'a', 'b',..., 'Z'}, and the character set and the internal code set corresponding to 1: 1 are S _code = {1, 2, 3 , ..., and 27}, it represents a mapping from _{S c} to the _{S code} in Code (). For example, Code ('b') = 3. '#' Is a special character representing the end of a character string, and is called a terminal symbol.
In the transition in the double array, when the current State is s, the transition destination State is t, and the input character is c, t is obtained according to (Equation 1) below.

t = Base [s] + Code (c) (Formula 1)
At this time,
Check [t] = s (Formula 2)
If so, the transition is successful. When Base [t] = − 1, it indicates the end of the word, and the transition ends there. If Check [t] ≠ s, transition by the character c cannot be made, that is, such a character string is not registered. Searching for a word is possible by making a transition according to (Equation 1) until the transition becomes impossible or the end of the character string is reached.
A method for constructing such a Base array and a Check array is known as shown in Non-Patent Document 1 above. An example of searching for a character string is shown below.

(Example 1) Search for “abc”.
1. Transition from State = 1 to “a” (Code (′ a ′) = 2) and Base [1] = 1, and therefore State = Base [1] + Code (′ a ′) = 3. Since Check [3] = 1, the transition is successful.
2. Transition from State = 3 by “b” (Code ('b') = 3), and Base [3] = 2, so State = 5. Since Check [5] = 3, the transition is successful.
3. Transition from State = 5 by “c” (Code ('c') = 4). Since Base [5] = 3, State = 7. Since Check [7] = 5, the transition is successful.
4). A transition is made from State = 7 by “#” (terminal symbol, Code (′ # ′) = 1), and since Base [7] = 7, state 8 is entered. Since Check [8] = 7, the transition is successful.
5. Since Base [8] = − 1, it can be seen that the character string is at the end, and that “abc” is registered.

(Example 2) Search whether "aba" exists.
1. Transition from State = 1 to “a” (Code ('a') = 2), and Base [1] = 1, so State = 3. Since Check [3] = 1, the transition is successful.
2. Transition from State = 3 by “b” (Code ('b') = 3), and Base [3] = 2, so State = 5. Since Check [5] = 3, the transition is successful.
3. Transition from State = 5 by “a” (Code (′ a ′) = 2), and Base [5] = 3, so State = 5. Since Check [5] = 3, the transition fails and it is understood that “aba” is not registered.

  However, as described above, transition is made one character at a time based on the input character, and the transition is confirmed by confirming whether the transition destination is correct each time. Need to explore. For example, to search for a word that directly matches “ab”, it is as follows.

(Example 3) A word that matches forward with “ab” is searched.
1. Transition from State = 1 to “a” (Code ('a') = 2), and Base [1] = 1, so State = 3. Since Check [3] = 1, the transition is successful.
2. Transition from State = 3 by “b” (Code ('b') = 3), and Base [3] = 2, so State = 5. Since Check [5] = 3, the transition is successful.
3. It calculates a new State = t by (Equation 1) for ^{∀ x∈S} _c from State = 5, listed as a Check [t] = 5. {'C', 'f'} is obtained.
4). From State = 5 to 3. The transition is made by “c” (Code ('c') = 4) obtained in the above, and since Base [5] = 3, State = 7. Since Check [7] = 5, the transition is successful.
5. From State = 7 to 3. The process similar to the above is performed recursively to find {“abc”, “abcd”} (end if the obtained character set is only a terminal symbol. No transition is made after the terminal symbol).
6). 4. above. ~ 5. In the same manner as described above, {= abfgh}} is found by making a transition from State = 5 by “f” and recursively searching.

  As described above, the conventional search method has to be searched recursively, and there is a problem that the forward matching search cannot be performed at high speed.

  The present invention has been made to solve the above-described problems, and an object of the present invention is to provide a dictionary search apparatus that can perform a forward match search using a double array at high speed.

  When a search character string is given, the dictionary search device according to the present invention has a double array index search means for searching for a node corresponding to the search character string from the double array index, and a child node in the trie structure in the double array index. Based on the minimum / maximum child node index that stores information for transitioning to the smallest registered word in the dictionary order and information for transitioning to the largest registered word, it was searched by the double array index search means. Among the child nodes of the node, a word list for searching for the minimum / maximum child node for searching for the node having the smallest character string and the node having the largest character string in the dictionary order, and storing the registered words sorted in the dictionary order And word extraction means for extracting words from the word corresponding to the minimum node searched for by the minimum / maximum child node search means to the word corresponding to the maximum node. A.

  The dictionary search device according to the present invention searches for a node having the smallest character string and a node having the largest character string in the dictionary order among the child nodes of the node searched by the double array index search means, Since the words from the corresponding word to the word corresponding to the maximum node are extracted, the forward matching search by the double arrangement can be performed at high speed.

It is a block diagram which shows the dictionary search device by Embodiment 1 of this invention. It is a flowchart which shows the search procedure of the dictionary search device by Embodiment 1 of this invention. It is explanatory drawing which shows an example of the double arrangement | sequence index and minimum / maximum child node index of the dictionary search device by Embodiment 1 of this invention. It is explanatory drawing which shows an example of the word list | wrist of the dictionary search device by Embodiment 1 of this invention. It is a flowchart which shows the index creation procedure of the dictionary search device by Embodiment 1 of this invention. It is a flowchart which shows the procedure of the word registration of the dictionary search device by Embodiment 1 of this invention. It is a block diagram of the dictionary search device by Embodiment 2 of this invention. It is explanatory drawing which shows an example of the blocked word list | wrist of the dictionary search device by Embodiment 2 of this invention. It is a flowchart which shows the procedure of the word registration of the dictionary search device by Embodiment 2 of this invention. It is a flowchart which shows the search procedure of the word W in the word registration of the dictionary search device by Embodiment 2 of this invention. It is a block diagram of the dictionary search device by Embodiment 3 of this invention. It is explanatory drawing which shows an example of the blocked word list with a score of the dictionary search apparatus by Embodiment 3 of this invention. It is a flowchart which shows the procedure of the score high-order extraction of the dictionary search device by Embodiment 3 of this invention. It is explanatory drawing which shows an example of the block-ized word list with a score of the dictionary search apparatus by Embodiment 4 of this invention. It is explanatory drawing which shows an example of a general double arrangement | sequence. It is explanatory drawing which shows the double arrangement | sequence of FIG. 15 with a tree structure.

Embodiment 1 FIG.
FIG. 1 is a configuration diagram illustrating the dictionary search apparatus according to the first embodiment.
The illustrated dictionary search apparatus includes a search character string input means 101, a double array index search means 102, a minimum / maximum child node search means 103, a word extraction means 104, a search result output means 105, an index creation means 106, and a double array index 111. , A minimum / maximum child node index 112, a word list 113, and a word set 114.

  In FIG. 1, a double array index 111 is data for storing a Base array and a Check array in the double array method. The minimum / maximum child node index 112 is data that stores an internal code for transitioning to the minimum character string in the dictionary order and an array having values for the internal code for transitioning to the maximum character string. The word list 113 is data in which character strings of registered words are sorted and stored in dictionary order. The word set 114 is a list of words to be indexed.

  The search character string input means 101 is for inputting a character string to be searched. The double array index search means 102 searches the double array index 111 for the character string input by the search character string input means 101 and acquires the corresponding node. The minimum / maximum child node search unit 103 selects the node that becomes the minimum character string and the node that becomes the maximum character string in the dictionary order from among the child nodes of the node searched by the double array index search unit 102. A search is made from the node index 112 to obtain the corresponding node. The word extraction unit 104 obtains a word corresponding to the minimum node and a word corresponding to the maximum node from the word list 113 and a set of words included between the minimum node and the maximum node acquired by the minimum / maximum child node search unit 103. To get. The search result output unit 105 is a unit that outputs a set of words acquired by the word extraction unit 104. The index creating means 106 receives the word set 114, creates or updates the double array index 111, the minimum / maximum child node index 112, and the word list 113, and registers the words.

  The dictionary search device is realized by using a computer. The double array index search means 102 to the word extraction means 104 and the index creation means 106 are software corresponding to each function and hardware such as a CPU and a memory for executing the software. It consists of hardware. Alternatively, each of these means may be configured by dedicated hardware. The double sequence index 111 to the word set 114 may be provided integrally with the dictionary search device, but is provided outside the dictionary search device and accessed by the double sequence index search unit 102 to the word extraction unit 104 via the network. It may be configured as follows.

Next, the operation of the dictionary search apparatus according to the first embodiment will be described.
Since the present embodiment is divided into a word search operation and a word registration (index creation) operation, the search operation will be described first.
FIG. 2 is a flowchart showing a search procedure in the present embodiment. The search procedure is as follows.
First, a character string to be searched is acquired from the search character string input means 101 (step ST1). The double array index search means 102 checks whether a search character string is registered (step ST2). In step ST3, if it is a registered word, the corresponding word is acquired from the node information by the word extraction means 104 (step ST4). On the other hand, if there is a word that is not a registered word but matches forward in step ST3 (step ST5), the word that is the smallest and largest in dictionary order among the words that are forward matched by the minimum / maximum child node search means 103. Are obtained (step ST6), and then all words that match forward are extracted by the word extraction means 104 (step ST4). After the word extraction by the word extraction means 104, the search result output means 105 outputs the search result (step ST7), and the search ends. If there is no word that matches the front rather than the registered word, the search is terminated as it is.

The outline of the operation of the first embodiment will be described below with reference to FIGS.
FIG. 3 is an example of the double array index 111 and the minimum / maximum child node index 112 when the word set 114 is {“aaa”, “abc”, “abcd”, “abfgh”, “afghhi”}. Similarly, FIG. 4 is an example of the word list 113. An address portion 1001 indicates an address for accessing a word registered in the word list 113. The entry unit 1002 stores registered words. The Child_First array of FIG. 3 stores an internal code for transitioning to the word that becomes the smallest in the dictionary order among the child nodes that can transit from each State, and Child_Last changes to the word that becomes the largest in the dictionary order. The internal code for this is stored. Further, although the value of the Base array of the node corresponding to the end of the word is conventionally -1, in this embodiment, the address value to the word list 113 in which the corresponding word is registered is stored as a negative value. To do.

  To perform a forward matching search using the double array index 111, the minimum / maximum child node index 112, and the word list 113 configured as described above, the following is performed. First, the double array index search means 102 transitions on the double array index 111 using (Equation 1) and (Equation 2) one character at a time from the beginning of the search character string. When the state when reaching the end of the search character string is t, the transition after t is transitioned by the minimum / maximum child node search means 103 using the internal code stored in the Child_First array. When a transition is made until the element of the Base array becomes a negative value, it is the end of the word that becomes the smallest in dictionary order among the words that match the search word. Further, transition is made from State = t by the internal code stored in the Child_Last array. When a transition is made until the element of the Base array becomes a negative value, it is the end of the word that becomes the largest in dictionary order among the words that match the search word forward. As a specific example, an example of searching for a word that matches forward with “ab” in the double array index 111 and the minimum / maximum child node index 112 of FIG. 3 is shown below.

(Example 4) All words that match the prefix "ab" are acquired.
1. Transition from State = 1 to “a” (Code (′ a ′) = 2) and Base [1] = 1, so that State = Base [1] + Code (′ a ′) = 3. Since Check [3] = 1, the transition is successful.
2. Transition from State = 3 by “b” (Code ('b') = 3), and Base [3] = 2, so State = 5. Since Check [5] = 3, the transition is successful.
3. Since the input is completed, in order to search for the smallest word that matches forward, Child_First [5] is regarded as the internal code of the next input and a transition is made. Since Base [5] = 3 and Child_First [5] = 4, State = 7.
4). From State = 7, Child_First [7] is regarded as an input internal code and a transition is made. Since Base [7] = 7 and Child_First [7] = 1, the state transitions to State = 8.
5. Since Base [8] = − 501 <0, it is the end of the word, and this is the address value of the word list 113 for accessing the minimum word. -501 is stored as First_Index.

6). In order to search for the largest word that matches forward from State = 5, Child_Last [5] is regarded as an internal code of the next input and a transition is made. Since Base [5] = 3 and Child_Last [5] = 7, the state transitions to State = 10. Similarly, Child_Last is regarded as an input internal code, and a transition is made to State = 15.
7. Since Base [15] = − 503 <0, it is the end of the word, and this is the address value of the word list 113 for accessing the maximum word. Store -503 as Last_Index.
8). The word list 113 is sequentially acquired from First_Index to Last_Index. Referring to FIG. 4, word sets {“abc”, “abcd”, “abfgh”} from 501 to 503 can be obtained. All of the words obtained here are words that coincide with “ab”.

  As described above, the range of forward matching words is acquired by tracing Child_First and Child_Last, so that all the forward matching words can be acquired at high speed regardless of the number of registered words.

Next, a method for constructing the minimum / maximum child node index 112 and the word list 113 will be described. For the construction of the double array index 111, for example, the method described in Non-Patent Document 1 is used.
FIG. 5 shows a procedure for creating the double array index 111, the minimum / maximum child node index 112, and the word list 113 from the word set. FIG. 6 is a diagram showing a procedure for constructing the double array index 111 and the minimum / maximum child node index 112 for the registration of one word in FIG.
To create an index, one word is taken out from the word set, and a double array index 111 and minimum / maximum child node index 112 are constructed according to the procedure of FIG. 6 (steps ST11 to ST13). After registering all the words, at this stage, the value of the terminal node corresponding to the terminal symbol in the Base array in the double array index 111 is −1 as usual. Next, this value is updated to the address value for the corresponding word in the word list 113 (steps ST14 to ST18). First, the word list 113 is sorted in ascending order in dictionary order (step ST14). Next, words are sequentially extracted from the top of the word list 113 (step ST15), and the double array index search means 102 performs a search (step ST16). In this search, the node corresponding to the terminal symbol of the word is acquired, and the value of the Base array is replaced with the address value to the word list 113 (step ST17). In step ST18, if the values of the Base array are replaced for all words, index creation is completed.

The registration process for each word shown in FIG. 6 is as follows. In the minimum / maximum child node index 112, all of Child_First and Child_Last are set to 0. The update of Child_First and Child_Last is performed by referring to the values of Child_First and Child_Last in the State that branches at the time of new branching of the trie structure. When registering each word, the initial value of State is set to s = 1 (step ST21),
While acquiring the character string of the word one by one, the transition is made on the double array index 111 according to (Equation 1) and (Equation 2) (steps ST22 to ST25).

  In the above-described steps ST22 to ST25, when State = s in which (Equation 2) does not hold, for example, the values of the Base array and Check array in State [t] are set using a conventional method (step ST26). Then, if the internal code of the next transition character c is smaller than Child_First [s] or Child_First [s] is 0, Child_First [s] = Code (c) is set (step ST27 to step ST28). At the same time, if the internal code of c is larger than Child_Last [s] or Child_Last [s] is 0, Child_Last [s] = Code (c) is set (step ST29 to step ST30). Next, the state [t] of the transition destination is substituted for the current State [s] (step ST31), and the processing from step ST22 is repeated. If c is a terminal symbol, Child_First [s] and Child_Last [s] are not updated, and the word being registered is added to the word list 113.

An example of adding the word “abz” to the double array index 111 and the minimum / maximum child node index 112 in FIG.
(Example 5) "abz" is added.
1. Transition from State = 1 to “a” (Code (′ a ′) = 2) and Base [1] = 1, so that State = Base [1] + Code (′ a ′) = 3. Since Check [3] = 1, the transition is successful.
2. Transition from State = 3 by “b” (Code ('b') = 3), and Base [3] = 2, so State = 5. Since Check [5] = 3, the transition is successful.
3. Transition from State = 5 by “z” (Code ('z') = 27), and Base [5] = 3, so State = 30. Since the Base array and the Check array have only State = 19, it is understood that they are not yet registered, and State = 30 is created as a new child node from State = 5. That is, the value of Base [30] is set to an appropriate value, and Check [30] = 5. The method described in Non-Patent Document 1 is used to obtain the value of Base [30]. Here, the value of Base [30] is 30.

4). At State = 5, Code _ '[1] = 27 is larger than the value 4 of Child_First [5], so Child_First [5] is not updated.
5. At State = 5, Code ('z') = 27 is larger than the value 7 of Child_Last [5], so the value of Child_Last [5] is updated to Child_Last [5] = 27.
6). Transition from State = 30 by “#” (Code (“#”) = 1) and Base [30] = 30, so State = 31. Since the Base array and the Check array have only State = 30, it is understood that they are not yet registered, and State = 31 is created as a new child node from State = 30. Since it is a terminal symbol, the value of Base [31] is set to -1, and Check [31] = 30.
7. “Abz” is added to the word list 113.

  As described above, the double array index 111, the minimum / maximum child node index 112, and the word list 113 in the present embodiment can be created. In the above example, State = 30 and beyond after no branching at the time of node creation is stored in the Base array and the Check array. However, as in Non-Patent Document 1, a Tail array may be used.

In this embodiment, the registered word is composed of alphabets, and the internal code is S _code = {1, 2, 3,..., 27}, but a general character string (Hiragana, Kanji, Chinese, etc.) In the case of), it can be applied in exactly the same way by dividing the character string in units of 1 byte and considering it as an internal code. In this case, since Child_First and Child_Last each need only 1 byte, the capacity of the double array index 111 and the minimum / maximum child node index 112 is only (Base array size × 2) bytes larger than the conventional double array index. It is. This can also be applied to the following embodiments.

  In this embodiment, the word readings or headings registered in the word list 113 are stored. However, it is sufficient to have an index on a database for storing other detailed information including word readings or headings. In that case, the word character string may be acquired from the word list 113 by an index from the database.

  As described above, according to the dictionary search device of the first embodiment, when a search character string is given, the double array index search means for searching for a node corresponding to the search character string from the double array index, and the double array index Double based on the minimum / maximum child node index that stores information for transitioning to the smallest registered word in dictionary order and information for transitioning to the largest registered word among the child nodes in the trie structure in the middle Among the child nodes of the node searched by the array index search means, the minimum / maximum child node search means for searching for the node having the smallest character string and the node having the largest character string in the dictionary order, and the registered word A word extractor that extracts words from the word corresponding to the minimum node searched by the minimum / maximum child node search means to the word corresponding to the maximum node from the word list sorted and stored in order. Since a unit, the prefix search by double array can be performed at high speed.

Embodiment 2. FIG.
In the first embodiment described above, the word list 113 is the continuous data as a whole, but an example in which words are added or deleted at high speed by dividing the word list 113 will be described as a second embodiment. Show.
FIG. 7 is a configuration diagram of the dictionary search apparatus according to the second embodiment.
In the figure, a blocked word list 121 is obtained by dividing the word list 113 in the first embodiment into blocks. The blocked word list creation unit 107 is a unit that creates or updates the blocked word list 121.

  FIG. 8 is an example in which the word list 113 is divided into blocks like the blocked word list 121. The block address portion 1001a has a block number and an in-block address, and is indicated by “:” in FIG. The left side of “:” indicates a block number, and the right side indicates an in-block address. The entry part 1002a is a registered word corresponding to the block address part 1001a. In order to divide the word list 113 in this way, the word list 113 that has been sorted in ascending order in dictionary order may be divided for each fixed number of words. However, since the block address portion 1001a requires two values of a block number and an in-block address, it cannot be stored in the elements of the Base array in the double array index 111. Therefore, the Child_First array and the Child_Last array are used, and the in-block address is stored as a negative value in the element corresponding to the terminal symbol in the Base array as in the first embodiment. At this time, both Child_First and Child_Last are 0, but the value of the element corresponding to the terminal node of the word in the Base array is replaced with the address value from -1 to the word list in the index creation process in the first embodiment. At this time, Child_First and Child_Last are also changed to store the block number.

Next, a procedure for updating the Base array of the blocked word list 121 and the double array index 111 will be described. FIG. 9 is a diagram showing a procedure when a new word is added to the blocked word list 121. FIG. 10 is a diagram showing a procedure for searching for the word W in FIG. The blocked word list creation means 107 operates as follows.
1. Among words registered in double array index 111, the largest word W that is smaller in dictionary order than the word to be added is searched (step ST41).
2. The block number in which the searched word W is registered is obtained from Child_First and Child_Last (step ST42).
3. Words are added to the corresponding block and sorted in ascending order within the block (steps ST43 and ST44).
4). Since the in-block address of the word after the newly added word in the corresponding block is changed, these words are searched from the double array index 111, and the element of the Base array corresponding to the terminal symbol is used as the new in-block address. Replace (step ST45).

Above 1. In order to search for the largest word W that is smaller in dictionary order than the word to be added among the words registered in the double array index 111, the following procedure is performed as shown in FIG.
1. Transitions are made sequentially from the first character of the word to be added according to (Equation 1) (step ST51 to ST step ST54).
2. When (Equation 2) is not satisfied in step ST54, the internal code of the character used for the transition at that time is stored in y (step ST55).
3. Let y be y-1, and transition is made according to (Equation 2) (steps ST56 to ST58).
4). 2. When (Equation 2) is not satisfied in step ST58. Return to.
5. When there is a maximum word W that is smaller in dictionary order than the word to be added, y for which (Equation 2) holds can always be found before y = 0. Next, in order to make a transition at y, t is substituted for s (step ST59).
6). When the Base array value is negative (step ST60), it is the terminal node of the largest word W that is smaller in dictionary order than the word to be added, and the search is terminated.
7. 3. When the Base array value is not negative, the maximum value of the internal code is substituted for y in order to search for a transition at the next character (step ST61). Return to.

By dividing the word list 113 into blocks as described above, it is not necessary to change the entire word list 113, and only the change within the block is sufficient, so the cost for adding words can be reduced.
When deleting a word, the word to be deleted may be searched and deleted from the double array index 111. When deleting also from the word list 113a, the addresses in the block are changed for words that are larger in the dictionary order than the deleted word. Therefore, those words are searched from the double array index 111 and added to the terminal symbol as in the case of adding. A corresponding element in the Base array may be replaced with a new in-block address.

  As described above, according to the dictionary search device of the second embodiment, the word list is composed of a plurality of blocks obtained by dividing the registered word into predetermined numbers, and registration is performed when a new word is registered in the word list. It has a block word list creation means that searches for the largest word that is smaller in dictionary order than the new word and adds the new word to the searched word block, so even when registering a word It is not necessary to change the entire list, and the maintenance of the word list becomes easy.

Embodiment 3 FIG.
In the above embodiment, all the words that coincide with the search word are acquired. However, when the top M items are acquired with a score given in advance for each word, the word list is divided into blocks. An example of acquiring M items at a high speed based on the maximum score will be described as a third embodiment.

FIG. 11 is a configuration diagram of the dictionary search apparatus according to the third embodiment.
The scored blocked word list 122 is a word list divided into blocks each having a score. The scored blocked word list creation means 108 is means for creating or updating the scored blocked word list 122. The higher score word extraction means 109 is a word extraction means for extracting the highest M scores from the word set obtained as a result of the forward match search.
First, for the sake of explanation, a method is described in which a word that matches the search character string is searched from a scored word list that is not blocked, and the M score is obtained.

  The left diagram in FIG. 12 is an example of the scored word list 113a having score information. It consists of an address part 1001, an entry part 1002, and a score part 1003. The score given to each word need not be particularly limited, and may be, for example, the frequency of appearance of a word in a document. First, as in the first embodiment, a range on the word list 113 of words that match forward is searched. Get the words in that range sequentially, and leave only those with the highest score. A specific example is shown below.

(Example 6) From the word list with scores 113 in FIG.
1. The minimum forward matching word “aaa” and the maximum forward matching word “azzz” are searched in dictionary order by the same method as in the first embodiment, and the addresses 500 and 505 pointed to by each are obtained.
2. The word list 113 is scanned sequentially from the address 500, and “aaa” and “abc” are added to the output candidates.
3. Next, “abcd” is acquired. Since the minimum score of the output candidate is 30 and the score of “abcd” is 5, the output candidate is not added to the output candidate.
4). Next, “abfgh” is acquired, but is not added to the output candidate because the score is below the minimum score.
5. Next, “afghi” is acquired, but is not added to the output candidate because the score is below the minimum score.
6). Next, “azzz” is acquired. Since the score is 40, which is larger than the current score minimum value 30, the current minimum score “aaa” is deleted, “azzz” is added to the output candidate, and the minimum score is updated to 40.
7. Since address 505 is reached, the current output candidate is output. {“Abc”, “azzz”}

  However, in the above method, when there are N words that match forward, N word list accesses and score comparisons occur, which is inefficient. Therefore, the word list 113 is divided into a plurality of blocks every predetermined number like the scored blocked word list 122 of FIG. The block address portion 1001a is expressed as “block number: address in block” as in the second embodiment. The score part 1003a stores the score of each word in a part corresponding to the score part 1003 of the word list 113. The intra-block maximum score unit 1004 stores the maximum score in each block. The scored blocked word list creation unit 108 searches for a block to be added and adds a word in the same manner as the blocked word list creation unit 107 of the second embodiment when adding a word. However, at that time, the intra-block maximum score part 1004 is referred to, and if the score of the word to be added is larger than the intra-block maximum score, the intra-block maximum score part 1004 is updated to the word score to be added.

  FIG. 13 is a diagram showing a procedure for acquiring the top M scores by such a configuration. When sequentially acquiring words from the word list and comparing the scores as in (Example 6), the score can be skipped by comparing with the maximum score in the block, and the top M items can be acquired efficiently. . A specific example is shown below.

(Example 7) From the scored blocked word list 122 of FIG.
1. The minimum score value of the output candidate is initialized to 0, the block number B is initialized as the block number of the minimum word, and the intra-block address A is initialized as the intra-block address of the minimum word (steps ST71 and ST72). Then, the smallest forward matching word “aaa” and the largest forward matching word “azzz” are searched in the dictionary order by the same method as in the first embodiment, and block addresses 5:14 and 7: 1 pointed to by each are obtained. .
2. The scored blocked word list 122c is scanned in order from the block address 5:14 to obtain “aaa”. Since one item has not yet been acquired, it is added to the output candidate, and since it is not the block end, the block address A is incremented (step ST73 → ST74 → ST75 → ST78 → ST79 → ST80).
3. Next, “abc” is acquired. Since only one item has been acquired yet, it is added as an output candidate. At this point, the minimum score is 30. The in-block address A is incremented (steps ST73 → ST74 → ST75 → ST78 → ST79 → ST80).
4). Next, “abca” is acquired. Since two output candidates have already been acquired, the output candidate minimum score is compared with the score (steps ST73 → ST74 → ST76). Since the output candidate minimum score is larger, it is not added to the output candidate. Since this is the end of the block, the block number B is incremented (steps ST78 → ST79 → ST81).

5. As a result of the increment of B, reference is made to block 6, but since the maximum score in block 6 is 20 and is smaller than the current minimum score 30, there may be no word to be added to the output candidate in this block. It can be understood (step ST82). Word acquisition from block 6 is not performed, and B is incremented and moved to block 7 (step ST79 → ST81).
6). In step ST82, since the maximum score in the block 7 is 70 and is larger than the current minimum score 30, there is a possibility that a word to be added to the output candidate exists in this block. Therefore, “azzz” is acquired and the score is 40. Therefore, the current minimum score “aaa” is deleted because it is larger than the current score minimum value 30 and “azzzz” is added to the output candidate, and the minimum score is set to 40. Update (steps ST83 → ST73 → ST74 → ST76 → ST77).
7. In step ST78, since address 7: 1 has been reached, the current output candidate is output {“abc”, “azzz”}.
As described above, by dividing the word list and storing the maximum score in the block, it is possible to perform a high-speed search of a character string by a double arrangement and efficient extraction of the upper rank of the score.

  As described above, according to the dictionary search device of the third embodiment, the word list is composed of a plurality of blocks obtained by dividing the registered words into predetermined numbers, and each registered word is given a score. , Each block has a maximum score of registered words belonging to the block, and the word extraction means has a maximum score smaller than the output candidate minimum score when extracting an arbitrary number of words having a higher score from the word list Since the block is excluded from the extraction target, the search can be performed at high speed, and the word having the higher score can be efficiently extracted.

Embodiment 4 FIG.
In the third embodiment, the word list is divided into a predetermined number. However, an example in which search results are efficiently obtained in groups by grouping and dividing each word set having the same morpheme is described below. Embodiment 4 will be described below. The configuration of the dictionary search apparatus in the fourth embodiment in the drawing is the same as that in the third embodiment, and will be described with reference to the configuration in FIG.

  FIG. 14 shows an example of the scored blocked word list 122 in the fourth embodiment. The left diagram in FIG. 14 is an example of the word list 113b in which “/” is inserted in the morpheme break. For example, “Tokai / Daigaraku” in the entry portion 1002b indicates that it is composed of two morphemes “Tokaikai” and “Daigaraku”. The score part 1003b is a score corresponding to the entry part 1002b. Consider searching for a word that matches the search character string from such a word list and outputting the first morpheme of the corresponding word. When outputting only M cases with higher scores, the maximum score within the group is regarded as the group score, and the group with higher scores is output.

  In the case of the word list 113b on the left side of FIG. / Daigaku / Mae, Tohoku / Daigaku, “Tohoku / Hotel”, but the first groups are “Tokai”, “Tokai”, “Tokyo”, “Tokyo” , “Tokyo”, “Tohoku”, and “Tohoku”, so there are duplicates. When duplication is removed, the output is “Tokai”, “Tokyo”, and “Tohoku”.

  When outputting the top two scores, the “Tokai” group has a maximum score of 45 in the group, the “Tokyo” group is 70, and the “Tohoku” group is 40. .

Next, the present embodiment shows an example in which the top M items are efficiently output by grouping the word list 113b with the same head morpheme and dividing it into blocks.
An example of the scored blocked word list 122 is shown on the right side of FIG. The entry portion 1002c is grouped by “TOKAI”, “TOKYO”, and “TOHOHOKU”, and is divided into blocks. The score portion 1003c indicates the score corresponding to the entry portion 1002c, and the intra-block maximum score portion 1004a indicates the maximum score in the block. Since the block 7 does not have a plurality of the same head morphemes, the block is divided into a predetermined number of words as in the third embodiment. As in the third embodiment, the higher score word extraction unit 109, which is a word extraction unit, can efficiently acquire a higher score group by skipping blocks.

For example, in the blocked word list 122 with a score on the right side of FIG. 14, when searching for the first group of the top two words with the highest score that matches “to”, first, as in the second embodiment, first the block address “4: 1” is searched. ”To“ 7: 1 ”are searched as forward matching words.
Words are sequentially acquired from the block address “4: 1”, the leading morpheme “Toukai” and the maximum score 45 in the block are acquired and added to the output candidates. Next, the top morpheme “Tokyo” and the maximum score 70 in the block are acquired from the block 5 and added to the output candidates. At this time, the output candidate group has a minimum score of 45, and the next block 6 has a maximum score in the block of 40, so that it can be skipped. Further, since the next block 7 has a maximum score in the block of 65, the word is sequentially acquired, the first morpheme “Toritsu” and the score 50 are obtained, and “Tokakai” in the output candidates is replaced with “Toritsu”. Since the forward matching word ends here, “Tokyo” and “Toritsu” are output.

By grouping in accordance with the output format as described above, it is possible to efficiently acquire a group having a higher score.
In the present embodiment, only the first morpheme is used for grouping. However, it is possible to set the output unit to an arbitrary layer by grouping hierarchically after the second morpheme.

  As described above, according to the dictionary search device of the fourth embodiment, the word list is divided into blocks with a set of words having the same morpheme, and each registered word is given a score, and each block When the word extraction unit extracts an arbitrary number of words having a higher score, the block having the maximum score lower than the output candidate minimum score is excluded from the extraction target. As described above, even when the word list is a word set having the same morpheme, the search can be performed at a high speed, and a word having a higher score can be efficiently extracted.

  101 search character string input means, 102 double array index search means, 103 minimum / maximum child node search means, 104 word extraction means, 105 search result output means, 106 index creation means, 107 blocked word list creation means, 108 with score Blocked word list creation means, 109 score higher word extraction means, 111 double array index, 112 minimum / maximum child node index, 113 word list, 114 word set, 121 blocked word list, 122 blocked word list with score.

Claims (4)

When a search character string is given, a double array index search means for searching for a node corresponding to the search character string from the double array index;
In the minimum / maximum child node index storing information for transitioning to the smallest registered word in dictionary order and information for transitioning to the largest registered word among the child nodes in the trie structure in the double array index Based on the child node of the node searched by the double array index search means, minimum and maximum child node search means for searching for the node that becomes the minimum character string and the node that becomes the maximum character string in the dictionary order; ,
A word extracting unit that extracts words from a word corresponding to the minimum node searched by the minimum / maximum child node searching unit to a word corresponding to the maximum node from a word list in which the registered words are sorted and stored in a dictionary order; A dictionary search device comprising: The word list is composed of a plurality of blocks obtained by dividing a registered word into predetermined numbers.
When registering a new word in the word list, the largest word that is smaller in dictionary order than the new word is searched for among the registered words, and the new word is added to the block of the searched word 2. The dictionary search apparatus according to claim 1, further comprising a block word list creating means. The word list is composed of a plurality of blocks obtained by dividing a registered word by a predetermined number, and each registered word has a score, and each block has a maximum score of the registered words belonging to the block,
The word extracting means, when extracting an arbitrary number of words having a higher score from the word list, excludes blocks whose maximum score is lower than an output candidate minimum score from extraction targets. The dictionary search device according to claim 1 or 2. The word list is divided into blocks with a set of words having the same morpheme, and each registered word is given a score, and each block has a maximum score of registered words belonging to that block,
2. The dictionary search according to claim 1, wherein the word extraction unit excludes a block having the maximum score lower than the output candidate minimum score from the extraction target when extracting an arbitrary number of words having the higher score. apparatus.

Images