JP2011159100A - Successive similar document retrieval apparatus, successive similar document retrieval method and program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a successive similar document retrieval apparatus, method and program, which has high convenience when retrieving documents in which prescribed document are similar in texts such as news, blog news and diaries of a social network which are daily produced in so large amounts. <P>SOLUTION: The successive similar document retrieval apparatus has: a successive similar document retrieval means for successively retrieving similar documents; and an updating means for updating retrieved results retrieved by the successive similar document retrieval means. <P>COPYRIGHT: (C)2011,JPO&INPIT

Description

  The present invention relates to a sequential similar document search apparatus, a sequential similar document search method, and a program.

  With the development of the web, texts such as news, blog articles, and social network diaries are being produced in large quantities every day. Since the recorded text is intended for someone to read, whether it is similar to text already written by someone is a fundamental question of the value of the text.

  Therefore, it can be said that the similar document retrieval technique in the document database composed of a large number of documents made possible by the development of computers is a very important technique. In fact, its application range is wide, and attempts are being made to apply to patent documents and papers.

  When measuring the degree of similarity between documents, there is a method in which words used in the documents are represented as vectors as a set of symbols and the distance is measured, which is widely used for similar document search. But words, or words, are created by people, and it is not enough to treat the diversity of meanings as symbols.

  Therefore, a concept-based method has been proposed as a method for representing a document that does not appear in the immediate document and takes into account the rich meaning of the word (see Non-Patent Document 1, for example). The concept-based method uses a large amount of training data to express a word as a vector (expressed as a word concept vector). A document can be expressed as the center of gravity of a word concept vector that appears. That is, when a word is expressed by a word concept vector, it expresses how the word is used. By using the word concept vector, it is possible to search for similar documents in consideration of the rich meaning of words created by humans.

  The concept-based method replaces the similar document search with a similar search in a dense vector space of hundreds to thousands of dimensions (the vector dimension is determined depending on the application). However, conventionally, it is difficult to perform a similar search in a high-dimensional vector space at high speed due to a “dimensional curse”. Even in the concept-based method, when searching for similar documents, it is realized by a naive technique of ranking after matching all documents in the database, so searching for a few seconds against a database of millions of documents It takes time.

  On the other hand, from the database field, which is a field different from the document processing technique, research on an approximate vector similarity search technique that overcomes the “curse of dimension” has started around 1998 (for example, see Non-Patent Document 6). ). Of the various techniques proposed, a locality detectable hash (LSH) (see, for example, Non-Patent Document 4) is the most promising. The locality detectable hash is obtained by approximating a multidimensional vector and indexing using a plurality of hashes. Thus, the search calculation cost can be reduced to (number of hashes) × (number of sampling bits) while guaranteeing the search accuracy stochastically.

  Theoretically, similar retrieval is possible at high speed without greatly depending on the number of dimensions, and application to information recommendation, image retrieval, etc. on the web is expected.

  Although the locality-detectable hash (LSH) is an approximation algorithm, the accuracy is probabilistically guaranteed (see, for example, Non-Patent Documents 3 and 4), and a neighborhood (similar) search can be realized very quickly. . The theoretical framework is organized in Non-Patent Document 3, and Non-Patent Document 4 implements a locality-detectable hash (LSH) that maps a multidimensional vector space in which an L1 norm is defined to a Hamming space. . Recently, not only the L1 norm but also an L2 norm version using a stable distribution, a cosine similarity version, and a Jaccard coefficient version have been proposed.

  By the way, in the prior art, sequential search using keywords (incremental search) is widely spread and used regardless of English or Japanese (see various search engines and Non-Patent Document 2).

  “Sequential search” is a search method in which candidates are displayed immediately every time a user inputs a character, rather than inputting all the words to be searched. The sequential search is a kind of “Dynamic Query” in which the search dynamically proceeds according to the user's input and leads not only to efficient search but also to efficient text editing (for example, see Non-Patent Document 2). . The normal sequential search is a partial match search using a partial character string of a search query, and is a technique for quickly reaching a matching portion after regarding an input character string as a symbol and regarding a search target as a symbol.

  A similar document search technique using a rich concept of a language has been proposed for a normal match search in which keywords are regarded as symbols (for example, see Non-Patent Document 1). The described invention cannot reduce the cost of calculating the distance between high-dimensional concept vectors.

