JP7032650B2 - Similar text search method, similar text search device and similar text search program - Google Patents

Description

The present invention relates to a similar text search method, a similar text search device, and a similar text search program.

As a natural language process by a computer, you may want to search for stored text that is similar to the input text from the stored text stored in the database. For example, a dialogue system that registers a sample of inquiry text and a response text corresponding to the sample in a database, searches for a sample similar to the input inquiry text, and outputs a response text corresponding to the similar sample. Is conceivable to build.

As a method of searching for a stored text similar to the input text, there is a method of evaluating the commonality of words appearing between the two texts. For example, the following search methods can be considered. A plurality of hash functions (sometimes called Min-hash functions) that calculate one hash value from a word set contained in a certain text are defined. Each hash function has a correspondence relationship in which different values are associated with different words, and outputs the smallest value among the values corresponding to the words included in a certain word set as a hash value. For each stored text, a vector enumerating a plurality of hash values calculated by using the plurality of hash functions is generated in advance. Similarly, a vector is calculated from the word set contained in the input text and the above-mentioned multiple hash functions, and a stored text having an approximate vector is selected.

A question / answer server has been proposed that narrows down the candidates for the response text corresponding to the inquiry text. The question-and-answer server of the proposal extracts words from the inquiry sentence, searches a plurality of comment sentences including the extracted words from the database, and classifies the searched comment sentences into a plurality of topic groups. The question-and-answer server extracts from the database the candidates for the answer sentence whose similarity with the comment sentence is equal to or more than the threshold value for each topic group.

Further, a terminal device for searching a response sentence corresponding to an inquiry sentence by using different search methods in combination has been proposed. The proposed terminal device searches for a response sentence corresponding to the inquiry sentence by the first search method, and reproduces the searched first response sentence by voice. While the first reply sentence is being played back, the terminal device searches for the reply sentence corresponding to the inquiry sentence by the second search method, and the searched second reply sentence is similar to the first reply sentence. If the degree is low, the second response sentence is additionally reproduced by voice after the reproduction of the first response sentence is completed.

Further, a hash function generation device for learning a hash function for calculating a hash value of contents has been proposed. The proposed hash function generator calculates a feature amount from each of a plurality of contents. Further, the hash function generation device calculates the correlation of the semantic label for each combination of the two contents based on the semantic label given to each content. The hash function generator learns the hash function so that the higher the correlation between the semantic labels, the closer the hash value calculated from the features of each of the two contents.

Japanese Unexamined Patent Publication No. 2014-11316 Japanese Unexamined Patent Publication No. 2016-9091 Japanese Unexamined Patent Publication No. 2016-66012

In the search method that evaluates the commonality of the words that appear, the commonality of the words is evaluated low because different expressions are used even though the similarities of the contents are high, and there is a problem that search omission may occur. There is. For example, if the input text or the stored text is a user's utterance message, the spoken language is short and has various expressions, so the overall probability that a common word will appear between the input text and the stored text is overall. It gets lower. As a result, the search accuracy of the stored text similar to the input text tends to be low.

In one aspect, it is an object of the present invention to provide a similar text search method, a similar text search device, and a similar text search program that improve the search accuracy of similar texts.

In one aspect, a computer-executed similar text retrieval method is provided. Accepts the input of the first text. A first word belonging to any of the two or more first words by extracting two or more first words contained in the first text and referring to a related word dictionary indicating a group of related words. A first dummy word indicating the group is assigned to the word. Generates first feature information according to a first word set containing two or more first words and a first dummy word. Includes two or more second words contained in the second text and a second dummy word indicating a group to which any second word belongs, which is stored corresponding to each of the plurality of second texts. A second text similar to the first text is searched based on the comparison between the second feature information according to the second word set and the first feature information.

Further, in one embodiment, a similar text search device having a storage unit and a processing unit is provided. Also, in one aspect, a similar text search program is provided.

In one aspect, the search accuracy of similar texts is improved.

It is a figure explaining the example of the similar text search apparatus of 1st Embodiment. It is a block diagram which shows the hardware example of an information processing apparatus. It is a figure which shows the example of the utterance table. It is a figure which shows the example of a hash function and a vector. It is a figure which shows the example of the search tree. It is a figure which shows the calculation example of a Jackal coefficient. It is a graph which shows the relation example between the threshold of similarity and the number of hits of a search target utterance. It is a figure which shows the example of the related word table. It is a figure which shows the example of calculating a vector from a word set. It is a figure which shows the selection example of the answer utterance corresponding to the inquiry utterance. It is a block diagram which shows the functional example of an information processing apparatus. It is a flowchart which shows the procedure example of index generation. It is a flowchart (continued) which shows the procedure example of index generation. It is a flowchart which shows the procedure example of the utterance search.

Hereinafter, the present embodiment will be described with reference to the drawings.
[First Embodiment]
The first embodiment will be described.

FIG. 1 is a diagram illustrating an example of a similar text retrieval device according to the first embodiment.
The similar text search device 10 of the first embodiment searches the database for text similar to the input text. The similar text search device 10 may be referred to as an information processing device or a computer. Further, the similar text search device 10 may be a client device operated by a user or a server device accessed via a network. The similar text search device 10 may be used in a dialogue system that receives inquiry text from a user and outputs response text.

The similar text retrieval device 10 has a storage unit 11 and a processing unit 12. The storage unit 11 may be a volatile semiconductor memory such as a RAM (Random Access Memory) or a non-volatile storage such as an HDD (Hard Disk Drive) or a flash memory. The processing unit 12 is, for example, a processor such as a CPU (Central Processing Unit), a GPU (Graphics Processing Unit), or a DSP (Digital Signal Processor). However, the processing unit 12 may include an electronic circuit for a specific purpose such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array). A collection of multiple processors may be referred to as a "multiprocessor" or simply a "processor."

The storage unit 11 stores the related word dictionary 13. The related word dictionary 13 is data indicating a group of words related to each other. Related words are words that have similar meanings. For example, the related word dictionary 13 indicates that "cat" and "nyanko" belong to the same group G1 and "rice" and "food" belong to the same group G2.

Further, the storage unit 11 stores a plurality of feature information (second feature information) including the feature information 19a and 19b corresponding to the plurality of texts (second text) including the texts 15a and 15b. The texts 15a and 15b are search target texts to be collated with the text 14 (first text) input to the similar text search device 10, and are character strings including two or more words. The feature information 19a, 19b is used as an index for searching and is generated from the texts 15a, 15b. The storage unit 11 may or may not store the texts 15a and 15b themselves. The feature information 19a and 19b may be generated by the similar text search device 10 or may be generated by another information processing device.

The method for generating the feature information 19a and 19b will be described later. When the similar text search device 10 is used in the dialogue system, the storage unit 11 may store a plurality of response texts (third texts) in association with a plurality of texts including the texts 15a and 15b. For example, when the search target text most similar to the inquiry text from the user is selected, the response text associated with the selected search target text is output.

