JP5669707B2 - Similar document search device - Google Patents

Description

  The present invention relates to a search device used in a content search system based on content-related terms and a text search system for searching a large amount of document data (text document), and a specific character string (hereinafter referred to as a query) called a query. Even if the search string does not match the original text of the document to be searched, a similar document that allows the target document to be searched from multiple search target documents by quickly determining the similarity The present invention relates to a search device.

For example, in the FASTA program of Non-Patent Document 1, a sequence similar to a specified DNA sequence is obtained by executing two types of search procedures (two-pass search) in units of N-Gram elements (consecutive N characters). High-speed database search is realized.
That is, first, the character string to be searched (the amino acid sequence of the protein in plain text format stored in the DNA database) is decomposed into N-Gram elements, and the above N-Gram elements and their occurrences are used for collation. Register in the table.
When searching, the search string (amino acid sequence of the specified protein) in the first pass is similarly decomposed into N-Gram elements and the matching table is searched, and the percentage of N-Gram elements in the search string is included The search target part (several places in the amino acid sequence of the protein in the DNA database) having a high (degree of matching) is output as a search target candidate.
Then, a dynamic programming calculation based on the Smith-Waterman method is performed in a region limited to these candidates in the second pass.

  Further, in the “voice search system” of Patent Document 1, voice data such as news and lectures to be searched is converted into a character string in advance by voice recognition, and the search is performed using the input search character string. There has been disclosed a technique that enables search even when a voice portion corresponding to a character string is misrecognized and does not match the character string of the voice recognition result and the search character string, and enables high-speed search. As a search method, in the words of the recognition dictionary used for the speech recognition, a word string candidate (sequence of words in the recognition dictionary) that is acoustically similar to the search character string is efficiently obtained, and the word string candidate What appears in the recognition result is output as a search result. When obtaining the word string candidates, the input search character string is converted into a phoneme string, and a frame-synchronized beam search used in continuous word speech recognition (the input feature vector is replaced with the phoneme string of the search character string) ) And level building or the like, and by comparing the phoneme string of the search character string with the phoneme string of various combinations of words in the recognition dictionary, word combinations having high similarity are selected as candidates.

In addition, in the document data search apparatus for searching for music by inputting a part of lyrics, the present inventors can determine the similarity at high speed even when searching with lyrics that the user has mistakenly remembered. Japanese Patent Application Laid-Open No. 2010-123005 (Patent Document 2) proposed a search device capable of searching for target lyrics.
In this search device, first, a word that is likely to appear in an input search character string is predicted, and a distance value that represents a similarity to a document (lyric) that is a search target is calculated in advance and registered in INDEX. In the distance value calculation method, in each search target document, constituent words are extracted from predicted search character strings, converted into phoneme strings, respectively, and then phoneme-based DPs sequentially with the phoneme strings of the words. Matching is performed, and the lowest DP matching cost value is set as the distance value between the predicted word and the document.
At the time of search, words are extracted from the search character string, the above INDEX is searched for each search target document, and the distance values for the words constituting the search character string (ignoring the appearance order) are summed to obtain the similarity. A search result is output based on the similarity between the search character string and the search target document.

JP 200631278 A JP 2010-123055 A

Proceedings of National Academy of Sciences USA 85, 2444-2448 (1988) (Proc. Natl. Acad. Sci. U.S.A., vol. 85, pp. 2444-2448 (1988))

  When performing document search such as lyrics search or movie script search, the search character string often includes partial errors due to mistakes in listening or memory differences. For example, while the original text of the lyrics is “Musunohikari”, the search character string may be incorrectly entered as “Massgunakari” which is different in sound but acoustically similar. This is the case.

In such a search, non-patent document 1 realizes a high-speed search by two-pass processing, but in the first pass, in the document or character string to be searched, the N-Gram element of the search character string Since a portion with a high percentage (matching degree) is included as a search target candidate, there is a problem that the similarity between the N-Gram element not included and the search target is not considered.
That is, for the search example described above, in the “Musunohikari” to be searched, only the “Hikari” is included in the N-Gram element of the search string “Mass Gunaharikari”, and the N-Gram element matches Since the degree is low, the correct answer “Musunohikari” is excluded from the search candidates in the first pass, and the search accuracy decreases.

  Although the acoustic similarity is taken into consideration in the system of Patent Document 1, it is necessary to perform similarity calculation for obtaining similar word string candidates of search character strings for all words in the speech recognition dictionary each time a search is performed. There is. At present, when there are many search targets on the Web (in the case of commercial lyrics search systems, which target tens of thousands or hundreds of thousands of lyrics), there is a search space (number of types of word combinations) for calculating similarity. There is a problem that online search becomes very slow due to the enormous volume.