Katsuhito Bessho, Toshiro Uchiyama, Ryoji Kataoka, “Concept-based extension based on co-occurrence between words and semantic attributes”, IPSJ Research Report 2006-ICS-144 2006/7/28, pp.29-34. Satoshi Takabayashi, Hiroyuki Komatsu, Toshiyuki Masui “Migemo: Japanese Incremental Search”, Transactions of Information Processing Society of Japan, Vol. 43, No. 12, pp. 3698-3705, December, 2002. Kevin S. Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft “When Is“ Nearest Neighbor ”Meaningful?” ICDT 2005 Piotr Indyk, Rajeev Motwani, “Approximate nearest neighbors: towards removing the curse of dimensionality” Annual ACM Symposium on Theory of Computing 1998 “Similarity Search in High Dimensions via Hashing” by Aristides Gionis, Piotr Indyk, Rajeev Motwani, Very Large Data Bases 1999 Roger Weber, Hans-Jorg Schek, Stephen Blott “A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces” Very Large Data Bases 1998

  In the conventional example described above, in the similar document search using the concept of the word, the poor response of the similar document search interface caused by the decrease in the search speed caused by the “dimensional curse” occurs, that is, the convenience of the similar document search is low. There is a problem.

  In the above conventional example, since the search is started after the user completes the creation of the question sentence, the result of the similar document search cannot be obtained in the middle of the question sentence creation by the user. It is necessary to wait until the question sentence is completed. In this sense, there is a problem that the convenience of similar document search is low.

  Furthermore, in the above conventional example, there is a problem that the retrieval accuracy is lowered, the CPU cost of the retrieval server is not lowered, and high-speed sequential similar document retrieval cannot be performed.

  An object of the present invention is to provide a sequential similar document search apparatus, a sequential similar document search method, and a program that are highly convenient in similar document search.

  The present invention has a sequential similar document search device comprising: sequential similar document search means for sequentially searching similar documents; and update means for updating a search result searched by the sequential similar document search means. It is.

  According to the present invention, there is an effect that convenience is high in a similar document search.