The processing unit 12 accepts the input of the text 14. The text 14 is an inquiry text input by the user, and is a character string including two or more words. The text 14 may be input from an input device connected to the similar text search device 10, or may be received from another information processing device via a network. Further, a voice signal may be input to the similar text search device 10 and the voice signal may be converted into the text 14 by voice recognition.

The processing unit 12 extracts two or more words included in the text 14 and generates a word set 16 including the extracted words. For example, the processing unit 12 extracts "nyanko" and "food" from the text 14 and generates a word set 16 including "nyanko" and "food".

Further, the processing unit 12 refers to the related word dictionary 13 and assigns a dummy word (first dummy word) indicating the group to a word belonging to any group of the words extracted from the text 14. .. The processing unit 12 adds the assigned dummy word to the word set 16. The dummy word is a virtual word that is not used in the text 14 and the texts 15a and 15b. For example, since "Nyanko" belongs to the group G1, the dummy word "G1" indicating the group G1 is added to the word set 16. Further, since "food" belongs to the group G2, the dummy word "G2" indicating the group G2 is added to the word set 16. At this time, the original words "Nyanko" and "Esa" are left without being deleted from the word set 16.

The processing unit 12 generates the feature information 18 (first feature information) corresponding to the index of the text 14 from the word set 16 including the original word and the dummy word included in the text 14. The feature information 18 is information for evaluating the commonality of words appearing between the inquiry text and the search target text. The feature information 18 is generated, for example, as follows.

The processing unit 12 prepares a plurality of different hash functions in advance. The processing unit 12 inputs a word set 16 into each of a plurality of hash functions, and generates a vector listing a plurality of hash values output from the plurality of hash functions as feature information 18. The hash function may be a Min-hash function. For example, each hash function has a correspondence relationship in which a unique value is associated with each word and dummy word. Different hash functions have different correspondences. The hash function outputs the smallest value among the values corresponding to the words and dummy words included in the word set as the hash value. For example, a vector such as (0, 1, 2, 2, ...) Is generated from the word set 16 including "Nyanko", "food", "G1" and "G2".

It is possible to generate feature information 19a and 19b from the texts 15a and 15b in the same manner. Two or more words included in the text 15a are extracted, a dummy word (second dummy word) is assigned to the extracted words by referring to the related word dictionary 13, and the original word and the original word included in the text 15a and A word set 17a containing a dummy word is generated. Then, the feature information 19a is generated from the word set 17a. For example, by inputting the word set 17a into a plurality of hash functions, a vector enumerating a plurality of hash values calculated is generated. Further, two or more words included in the text 15b are extracted, dummy words are assigned to the extracted words by referring to the related word dictionary 13, and the original words included in the text 15b and words containing the dummy words are assigned. The set 17b is generated. Then, the feature information 19b is generated from the word set 17b. For example, by inputting the word set 17b into a plurality of hash functions, a vector enumerating a plurality of hash values calculated is generated.

For example, "cat" and "rice" are extracted from the text 15a, a dummy word "G1" indicating the group G1 to which the "cat" belongs is added, and a dummy word "G2" indicating the group G2 to which the "rice" belongs is added. Will be done. Then, a vector such as (0,0,2,2, ...) Is generated from the word set 17a including "cat", "rice", "G1" and "G2". Further, "mail" and "meeting" are extracted from the text 15b, a dummy word "G3" indicating the group G3 to which the "mail" belongs is added, and a dummy word "G4" indicating the group G4 to which the "meeting" belongs is added. Will be done. Then, a vector such as (4, 4, 5, 5, ...) Is generated from the word set 17b including "mail", "meeting", "G3" and "G4".

The processing unit 12 searches for text similar to the text 14 from the search target texts such as the texts 15a and 15b based on the comparison between the feature information 18 and the feature information 19a and 19b. For example, the processing unit 12 searches for the feature information that most closely resembles the feature information 18 from the feature information corresponding to the search target texts such as the feature information 19a and 19b. When the feature information 18 is a vector of hash values, the approximate feature information is, for example, the vector having the largest number of matching hash values. The processing unit 12 may search for the most similar feature information by a predetermined neighborhood search algorithm. For example, the processing unit 12 stores in advance a search tree for binary search generated from a vector corresponding to the search target text in the storage unit 11, and traces the search tree to obtain a vector that most closely resembles the feature information 18. You may search.

For example, the feature information 18 is a vector (0,1,2,2,2, ...), The feature information 19a is a vector (0,0,2,2, ...), And the feature information 19b is a vector (4,4,4). 5, 5, ...). In this case, since the feature information 18 is closer to the feature information 19a than the feature information 19b, the text 14 is more similar to the text 15a than the text 15b.

The processing unit 12 may output a text 15a similar to the text 14. For example, the processing unit 12 may output the text 15a to the output device, such as displaying the text 15a on the display connected to the similar text search device 10, or transmit the text 15a to another information processing device. May be. Further, the processing unit 12 may output the response text associated with the text 15a to an output device such as displaying it on a display, or may transmit it to another information processing device. Further, the processing unit 12 may convert the response text associated with the text 15a into a voice signal and reproduce it as voice.

Here, the text 15a includes related words having a meaning similar to the words contained in the text 14, and it can be said that the text 14 and the text 15a are similar to some extent. However, when the degree of commonality between the word contained in the text 14 and the word contained in the text 15a is simply evaluated, it may be determined that the text 15a is not similar to the text 14 because there is no common word. In addition, when related words are simply regarded as the same word, the text 14 and the text 15a are equated with the text having the same expression even though the expressions used are different, and the degree of similarity is overestimated. May be done.

On the other hand, the similar text search device 10 adds, in addition to the original word contained in the text 14, a dummy word indicating a group of related words corresponding to the original word to the word set 16 from the word set 16. The feature information 18 is generated. Further, in addition to the original word included in the text 15a, a dummy word indicating a group of related words corresponding to the original word is added to the word set 17a, and the feature information 19a is generated from the word set 17a.

Therefore, even if the word contained in the text 14 and the word contained in the text 15a are not the same, the semantic closeness between the two is evaluated. Moreover, since the original word remains in the word sets 16 and 17a, the difference in the expressions used is also evaluated. That is, it can be expressed by the feature information 18, 19a that the text 14 and the text 15a are similar to some extent. As a result, the search accuracy of similar texts is improved. Further, similar text can be searched by comparing the feature information 18 generated from the word set 16 and the feature information 19a generated from the word set 17a, and the speed of the similar text search can be improved.

[Second Embodiment]
Next, a second embodiment will be described.
The information processing apparatus 100 of the second embodiment is used for a dialogue system that receives an inquiry utterance from a user and outputs an appropriate response utterance corresponding to the inquiry utterance. The information processing device 100 may be a client device or a server device.

FIG. 2 is a block diagram showing a hardware example of the information processing apparatus.
The information processing apparatus 100 includes a CPU 101, a RAM 102, an HDD 103, an image signal processing unit 104, an input signal processing unit 105, a medium reader 106, and a communication interface 107 connected to the bus. The information processing device 100 corresponds to the similar text search device 10 of the first embodiment. The CPU 101 corresponds to the processing unit 12 of the first embodiment. The RAM 102 or the HDD 103 corresponds to the storage unit 11 of the first embodiment.