In the search device of Patent Document 2, since a word that can appear in a search character string is predicted and registered in INDEX, the word of the actually input search character string is not registered (OUT-OF-VOCABULRY problem) The search character string is converted online into a phoneme string, DP matching with the phoneme string of each search target document is performed, and the search is performed based on the DP matching cost value obtained as a result. There was the problem of being slow. Further, if all existing words are registered in the INDEX, the size of the INDEX becomes enormous, and there is a problem that the cost for implementation in an actual system becomes high.
Further, in the search device of Patent Document 2, the second pass does not use sort information by the approximate distance calculation of the first pass, and performs the calculation by DP matching for all search target candidates, so that the search efficiency is reduced. There was a problem.

  The present invention has been proposed in view of the above circumstances, and when performing a document search, a plurality of search objects are obtained even if the search character string includes partial errors due to mishearing or memory errors. An object of the present invention is to provide a similar document search apparatus capable of realizing a search for a target document from a document at high speed and with high accuracy.

  In order to achieve the above object, the present invention considers the similarity between a search character string and a search target document in units of a subword chain (a fixed number of continuous phonemes or syllables) as a component of a document in a similar document search apparatus. To do. Then, when considering the similarity between the search character string and the search target document, the search target document candidates are narrowed down by performing the first-stage search (first pass) using the pre-built search index. A 2 (type) path search algorithm for performing the second stage search (second path) is introduced.

First, in the construction of the search index, in order to deal with an unknown search character string, a combination of N syllables (or phonemes) or a syllable string composed of a desired number of syllables (or phonemes) from a large number of documents ( Syllable N-Gram) or phoneme string (phoneme N-Gram) is collected as a subword chain.
The syllable string (syllable N-Gram) or phoneme string (phoneme N-Gram) varies greatly depending on its length (syllable or number of phonemes), so between syllable N-Gram or phoneme N-Gram Clustering is performed based on the distance. A search index table is created in advance based on the similarity between the subword chain cluster (syllable string cluster or phoneme string cluster) obtained by clustering and the search target document (lyric data, script, etc.).

When searching for a search character string, the search character string is converted into a plurality of subword chains in the first pass, and the search target candidates having high similarity to the subword chain are narrowed down by high-speed search using the search index. A high-precision search is performed by end-point free DP matching based on phonemes in a phoneme string of search target candidates narrowed down in the second pass and a search character string.
In the second pass, instead of calculating by DP matching for all search target candidates, a plurality of search target candidate groups are created in order from the top searched in the first pass, and the search target candidates belonging to each group The DP matching is calculated for the above-mentioned, and the DP matching calculation for the subsequent grapes is discontinued based on the calculation result.

That is, the similar document search apparatus according to claim 1 includes an input interface for inputting a character string or a character string converted by speech recognition as a search character string, and a portion similar to the search character string from a plurality of search target documents. A search apparatus for searching for a search target document includes the following configuration.
INDEX creation means for search . The index creation means for search is a syllable string or phoneme string (hereinafter referred to as “subword”) formed by combining a predetermined number of subwords from a plurality of syllables or phonemes (hereinafter referred to as “subwords”) in a plurality of documents . A group including a plurality of subword chains clustered based on the distance between the subword chains and registering as a syllable string cluster or a phoneme string cluster (hereinafter referred to as “subword chain cluster”). The similarity is calculated by comparing the phoneme strings of the plurality of subword chain clusters and the search target document, and a similarity table corresponding to each subword chain cluster is created in advance as a search index.

The subword chain is created by combining a plurality of subwords , but may be composed of one subword .

Subword chain extraction means. The sub-word chain extracting means extracts a plurality of syllable strings or phoneme strings connecting the desired numbers from the syllables or phonemes constituting the search character string input to the input interface as sub-word chains.
Similarity calculation means. For each subword chain extracted by the subword chain extraction means, the similarity calculation means obtains each similarity corresponding to the subword chain cluster to which each subword chain belongs from the search INDEX, and calculates the total of each similarity Calculated as the similarity to the search target document.
Output interface. The output interface outputs a search result of document data based on the similarity.

The similarity calculation means performs a first pass INDEX search for narrowing down a plurality of search target document candidates in descending order of the similarity corresponding to the subword chain cluster to which each of the subword chains found from the search INDEX belongs. The output ranking is determined based on the similarity obtained by converting the plurality of search target document candidates into a phoneme string and performing a string similarity calculation with the phoneme string of the retrieved character string as a unit. A search based on the second pass character string similarity calculation is executed .
The search by the second pass character string similarity calculation is performed by dividing the search target document candidates searched by the first pass INDEX search into a plurality of sessions each having a group of M from the top as a group. The character string similarity calculation is sequentially performed on the search target document candidates belonging to each session in order to calculate the similarity, and the session similarity D calculated based on the minimum value and the average value of the similarity in the session is a predetermined threshold value. If it is smaller than α, similarity calculation by character string similarity calculation in subsequent sessions is terminated, and the output order of search target document candidates is determined based on the similarity calculated at that time.

In the similar document search device according to claim 1, the session similarity D and the threshold value α are set to a minimum value D (min) and an average value D (mean) of the similarity in the session.
Session similarity D = D (min) / D (mean),
Threshold value α = 0.0 to 1.0
It is characterized by that.

Claim 3 is the similar document search apparatus according to claim 2, wherein the standard deviation value in the session is D (s).
Session similarity D = D (s) / (D (mean) −D (min)),
It is characterized by that.

  According to a fourth aspect of the present invention, there is provided the similar document retrieval apparatus according to the first aspect, wherein the similarity in the INDEX creation means is obtained by converting a syllable string or a phoneme string representing each subword chain cluster and a search target document into a phoneme string. In the phoneme string, calculation is performed based on a cumulative character string similarity value obtained by performing character string similarity calculation in units of phonemes.