It is a block diagram which shows the outline of the sequential similar document search system 100 which is Example 1 of this invention. 2 is a diagram illustrating a hardware configuration of a client CL1 and a similar document search application 10 in a sequential similar document search system 100. FIG. It is explanatory drawing of operation | movement of the sequential similar document search system 100, and is a figure which shows the process outline | summary of the sequential similar document search process using a LSH index. 3 is a flowchart showing the operation of the first embodiment. It is explanatory drawing of operation | movement of the sequential similar document search system 200 which is Example 2 of this invention, and is explanatory drawing of the process using a concept base in the sequential similar document search using an LSH index. 6 is a flowchart showing the operation of the second embodiment. In the sequential similar document search system 300 which is Example 3 of this invention, it is a figure which shows the outline | summary of the process using the cache of a word concept vector using a concept base in the sequential similar document search using an LSH index. 10 is a flowchart illustrating the operation of the third embodiment.

  The modes for carrying out the invention are the following examples.

  FIG. 1 is a block diagram showing an outline of a sequential similar document search system 100 according to the first embodiment of the present invention.

  The sequential similar document search system 100 is an embodiment in which search is performed in units of index words instead of units of characters.

  Note that the above-described sequential similar document search is to perform similar document search incrementally. The index word boundary of the input search sentence q is recognized, and the retrieval result is dynamically updated at the timing when the index word is added. I do.

  The sequential similar document search system 100 includes a similar document search application 10, a network NW1, and clients CL1, CL2, and CL3. Users U1, U2, and U3 correspond to the clients CL1, CL2, and CL3, respectively. is doing.

  The similar document search application 10 is an example of a similar document search device, and includes a router 11, a LAN 12, an application server 13, database servers 14 and 15, and a similar document search engine 16. The similar document search engine 16 includes an LSH construction engine 161 and an inquiry processing engine 162.

  FIG. 2 is a diagram illustrating a hardware configuration of the client CL1 and the similar document search application 10 in the sequential similar document search system 100.

  The client CL1 includes a communication unit 31, a storage unit 32, a data processing unit 33, and a user interface 34.

  The similar document search application 10 includes a communication interface 17, a control unit 18, and a storage unit 19, and is connected to an input device 21 and an output device 22.

  The control unit 18 includes an LSH construction unit 181 and an inquiry processing unit 182.

  The storage unit 19 includes a ROM 191, a RAM 192, an HDD 193, and an SSD 194.

  FIG. 3 is an explanatory diagram of the operation of the sequential similar document search system 100 and is a diagram showing a processing outline of the sequential similar document search processing using the LSH index.

  Note that LSH is a locality-sensitive hash, which is a method for performing approximate neighborhood search using a hash, and hashes corresponding to the Hamming distance, Euclidean distance, L2 norm, and cosine similarity A method has been proposed.

  The original document set D1 is made into a document database using a document vector model or the like. A locality detectable hashing H1 is applied to the document database DB1 to construct an LSH index. The above is executed as preprocessing.

  The user U1 inputs the search sentence q and performs writing in real time, and similarly converts the search sentence q into a multidimensional vector using a document vector model or the like. Note that the above multidimensional vector expresses features such as the position and shape of an object, images, movies, and texts as a vector in Euclidean space, and the number of dimensions depends on the measuring device and application. Can be decided. For example, a concept-based word concept vector is a multidimensional vector.

  An approximate similarity search is performed using the LSH index, and a similar document set D2 is obtained as a result. Finally, the result list is displayed to the user U1 while being sequentially updated.

  The sequential similar document search system 100 realizes high-speed similar document search using the locality-detectable hashing H1. Furthermore, by using a high-speed search process, sequential similar document search (incremental similar document search), which has been impossible in the past, is realized, and the interface for similar document search is improved.

  In general, since the user U1 sequentially adds the search sentences q, the word vector already included in the search sentence q can be cached. You only need to query the words added to. That is, the query to the index word database DB2 can be realized at high speed. As described above, the similar document search is processed at high speed, so that the similar document search can be realized sequentially.

  According to the above-described embodiment, a search using a long natural sentence as a search sentence q can be realized at high speed, and thus a similar similar document search can be performed in a free form document editing environment. For example, on a Q & A site represented by “Tell me goo”, while a questioner is creating a new question, as the question is added, a similar question is immediately presented by performing a sequential search. can do. In other words, similar questions are presented to the user while creating a search statement, so the question may be resolved without asking questions. In this case, the similar question is repeatedly executed. This is a merit for both the questioner and the site operator.

  In addition, the application area of the proposed technology is not limited to Japanese. In the case of a clearly delimited language such as English, query vectors can be obtained without writing, so that similar document retrieval can be performed sequentially at higher speed.

  The similar document search system 100 can be used as a similar document search engine 16 for various contents such as news and web logs.

  The sequential similar document search system 100 shown in FIG. 1 is an example used inside the similar document search application 10.

  The similar document search engine 16 is used by the application server 13 and includes an LSH construction engine 161 and an inquiry processing engine 162. These processing units can be realized not only in a single server but also in a distributed configuration with a plurality of units.

  Next, the operation of the first embodiment will be described.