The CPU 101 is a processor that executes a program instruction. The CPU 101 loads at least a part of the programs and data stored in the HDD 103 into the RAM 102, and executes the program. The CPU 101 may include a plurality of processor cores, and the information processing apparatus 100 may include a plurality of processors. A collection of multiple processors may be referred to as a "multiprocessor" or simply a "processor."

The RAM 102 is a volatile semiconductor memory that temporarily stores a program executed by the CPU 101 and data used by the CPU 101 for calculation. The information processing apparatus 100 may include a type of memory other than the RAM, or may include a plurality of memories.

The HDD 103 is a non-volatile storage device that stores software programs such as an OS (Operating System), middleware, and application software, and data. The information processing device 100 may be provided with other types of storage devices such as a flash memory and an SSD (Solid State Drive), or may be provided with a plurality of storage devices.

The image signal processing unit 104 outputs an image to the display 104a connected to the information processing apparatus 100 in accordance with a command from the CPU 101. As the display 104a, any kind of display such as a CRT (Cathode Ray Tube) display, a liquid crystal display (LCD: Liquid Crystal Display), and an organic EL (OEL: Organic Electro-Luminescence) display can be used.

The input signal processing unit 105 receives an input signal from the input device 105a connected to the information processing device 100. As the input device 105a, any kind of input device such as a mouse, a touch panel, a touch pad, and a keyboard can be used. Further, a plurality of types of input devices may be connected to the information processing apparatus 100.

The medium reader 106 is a reading device that reads programs and data recorded on the recording medium 106a. Examples of the recording medium 106a include magnetic disks such as flexible disks (FDs) and HDDs, optical disks such as CDs (Compact Discs) and DVDs (Digital Versatile Discs), and optical magnetic disks (MOs: Magneto-Optical disks). A semiconductor memory or the like can be used. The medium reader 106 stores, for example, a program or data read from the recording medium 106a in the RAM 102 or the HDD 103.

The communication interface 107 is an interface that is connected to the network 107a and communicates with other information processing devices via the network 107a. The communication interface 107 may be a wired communication interface connected to a wired communication device such as a switch or a router, or may be a wireless communication interface connected to a base station or an access point.

Next, a method of determining a response utterance from an inquiry utterance will be described.
FIG. 3 is a diagram showing an example of an utterance table.
The information processing apparatus 100 holds the utterance table 141 as a database in which a large number of inquiry and response samples are stored. The utterance table 141 includes an utterance ID, a search target utterance, and a response utterance item. The utterance ID is an identifier that identifies the utterance to be searched.

The search target utterance is a sample of inquiry utterances. The search target utterance is a character string indicating a sentence that the user may verbally utter, and is a text containing two or more words. The utterance to be searched is composed of one relatively short sentence or a small number of sentences. The reply utterance is associated with the search target utterance. When an inquiry utterance similar to a certain search target utterance is input, the response utterance associated with the search target utterance is output. The reply utterance is a character string indicating a sentence that may be transmitted to the user, and is a text containing two or more words. Response utterances consist of one relatively short sentence or a small number of sentences.

For example, the information processing apparatus 100 receives a voice signal indicating an inquiry utterance verbally uttered by the user, and converts the voice signal into a text inquiry utterance by voice recognition. The information processing apparatus 100 determines a search target utterance similar to a text inquiry utterance, and selects a response utterance corresponding to the determined search target utterance. The information processing apparatus 100 converts the text response utterance into a voice signal and reproduces the response utterance as voice.

Next, a search method for searching for a search target utterance similar to the inquiry utterance will be described. The information processing apparatus 100 evaluates the commonality of the appearing words between utterances by using the Min-hash function.
FIG. 4 is a diagram showing an example of a hash function and a vector.

As an example, the information processing apparatus 100 receives an inquiry utterance 31. Further, the search target utterances 32 and 33 are registered in the utterance table 141. Further, the information processing apparatus 100 holds hash functions 34 to 36, which are Min-hash functions.

The inquiry utterance 31 includes the words "Otani", "LA", "stolen base", "major", "ball" and "home run". The search target utterance 32 includes the words "Matsui", "NY", "strikeout", "major", "ball" and "home run". The search target utterance 33 includes the words "Otani", "strikeout", "tachi", "Sengoku period", "Sekigahara", and "seppuku". When the information processing apparatus 100 receives the inquiry utterance 31, the information processing apparatus 100 generates the vector 37 from the inquiry utterance 31 by using the hash functions 34 to 36. Further, the information processing apparatus 100 generates and holds the vector 38 in advance from the search target utterance 32 by using the hash functions 34 to 36. Further, the information processing apparatus 100 generates and holds a vector 39 in advance from the search target utterance 33 by using the hash functions 34 to 36.

Hash functions 34 to 36 are Min-hash functions that calculate one hash value from one word set included in one inquiry utterance or one search target utterance. Each of the hash functions 34 to 36 has a correspondence relationship in which different integers are associated with different words. Different hash functions have different correspondences. For example, the information processing apparatus 100 randomly arranges a plurality of words that may appear in the search target utterances 32 and 33, and assigns a continuous non-negative integer such as 0, 1, 2, ... To the word sequence. Generate one hash function. However, discontinuous integers may be assigned to a plurality of words.

For example, the hash function 34 assigns an integer 0 to "major", an integer 1 to "Sengoku period", and an integer 2 to "baseball". The hash function 35 assigns an integer 0 to "seppuku", an integer 1 to "history", and an integer 2 to "home runs". The hash function 36 assigns an integer 0 to "NY", an integer 1 to "LA", and an integer 2 to "Sekigahara". Each of the hash functions 34 to 36 selects the smallest integer from two or more integers corresponding to two or more words included in the word set, and outputs the selected minimum integer as a hash value.

The vector 37 is an integer vector enumerating three hash values calculated by inputting the word set of the inquiry utterance 31 into the hash functions 34 to 36. For the inquiry utterance 31, the hash function 34 outputs the integer 0 corresponding to the "major", the hash function 35 outputs the integer 2 corresponding to the "home base", and the hash function 36 outputs the integer corresponding to the "LA". Output 1 Therefore, the vector 37 becomes (0, 2, 1).

The vector 38 is an integer vector enumerating three hash values calculated by inputting the word set of the search target utterance 32 into the hash functions 34 to 36. For the search target speech 32, the hash function 34 outputs an integer 0 corresponding to "major", the hash function 35 outputs an integer 2 corresponding to "home base hit", and the hash function 36 corresponds to "NY". Outputs the integer 0. Therefore, the vector 38 becomes (0,2,0).