5. The similar document search apparatus according to claim 4, wherein the character string similarity calculation between the phoneme strings is performed by performing a speech recognition experiment using a phoneme replacement cost value, a phoneme insertion cost value, or a phoneme dropout cost value. The calculation is based on the phoneme confusion matrix.

  According to a sixth aspect of the present invention, in the similar document search apparatus of the fifth aspect, the replacement cost value, the insertion cost value, and the dropout cost value are values determined by an experience value or a pronunciation dictionary.

  According to a seventh aspect of the present invention, in the similar document search apparatus according to the first aspect, the subword chain cluster is a group to which a plurality of subword chains belong, and is only one subword chain.

  According to an eighth aspect of the present invention, in the similar document search apparatus according to the first aspect, the input interface inputs a part of the lyrics as text data.

  9. The similar document search device according to claim 1, wherein the input interface inputs a part of the lyrics by voice, converts the input voice into text data by a voice recognition method, and searches. Yes.

According to a tenth aspect of the present invention, in the similar document retrieval apparatus of the first aspect, the output interface presents a song name, an artist name, or a full text of a lyrics as a retrieval result.

  In the similar document search device according to claim 11, the output interface displays the full text of the lyrics linked to each other, and highlights the lyric portion matched with the query when displayed.

According to a twelfth aspect of the present invention, in the similar document search apparatus according to the first aspect, the subword chain is created by a combination of a plurality of subwords .

According to a thirteenth aspect of the present invention, in the similar document search device according to the first aspect, the subword chain is composed of one subword .

14. The similar document search apparatus according to claim 1, wherein the character string similarity calculation is performed by using a phoneme as a unit in two phoneme sequences, and an endpoint-free DP considering a cost of insertion, deletion, or replacement of phonemes. It is characterized by using a matching method.

  According to a fifteenth aspect of the present invention, in the similar document search apparatus according to the first aspect, the character string similarity calculation is performed by a similarity calculation method based on the number of different phonemes in two phoneme strings.

  According to the present invention, since the similarity between each subword chain cluster and the search target document is calculated in advance at the time of creating the search INDEX, the first pass INDEX search at the time of searching for similar search character strings is performed. It is not necessary to calculate the similarity for the narrowing-down process. Therefore, since the calculation of the character string similarity with a large amount of calculation performed between the phonemes of the search character string and the search target document is limited to a small amount of search target candidates in the second pass, the total calculation amount is reduced. By doing so, high-speed search can be realized.

  Further, in the character string similarity calculation of the second pass, when the session similarity D calculated based on the minimum value and the average value of the similarity in the session is smaller than a predetermined threshold value α, the similarity is small and the search character Since it is determined that there are search target document candidates that are similar to the column and the similarity calculation by the character string similarity calculation in the subsequent session is terminated, the number of search document candidates that perform the character string similarity calculation can be reduced. Therefore, the speed of the detection process can be improved without reducing the search rate.

  Also, when creating a search INDEX, the first pass INDEX search is correct because the similarity between the search target document and the syllable string cluster including the subword chain that may be a constituent part of the search character string is considered. The probability that the search target document is excluded from the candidates can be reduced. As a result, it is possible to realize the same search accuracy as the search by the character string similarity calculation for all search targets.

In addition, by using a subword chain (syllable string or phoneme string) instead of a word when creating a search INDEX and searching a search string, the corresponding word between the search string and the search target document can be obtained. The problem of non-existence (OUT-OF-VOCABULRY) will no longer occur.
Furthermore, the number of entries in the search INDEX is reduced by clustering (because the number of syllable strings or phoneme strings clusters is reduced from the number of syllable strings or phoneme strings), so the syllable string or phoneme string for creating the search INDEX is reduced. Even if there are many types, the index size for search can be reduced.

It is a functional block diagram which shows an example of embodiment of the similar document search apparatus of this invention. It is a flowchart which shows the INDEX file creation processing procedure for search in the similar document search apparatus of this invention. It is a table figure which showed the similarity degree of the syllable string cluster obtained by the search index creation means and the syllable string of the lyrics data. It is a calculation result table for demonstrating the procedure of calculation of DP distance by the end point free DP matching of search phoneme sequence S1 "toganai" and search object phoneme sequence S2 "... kobotanaia ...". It is a flowchart which shows an example of the search process in the similar document search apparatus of this invention. FIG. 6 is an explanatory diagram illustrating details of processing in a first pass INDEX search of the flowchart of FIG. 5. It is the search result table which ranked lyric data in order with the low value of approximate acoustic distance R with respect to each lyric data by the 1st pass INDEX search. 6 is a flowchart showing details of processing in the second path DP matching search of the flowchart of FIG. 5.