[Sequential search processing]
FIG. 4 is a flowchart illustrating the operation of the first embodiment.

  In S1, the LSH index idx constructed for the document database DB1 and the search sentence q at a certain point in time are input.

  The document database DB1 shown in FIG. 3 need not be limited to the one based on the concept-based method. For example, a tf * idf method or the like in which a word is regarded as a symbol and weighted at the frequency may be used. By doing so, each document can be made into a multidimensional vector and can be indexed by using the locality detectable hashing H1.

  Next, in S2, the search sentence q is divided and a result word string Vq is generated. For example, it is conceivable to use a tf * idf method in which a word is regarded as a symbol and weighted at the frequency. Then, in S3, it is determined whether or not the end of the search sentence q is an index word boundary. If it is determined that it is not an index word boundary, it waits for the user U1 to add a search part q (query) in S4. . If it is determined that it is an index word boundary, a similarity search process is performed in S5 using the result word string Vq and using a pre-constructed LSH index idx.

  The similarity search is a search for obtaining a vector similar to (similar to) a given search sentence q from a multidimensional database in which a large number of multidimensional vectors are stored. The proximity is determined by the distance (similarity). In particular, when a document is a search target vector, if the document is a search target vector, it is called a similar document search. The distance satisfies a distance axiom among measures defined between two multidimensional vectors.

  When determining whether or not the end of the search sentence q is an index word boundary, as shown in [Example 1] described later, if the part of speech of the word that is the result of the morphological analysis is a noun or a sub-variable, the index word As shown in [Example 2], which will be described later, if there is a word in the index word database DB2, it is determined that the word is a post-search boundary. It can be determined whether the end is an index word boundary.

"Example of determining whether the end of the search sentence q is a word boundary"
[Example 1]: Method of indexing a document set (determining that it is an index word boundary) by performing morphological analysis and using “noun” and “sa-variable” In the above [Example 1], the search sentence q If the end of the morphological analysis is a noun or a sub-variable, it is determined that it is a search word boundary. For example, morphological analysis of “Today's weather is now” as the search sentence q, “Today: noun, no: case particle, weather: noun, ha: continuous particle, yes ,: verb stem, performance: verb suffix” It is. Since the end “mai” of the search sentence q is a verb suffix and is neither a noun nor a sub-variable, it is determined that the end of the search sentence q is not an index word boundary.