The vector 39 is an integer vector enumerating three hash values calculated by inputting the word set of the search target utterance 33 into the hash functions 34 to 36. For the search target speech 33, the hash function 34 outputs an integer 1 corresponding to "Sengoku era", the hash function 35 outputs an integer 0 corresponding to "cutting", and the hash function 36 corresponds to "Sekigahara". Outputs the integer 2 to be used. Therefore, the vector 38 becomes (1,0,2).

The information processing apparatus 100 can evaluate the similarity between the inquiry utterance 31 and the search target utterance 32 by comparing the vector 37 and the vector 38. The similarity is expressed by the number of dimensions in which the integers match among the dimensions of the vectors 37 and 38. Here, it is important whether or not the integers match, and if the integers are different, the closeness of the integers is not important. Between the vector 37 and the vector 38, the integers match in two of the three dimensions. Similarly, the information processing apparatus 100 can evaluate the similarity between the inquiry utterance 31 and the search target utterance 33 by comparing the vector 37 and the vector 39. Between the vector 37 and the vector 39, the integers do not match even in one of the three dimensions. Therefore, it can be determined that the inquiry utterance 31 is more similar to the search target utterance 32 than the search target utterance 33.

The probability that any hash function will output the same hash value for one query utterance and one search target utterance is the rate at which a common word appears between the query utterance word set and the search target utterance word set. Matches. The ratio of common words is sometimes called the Jackal coefficient. Therefore, it is possible to use the ratio of matching hash values among a plurality of hash values calculated by different hash functions as an approximate value of the Jackal coefficient. If the vectors corresponding to a large number of search target utterances are calculated in advance, it is possible to search for search target utterances similar to the received inquiry utterances at high speed.

For example, between the inquiry utterance 31 and the search target utterance 32, three words out of the nine words (nine kinds of words) from which duplicates have been removed are common, so the Jackal coefficient is 0.33. .. Further, since one of the 11 words from which the duplication has been removed is common between the inquiry utterance 31 and the search target utterance 33, the Jackal coefficient is 0.09. Therefore, the ratio of hash values that match between vectors is close to the Jackal coefficient.

The information processing apparatus 100 may search for one vector having the highest degree of matching with the vector corresponding to the inquiry utterance or a small number of vectors having a high degree of matching from among a large number of vectors corresponding to a large number of search target utterances. Therefore, the information processing apparatus 100 searches for one or a small number of vectors by neighborhood search using a binary search tree.

FIG. 5 is a diagram showing an example of a search tree.
The information processing apparatus 100 generates and holds the search tree 142 in advance based on the vector generated from the search target utterance registered in the utterance table 141. The search tree 142 includes a plurality of nodes connected to the tree structure. Two child nodes are connected to each node other than the leaf node. Each node except the leaf node has a threshold for a particular dimension in the vector. If the hash value of a specific dimension in the input vector is greater than or equal to the threshold value, the process proceeds to the right child node, and if the hash value of the specific dimension is less than the threshold value, the process proceeds to the left child node. In this way, the search tree 142 is traced from the root node to the leaf node.

For example, in the example of FIG. 5, the root node has 10 as a threshold value for the first dimension. Therefore, if a vector having a hash value of 10 or more in the first dimension is input, the process proceeds from the root node to the right child node, and if a vector having a hash value of less than 10 in the first dimension is input. Will go from the root node to the left child node.

The leaf node of the search tree 142 points to the utterance to be searched. For example, the leaf node contains a vector of search target utterances and an utterance ID that identifies the search target utterance. However, the leaf node does not have to contain the vector. When the vectors of two or more search target utterances are close to each other, one leaf node may be associated with two or more search target utterances. However, in order to efficiently narrow down the search target utterances, it is preferable that one leaf node points to one or a small number of search target utterances. The leaf nodes of the search tree 142 do not have to have the same depth from the root node, and hash values of all dimensions may not be used for the search.

Next, the problem when the inquiry utterance and the search target utterance do not contain the same word but contain related words will be described. Since the inquiry utterance and the search target utterance are short sentences using spoken words, the same or similar events can be expressed by various words, and the probability that the same word appears between the inquiry utterance and the search target utterance is high. Overall low. Therefore, in the method of simply evaluating the commonality of words, there is a problem that the similarity between the inquiry utterance using the related word and the search target utterance is not appropriately evaluated.

FIG. 6 is a diagram showing a calculation example of the Jackal coefficient.
(A) The inquiry utterance 41 includes "cat" and "rice" as words. The search target utterance 42 includes "nyanko" and "food" as words. "Cat" and "Nyanko" are related words with similar meanings, and "rice" and "food" are related words with similar meanings. However, if the Jackal coefficient is simply calculated based on the identity of the words, the inquiry utterance 41 and the search target utterance 42 do not include the same word, so that the Jackal coefficient is 0.00. Therefore, although the inquiry utterance 41 and the search target utterance 42 are likely to represent similar contents, the degree of similarity is determined to be very low.

(B) The inquiry utterance 43 includes "cat" and "rice" as words. The search target utterance 44 includes "nyanko" and "food" as words. Here, since "Nyanko" in the search target utterance 44 is a related word of "cat", it is assumed that "nyanko" is regarded as the same word as "cat". Further, since "food" in the search target utterance 44 is a related word to "rice", it is assumed that "food" is the same word as "rice". Then, the Jackal coefficient between the inquiry utterance 43 and the search target utterance 44 is calculated as 1.00. However, since the inquiry utterance 43 and the search target utterance 44 use different expressions, the similarity is overestimated, and it is difficult to distinguish them from other search target utterances that use the same expression as the inquiry utterance 43. Become.

Therefore, in the second embodiment, the degree of similarity is evaluated as follows.
(C) The inquiry utterance 45 includes "cat" and "rice" as words. The search target utterance 46 includes "nyanko" and "food" as words. "Cat" and "Nyanko" belong to the same related word group, and "rice" and "food" belong to the same related word group.

Then, the virtual word s ₁ corresponding to the related word group to which "cat" belongs is added to the word set of the inquiry utterance 45, and the virtual word s ₂ corresponding to the related word group to which "rice" belongs is added to the word set of the inquiry utterance 45. Add to. A virtual word is a virtual word that does not appear in inquiry utterances or search target utterances, and can also be called a dummy word or a label. Virtual words s ₁ and s ₂ are added while leaving "cat" and "rice". Further, the virtual word s ₁ corresponding to the related word group to which "Nyanko" belongs is added to the word set of the search target utterance 46, and the virtual word s ₂ corresponding to the related word group to which "Esa" belongs is added to the search target utterance 46. Add to the word set. Virtual words s ₁ and s ₂ are added while leaving "Nyanko" and "Esa".

Comparing the word set of the inquiry utterance 45 to which the virtual word is added and the word set of the search target utterance 46 to which the virtual word is added, since two kinds of words out of the six kinds of words are common, the Jackal coefficient. Is calculated as 0.33. The Jackal coefficient calculated in this way may be referred to as an extended Jackal coefficient in the second embodiment. The extended Jackal coefficient is larger than the Jackal coefficient when ignoring the relevance (similarity of meaning) between words. In addition, since the virtual word is added while leaving the original word in the word set, the extended Jackal coefficient is smaller than the Jackal coefficient when the related words are equated. Therefore, it is possible to appropriately evaluate the similarity between the inquiry utterance using different expressions and the search target utterance.