Hereinafter, an embodiment of a similar document search apparatus of the present invention will be described with reference to the block diagram of FIG.
As an example of the similar document search apparatus, a lyrics search apparatus that inputs a part of phrases of lyrics as a search character string and outputs lyrics data and music information will be described as an example. In the lyric search device, the similarity between the search character string and the registered lyric data is taken into consideration in units of subword chains (constant continuous phonemes or syllables) that are constituent elements of the lyrics. A subword chain (syllable string or phoneme string) is formed by combining a predetermined number of subwords connected in advance from subwords (syllables or phonemes).
A similar document search device 1 serving as a lyrics search device includes an input interface 2 for inputting a part of phrases of lyrics of a song as a search character string, an output interface 3 for outputting a search result of lyrics data (document data), A lyrics database 4 in which a plurality of lyrics data to be searched (documents to be searched) are stored, and a control unit that performs a search process of lyrics data stored in the lyrics database 4 from a search character string input to the input interface 2 10. The search character string input to the input interface 2 may be a character string converted by voice recognition.

  More specifically, the similar document retrieval apparatus of the present invention includes a central processing unit (CPU), a storage unit such as a hard disk, a reading unit such as a driver, an input unit such as a keyboard, a display unit such as a display, and the like. It is configured by installing a dedicated program on a general-purpose personal computer (PC) or portable information device. Therefore, in the PC, the input interface 2 corresponds to the input unit, the output interface 3 corresponds to the display unit, the lyric database 4 is constructed in the storage unit, and the syllable string cluster generation unit 11, the search INDEX generation unit 12, the subword chain extraction unit. 13. Various processes in the similarity calculation means 14 are executed by a central processing unit (CPU). Alternatively, the input interface 2 may be a portable terminal and the search process may be performed by a PC.

  For example, a part of the lyrics is input to the input interface 2 as text data from the input unit. Further, the input interface may input a part of the lyrics by voice and convert the input voice into text data by a voice recognition method.

  The control unit 10 performs clustering based on the distance between syllable N-Gram described later, and creates a syllable string cluster creating means 11 for registering a subword chain cluster (syllable string cluster), a subword chain cluster (syllable string cluster), and a lyrics database. INDEX creation means 12 for creating a search INDEX in advance with a table of similarities to the phoneme string of each lyric data (search target document) 4 and subword chain extraction for extracting a plurality of subword chains from the search character string Means 13 and similarity calculating means 14 for calculating the similarity of each lyric data (search target document) with respect to the search character string are provided.

The syllable string cluster creating means 11 creates a plurality of syllable N-Grams as a subword chain by combining a predetermined number (N) of syllables from a large number of syllables in a large number of documents, and between each syllable N-Gram. A group to which a plurality of syllable N-Grams clustered on the basis of the distance is registered as a subword chain cluster (syllable string cluster).
A subword chain cluster is a group to which a plurality of subword chains belong, and may be a single subword chain.
Note that phonemes may be used instead of syllables. In this case, the syllable string cluster creating means 11 becomes the phoneme string cluster creating means 11 and creates a plurality of phoneme N-Grams by combining a preset number (N) of phonemes, and between each phoneme N-Gram. A group to which a plurality of phonemes N-Gram clustered on the basis of the distances may be registered as a phoneme string cluster.
The distance between each syllable N-Gram (between each phoneme N-Gram) is a character that is determined by comparing the phonemes that make up the N syllables that make up each syllable N-Gram (the number of phonemes may be different) It is calculated by column similarity calculation (DP matching). The DP matching will be described later.

  The search index creation means 12 creates in advance a search index using a table of distances between a plurality of registered syllable string clusters and phoneme strings of each lyrics data in the lyrics database 4. Each syllable string cluster is a syllable N-Gram representing a plurality of syllable N-Grams. In the search INDEX, the distance of each lyric data with respect to each syllable string cluster calculated in advance is stored. The procedure for creating the search INDEX will be described later.

The subword chain extraction means 13 extracts the input search character string as a plurality of subword chains divided into N syllables. For example, if the search string is composed of 8 syllables and N is 3, the first, second, third syllable, second, third, fourth syllable, third, fourth, fifth The syllable, the fourth, fifth and sixth syllables, the fifth, sixth and seventh syllables, and the sixth, seventh and eighth syllables (syllable 3-Gram) are extracted as subword chains.
In response to the phoneme string cluster creation means 11, the subword chain extraction means 13 uses phonemes instead of syllables, and divides the search character string into N syllables as a plurality of subword chains (phoneme N-Gram). Extract.
A subword chain (syllable string or phoneme string) is created by combining a plurality of subwords (syllable or phoneme), but may be composed of a single subword (syllable or phoneme).

The search document by the similarity calculation means 14 refers to the first pass INDEX search that narrows down the lyrics data candidates for the search character string with reference to the search INDEX, and DP matching between the phoneme strings of the lyrics data candidate and the search character string. This is performed by a second pass DP matching search that is performed to search for final lyrics data.
In the first pass INDEX search, the phoneme string of each lyric data is calculated from the sum of the distances of the subword chain clusters (syllable string clusters) corresponding to each subword chain (syllable 3-Gram) extracted with reference to the above-described search index. This is done by calculating the similarity of. That is, each distance corresponding to the cluster to which each subword chain belongs is obtained from the search INDEX, and the total of each distance is calculated as the similarity to each search target document (phoneme string of each lyric data).
In the second pass DP matching search, the final lyrics data is searched by calculating the similarity by DP matching between phoneme strings of the lyrics data candidate and the search character string.

  The output interface 3 outputs the search result of the lyrics data (search target document) based on the calculation result in the similarity calculation means 14. Search results are output in descending order of similarity to the search character string input to the input interface 2.

  In addition, the output interface may present the song name, artist name, and full lyrics of the lyrics that are the search results. Alternatively, the output interface highlights the entire lyrics that are linked and displayed, and highlights the lyrics that match the query by displaying them in different colors or in large letters. Processing may be performed.

  Next, a procedure for creating a search INDEX used when searching lyrics data for a search character string in the first pass INDEX search will be described with reference to FIG. The search INDEX is created from information input in advance to the syllable string cluster creation means 11 and the search INDEX creation means 12.

