JP2012059126A - Search device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To solve the problem that an unnatural search result is obtained due to a sequence of words or syllables in a conventional device which compares an input character string with candidates of a search object facility name per word or syllable to calculate search scores on the basis of the numbers of matching words or syllables and presents the candidates in order from the highest score when searching a facility name of a facility with its formal name unknown.SOLUTION: A search device includes: search means which collates an input character string with a plurality of search object documents and outputs a plurality of documents and search scores according to frequencies with which the character string appears in the documents; a morpheme dictionary which holds morphemes of the search object documents and penalty values which are given to respective morphemes in accordance with their degrees of importance during search; and search ranking correction means which refers to the morpheme dictionary for search results to reconfigure the output order of the search results on the basis of corrected search scores obtained by subtracting penalty values from morphemes existing in the documents but not extracted from the character string.

Description

  The present invention relates to a large-scale search apparatus that efficiently searches a desired document or facility name from a large number of documents and facility names.

  When building a search system that searches various facility names, users may not know the official name of the facility, so the facility name is decomposed into morphemes and syllables, and morphemes and syllable unigrams and bigrams are converted. Conventionally, there is a technique for performing a search as a collation unit, and such a technique is disclosed in Patent Document 1 below.

In Patent Document 1, an input character string is compared with the name of a facility to be searched in units of words, syllables, etc., a search score is calculated based on the number of unigrams and bigrams of matched words and syllables, and candidates are in descending order of score. The technique which presents is disclosed.
However, in the technique of Patent Document 1, for example, when the official name of the department store “Umibe” in the Ofuna is “Umibe Ofuna”, the input string “Ofuna Umibe (Ofune Umibe)” is used for the number of syllable bigrams. Based on the search result, the search result is more unnatural than the correct answer, “Umbeo Funa (Umibe Ofuna)”, “Eshshoboo Funa Umbeten (A Shobo Ofuna Umibe)” There was a problem of being output to the top of the. This is because the syllable bigram "Nau" in the input string does not match in the former "Umibeo Funa", but in the latter "Esshoboo Funa Umibeten" This is because the latter has a higher search score.

JP 2008-262279 A

  The present invention has been made to solve the above-described problems, and an object thereof is to suppress the unnatural search results as described above and improve the search accuracy.

The search device according to the present invention provides:
A search device for searching a desired document from a plurality of documents to be searched based on an input character string,
Using the character string as input, the character string and a plurality of documents to be searched are collated, a plurality of documents partially or completely matching the character string, and the character string appear in the plurality of documents. Search means for outputting a search score corresponding to the number of times to be searched as a search result;
A morpheme dictionary that holds a morpheme for each of the plurality of documents to be searched and a penalty value assigned to each morpheme according to the importance used during the search;
The search result of the character string and the search means is input, and for each document of the search result, the morpheme is extracted from the character string with reference to the morpheme dictionary, and exists in the document, Search rank correction means for correcting the search score by subtracting the penalty value from the morpheme that has not been extracted from the character string, and reconstructing and outputting the output rank of the search result based on the corrected search score; Is provided.

  According to the search device of the present invention, a plurality of documents to be searched searched by the search means based on the input character string, and a search score corresponding to the number of times the character string appears in the plurality of documents The search result is referred to by referring to a morpheme dictionary that holds a morpheme for each of a plurality of documents to be searched and a penalty value assigned to each morpheme according to the importance used in the search. The search score is corrected by subtracting the penalty value for morphemes that are present in the document but not extracted from the input character string, and the output order of the search results is re-established based on the corrected search score. There is an effect of suppressing unnatural search results by the search order correcting means configured and output.

It is a block diagram which shows the structure of Embodiment 1 of the search device by this invention. It is explanatory drawing of the search object facility name for text search dictionary preparation. It is explanatory drawing of the text search dictionary created from the search object facility name. It is explanatory drawing which shows the example of a morpheme dictionary in which the penalty value was set. It is explanatory drawing which shows the example of an output of the intermediate search result of the ID number of a facility name which is a search result of a search means, and a search score pair. It is a flowchart of the process sequence by a search order correction means. It is explanatory drawing which shows the magnitude | order rearrangement result of the correction search score by a search order correction means. It is a block diagram which shows the structure of Embodiment 2 of the search device by this invention. It is explanatory drawing which shows the order rearrangement result of the corrected search score by the search order correction means of Embodiment 2.