The information processing apparatus 100 treats a virtual word as an independent word and generates a plurality of hash functions. The information processing apparatus 100 generates a word set to which a virtual word is added from the search target utterance registered in the utterance table 141, inputs the word set to the hash function, and calculates a vector reflecting the influence of the virtual word. The information processing apparatus 100 generates a search tree 142 from a vector that reflects the influence of a virtual word. When the inquiry utterance is input, the information processing apparatus 100 generates a word set to which a virtual word is added from the inquiry utterance, inputs the word set to the hash function, and calculates a vector reflecting the influence of the virtual word. The information processing apparatus 100 uses the search tree 142 to search for a vector of search target utterances that approximates the vector of inquiry utterances. In this way, the information processing apparatus 100 can search for similar search target utterances at high speed by diverting a search method that does not consider related words by extending the hash function and the word set.

FIG. 7 is a graph showing an example of the relationship between the threshold value of similarity and the number of hits of the utterance to be searched.
The graph 50 shows the relationship between the threshold value of the similarity between the inquiry utterance and the search target utterance and the number of search target utterances (hits) whose similarity is larger than the threshold value. The similarity is the number of dimensions in which the hash values match between the vector of inquiry utterances and the vector of search target utterances.

(A) In the method of calculating the vector without considering the related words, the similarity between the inquiry utterance and each search target utterance is calculated to be low as a whole. Therefore, the relationship between the threshold of similarity and the number of hits is as shown in the curve 51. That is, even if the threshold value of the similarity is set low, the number of hits is small, and the search omission of similar search target utterances is large.

(B) In the method of equating related words and calculating the vector, the similarity between the inquiry utterance and each search target utterance is calculated to be high as a whole. Therefore, the relationship between the threshold of similarity and the number of hits is as shown in the curve 52. That is, even if the threshold value of the similarity is set high, the number of hits increases, and it is difficult to efficiently narrow down similar search target utterances.

(C) In the method of calculating the vector by adding a virtual word indicating a related word group while keeping the original word, the similarity between the inquiry utterance and each search target utterance takes an intermediate value between the above two methods. Therefore, the relationship between the threshold of similarity and the number of hits is as shown in curve 53. The addition of virtual words slightly increases the number of matching hash values. On the other hand, since the original word remains, it is possible to prevent the number of matching hash values from increasing too much. As a result, search target utterances similar to inquiry utterances can be efficiently narrowed down.

Related word groups are predefined.
FIG. 8 is a diagram showing an example of a related word table.
The information processing apparatus 100 holds a related word table 143. The related word table 143 can also be called a related word dictionary. The related word table 143 includes the group ID and related word items. The group ID is an identifier that identifies a related word group. One virtual word is assigned to one related word group. The related word item lists two or more words that belong to the same related word group. Words that belong to the same related word group are words that may be used as having similar meanings.

"Cat" and "Nyanko" belong to the same related word group. Therefore, for example, the information processing apparatus 100 assigns the same virtual word s ₁ to "cat" and "nyanko". Also, "rice" and "food" belong to the same related word group. Therefore, for example, the information processing apparatus 100 assigns the same virtual word s ₂ to "rice" and "food".

A word not registered in the related word table 143 does not belong to any related word group and has no other related words. As will be described later, in the second embodiment, a unique virtual word is added to a word for which a related word does not exist, and a hash value is calculated. This is to ensure that the same Jackal coefficient and extended Jackal coefficient are calculated from a word set in which no related word exists, and to maintain the consistency between the Jackal coefficient and the extended Jackal coefficient. However, it is also possible not to assign a virtual word to a word that does not have a related word. Even in that case, the extended Jackal coefficient takes a value equal to or higher than the Jackal coefficient when the related words are not considered, and a value equal to or lower than the Jackal coefficient when the related words are equated.

Here, the mathematical aspects of the Jackal coefficient and the hash function will be described.
The hash function used in the second embodiment is a Min-hash function, which is a mapping that converts a word set into an integer. The inquiry utterance and the search target utterance in which a vector to be approximated by a plurality of hash functions are generated are utterances in which the appearance rate of a common word is high. Assuming that the word set of one utterance (for example, one search target utterance) is A and the word set of the other utterance (for example, inquiry utterance) is B, the Jackal coefficient is defined as in the mathematical formula (1). The word sets A and B indicate the types of words that appear, and even if the same word appears more than once, they are not counted twice.

When the hash value of one hash function matches between two vectors, the word corresponding to the hash value appears in both utterances. If they do not match, the word corresponding to the smaller hash value appears in only one utterance. As described above, since the probability that the hash values of one hash function match is equal to the Jackal coefficient, the Jackal coefficient can be approximated by the matching ratio for a plurality of hash functions. An approximate value can be obtained by a predetermined number of hash value calculations that do not depend on the number of words included in the word sets A and B.

Let n be the number of utterances to be searched, m be the average number of words per utterance, and k be the number of hash functions. Then, the amount of calculation for calculating the vector of the utterance to be searched in advance is O (kmn). The amount of calculation for calculating the vector of one inquiry utterance is O (km), and the calculation cost of the neighborhood search using this vector is O (log (n)). K hash functions are randomly generated in advance. When k is O (log (n)), the collision probability in which the same hash value is calculated from different search target utterances can be sufficiently reduced.

On the other hand, the Jackal coefficient and hash function are extended. If there are no related words in the word sets A and B, the extended Jackal coefficient is equal to the Jackal coefficient. If a related word is present, the extended Jackal coefficient is greater than the Jackal coefficient when the related word is regarded as a different word and smaller than the Jacker coefficient when the related word is regarded as the same word. A virtual word is added to the word sets A and B so that the matching probability of the hash value is equal to the extended Jackal coefficient, and the hash function is expanded so that an integer is also assigned to the virtual word.

Let W be a set of words that can appear in the search target utterance, and let W'be a set of virtual words that are not included in the word set W. A unique virtual word s _i belonging to the virtual word set W'is assigned to any word a belonging to the word set W. The same virtual word is assigned to words that belong to the same related word group. Words that do not belong to any related word group are assigned virtual words that are not used for other words. The function f shown in the mathematical formula (2) is a mapping from W to W × W', and returns a set of the word and a virtual word from one word.

The extended Jackal coefficient J'is defined as in the equation (3) using the definition of the Jackal coefficient J and the function f. By the function f, the virtual word corresponding to each word included in the word set A is inserted into the word set A, and the virtual word corresponding to each word included in the word set B is inserted into the word set B. Then, the extended Jackal coefficient J'is obtained by calculating the Jackal coefficient J for the word set into which the virtual word is inserted. If the original word sets A and B do not contain related words, then J'(A, B) = J (A, B).