If the part of speech of the last word in the word string resulting from morphological analysis is the part of speech (noun or sub-variable) that is to be indexed (determined to be an index word boundary), The “last word” is the index word boundary. When characters are sequentially input as shown below, three index word boundaries x, y, and x appear, and similar documents are searched only at the index word boundaries. Therefore, if similar document search is executed three times In short, the CPU cost of the search server (similar document search engine 16 of the similar document search application 10 shown in FIG. 5) is reduced.
・ Today's heaven (noun) ... index word boundary x
That is, if you enter “heaven” sequentially after “today”, the input “heaven” is a noun, and the noun is the part of speech to be indexed. Is an index word boundary, and this boundary is expressed as an index word boundary x.
・ Today's weather (noun) ... index word boundary y
In other words, if “ki” is entered sequentially after “Today's heaven”, the inputted “ki” is a noun, and the noun is the part of speech to be indexed. "Is an index word boundary, and this boundary is expressed as an index word boundary y.
・ Today's weather (continuous particle)
That is, if you enter “ha” sequentially after “Today's weather”, the input “ha” is a continuous verb, and the continuous verb noun is not a part of speech to be indexed. “Ha” is not an index word boundary.
・ The weather today is yes (verb stem)
・ Today's weather is now (noun) ... Index word boundary z
That is, if you enter "now" sequentially after "Today's weather is", the entered "now" is a noun and the noun is the part of speech that is to be indexed. “Now” is an index word boundary, and this boundary is expressed as an index word boundary z.
・ Today's weather is now (verb suffix)
・ Today's weather is not good enough (continuous verbs)
・ The weather today is not good enough (determinants)
・ The weather today is not good enough (final particle)
・ The weather today was not good enough (determinants)
[Example 2]: Method of determining whether or not the index word database DB2 is an index word boundary In the above [Example 2], the last word of the segmentation result is index word database DB2 using the result of segmentation only. If it is included, the index word boundary is determined. In [Example 2], it is not necessary to perform morphological analysis. The index word database DB2 is stored in the HDD 193 or the like.
・ Today's “heaven” (included) index word boundary In other words, when “heaven” is sequentially input following “today”, the last word “heaven” input is stored in the index word database DB2. Since it is included, the input “heaven” is an index word boundary, and this boundary is expressed as an index word boundary x.
-Today's "weather" (included) index word boundary That is, when "ki" is sequentially input following "today's heaven", the last word "weather" input is the index word database DB2. Therefore, the inputted “qi” is an index word boundary.
・ Today ’s weather “ha” (not included)
That is, when “ha” is sequentially input following “today's weather”, since the last word “ha” input is not included in the index word database DB2, the input “ha” is input. Is not an index word boundary.
・ Today ’s weather is “I” (not included)
・ Today ’s weather is “now” (not included)
If “now” is “now” of the Chinese character, “now” is included in the index word database DB2, and thus “now” input is an index word boundary. However, since “now” is not included in the index word database DB2, the input “now” is not an index word boundary.
・ Today ’s weather is “Mai” (not included)
-Today's weather is "Imaichi" (included) index word boundary-Today's weather is "Ida" (not included)
・ Today ’s weather is “not good” (not included)
・ Today ’s weather was “good” (not included)
Note that the above “(included)” means that the last word of the segmented result is included in the index word database DB2. In addition, the above “(not included)” means that the last word of the segmented result is not included in the index word database DB2.

  It should be noted that the index word set included in the segmentation result other than the index word boundary is the same as the index word set included in the segmentation result immediately before the index word boundary. In other words, the search result does not change even if the similar document search is performed in the state of the search word boundary or the similar document search is performed in a state other than the search word boundary. That is, even if a similar document is searched only in the search word boundary state, the search accuracy does not decrease. That is, even if the number of searches is reduced without searching for similar documents in a state other than the search word boundary, the search results are not affected, and therefore the search accuracy is not lowered. It should be noted that every time a character is input, index word boundary detection processing is executed, and immediately before the above is immediately before detecting an index word boundary of a search sentence, which is boundary detection immediately before the boundary detection just performed.

  Next, in S6, the result search result vector set Rq is sequentially added to the interface viewed by the user U1. Thereby, a sequential search can be realized.

  For example, in the above [Example 1], the following search results can be obtained by performing a search using the respective search sentences q (queries) up to the index word boundaries x, y, and z.

Index word boundary x… Today's heaven → Today, heaven [Search results]: “The weather is good today”, “Today we were called by heaven”
In other words, when searching for “Today's sky”, which is the search sentence q up to the index word boundary x, the search results (the top two search results in the ranking) are “Today's weather is good” Suppose you were called.

Index word boundary y… Today's weather → Today, weather [Search results]: “How is the weather today?”, “Today ’s weather is good”
In other words, when searching for “Today's weather” that is the search sentence q up to the index word boundary x, the search results (the top two search results in the ranking) are “How is the weather today?” It ’s good. ”