Embodiment 1 FIG.
In the present embodiment, a description will be given taking as an example the case of searching for names of facilities and sightseeing spots (hereinafter, facilities and sightseeing spots are collectively referred to as facilities for simplicity).
FIG. 1 is a block diagram showing a configuration of a first embodiment of a search device according to the present invention.
In the figure, 1 is an input terminal of a character string, 2 is a character string, 3 is a search means, 4 is a search dictionary memory,
5 is an intermediate search result, 6 is a search order correcting means, 7 is a morpheme dictionary memory, and 8 is a search result.

  In the search dictionary memory 4, a text search dictionary is created and stored in advance. A method for creating a text search dictionary will be described. For example, as shown in FIG. 2, the search target facility name is described as “A Shobo Ofuna Umibe Store”, “Umibe Ofuna”, and the like. Figures in parentheses indicate the name of the facility. Here, “Umibe” is a proper noun of the facility, and in this example, it is a department store name.

  The text search dictionary is configured as a transposed index with language units constituting facility names as index words. In this example, two chain (syllable bigram) of the syllable of the facility name reading is used as an index word. The syllable bigrams included in “A Shobo Ofuna Umibe” are “Esho,” “Shoboo,” “Booh,” “Ohfu,” “Fu” There are 10 types: N, Nau, Umi, Mibe, Bete, and Ten. There are five syllable bigrams in “Umibe Ofuna”: “Umi”, “Mibe”, “Beow”, “Ohfu”, and “Funa”. The search dictionary memory 4 holds these syllable bigrams as index words and the index words and facility name ID numbers as text search dictionaries. A text search dictionary created from the facility name is shown in FIG.

  In the morpheme dictionary memory 7, a morpheme dictionary is created and stored in advance. A method for creating a morpheme dictionary will be described. First, the facility name to be searched is divided into morphemes using a morphological analyzer or the like. If necessary, the division result into morphemes may be corrected manually. In addition, division processing is unnecessary in a language originally divided into words such as English, and in this case, the word is regarded as a morpheme. Next, a predetermined penalty value is assigned to each morpheme according to the importance used at the time of search, and the morpheme dictionary is held together with the morpheme. In the present embodiment, the penalty value is set to a larger value for a morpheme that is less likely to be omitted when searching for the facility. FIG. 4 shows an example of the morpheme dictionary for “A Shobo Ofuna Umibe Store” and “Umibe Ofuna”. The morpheme dictionaries of “A Shobo Ofuna Umibe” are “Eshshobo (3)”, “Ohuna (1)”, and “Umibe (1)”. Values in parentheses are penalty values. The character string 2 when searching for “A Shobo Ofuna Umibe store” is considered to be unlikely to omit the morpheme “Eshoshibo”, so a higher penalty value than other morphemes is given. . On the other hand, the morpheme dictionary for “Umibe Ofuna” gives a higher penalty value than other morphemes because it is unlikely that the morpheme “Umibe” will be omitted as an utterance when searching for the facility. ing.

Next, the search operation will be described.
When the character string 2 is input from the character string input terminal 1, the search means 3 first extracts all syllable bigrams constituting the character string 2. For example, if the input character string 2 is “Ohuna Umibe”, five syllable bigrams “Ohu”, “Funa”, “Nau”, “Umi”, and “Mibe” are extracted as syllable bigrams. .

  Next, the search means 3 refers to the text search dictionary stored in the search dictionary memory 4 and adds 1 to the search score of the facility including the syllable bigram for each extracted syllable bigram. This score addition process is performed on the extracted whole syllable bigram. In this example, “A Shobo Ofuna Umibe store” with facility ID = 1 is “Ofu” “Funa” “Nau” “Umi” “Mibe” Since the five syllable bigrams match the syllable bigram of the character string 2, the search score is 5. On the other hand, “Umibe Ofuna” with facility ID = 2 matches the four syllable bigrams of “Ohu”, “Funa”, “Umi”, and “Mibe” with the syllable bigram of string 2. Therefore, the search score is 4. After the addition process is completed, the search means 3 outputs a pair of ID numbers and search scores of N facility names having a search score of 1 or more as the intermediate search result 5. Here, N is an integer of 1 or more. An output example of the intermediate search result 5 is shown in FIG.

  Next, the search order correction means 6 receives the character string 2 from the character string input terminal 1 and the intermediate search result 5 from the search means 3 as input, and morpheme dictionary memory for each of the N facility names in the intermediate search result 5. The morpheme contained in the character string 2 is extracted by collating with the character string 2 using the morpheme dictionary of the facility name stored in 7. The extracted morpheme and the morpheme dictionary of the facility stored in the morpheme dictionary memory 7 are compared, and the morpheme present in the morpheme dictionary but not extracted from the phoneme string of the recognition result is shown in FIG. The search score is re-scored by assigning a preset penalty value to the indicated morpheme dictionary.