First, a large amount of document data such as lyric data and newspaper corpus is input to the sub-word chain extraction means 13, morphological analysis is performed by designating a desired number N, and converted into a syllable string, whereby syllables included in the document data All syllable strings composed of N are calculated as syllable N-GramA (i).
For example, as shown in FIG. 2, when the character string “There is nothing you like” exists in the document data and is input to the subword chain extraction means 13 (step 21), the syllable string “su” is obtained by performing syllable conversion processing. -ki-na-ko-to-ga-na-i "(step 22). If the desired number N is 3, a plurality of syllables N-Gram (syllable 3- Gram) Convert to A (m). Syllable N-GramA (1-6) are "su-ki-na", "ki-na-ko", "na-ko-to", "ko-to-ga", "to-ga-na", "ga-" na-i "(step 23).

  Next, a distance matrix between syllable N-Grams is calculated for all the created syllable N-Gram A (m) (step 24). Regarding the calculation of the distance between the syllable N-Grams, the two syllable N-Grams are converted into phoneme strings, respectively, and the acoustic distance between the two phoneme strings is obtained. As for the method of calculating the acoustic distance between phoneme strings, DP matching (calculation of similarity between series of data) is performed in units of phonemes in two phoneme strings.

  DP matching is a string similarity calculation based on dynamic programming, which is an existing technology. When calculating the acoustic similarity distance between two phoneme strings, the difference between phonemes and the insertion or deletion of phonemes are taken into account. Calculate by calculation means. A specific calculation example of DP matching will be described later.

Returning to the flowchart of FIG. 2, a group to which a plurality of syllable N-Grams clustered based on the acoustic distance between syllables by DP matching belongs is registered as a syllable string cluster C (n) (step 25).
Clustering of a plurality of syllables N-GramA (m) is performed in the following procedure.
As for the calculation of each acoustic distance value composed of the distance matrix between syllable N-Grams (calculation of the distance between syllable N-Grams), each syllable N-Gram is converted into a phoneme string as described above. Then, the acoustic distance between the two phoneme strings is obtained.
Then, each syllable N-Gram is plotted on the acoustic distance value space, and the space is clustered with the acoustic distance values that are close to each other to calculate a syllable string cluster C (n) that is a representative vector of each cluster. The syllable string cluster C (n) represents a plurality of (non-constant numbers different depending on the clusters) syllable N-GramA (m).

As a specific means for realizing clustering, k-means, which is a known technique, can be used. Clustering by k-means is performed by the following procedures (1) to (4).
(1) The data is divided into k clusters, which are an arbitrary number. For example, the number n of syllable string clusters C (n) is 1000.
(2) Calculate the centroid for each cluster.
(3) A cluster that minimizes the distance from the center of gravity is obtained for all data, and each data is assigned to the smallest cluster.
(4) End if there is no change from the previous cluster. If there is a change, return to (2).

  In the above example, the syllable N-Gram (syllable 3-Gram) A (m) is created by inputting the document data to the subword chain extraction means 13 and converting it into a syllable string. However, without inputting the document data. It can also be obtained. That is, in the syllable string cluster creating means 11, a desired number (for example, three sounds) from a large number of phonemes (including about 120 to 130 at the maximum) including 50 sounds and muddy sounds such as “sha” and “ja” and prompt sounds (for example, 3 sounds). All syllables N-Gram (syllable 3-Gram) A (m) connecting N phonemes may be created. In this case, for example, all syllables N-GramA (m) are created with a unit of three phonemes such as “A”, “I”, “U”, “Sha”, “K”, and “I”. If 100 sounds are selected as phonemes, there are 100 cubed syllables N-Gram (syllable 3-Gram) A (m).

  By clustering using the k-means method based on the distance between syllable N-Grams, syllable N-Grams representing multiple syllable N-Grams are automatically classified as syllable string clusters C (n). Then, each acoustic distance value between the syllable string cluster C (n) and the phoneme strings of the plurality of lyrics data L (k) which are search target documents registered in the lyrics database 4 is calculated, and the search as shown in FIG. The INDEX table 30 is created in advance.

  The similarity between the syllable string cluster C (n) and the phoneme string of the lyrics data L (k) is calculated by DP matching. In this case, since the number of phonemes in the lyric data L (k) is larger than the number of phonemes in the syllable string cluster C (n), the lengths of the two phoneme strings are different, so that end point free DP matching is used. By using the end point free DP matching, it is possible to calculate the longest common subsequence of the phoneme series and the lyric data constituting the syllable sequence cluster C (n), and the similarity of the common portion can be calculated. That is, in the end point free DP matching, character string similarity is calculated in consideration of the cost of insertion, deletion, and replacement of phonemes in units of phonemes in two phoneme strings. In the character string similarity calculation, the similarity calculation may be performed based on the number of different phonemes in the two phoneme strings (only the replaced phonemes).

  A specific calculation method by end point free DP matching will be described. If there are two phoneme sequences S1 and S2, and the cost values for insertion, omission, and replacement in DP matching calculation are Cins, Cdel, and Csub, respectively, the initial value of the DP matching calculation formula is Equation 1, and the calculation value is Equation 2 The result value is expressed by Equation (3).

  FIG. 4 shows the DP distance calculation processing result, taking as an example the case where the search phoneme string S1 is “toganai” and the search target phoneme string S2 is “... In this case, in order to simplify the calculation, Cins = 1, Cdel = 1, and Csub = 1. Actually, cost values of Cins, Cdel, and Csub are calculated for each phoneme by a phoneme confusion matrix described later.