Index word boundary z… Today ’s weather is now → Today ’s weather, now [Search Results]: “What ’s the weather today?”, “How about the weather today?”
The more the search text is added, the more the characteristics of the keyword can be used. Therefore, it can be expected that the accuracy of the search result increases.

  Finally, if it is determined in S7 that the search sentence q is updated, that is, if the user U1 modifies the search sentence q (query), the process returns to step S2 where a vector is generated from the query, and the same processing is repeated.

  Example 1 is an invention that implements sequential similar document search while solving performance problems using locality-detectable hashing H1 that maps a multidimensional vector space to a Hamming space. In sequential similar document search, The index word boundary of the input search sentence q is recognized, and the retrieval result is dynamically updated at the timing when the index word is added, and the search result can be obtained sequentially as the search sentence q is input. .

  According to the first embodiment, it is possible to perform a high-speed sequential similar document search without reducing the search accuracy and reducing the CPU cost of the search server.

  In the first embodiment, it is not necessary to sequentially search for similar documents in units of index words, and it is not necessary to detect index word boundaries of search sentences. That is, it suffices to sequentially search for similar documents, and in the above embodiment, the sequential similar document search means for sequentially searching for similar documents and the update for updating the search results searched by the sequential similar document search means are described. FIG. 2 is an example of a sequential similar document search apparatus having a means. In this way, it is possible to obtain a similar document search result during the creation of a question sentence by the user, and there is no need to wait for the result of the similar document search until the question sentence is completed, and the convenience of the similar document search is high.

  The sequential similar document search system 200 according to the second embodiment of the present invention is an embodiment in which search is performed in index word units and the concept-based method is used.

[Sequential search processing using concept base]
The hardware of the sequential similar document search system 200 is the same as that of the sequential similar document search system 100 shown in FIGS.

  Next, the operation of the second embodiment of the present invention will be described.

  FIG. 5 is an explanatory diagram of the operation of the sequential similar document search system 200 according to the second embodiment of the present invention, and is an explanatory diagram of processing using the concept base in the sequential similar document search using the LSH index.

  The concept base is a database extracted by performing singular value decomposition on words and semantic attribute co-occurrence matrices. By using a morphological analyzer having a semantic attribute assigning function, it is possible to construct a word semantic vector reflecting the meaning of a large amount of training data. A document can be expressed as the center of gravity of the word vector that appears, and a concept search based on the semantic similarity of the document can be realized using the proximity of the distance between vectors.

  A document database DB1 and an index word database DB2 are constructed from the original document set D1 using a concept-based method. A locality detectable hashing H1 is applied to the document database DB1 to construct an LSH index. The above is executed as preprocessing.

  The user U1 inputs the search sentence q (query), performs the division in real time, uses the index word database DB2, and converts the input search sentence q (query) into the query concept vector shown in FIG. An approximate similarity search is performed using the LSH index, and a similar document set D2 is obtained as a result. Finally, the result list is displayed to the user U1 while being sequentially updated.

  FIG. 6 is a flowchart illustrating the operation of the second embodiment.

  In Example 2, in S11, a word concept base (see FIG. 5, a database that allows word concept vectors to be searched by word names) constructed by the concept base method is prepared (see Non-Patent Document 1). In S2, as in the similar document search process of the concept-based method, first, the search sentence q is written out and the word set Vq is obtained. Next, the concept vector of each word in the word set Vq is acquired from the word concept base.

In S12, the center of gravity of these word concept vector sets is obtained. Center of gravity, for example, a set Dw word concept vector, Dw = {v1, v2, ... vm} is taken as the center of gravity vector _{G q,}

と表すことができる。なお、ｍは、単語概念ベクトルの数である。Ｓ１３で、この重心ベクトルＧ_ｑを検索キーとして、ＬＳＨ索引ｉｄｘに対して検索処理を行い、Ｓ１４で、検索結果を逐次的にインタフェースに追加する。さらに、検索文ｑに更新があれば、Ｓ２に戻り、再度検索を行い、結果を逐次的に更新する。