The specific processing procedure of the search order correction means 6 will be described below with reference to FIG.
Procedure 1) Set k = 1 (st101 in FIG. 6)
Procedure 2) Refers to the morpheme dictionary stored in the morpheme dictionary memory 7 and refers to the facility name of the k-th place (in this case, k = 1 because it is k = 1) of the intermediate search result 5 of the search means 3 shown in FIG. The morpheme and character string 2 are collated, and the morpheme contained in the character string 2 is extracted (st102 in FIG. 6). Here, the collation processing is to check whether or not a combination of one or more morphemes in the morpheme dictionary matches the character string 2. If they match, the one or more morphemes are converted into the character string 2. It is determined that it is included, and the one or more morphemes are extracted.
For example, in the case of k = 1, the search result of the first place is the facility name with the facility ID = 1 as described above. As shown in FIG. 4, the morphemes in the morpheme dictionary are “Esshobo”, “Ohfu” "N", "Umibe", "Ten". When collation is performed between these morphemes and the character string 2 “Oh Funa Umibe”, two morphemes “Oh Funa” and “Umibe” are extracted.

Step 3) The morpheme included in the character string 2 extracted in step 2 is compared with the morpheme in the morpheme dictionary of the k-th search result, and the morpheme that exists in the morpheme dictionary but does not exist in the character string 2 On the other hand, a penalty accumulated value P (k) obtained by accumulating the penalty values in the morpheme dictionary is calculated (st103 in FIG. 6).
For example, in the case of k = 1, as described above, the morpheme included in the character string 2 is “Ofuna” and “Umbe”, and the morpheme in the morpheme dictionary is “Eshoshibo”, “Oh Since “Funa”, “Umibe”, and “Ten”, the two morphemes that exist in the morpheme dictionary but do not exist in the character string 2 are “Esshobo” and “Ten”. Since the penalty values for these morphemes are 3 and 0, respectively, as shown in FIG. 4, the penalty accumulated value P (k) is P (k) = 3 + 0 = 3.

  Procedure 4) The corrected search score S '(k) is calculated from the penalty accumulated value P (k) calculated in the procedure 3 and the search score S (k) by the following equation (1) (st104 in FIG. 6). In the equation (1), α is a constant determined experimentally in advance, and α = 0.5 in the present embodiment.

S '(k) = S (k)-αP (k) (1)
As a result, in the above-described example of k = 1, S ′ (1) = 5−0.5 * 3 = 3.5.

Step 5) If k = N, go to step 6. If k <N, set k = k + 1 and return to step 2. (St105, st106 in FIG. 6).
Step 6) Using the corrected score S ′ (k) (k = 1 to N) corrected in step 4, the search results are rearranged in descending order of the corrected score S ′ (k), and output as the search result 8. (St107 in FIG. 5)

The processing procedure is as described above. As a result of the above processing, if the facility ID = 2 as the output result of the search means, the morphemes in the morpheme dictionary are “Umbe” and “Ohuna” as shown in FIG. When matching is performed with “Ohuna Umibe” in column 2, two morphemes “Ohuna” and “Umibe” are extracted. As a result, since all the morphemes in the morpheme dictionary exist in the recognition result, the penalty accumulated value P (k) becomes 0, and the corrected search score S ′ (2) = calculated by the equation (1) = S (2) = 4.
FIG. 7 shows the result of rearranging the search order in descending order of the corrected search score. It can be seen that “Umibe Ofuna” is ranked first in the search order.

  As described above, according to the present embodiment, a morpheme dictionary is provided for each facility name, and a penalty value is set for each morpheme when the morpheme is not included in the character string 2. As the penalty value, a morpheme that is less likely to be omitted when searching for the facility is set with a larger penalty value, and the corrected score S ′ (k) is calculated by subtracting the penalty accumulated value P (k) as described above. Since the search results are output in descending order, the effect of suppressing the unnatural result that “A Shobo Ofuna Umibe Store” is searched higher than “Umibe Ofuna” for the utterance “Ofune Umibe”. There is.

  In this example, the search means 3 uses the syllable bigram as the index word of the transposed index, but the index word may be an arbitrary unit. For example, it may be a bigram of words or a unigram of words or syllables. In this example, the transposition index is used as the search method in the search means 3, but any search method that allows partial matching between the character string 2 and the search target may be used.

  In addition, as a penalty value to be assigned to each morpheme in the morpheme dictionary, a penalty value larger than other morphemes is assigned to the first morpheme of the facility name whose last morpheme constituting the facility name is `` store ''. May be. In general, the names of facilities in parks and department stores often have the pattern of “proprietary nouns such as brand names of facilities + (park name or department store name) + store”, and the name of the facility whose last morpheme is “store” This is because it is considered that the first morpheme of is hardly omitted when searching for the facility. Thus, by giving a penalty value, the effect of aiming at the efficiency of a penalty provision operation | work is acquired.