In extending the hash function, the function h'is defined for each hash function as in the equation (4). The function h converts the word a belonging to the word set W into an integer n, and is used in the hash function before expansion. Assuming that the set of integers is N, the function h is a mapping from W to N. The function h'converts a word a belonging to the word set W or a virtual word a belonging to the virtual word set W'to an integer n, and is used in the expanded hash function. If n is an arbitrary integer in the integer set N and N'= {n + maxN + 1}, then the function h'is a mapping from W∪W'to N∪N'. The integer set N'shows an extended portion when the integer set N, which is the range of the function h, is expanded twice. This is because the size of the virtual word set W'is smaller than or equal to the size of the word set W. The function e converts the virtual word a belonging to the virtual word set W'to a word belonging to the word set W, and is an injective function from W'to W. The function g swaps the correspondence between a word or virtual word and an integer, and is a bijection from N∪N'to N∪N'.

That is, when expanding the hash function, the information processing apparatus 100 assigns an integer larger than the integer assigned to the existing word to the virtual word. The integers assigned to the virtual words are determined using the functions e and h. A unique existing word is selected from a virtual word a by the function e, and the maximum values maxN and 1 in the range of the function h are added to the integer h (e (a)) associated with the word by the function h. Things are assigned to the virtual word a. Then, the information processing apparatus 100 shuffles the correspondence between the existing word and the integer and the correspondence between the virtual word and the integer by the function g to generate a new correspondence.

The function e may select one word belonging to the related word group indicated by the virtual word from the input virtual word, or may randomly select a word belonging to the word set W. There may be. Further, the function g for exchanging the integers to be assigned may be randomly generated. Further, the function e and the function g may be used in common among a plurality of hash functions, or may be randomly generated for each hash function.

From the above function h', the extended hash function H'is defined as in the equation (5). The hash function H'calculates an integer corresponding to each of the word and the virtual word included in f (A) by the function h', and selects the smallest integer from the integers. The size of the domain of the function h'is at most twice the size of the domain of the function h. By increasing the range of the function h'by one digit or increasing the number k of the hash function by one, the probability that the hash values collide under the hash function H'is maintained equal to that of the original hash function. be able to.

Next, an example of vector calculation considering virtual words will be described.
FIG. 9 is a diagram showing an example of calculating a vector from a word set.
Table 60 shows the process of calculating and comparing the vector corresponding to the word set A and the vector corresponding to the word set B. The word set A includes "cat" and "rice", and further inserts virtual words "s ₁ " and "s ₂ ". The word set B includes "nyanko" and "food", and further inserts virtual words "s ₁ " and "s ₂ ". Further, 12 hash functions having different correspondences between words and virtual words and integers are defined, and a list of 12 hash values corresponds to the vector corresponding to the word set A and the word set B. Become a vector.

The function h'1 used in the hash function H'1 is ₀ for "cat", ₁ for "rice", 2 for "nyanko", 3 for "food", 4 for "s ₁ ", and "s ₂ ". Is assigned to 5. Therefore, the hash value for the word set A is 0 corresponding to "cat", and the hash value for the word set B is 2 corresponding to "nyanko". The function _h'2 used in the hash function _H'2 is 1 for "cat", 0 for "rice", 5 for "nyanko", 4 for "food", 3 for "s ₁ ", and "s". ₂ is assigned to "2". Therefore, the hash value for the word set A becomes 0 corresponding to "rice", and the hash value for the word set B becomes 2 corresponding to "s ₂ ".

The function _h'5 used in the hash function _H'5 is 2 for "cat", 3 for "rice", 4 for "nyanko", 5 for "food", 0 for "s ₁ ", and "s". 1 is assigned to " ₂ ". Therefore, the hash value for the word set A becomes 0 corresponding to "s ₁ ", and the hash value for the word set B becomes 0 corresponding to "s ₁ ". In this way, a vector (0,0,2,2,0,0,0,1,1,0,0,0) is calculated from the word set A. A vector (2,2,0,0,0,0,1,0,0,0,0,1) is calculated from the word set B.

Although there is no common word between the original word sets A and B, the hash values of the hash functions _H'5 , _H'6 , H'10, and _H'11 out of the ₁₂ hash functions match. The hash value match ratio is 0.33. If the virtual word is not used, the hash value match ratio is 0.00. Therefore, the similarity of utterances can be appropriately evaluated.

FIG. 10 is a diagram showing a selection example of a response utterance corresponding to an inquiry utterance.
As described above, the information processing apparatus 100 selects the search target utterance most similar to the inquiry utterance from the accumulated search target utterances, and outputs the response utterance corresponding to the selected search target utterance. As an example, search target utterances 71 to 73 are accumulated.

The search target utterance 71 is a message "check the mail", the search target utterance 72 is a message "schedule adjustment", and the search target utterance 73 is a message "want to adjust the meeting". The information processing apparatus 100 generates a vector 74 from the search target utterance 71, a vector 75 from the search target utterance 72, and a vector 76 from the search target utterance 73 in advance. The vector 74 is a sequence of integers (0,0,1,1,2,2, ...), And the vector 75 is a sequence of integers (2,2,0,0,1,1, ...). The vector 75 is a sequence of integers (1,2,2,2,1,1, ...).

The information processing apparatus 100 receives the inquiry utterance 77. The inquiry utterance 77 is a message "I want to coordinate the meeting". The information processing apparatus 100 generates a vector 78 from the inquiry utterance 77. The vector 78 is a sequence of integers (1,1,2,2,1,1, ...). Of the vectors 74 to 76, the one closest to the vector 78 is the vector 76. Therefore, the information processing apparatus 100 selects the search target utterance 73 and outputs the response utterance 79 corresponding to the search target utterance 73. The response utterance 79 is a response to the inquiry utterance 77, and is a message "adjust the schedule". If it is registered in advance that "meeting" and "meeting" are related words having similar meanings, the information processing apparatus 100 can determine that the search target utterance 73 is similar to the inquiry utterance 77.

When a single search target utterance is searched by a neighborhood search using a vector, such as when a single search target utterance is associated with the leaf node of the search tree 142, the information processing apparatus 100 performs the search. The response utterance corresponding to the target utterance may be output. On the other hand, when two or more search target utterances are searched by a neighborhood search using a vector, such as when two or more search target utterances are associated with the leaf node of the search tree 142, the information processing apparatus 100 uses some method. It is conceivable to narrow down the search target utterances to one. For example, the information processing apparatus 100 narrows down the search target utterances by a detailed analysis different from a simple similarity determination using a vector.

Next, the functions and processing procedures of the information processing apparatus 100 will be described.
FIG. 11 is a block diagram showing a functional example of the information processing apparatus.
The information processing apparatus 100 has an utterance database 121, a related word storage unit 122, a hash function storage unit 123, and an index storage unit 124. These storage units are realized by using, for example, the storage area of the RAM 102 or the HDD 103. Further, the information processing apparatus 100 includes a hash function generation unit 131, an index generation unit 132, an inquiry reception unit 133, a hash value calculation unit 134, a search unit 135, and a response output unit 136. These processing units are realized, for example, by using a program executed by the CPU 101.