It can be expressed as. Note that m is the number of word concept vectors. In S13, as a search key the centroid vector _{G q,} it performs a search process on LSH index idx, in S14, to add to sequentially interface search results. Further, if there is an update in the search sentence q, the process returns to S2, the search is performed again, and the results are updated sequentially.

  According to the second embodiment, when an index word boundary is detected, a similar document search by the concept-based method is realized, so that it is possible to perform a similar similar document search in consideration of the meaning of the word. That is, in the second embodiment, the document database DB1 vectorized by the concept-based method is indexed in advance using the locality detectable hashing H1 (detects index word boundaries). A word concept vector set constructed by the concept-based method is also indexed as an index word database DB2 by adding an index (hash, B-tree, etc.) to the word name. Each time the user U1 inputs a character string of the search sentence q, a word set is acquired. In the case of Japanese with no word breaks, the search sentence q (search query) is immediately written and a word set is acquired. If a word is added or deleted from the immediately preceding state, the index word database DB2 is searched using each divided word, a centroid vector of a word set included in the database is obtained, and this is used as a search query vector. And Note that this search query vector (= query vector) is a superordinate concept of the query concept vector, and among the search query vectors, a vector created using the word concept base is a query concept vector.

  The document database DB1 is inquired using the search query vector as a search key. The document database DB1 can return the similar document set D2 at high speed by the locality-detectable hashing H1, and can return the pseudo-similar document set D2 to the user U1 sequentially and show it. Unlike normal sequential search (incremental search), updating the search result in terms of words instead of characters can reduce the load on the server.

[Sequential search processing using word vector cache]
The sequential similar document search system 300 according to the third embodiment of the present invention searches in index word units, uses a concept-based method, stores the previous centroid vector and word, and uses only the difference to determine the next centroid vector. Is an embodiment in which

  Next, the operation of the sequential similar document search system 300 will be described.

  FIG. 7 is a diagram showing an overview of processing using a concept base and using a word concept vector cache in sequential similar document search using an LSH index in the sequential similar document search system 300 according to the third embodiment of the present invention. It is.

  A document database DB1 and an index word database DB2 are constructed from the original document set D1 using a concept-based method. A locality detectable hashing H1 is applied to the document database DB1 to construct an LSH index. The above is executed as preprocessing.

  The user U1 inputs the search sentence q and performs a writing in real time, and detects whether or not there is a difference from the immediately preceding search sentence q in the search sentence q. Only the words that have been newly added or deleted are queried using the index word database DB2 and used together with the immediately preceding search sentence q to construct a query concept vector. The set of search sentences q is stored for the next inquiry. An approximate similarity search is performed using the LSH index, and a similar document set D2 is obtained as a result. Finally, the result list is displayed to the user U1 while being sequentially updated.

  FIG. 8 is a flowchart illustrating the operation of the third embodiment.

During a normal search, the user U1 often appends a search sentence q. Further, in a free-form text editing environment such as a diary entry text area or a question text creation text area on a Q & A site assumed by the present technology, a long document is added to some extent. Therefore, the centroid vector and the word immediately before the successive similar document search are stored, and in S21, the difference between the index word set acquired from the pre-update segmentation result and the index word set acquired from the post-update segmentation result is detected. By searching only for the detected difference, the number of queries to the word concept base is reduced to update the centroid vector. The difference Δ is a difference between the divided word sets, and includes an added word set δ ₊ and a deleted word set δ ₋ . In this case, the updated center-of-gravity vector G _q ′ can be updated by the following equation (2).