Embodiment 2. FIG.
In the present embodiment, a case where a facility name is searched as in the first embodiment will be described as an example.
FIG. 8 is a block diagram showing the configuration of the second embodiment of the search device according to the present invention.
In the figure, the same parts as those in the first embodiment are denoted by the same reference numerals, and the description thereof is omitted. Reference numeral 9 is a voice input terminal, 10 is an input voice, 11 is a voice recognition means, 12 is a language model memory, and 13 is an acoustic model memory.

A statistical language model is created and stored in the language model memory 12 in advance. In this example, trigrams in units of syllables are learned and stored using the syllable string of all facility names to be searched as learning data. The advantage of using syllables as a unit is that, regardless of the number of facilities used as learning data, the number of types of syllables is less than a few hundred, so a language model can be created that suppresses the increase in the amount of computation during recognition. .
The acoustic model memory 13 stores an acoustic model obtained by modeling a voice feature. In the present embodiment, the acoustic model is, for example, an HMM (Hidden Markov Model).

Next, speech recognition and search operations will be described.
When speech 10 is input from the speech input end 9, the speech recognition means 11 uses the language model stored in the language model memory 12 and the acoustic model stored in the acoustic model memory 13 to perform speech recognition using, for example, a Viterbi algorithm. The character string 2 is output as the speech recognition result. The character string 2 is written in hiragana in this example.
For example, the output of the speech recognition means 11 whose utterance content of the voice 10 is “Ofuna Umibe” is, for example, “Oh Fu Umi de”. In this example, it is assumed that the last syllable of “Umbe” is misrecognized as “de”.

  Next, the search means 3 performs the search process as follows with the character string 2 “Oh Fu Na Umi” as an input. First, all the syllable bigrams that make up the character string “Oh Fu Na Umi” are extracted. In this example, five syllable bigrams “Ofu” “Funa” “Nau” “Umi” “Mide” are extracted. Next, the text search dictionary stored in the search dictionary memory 4 is referred to, and 1 is added to the search score of the facility including the syllable bigram for each extracted syllable bigram. This search score addition processing is performed on the extracted whole syllable bigram. In this example, “A Shobo Ofuna Umibeten” with facility ID = 1 has four “Ofu”, “Funa”, “Nau”, and “Umi”. The search score is 4 because the syllable bigram matches the syllable bigram of string 2. On the other hand, “Umibe Ofuna” with facility ID = 2 matches the three syllable bigrams of “Ohu”, “Funa”, and “Umi” with the syllable bigram of string 2, so search The score is 3. After the addition process is completed, the search means 3 outputs a pair of ID numbers and search scores of N facility names having a search score of 1 or more as the intermediate search result 5. Here, N is an integer of 1 or more.

  Next, the search order correcting means 6 receives the character string 2 and the intermediate search result 5 as input, and collates with the character string 2 by using the facility name morpheme dictionary for each of the N facility names of the intermediate search result 5. Thus, the morpheme included in the character string 2 is extracted. The extracted morpheme is compared with the morpheme dictionary of the facility, and a search score is given by assigning a preset penalty value to the morpheme that exists in the morpheme dictionary but is not extracted from the phoneme string of the recognition result. Rescore.

  The specific processing procedure of the search order correcting means 6 is almost the same as that of the first embodiment. The difference is the method of collation processing between the morpheme of the facility name of the retrieval result and the character string 2 in the processing procedure 2 of the retrieval order correcting means 6 described in the first embodiment. In Embodiment 1, collation processing is performed by checking whether or not a combination of one or more morphemes in the morpheme dictionary matches the character string 2, but in this embodiment, one or more in the morpheme dictionary. The morpheme combination and the character string 2 are collated by DP (Dynamic Programming) matching that allows substitution, omission, or insertion of syllables or phonemes. If the number of replacements, omissions, or insertions is equal to or less than a predetermined number c, it is determined that the one or more morphemes are included in the character string 2, and the one or more morphemes are extracted. In the present embodiment, the predetermined number c = 1. The reason for using DP matching is to enable extraction of a morpheme even when there is a speech recognition error in the character string 2 and the morpheme in the morpheme dictionary does not completely match the syllable or phoneme.

  For example, in the case of k = 1, the search result of the k (= 1) rank is the facility name of the facility ID = 1, and the morphemes in the morpheme dictionary are “Esshobo”, “Ohfu” as shown in FIG. "N", "Umibe", "Ten". A matching process using DP matching is performed between these morphemes and the speech recognition result “Oh Fu Na Umi”. As a result, two morphemes “Ofuna” and “Umibe” are extracted from the character string 2 “Ohuna Umi de”. Of these, “Umibe” has no exact syllable string in “Ohuna Umi de”, which is the character string 2 of the speech recognition result, but there is one replacement of the syllable “be” and “de”. Therefore, extraction is possible by performing DP matching.