First, each value of the search target phoneme string S2 is initialized by the initialization calculation formula 1 (STEP 1). Next, the calculated value of each element of the search target phoneme string S2 with respect to “t” of the search phoneme string S1 is calculated by Equation 2 (STEP 2). In Equation 2, the minimum value among the four equations is selected.
This calculation is sequentially performed on “o”, “g”, “a”, “n”, “a”, and “i” of the search phoneme string S1 (STEPs 3 to 8), and all D (ij) are calculated.

By using the minimum value of D (len (S1), j) as the end point and back-tracing from the end point, an optimum route with D (i, j) having the minimum value (shortest distance) is derived (STEP 9).
As a result, the search phoneme string S1 “toganai” is similar to “towana” of the search target phoneme string S2 “...

  In the search index table 30, as shown in FIG. 3, the calculated syllable string clusters are arranged vertically, the lyrics data are arranged horizontally, and the pre-calculated cluster syllable and the phoneme strings of the lyric data are exchanged. The degree of similarity is composed of a table described in the corresponding part.

In the DP matching calculation, the replacement cost value of phonemes (replacement cost value between different phonemes), the phoneme insertion cost value, and the phoneme dropout cost value are given in advance, and the accumulated DP matching cost representing the similarity between phoneme strings. Ask for. This accumulated DP matching cost is set as an acoustic distance value between phoneme strings. The above phoneme replacement, insertion, and dropout values are calculated based on a phonetic confusion matrix from a speech recognition experiment.
The insertion cost value and dropout cost value are values determined by experience values and pronunciation dictionaries in speech recognition experiments.

  The phoneme confusion matrix is obtained by a speech recognition experiment or the like, and represents a matrix element with a probability. In the speech recognition experiment, a large amount of speech data is collected as learning data, and an acoustic model of phonemes for speech recognition is created using the learning data by an HMM learning algorithm.

Further, an example of calculating the insertion cost of each phoneme using the interphoneme confusion matrix and the replacement cost with other phonemes will be described with reference to Table 1. In this case, the test speech data is input to the speech recognizer, the phoneme sequence that is the recognition result is output, and the correct phoneme sequence that transcribes the test speech data is compared with the phoneme sequence that is the recognition result. Creates a phoneme confusion matrix.
Table 1 shows the number of substitutions, omissions, and insertions for each phoneme of a, b... Z, where n (p, k) is the number of times the phoneme p is recognized as the phoneme k by the speech recognizer, n (φ , p) indicates the number of times the phoneme p has been inserted into the speech recognition result by the speech recognizer (does not exist in the correct phoneme string), and n (p, φ) indicates the number of times the phoneme p has been dropped by the speech recognizer. Yes.

  The cost values (Cins, Cdel, Csub) for insertion, omission, and substitution in DP matching calculation are obtained by Equations 4 to 6, where M is a set of phonemes.

Next, the case of searching for similar lyrics data by inputting a search character string will be described with reference to the flowchart of FIG.
First, a phrase (a character string that is a set of familiar words. For example, “nothing you like”) that the user has stored as part of the lyrics is input as a search character string from the input interface 2 (steps). 41). The phrase “I don't like it” does not have to completely match the syllable included in the actual lyrics.

  The input phrase is subjected to syllable conversion processing from the characters constituting the phrase by the subword chain extraction means 13 (step 42). Specifically, the phrase “I don't like it” is converted into a syllable string “su-ki-na-ko-to-ga-na-i”.

Subsequently, it is converted into a plurality of syllables N-Gram (syllable 3-Gram) Q composed of a specified number N (“3” in this example) (step 43).
The syllable N-GramQ is Q (1) “su-ki-na”, Q (2) “ki” for the syllable string “su-ki-na-ko-to-ga-na-i” in the above example. -na-ko ", Q (3)" na-ko-to ", Q (4)" ko-to-ga ", Q (5)" to-ga-na ", Q (6)" ga-na -i "is converted into six.

Next, the first pass INDEX search for selecting a plurality of (P) lyric data having a smaller value as candidates using the index 30 for searching for the similarity R (k) to the lyric data L (k). Is performed (step 44).
As shown in FIG. 6, this search is performed by using the similarity R (k) that is the sum of the distances between the syllable string cluster C including each syllable N-GramQ corresponding to the phrase of the search character string and the syllable string of the lyrics data. ) = D (35, k) +... + D (n, k) +... + D (1000, k)) is calculated based on the values stored in the table.

Specifically, the syllable string cluster including Q (1) “su-ki-na” is C (35), and the syllable string cluster including Q (m) “na-ko-to” is C (n). ) And the syllable string cluster including Q (6) “ga-na-i” is C (1000), the value obtained by adding these is the similarity R (k).
Then, as a first pass INDEX search result, as shown in FIG. 7, the lyric data is ranked in descending order of the similarity R value for each lyric data, and the top P (for example, 800) lyric data L ( k) is narrowed down as a search target candidate. P, which is the number of lyrics data to be narrowed, can be made variable.