If | V _q | is sufficiently large (that is, if the immediately preceding search sentence q is long), the number of word concept-based searches can be greatly reduced, and the search speed is improved. In the above formula (2), V _q , δ ₊ , and δ ₋ all indicate a set, and these absolute value symbols indicate the number of elements included in the set.

  Each of the above embodiments can be implemented as software usable on a computer. The program can be stored in any computer-readable medium such as a hard disk, CD-ROM, optical storage device, or magnetic storage device.

  According to the third embodiment, the previous centroid vector and the word are stored, and the next centroid vector is updated only in accordance with the difference between the immediately preceding received vector and the current received vector. Successive similar document search is executed at high speed.

  According to the above-described embodiment, it is possible to realize a sequential similar document search that has been impossible in the past.

  In the first embodiment, by performing a search in units of words rather than in units of characters, it is possible to sequentially perform similar document searches by reducing the number of searches to the database without reducing the search accuracy and response time. Further, in the second embodiment, by using the concept-based method, it is possible to realize a sequential similar document search considering the rich meaning of words. Furthermore, in the third embodiment, a similar centroid search is realized at a higher speed by storing a centroid vector and a word set immediately before searching for an index word boundary and searching the database only for differences to the next search sentence q. it can.

  As a feature of the proposed technology, a search using a long natural sentence as a search sentence q can be realized at high speed. As a result, it is possible to search for similar documents sequentially in a free form document editing environment. For example, in a Q & A site represented by “Tell me goo”, while a questioner is creating a new question, as the question is added, a similar question is immediately presented by a sequential search. be able to. In this way, since similar questions are searched immediately, it will refrain from asking similar questions, avoiding repeated similar questions, and gaining benefits for both the questioner and the publisher. It is done.

  Further, if the means in each of the above embodiments is changed to a process, the above embodiment can be grasped as a method invention. That is, in the above embodiment, the sequential similar document search means sequentially searches for similar documents and stores them in the storage means, and the search results searched in the sequential similar document search stage. It is an example of the sequential similar document search method characterized by having the update step which updates.

  In this case, the search word boundary search means has a search word boundary search stage that detects an index word boundary of the search sentence and stores it in the storage means, and the sequential similar document search stage includes the index word boundary detection stage. This is a step of sequentially searching for similar documents in units of index words each time an index word boundary of the search sentence is detected. The index word boundary detection step is a step of detecting an index word boundary of a search sentence using locality detectable hashing. Further, the index word boundary detection step is a step of realizing a similar document search by a concept-based method.

  Moreover, the said Example can be grasped | ascertained as invention of a program. That is, it is possible to assume a program that causes a computer to execute the sequential similar document search method. The program may be recorded on a computer-readable recording medium such as a semiconductor memory, CD, DVD, magnetic disk, magneto-optical disk, or HD.

100, 200, 300 ... Sequential similar document search system,
10: Similar document search application,
16 ... Similar document search engine,
18 ... control means,
181 ... LSH construction means,
182 ... Inquiry processing means,
DB1 ah document database,
DB2 ... Index word database,
D1 ... original document set,
D2 ... Similar document set.

Claims (10)

A sequential similar document search means for sequentially searching similar documents;
Updating means for updating a search result searched by the sequential similar document search means;
A sequential similar document search apparatus characterized by comprising: In claim 1,
Having an index word boundary detecting means for detecting an index word boundary of a search sentence;
The sequential similar document search means is means for sequentially searching for similar documents in units of index words each time the index word boundary detection means detects an index word boundary of the search sentence. Similar document search device. In claim 2,
The sequential similar document search device, wherein the index word boundary detecting means is means for detecting an index word boundary of a search sentence using locality detectable hashing. In claim 2,
The sequential similar document search device, wherein the index word boundary detection means is means for realizing similar document search by a concept-based method. In claim 4,
Storage means for storing a centroid vector of the search sentence and a word vector in the search sentence immediately before detecting an index word boundary of the search sentence;
The index word boundary detecting means is a means for searching only index words newly added and deleted from the immediately preceding state,
The sequential similar document search device, wherein the updating means is means for updating the centroid vector. A sequential similar document search means for sequentially searching for similar documents and storing them in a storage means;
An update stage for updating the search results searched in the sequential similar document search stage;
A sequential similar document search method characterized by comprising: In claim 6,
The search word boundary search means has a search word boundary search stage for detecting an index word boundary of the search sentence and storing it in the storage means,
The sequential similar document search step is a step of sequentially searching for similar documents in units of index words each time an index word boundary of the search sentence is detected in the index word boundary detection step. Sequential similar document search method. In claim 7,
The sequential similar document search method, wherein the index word boundary detection step is a step of detecting an index word boundary of a search sentence using locality detectable hashing. In claim 7,
The sequential similar document search method, wherein the index word boundary detection step is a step of realizing a similar document search by a concept-based method.   A program for causing a computer to execute the sequential similar document search method according to any one of claims 6 to 9.

Images