In the case of k = 2, the search result of the k (= 2) rank is the facility ID = 2, and the morpheme in the morpheme dictionary is “Umbe” and “Ohuna” as shown in FIG. When DP matching is performed between the morpheme and the character string 2 of the speech recognition result “Oh Funa Uide”, two morphemes “Oh Funa” and “Umbe” are extracted.
Since the processing after the procedure 3 is the same as that of the first embodiment, the description thereof is omitted.

  FIG. 9 shows a result of rearranging the search order in the descending order of the corrected search score by the above processing. According to FIG. 9, it is understood that “Umibe Ofuna” is ranked first in the search order. In addition, compared with the search score and the corrected search score in the first embodiment shown in FIG. 7, each of the search score and the corrected search score in this example is 1 smaller, but this is a speech recognition result as described above. The last one syllable “de” of “Oh fu na umi” in the character string 2 is a misrecognized “be”, and as a result, the number of syllable bigrams that match when calculating the search score in the search means 3 is one. This is because it has decreased.

  The penalty value assigned to each morpheme of the morpheme dictionary held in the morpheme dictionary memory 7 is different from the first morpheme of the facility name whose last morpheme constituting the facility name is “store”. You may give a penalty value larger than a morpheme. In general, the names of facilities in parks and department stores often have the pattern of “proprietary nouns such as brand names of facilities + (park name or department store name) + store”, and the name of the facility whose last morpheme is “store” This is because it is considered that the first morpheme of is hardly omitted when searching for the facility. Thus, by giving a penalty value, the effect of aiming at the efficiency of a penalty provision operation | work is acquired.

  The present invention relates to a search device that efficiently performs a large-scale search for a desired document or facility name from a large number of documents and facility names using character strings, and can be applied to various navigation systems such as portable terminals and car navigation systems. is there.

  1, 9; character string input terminal, 2; character string, 3; search means, 4; search dictionary memory, 5; intermediate search result, 6; search rank correction means, 7; morpheme dictionary memory, 8; 10; input speech; 11; speech recognition means; 12; language model memory; 13; acoustic model memory.

Claims (5)

A search device for searching a desired document from a plurality of documents to be searched based on an input character string,
Using the character string as input, the character string and a plurality of documents to be searched are collated, a plurality of documents partially or completely matching the character string, and the character string appear in the plurality of documents. Search means for outputting a search score corresponding to the number of times to be searched as a search result;
A morpheme dictionary that holds a morpheme for each of the plurality of documents to be searched and a penalty value assigned to each morpheme according to the importance used during the search;
The search result of the character string and the search means is input, and for each document of the search result, the morpheme is extracted from the character string with reference to the morpheme dictionary, and exists in the document, Search rank correction means for correcting the search score by subtracting the penalty value from the morpheme that has not been extracted from the character string, and reconstructing and outputting the output rank of the search result based on the corrected search score; ,
A search device comprising:   2. The search apparatus according to claim 1, wherein the input character string is obtained by recognizing the input voice by voice recognition means and outputting the recognition result as a character string.   The penalty value given to the morpheme is assigned a larger penalty value for a morpheme that is less likely to be omitted from an input character string when searching for the document. Search device.   The search order correction means uses DP matching on a character string as a method of extracting a morpheme from the character string with reference to the morpheme dictionary, and even when the character string and the morpheme in the morpheme dictionary do not completely match The search device according to claim 1, wherein a morpheme is extracted from the character string.   The document to be searched is a plurality of facility names, and a penalty value larger than other morphemes is given to the first morpheme of the facility name whose last morpheme constituting the facility name is “Store” The search device according to claim 1, wherein:

Images