Subsequently, a second pass DP matching search is performed to determine the lyric data having the shortest acoustic distance between the phoneme string of the search character string and the phoneme string of the lyric data (step 45). In this search, the similarity R ′ between the phoneme string of the search character string and the phoneme string of the lyric data that is the search target candidate by the first pass INDEX search is calculated by DP matching. When performing DP matching, a plurality (P) of P (800) lyric data that are candidates for search by the first pass INDEX search are grouped by M (10 to 100) from the top. / M sessions), and DP matching is performed on the lyrics data belonging to each session for each session.
Hereinafter, the procedure of the second path DP matching search will be described with reference to the flowchart of FIG.

  First, P (800) lyric data that are candidates for search by the first pass INDEX search are divided into a plurality of (P / M) sessions with M (10 to 100) as one group (step 51). ).

Subsequently, similarities are calculated by DP matching for search target document candidates (lyric data) belonging to each session in order of the top candidate session. First, the M pieces of lyrics data L (k) belonging to session 1 are calculated. Then, DP matching is performed for each of them to calculate M similarities (step 52).
Then, at the end of the DP matching calculation for all the lyrics data in the session, from the minimum value (D (min)) of similarity in the session and the average value (D (mean)) of M similarities, Similarity D = D (min) / D (mean) is calculated (step 53).

Next, it is determined whether or not the session similarity D is smaller than a predetermined threshold value α (0.4 to 0.5) (step 54).
If the session similarity D is smaller than the predetermined threshold value α, it is determined that there is lyrics data in the session that has a low similarity and is similar to the search character string, and the similarity calculation by DP matching in the subsequent sessions is aborted The output order of search target document candidates is determined based on the similarity calculated at that time, and the top X are output as search results (step 55).
That is, for the X pieces having low acoustic distance values (similarity) R ′ calculated in the DP matching calculated session, the lyrics data and the music information thereof are output as search results to the output interface 3. The X pieces to be output may be lyric data corresponding to all similarities calculated in at least one session for which DP matching has been calculated and their music information (in this case, X is a multiple of M). , It may be a higher one.

  If the session similarity D is not smaller than the predetermined threshold α, the next session obtained by adding “1” to the number of the session for which DP matching has been calculated is set as the DP matching calculation target (step 56). The process is repeated.

  In the above example, the presence / absence of lyrics data similar to the search character string is determined by setting the session similarity D = D (min) / D (mean) and the threshold α = 0.4 to 0.5. However, the session similarity D may be a value calculated based on the minimum value and the average value of the similarity in the session, and the threshold value α is a predetermined value in the range of 0.0 to 1.0. You can decide. For example, when the standard deviation value in the session is D (s), the session similarity D may be obtained from the following formula.

    Session similarity D = D (s) / (D (mean) −D (min))

  According to the second path DP matching search described above, the session similarity D (for example, D = D (min) / D (mean)) calculated based on the minimum value and average value of the similarity in the session is predetermined. If the threshold value α is smaller than the threshold α, it is determined that there is lyric data that has a low similarity and is similar to the search character string, and the similarity calculation by DP matching in the subsequent sessions is terminated. By reducing, the detection processing speed can be improved without reducing the search rate.

In addition, in the similarity calculation by DP matching described above, the number of phonemes in the search character string and the number of phonemes in the lyrics data L (k) are different, so the syllable string cluster and the lyrics at the time of creating the above-described search INDEX Similar to the calculation of the similarity to data, the endpoint free DP matching is used.
For example, if the input search string is "There is nothing you like", compare it with the phoneme string that makes up the lyrics data, and if the lyrics data contains "what you like" Compare the phoneme sequence “sukinakotoganai” (15 phonemes) of the “nothing you like” column with lyric data (15 phonemes or more) by end-point free DP matching, and the most similar “like thing” included in the lyric data The similarity R ′ to the “what” phoneme string “sukinakotowanani” is calculated.

  According to the similar document search device described above, the similarity between each syllable string cluster C (n) and the lyric data (search target document) L (k) is determined in advance at the stage of creating the table 30 in the search INDEX creating means 12. Therefore, the calculation of the lyrics data in the first pass INDEX search at the time of search of the search character string only needs to add the similarities in the table 30, and the calculation by the DP matching of the similarities becomes unnecessary. Therefore, since DP matching with a large amount of calculation performed between phonemes of the search character string and the search target document is performed only by the second pass DP matching search performed only for a small amount of search target candidates, the entire calculation is performed. High-speed search can be realized by reducing the amount.

  In addition, when the table 30 is created in the search index creation means 12, the similarity between the syllable string cluster including the syllable N-Gram that may be a subword chain of the search character string and the lyric data (search target document) is considered. Therefore, it is possible to reduce the probability that the lyrics data (search target document) that is the correct answer in the first pass INDEX search is excluded from the candidates. As a result, it is possible to realize the same search accuracy as the search by DP matching for all search targets.