The utterance database 121 stores an utterance table 141 in which a plurality of search target utterances and a plurality of response utterances corresponding to the plurality of search target utterances are registered. The set of the search target utterance and the response utterance may be registered in advance, may be added through a dialogue with a user who uses the information processing apparatus 100, or may be automatically collected from the network.

The related word storage unit 122 stores the related word table 143 showing the related word group. The related word group may be registered in advance, may be added through a dialogue with a user who uses the information processing apparatus 100, or may be automatically collected from the network.

The hash function storage unit 123 stores a plurality of different hash functions. Each hash function has a correspondence relationship in which a unique integer is associated with each of a word that can appear in the search target utterance and a virtual word that does not appear in the search target utterance, accepts a word set, and outputs one hash value. Different hash functions have different correspondences.

The index storage unit 124 stores the search tree 142 as an index for searching for a search target utterance similar to the inquiry utterance. The search tree 142 is generated based on a vector calculated from the search target utterance using a plurality of hash functions.

The hash function generation unit 131 generates a plurality of hash functions based on the search target utterance stored in the utterance database 121 and the related word table 143 stored in the related word storage unit 122, and generates a plurality of generated hash functions. It is stored in the hash function storage unit 123.

First, the hash function generation unit 131 extracts words used in the search target utterance, randomly arranges the extracted words, and generates a hash function before expansion. Further, the hash function generation unit 131 assigns a virtual word to a related word group registered in the related word table 143 and a word having no related word. The hash function generation unit 131 extends the hash function so that an integer can be assigned to a virtual word as well.

The index generation unit 132 generates a search tree 142 based on the search target utterance stored in the utterance database 121 and the hash function stored in the hash function storage unit 123, and the generated search tree 142 is stored in the index storage unit 124. Store.

First, the index generation unit 132 extracts a word set for each search target utterance, and adds a virtual word corresponding to each word to the word set. The index generation unit 132 inputs a word set to which a virtual word is added into each of a plurality of hash functions, and calculates a vector of hash values. The index generation unit 132 generates a search tree 142 so that a plurality of vectors corresponding to a plurality of search target utterances can be efficiently searched. For example, the index generation unit 132 pays attention to one dimension in the vector, and repeatedly determines the threshold value of the hash value of the dimension so that the set of vectors is divided into two. The index generation unit 132 generates an intermediate node so that a single vector is associated with the leaf node of the search tree 142 as much as possible.

The inquiry receiving unit 133 receives the inquiry utterance. The inquiry receiving unit 133 may receive the inquiry utterance input as a character string from the user, or may convert the voice signal of the inquiry utterance uttered by the user into a character string. Further, the inquiry receiving unit 133 may receive a character string or an audio signal from another information processing device.

The hash value calculation unit 134 generates a vector corresponding to the inquiry utterance based on the plurality of hash functions stored in the hash function storage unit 123. First, the hash value calculation unit 134 extracts a word set from the inquiry utterance and adds a virtual word corresponding to each word to the word set. The hash value calculation unit 134 inputs a word set to which a virtual word is added into each of a plurality of hash functions, and calculates a vector of hash values.

The search unit 135 searches for the search target utterance most similar to the inquiry utterance by neighborhood search based on the search tree 142 stored in the index storage unit 124 and the vector of the inquiry utterance. The search target utterance most similar to the inquiry utterance is the search target utterance having the largest number of dimensions with which the hash values match when the vectors are compared. The search unit 135 traces the search tree 142 from the root node toward the leaf node and reaches the specific leaf node while comparing the hash value of a specific dimension in the inquiry utterance vector with the threshold value. The search unit 135 selects the search target utterance corresponding to the reached leaf node. If two or more search target utterances are associated with the reached leaf node, that is, if the search target utterance cannot be narrowed down to one in the search tree 142, one search target utterance is selected by another method. do.

The response output unit 136 outputs the response utterance associated with the selected search target utterance. The response output unit 136 may display the character string of the response utterance on the display 104a, or may convert the response utterance into a voice signal and reproduce the voice by the speaker. Further, the response output unit 136 may transmit a character string or an audio signal to another information processing device.

FIG. 12 is a flowchart showing an example of an index generation procedure.
(S10) The hash function generation unit 131 collects words included in a plurality of search target utterances registered in the utterance table 141 and extracts a word set W.

(S11) The hash function generation unit 131 randomly arranges the words included in the word set W, and assigns integers in ascending order from the beginning to the end of the word sequence. The hash function generation unit 131 repeats this k times to generate k hash functions H.

(S12) The hash function generation unit 131 selects one word w included in the word set W and initializes the flag fw corresponding to the selected word w to 0.
(S13) The hash function generation unit 131 searches the related word table 143 for the word w selected in step S12, and whether the word w belongs to any related word group, that is, a relation having a meaning similar to the word w. Determine if a word exists. If there is a related word, the process proceeds to step S14, and if there is no related word, the process proceeds to step S15.

(S14) The hash function generation unit 131 updates the flag fw to 1.
(S15) The hash function generation unit 131 determines whether or not there is a word w that has not yet been selected in step S12 in the word set W. If there is an unselected word w, the process proceeds to step S12, and if there is no unselected word w, the process proceeds to step S16.

(S16) The hash function generation unit 131 assigns a unique virtual word s to each of the related word groups registered in the related word table 143. Further, the hash function generation unit 131 assigns a unique virtual word s to each word whose fw = 0. The virtual word s assigned here is a dummy word or label not included in the word set W, and does not overlap between the related word group and the word with fw = 0. The virtual word s may be a symbol such as "s ₁ ".

(S17) The hash function generation unit 131 selects one hash function H from the k hash functions H generated in step S11.
(S18) The hash function generation unit 131 selects one word w from the word set W.

(S19) The hash function generation unit 131 specifies an integer h (w) associated with the word w selected in step S18 in the hash function H selected in step S17. Then, the hash function generation unit 131 calculates a new integer h'(w) = g (h (w)) associated with the word w by using a predetermined function g for shuffling.

(S20) The hash function generation unit 131 determines whether or not there is a word w that has not yet been selected in step S18 in the word set W. If there is an unselected word w, the process proceeds to step S18, and if there is no unselected word w, the process proceeds to step S21.

FIG. 13 is a flowchart (continued) showing an example of the index generation procedure.
(S21) The hash function generation unit 131 selects one virtual word s from the set of virtual words (virtual word set W') assigned in step S16.

(S22) The hash function generation unit 131 identifies the word e (s) corresponding to the virtual word s selected in step S21 by using a predetermined function e that converts the virtual word into the existing word. The word e (s) may be one word in the related word group corresponding to the virtual word s or a single word corresponding to the virtual word s, or may be randomly selected from the word set W. .. The hash function generation unit 131 specifies an integer h (e (s)) associated with the word e (s) in the hash function H selected in step S17. The hash function generation unit 131 calculates a new integer h'(s) = g (h (e (s)) + maxN + 1) associated with the virtual word s by using a predetermined function g for shuffling. Note that maxN is the maximum value of the hash value (range) that can be output by the hash function H.

(S23) The hash function generation unit 131 determines whether or not there is a virtual word s that has not yet been selected in step S21 in the virtual word set W'. If there is an unselected virtual word s, the process proceeds to step S21, and if there is no unselected virtual word s, the process proceeds to step S24.

(S24) The hash function generation unit 131 determines the extended hash function H'corresponding to the hash function H selected in step S17 from the results of steps S19 and S22.
(S25) The hash function generation unit 131 determines whether or not there is a hash function H that has not yet been selected in step S17. If there is an unselected hash function H, the process proceeds to step S17, and if there is no unselected hash function H, the process proceeds to step S26.

(S26) The index generation unit 132 selects one search target utterance from the plurality of search target utterances registered in the utterance table 141.
(S27) The index generation unit 132 extracts words included in the search target utterance selected in step S26, and generates a word set A which is a set of the extracted words.

(S28) The index generation unit 132 determines a virtual word corresponding to each word included in the word set A, and adds the determined virtual word to the word set A. The virtual word assigned in step S16 is added to the word belonging to any of the related word groups. A virtual word assigned in step S16 is added to a word that does not belong to any of the related word groups (a word that does not have a related word).

(S29) The index generation unit 132 inputs the word set A to which the virtual word is added into the plurality of hash functions H'determined in step S24, and obtains a plurality of hash values. Each hash function H'determines an integer corresponding to each of the original word and the virtual word included in the word set A, and outputs the smallest integer as a hash value. The index generation unit 132 calculates a vector in which a plurality of hash values are listed.

(S30) The index generation unit 132 determines whether there is a search target utterance that has not yet been selected in step S26. If there is an unselected search target utterance, the process proceeds to step S26, and if there is no unselected search target utterance, the process proceeds to step S31.

(S31) The index generation unit 132 generates a search tree 142 as an index of the search target utterance from the plurality of vectors calculated in step S29.
FIG. 14 is a flowchart showing an example of the procedure for utterance search.

(S40) The inquiry receiving unit 133 receives the inquiry utterance.
(S41) The hash value calculation unit 134 extracts words included in the inquiry utterance received in step S40, and generates a word set B which is a set of the extracted words.

(S42) The hash value calculation unit 134 determines a virtual word corresponding to each word included in the word set B, and adds the determined virtual word to the word set B. The virtual word assigned in step S16 is added to the word belonging to any of the related word groups. A virtual word assigned in step S16 is added to a word that does not belong to any of the related word groups (a word that does not have a related word).

(S43) The hash value calculation unit 134 inputs the word set B to which the virtual word is added into the plurality of hash functions H'determined in step S24, and obtains a plurality of hash values. Each hash function H'determines an integer corresponding to each of the original word and the virtual word included in the word set B, and outputs the smallest integer as a hash value. The hash value calculation unit 134 calculates a vector in which a plurality of hash values are listed.

(S44) The search unit 135 collates the search tree 142 generated in step S31 with the vector calculated in step S43, and determines the most similar search target utterance.
(S45) The response output unit 136 acquires the response utterance associated with the search target utterance in step S44 from the utterance table 141, and outputs the acquired response utterance.

According to the information processing apparatus 100 of the second embodiment, in order to realize the dialogue system, the search target utterance similar to the inquiry utterance is searched from the database. At this time, a vector of hash values is calculated from a set of words included in each utterance by a plurality of Min-hash functions, and the similarity of the utterances is evaluated by the closeness of the vectors. Therefore, it is possible to search a large number of search target utterances similar to the inquiry utterance at high speed.

Further, referring to the related word dictionary indicating the related word group, a virtual word indicating the related word group to which the word belongs is added to the word set while keeping the original word included in the word set. Also, multiple Min-hash functions are extended so that different integers are assigned to the original word and the virtual word. Then, the vector is calculated by the word set to which the virtual word is added and a plurality of extended Min-hash functions. Thereby, when the inquiry utterance and the search target utterance do not include the same word but include related words having similar meanings, the similarity between the two can be appropriately evaluated.

For example, the similarity is evaluated higher than the case of ignoring the closeness of meaning between words, and the similarity is evaluated lower than the case of equating related words. As a result, the similarity between the inquiry utterance and the search target utterance using different expressions can be appropriately evaluated, and the search target utterance similar to the inquiry utterance can be efficiently narrowed down. In addition, since the hash value vector of the Min-hash function is used, the search speed can be maintained.

10 Similar text search device 11 Storage unit 12 Processing unit 13 Related word dictionary 14, 15a, 15b Text 16, 17a, 17b Word set 18, 19a, 19b Feature information

Claims (6)

The computer
Accept the input of the first text,
Extracting two or more first words included in the first text, referring to a related word dictionary showing a group of related words, and belonging to any group of the two or more first words. Assign the first dummy word indicating the group to the first word,
The first feature information corresponding to the first word set including the two or more first words and the first dummy word is generated.
Includes two or more second words contained in the second text and a second dummy word indicating a group to which any second word belongs, which is stored corresponding to each of the plurality of second texts. Searching for a second text similar to the first text, based on a comparison between the second feature information according to the second word set and the first feature information.
Similar text search method. The first feature information is a first vector containing a plurality of hash values calculated from the first word set by a plurality of different hash functions.
The second feature information is a second vector containing a plurality of hash values calculated from the second word set by the plurality of hash functions.
The similar text search method according to claim 1. Each of the plurality of hash functions has a correspondence relationship in which a unique value is associated with each word and a dummy word, and is the smallest value among the values corresponding to the word and the dummy word included in the input word set. Is output as a hash value,
The similar text search method according to claim 2. The computer further
The third text stored in association with the searched second text is output as a response to the first text.
The similar text search method according to claim 1. A related word dictionary showing a group of related words is stored, and two or more second words contained in the second text and any second word corresponding to each of the plurality of second texts are stored. A storage unit that stores a second feature information corresponding to a second word set including a second dummy word indicating a group to which the word belongs, and a storage unit that stores the second feature information.
The input of the first text is accepted, two or more first words included in the first text are extracted, and any group of the two or more first words is referred to with reference to the related word dictionary. A first dummy word indicating the group is assigned to the first word belonging to the above, and the first feature corresponding to the first word set including the two or more first words and the first dummy word. A processing unit that generates information and searches for a second text similar to the first text based on a comparison between the second feature information and the first feature information.
Similar text search device with. On the computer
Accept the input of the first text,
Extracting two or more first words included in the first text, referring to a related word dictionary showing a group of related words, and belonging to any group of the two or more first words. Assign the first dummy word indicating the group to the first word,
The first feature information corresponding to the first word set including the two or more first words and the first dummy word is generated.
Includes two or more second words contained in the second text and a second dummy word indicating a group to which any second word belongs, which is stored corresponding to each of the plurality of second texts. Searching for a second text similar to the first text, based on a comparison between the second feature information according to the second word set and the first feature information.
A similar text search program that executes processing.

Images