In addition, by using a syllable N-Gram (subword chain) instead of a word when creating the table 30 in the search INDEX creating means 12 and performing a similar document search by inputting a search character string The problem of no corresponding word (OUT-OF-VOCABULRY) between the search character string and the lyric data (search target document) does not occur.
Further, when the table 30 is created in the search INDEX creation means 12, the number of entries in the search INDEX is reduced by clustering (because the number of syllable N-Grams is reduced to the number of syllable string clusters). Therefore, even when there are many types of syllable N-Grams, the search index size can be reduced.

  In the similar document search device described above, when searching for lyric data (search target document) from the search character string in consideration of the similarity in the similarity calculation means 14, the lyric data narrowing-down process in the first pass INDEX search, Second pass DP matching search processing is performed by DP matching between phonemes of the search character string and the search target document. Since the number P of lyrics data in the first pass INDEX search is a variable, if the search accuracy is to be increased, the number P is increased and the second pass DP matching search process is performed to shorten the search processing time. In this case, the number P may be set so that the number P is reduced and the second pass DP matching search process is performed.

  DESCRIPTION OF SYMBOLS 1 ... Similar document search apparatus, 2 ... Input interface, 3 ... Output interface, 4 ... Lyrics database, 10 ... Control part, 11 ... Syllable string cluster production | generation means, 12 ... Index creation means for search, 13 ... Subword chain extraction means, 14: Similarity calculation means.

Claims (15)

In a search device comprising an input interface for inputting a character string or a character string converted by voice recognition as a search character string, and searching for a search target document including a portion similar to the search character string from a plurality of search target documents,
Create a syllable string or phoneme string (hereinafter referred to as “subword chain”) formed by combining a predetermined number of subwords from a plurality of syllables or phonemes (hereinafter referred to as “subwords”) in a plurality of documents . , A group to which a plurality of subword chains clustered based on the distance between each subword chain belongs is registered as a syllable string cluster or a phoneme string cluster (hereinafter referred to as “subword chain cluster”) , and a plurality of registered subword chain clusters are registered. And a search index creation means for creating a similarity table corresponding to each of the subword chain clusters in advance as a search index;
Subword chain extraction means for extracting a plurality of syllable strings or phoneme strings connecting the desired numbers from the syllables or phonemes constituting the search character string input to the input interface;
For each subword chain extracted by the subword chain extraction means, each similarity corresponding to a subword chain cluster to which each subword chain belongs is obtained from the search INDEX, and the total of the similarities is calculated as a similarity to each search target document. Similarity calculation means for calculating as
An output interface for outputting a search result of document data based on the similarity,
The similarity calculation means performs a first pass INDEX search for narrowing down a plurality of search target document candidates in descending order of the similarity corresponding to the subword chain cluster to which each of the subword chains found from the search INDEX belongs. When,
A second output order is determined based on a similarity obtained by converting the plurality of search target document candidates into a phoneme string, and calculating a character string similarity with the phoneme string of the search character string as a unit. Perform a search with path string similarity calculation ,
The search by the second path character string similarity calculation is as follows:
The search target document candidates searched in the first pass INDEX search are divided into a plurality of sessions, each grouping M from the top as one group,
Calculate the string similarity for the search target document candidates belonging to each session sequentially in the order of the top candidate session, and calculate the similarity,
When the session similarity D calculated based on the minimum value and the average value of the similarity in the session is smaller than the predetermined threshold value α, the similarity calculation by the character string similarity calculation in the subsequent session is terminated,
A similar document search apparatus characterized in that an output order of search target document candidates is determined based on a similarity calculated at that time. The session similarity D and the threshold α are set to the minimum value D (min) and the average value D (mean) of the similarity in the session.
Session similarity D = D (min) / D (mean),
Threshold value α = 0.0 to 1.0
The similar document search device according to claim 1. When the standard deviation value in the session is D (s),
Session similarity D = D (s) / (D (mean) −D (min)),
The similar document search device according to claim 2.   The similarity in the INDEX creation means is obtained by converting a syllable string or a phoneme string representing each subword chain cluster and a search target document into a phoneme string, and performing character string similarity calculation in units of phonemes in the two phoneme strings. The similar document search device according to claim 1, wherein the similar document search device calculates the cumulative character string similarity value obtained in this way. 5. The character string similarity calculation between the phoneme strings is performed by calculating a phoneme replacement cost value, a phoneme insertion cost value, or a phoneme dropout cost value based on a phoneme confusion matrix by a speech recognition experiment. Similar document search device.   The similar document search device according to claim 5, wherein the replacement cost value, insertion cost value, and dropout cost value are values determined by an experience value or a pronunciation dictionary.   The similar document search device according to claim 1, wherein the subword chain cluster is a group to which a plurality of subword chains belong, and is only one subword chain.   The similar document search apparatus according to claim 1, wherein the input interface inputs a part of lyrics as text data.   2. The similar document search device according to claim 1, wherein the input interface inputs a part of lyrics by voice, and searches after converting the input voice into text data by a voice recognition technique. The similar document search device according to claim 1, wherein the output interface presents a song name, an artist name, or a full text of lyrics as a search result.   The similar document search device according to claim 1, wherein the output interface displays the entire lyrics in a linked manner, and highlights the portion of the lyrics that matches the query when displayed. The similar document search device according to claim 1, wherein the subword chain is created by a combination of a plurality of subwords . The similar document search device according to claim 1, wherein the subword chain is composed of one subword . The similar document search apparatus according to claim 1, wherein the character string similarity calculation uses an end point free DP matching method in consideration of the cost of insertion, deletion, or replacement of phonemes in units of two phoneme strings.   The similar document search device according to claim 1, wherein the character string similarity calculation is performed by a similarity calculation method based on the number of different phonemes in two phoneme strings.