JP2008077252A - Document ranking method, document retrieval method, document ranking device, document retrieval device, and recording medium - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To rank documents based on a criterion associated with volume and density of topics of the documents. <P>SOLUTION: In a step S1, document input process is carried out for inputting documents. In a step S2, using a document database 11, morpheme analysis process is carried out for extracting morphemes from the documents. In a step S3, a simple sentence extraction process is carried out for extracting simple sentences from the documents. In a step S4, simple sentence similarity calculation process is carried out for calculating similarity between the simple sentences extracted by the simple sentence extraction process. In a step S5, using the document database 11, similar simple sentence concatenation set extraction process is carried out for extracting similar simple sentence concatenation set groups based on a similarity relationship between the simple sentences and appearance positional information of the simple sentences inside the documents. In a step S6, an inter-document score calculation processing is carried out for calculating a score of the document based on the extracted similar simple sentence concatenation set groups, and then, the processes are finished. <P>COPYRIGHT: (C)2008,JPO&INPIT

Description

  The present invention relates to a document ranking method, a document retrieval method, a document ranking device, a document retrieval device, and a recording medium, and is suitable for a document processing system based on natural language processing such as document retrieval and document classification.

In recent years, with the development of Internet technologies such as the World Wide Web (WWW), it has become possible to easily access a large amount of document data, and there are various techniques for searching only interesting document data from a large amount of document data. Document retrieval technology has been proposed and used.
For example, as seen in the search result of Google, which is a search system on a typical World Wide Web (hereinafter referred to as “WWW”), the search result is similar to the query word for the convenience of the user. It will be ranked and presented accordingly.

However, as pointed out in Patent Document 1, if the number of search query words is small, or if the word is a general word, a large amount of search results are obtained, and the query word is changed due to rapid WWW development. Search results also become large due to reasons such as the number of matching documents being essentially increased, and as a result, it is becoming increasingly difficult to effectively use the search results.
As a method for solving such a problem, there are Patent Documents 1 and 2, etc., and a method for providing an appropriate search result by re-ranking the search result by analyzing a link structure between documents of the search result is proposed. is doing. In other words, in the above-described invention, a document set satisfying a certain criterion collected by a search system or the like (in the case of a similar search system, matching similarity between a query word and a search target document) is re-ranked according to a different criterion. This indicates that the convenience of using search results is improved.
US Pat. No. 6,725,259 US Pat. No. 6,738,678 Japanese Patent No. 3612597 JP 2004-234284 A

By the way, for example, FIG. 1 is an example of a query word “postal privatization and management”, which is an example of a search result by Google, but it can be seen that there is a difference in the length of the search result document. Note that “and” in the inquiry word indicates an AND search. Furthermore, from this result, it can be inferred that the size of the area related to the “topic” corresponding to the query word and the level of detail are also different for each document.
Therefore, by extracting the area corresponding to the “topic” corresponding to the query word in each document of the search result, and comparing the size of the area as the detail level of the topic, the search result is ranked by the detail level of the topic. It is possible to improve the convenience of search results.

In addition, in the search result document, there should be not only the topic corresponding to the query word, but also the topic and topic area that are different but common, and by using these information together, It is considered that an abundant ranking considering document contents can be provided.
Furthermore, by identifying specific topic areas in different documents, if the areas are different in size, the topic areas of other documents may be summaries when viewed from the topic areas included in one document. It can be considered that it is a detailed description, and it can be used not only for the re-ranking of search results but also for analysis of document sets and information extraction. It is assumed that the simple sentence chain indicates a topic area, the single sentence concatenation set indicates a set of topic areas of a single topic, and the single sentence concatenation set group indicates a topic area set family.

  In the present invention, a single sentence is extracted from a document, a similarity between single sentences is obtained, a similar single sentence connected set group is extracted from the similarity between single sentences and the appearance position information of the single sentence in the document, and the extracted similar short sentence connected set group is also obtained. Document ranking method and document which can rank documents according to criteria related to the amount and density of document topics by calculating a score indicating the degree of association between the documents and ranking the documents based on the calculated score An object is to provide a ranking device. In addition, by using the ranking method described above for similar search results, a document search method and a document search device are provided in which search results are ranked according to criteria related to the amount and density of topics included in the document. The purpose is to do.

To achieve the above object, the present invention according to claim 1 includes a document input step for inputting a document, a single sentence extraction step for extracting a single sentence from the document, and a similarity between the single sentences extracted by the single sentence extraction step. Calculating a similarity between single sentences, a similar single sentence connected set group extracting step for extracting a similar single sentence connected set group from the similarity relation of the single sentence and appearance position information in the document of the single sentence, and the similar single sentence connected set The document ranking method includes a document score calculating step of calculating a score of a document based on the similar single sentence concatenated set group extracted by the group extracting step.
According to a second aspect of the present invention, the document ranking method according to the first aspect further includes a morpheme analysis step of extracting a morpheme from the document, and the simple sentence extraction step is analyzed in the morpheme analysis step. Extract simple sentences based on morphological information,
The similarity between single sentences is calculated based on the morpheme information analyzed in the single sentence similarity calculation step.

According to a third aspect of the present invention, in the document ranking method according to the second aspect, in the document score calculating step, the score is calculated based on the importance of the similar single sentence concatenation set included in the document and the ratio including the similar single sentence concatenation set. Is calculated.
A fourth aspect of the present invention includes the document ranking method according to the third aspect, a document search step for searching for similar documents, and a search result presentation step for presenting search results. The search result presented in the presenting step is characterized by a document search method ranked by the document ranking method.
The present invention according to claim 5 is a document input means for inputting a document, a single sentence extraction means for extracting a single sentence from the document, and a similarity between single sentences for calculating a similarity between single sentences extracted by the single sentence extraction means. Extracted by a calculating means, a similar single sentence connected set group extracting means for extracting a similar single sentence connected set group from the similarity relation of the single sentence and the appearance position information in the document of the single sentence, and the similar single sentence connected set group extracting means A document ranking apparatus comprising: a document score calculating unit that calculates a score of a document based on a group of similar single sentence connected sets.

A sixth aspect of the present invention is the document ranking apparatus according to the fifth aspect, further comprising a morpheme analyzing unit that extracts a morpheme from the document, wherein the simple sentence extracting unit analyzes the morpheme analyzed by the morpheme analyzing unit. A single sentence is extracted based on the information, and a single sentence similarity is calculated based on morpheme information analyzed by the single sentence similarity calculation means.
According to a seventh aspect of the present invention, in the document ranking apparatus according to the sixth aspect, the document score calculating means scores based on the importance of the similar single sentence concatenation set included in the document and the ratio including the similar single sentence concatenation set. Is calculated.
The invention according to claim 8 is the document ranking apparatus according to claim 7, comprising a document information database, an identifier of a document input by the document input means, and a document extracted by the morpheme analysis means Morphological analysis results, single sentence information of the document extracted by the single sentence extraction means, similarity between single sentences calculated by the similarity calculation means between single sentences, similar single sentence concatenated sets extracted by the similar single sentence connected set group extraction means The document score calculated by the group and the document score calculating means is stored in the document database in an appropriate format.

The present invention described in claim 9 comprises: the document ranking apparatus according to claim 8; document search means for searching for similar documents; and search result presentation means for presenting the search results. The search results presented by the presenting means are ranked by the document ranking device.
A tenth aspect of the present invention is a recording medium on which a program for executing the document ranking method according to any one of the first to third aspects is recorded in a computer-readable format.
The present invention described in claim 11 is a recording medium in which a program for executing the document search method described in claim 4 is recorded in a computer-readable format.

ADVANTAGE OF THE INVENTION According to this invention, the ranking method which can rank a document by the reference | standard relevant to the quantity and density of the topic of a document can be provided.
Further, by adopting the ranking method described above for similar document search results, a similar document search method is provided in which the search results are ranked according to criteria related to the amount and density of topics included in the document. it can.

Hereinafter, embodiments of the present invention will be described with reference to the drawings.
FIG. 2 is a configuration example of an information extraction apparatus according to an embodiment of the present invention.
The information extraction apparatus shown in FIG. 2 is constituted by a computer, and is a keyboard 2 as an input means for registering a document, a communication means for receiving a signal from the outside and transmitting a signal from the information extraction apparatus of this embodiment. A communication I / O interface 3, a CPU 4 that centrally executes processing in the information extraction apparatus of the present embodiment, a memory (both a volatile RAM and a nonvolatile ROM can be assumed) 5, and a hard disk as storage means 6. A display 7 and a printer 8 are provided as output means. The communication I / O interface 3 can be a modem or a terminal adapter, and can receive data from a server connected to the intranet or the Internet 10 via a communication line. The CPU 4 executes the program according to the procedure recorded in the memory 5.

FIG. 3 is a flowchart showing document ranking processing executed by the information extraction apparatus of this embodiment. Note that the processing shown in FIG. 3 is realized by the CPU 4 shown in FIG. 2 executing a program according to the procedure recorded in the memory 5.
In this case, the CPU 4 first executes a document input process for inputting a document in step S1. Next, in step S2, a morpheme analysis process for extracting morphemes from the document using the document database 11 is executed, and in step S3, a simple sentence extraction process for extracting simple sentences from the document is executed. Next, a single sentence similarity calculation process for calculating the similarity between the single sentences extracted by the single sentence extraction process in step S4 is executed, and in the subsequent step S5, the single database similarity relation and the single sentence in the single sentence document are used. A similar single sentence concatenated set group extraction process for extracting a similar single sentence concatenated set group from the appearance position information is executed. Thereafter, the inter-document score calculation process for calculating the score of the document based on the similar single sentence concatenated set extracted in step S6 is executed to finish the process.

FIG. 4 is a flowchart showing document search processing executed by the information extraction apparatus of this embodiment. Note that the processing shown in FIG. 4 is realized by the CPU 4 shown in FIG. 2 executing a program according to the procedure recorded in the memory 5.
In this case, the CPU 4 executes a document search process for searching for a similar document in step S11, and in the subsequent step S12, executes the document ranking process by the document ranking method as shown in FIG. The presentation process is executed in the result presentation process. In this case, the search results presented by the search presentation process are ranked by applying the document ranking method shown in FIG. 3 to the search result documents.

Hereinafter, each process described above will be described in detail.
<Document input processing>
In this embodiment, a document is defined as a character string determined as one unit by a user or an application. Here, it is assumed that each of document 1 to document 4 in FIG. 1 is a document, and these document data are input in an appropriate format.
A unique identification number is given to each input document. That is, numbers 1 to 4 of document data from document 1 to document 4 are given and recorded in the document information database.
The document information database may be constructed on an auxiliary storage device such as the hard disk 6 shown in FIG. 2 or may be constructed on a main memory such as the memory 5.

<Morphological analysis>
In the morpheme analysis process (document analysis process) in step S2, the input document is subjected to a morpheme analysis process to extract a morpheme string from the document. In this embodiment, since a Japanese document is used as an example, an operation example of Japanese morphological analysis processing is shown. However, the document may be in English or another foreign language, and in that case, the corresponding morphological analysis is performed. A system may be used.
FIG. 5 shows a result of applying morphological analysis to a part of the document with document identifier 1 (document 1), “Prime Minister Junichiro Koizumi meets with the LDP secretary-general at the Prime Minister's office on the morning of 25th”. In the present invention, no special morphological analysis system is required, and any morpheme and part-of-speech information may be used. For example, a tea bowl (http://chasen.naist.jp/hiki/ChaSen/) is well known as a Japanese morphological analysis system.

In FIG. 5, each line corresponds to each morpheme, and description, part-of-speech information, and an identifier are described as morpheme information.
In the present embodiment, the morpheme parts of speech are generally classified into those that are generally independent parts of speech and those that are attached parts of speech. In addition, self-supporting part-of-speech is the symbol “self” if it is a verbal part of speech such as a noun or unregistered word, the symbol “self-use” if it is a part-of-speech part of speech such as a verb or adjective verb. Is an attached word, except that the symbol “punctuation” is assigned to the punctuation and the symbol “reading” is assigned to the punctuation.
As the morpheme identifier, different identifiers are given when the morpheme notation and the part-of-speech information are different, but an identifier provided by the morpheme analysis system may be used for simplicity.
Although not explicitly shown, the morphological analysis is applied to the remaining text of the document 1 and other documents, and the analysis result is recorded in the document information database in an appropriate format.

As an example of data generated by the morpheme analysis processing, FIG. 6 shows a document information table, FIG. 7 shows a morpheme list table of document identifier 1, and FIG. 8 shows an example of a morpheme information table.
The document information table shown in FIG. 6 includes a document identifier arranged in a document, a morpheme list identifier of a morpheme list table corresponding to the document, and a single sentence list identifier of a single sentence list table corresponding to the document. In the present embodiment, numerical values are used as document identifiers, morpheme list identifiers, and simple sentence list identifiers, and the same values are arranged. However, the identifiers may be different unique numerical values or unique character information.
The morpheme list table shown in FIG. 7 is composed of all morpheme identifiers constituting individual documents and is listed in the order of appearance. A document can be reproduced by expanding the morpheme identifiers in the morpheme list in ascending order with reference to the morpheme information table shown in FIG.
Therefore, if this data is held, it is not necessary to store the original document data in the document information database. Further, by obtaining the frequency of the morpheme list identifier, it is possible to easily obtain the morpheme frequency information in the document.

The morpheme information table shown in FIG. 8 includes morpheme identifiers, notation, and part-of-speech information extracted from a document, and there is at most one morpheme entry having the same notation and part-of-speech information. The morpheme information table is shared from all morpheme identifier list tables.
In this embodiment, it is assumed that analysis results of all documents are recorded in the document information database in the table format shown in FIGS.

なお、式１において“［］”はクラスを、“＾”はクラス文字の否定を、“＋”は１つ以上の連続を、また“｜”は選択を夫々示している。（なお、正規表現については“詳説 正規表現 第２版”［ＩＳＢＮ４−８７３１１−１３０−７］等を参照すれば良い。 <Single sentence extraction processing>
In the single sentence extraction process in step S3, a single sentence is extracted from the input document. In this embodiment, an example of an operation for determining a range of a single sentence based on a rule for a morpheme string of a document is shown. However, even if a range of a single sentence is obtained using a rule that directly acts on a document character string without performing morpheme analysis. Good. In order to determine the range of a single sentence, the regular expression rule regarding the morpheme part-of-speech described in (Formula 1) is used.
(Formula 1)

In Equation 1, “[]” indicates a class, “^” indicates negation of a class character, “+” indicates one or more sequences, and “|” indicates selection. (Regarding regular expressions, “Detailed Regular Expressions Second Edition” [ISBN4-87311-130-7] or the like may be referred to.

Equation 1 is a regular expression that matches a morpheme sequence of a part of speech whose part of speech is neither a punctuation nor a punctuation, followed by a morpheme sequence of self morpheme and a punctuation point of part of speech, or a morpheme sequence of which the part of speech is a morpheme of reading.
A simple sentence obtained by applying this rule to the morphological analysis result of document 1 is shown in FIG. Two simple sentences are extracted from the document 1, and a unique identifier is attached to each simple sentence. Note that the upper part of the simple sentence is morpheme notation, the lower part is morpheme part of speech, and each morpheme is blank separated for visibility.
Although not clearly shown, extraction of simple sentences is also performed in document 2 to document 4, and the result is shown in FIG. From document 1, two simple sentences of document identifiers 1 and 2, from document 2, four simple sentences of identifiers 3 to 6, from document 3, eight simple sentences of document identifiers 7 to 14, and from document 4 to document identifiers 15 to 24 Ten simple sentences are extracted. The single sentence information of the extracted document is stored in an appropriate format in the document information database.

As an example of data generated in the single sentence extraction process, FIG. 11 shows a single sentence end position list table of the document identifier 1.
Since simple sentences appear continuously in a document, simple sentences can be uniquely identified by the position information of the terminal sentence morphemes in the document. Therefore, the single sentence end position list is a list of index numbers (appearance positions) in the morpheme list table of the terminal morphemes of the single sentence in the order of appearance of the single sentences.
That is, in FIG. 8, the index number 8 in the list table of FIG. 7 of the punctuation point of document 1 and 38, which is the index number of the reading point of document 1, are not explicitly shown in FIG. . In the present embodiment, it is assumed that simple sentence extraction results of all documents are recorded in the document information database in the table format shown in FIG.

上記式２において、ｓ１とｓ２は、文書全体で固有の自立語品詞をもつ形態素数と同一の次元をもつ、夫々単文１と単文２の形態素出現頻度ベクトルであり、・はベクトルの内積を、また｜｜はベクトルのノルムを夫々示す。
なお、本実施形態で採用している単文間類似度は文書間類似度において極めて一般的なものであり、文書間類似度に関しては、様々な先行研究がなされているため、単文を文書と見なすことでそれらの類似度を導入することができる。 <Simple sentence similarity calculation processing>
In the single sentence similarity calculation process in step S4, an arbitrary pair of similarities of each extracted single sentence is calculated. In the present embodiment, an example of operation is shown in which the similarity between simple sentences is calculated as a cosine between vectors shown in (Equation 2) using frequency information (frequency vectors) of morphemes where the part of speech of each single sentence is an independent word. Note that the frequency vector of simple sentences can be easily obtained by using the morpheme list table of FIG. 7 and the simple sentence end position list table of FIG.
(Formula 2)

In the above equation 2, s1 and s2 are morpheme appearance frequency vectors of single sentence 1 and single sentence 2, respectively, having the same dimension as the number of morphemes having unique independent part-of-speech in the entire document. || indicates the norm of the vector.
Note that the similarity between single sentences adopted in the present embodiment is very general in the similarity between documents, and regarding the similarity between documents, various previous studies have been made, so a single sentence is regarded as a document. The similarity can be introduced.

FIG. 12 shows the result of calculation by applying the morpheme frequency vector of each simple sentence shown in FIG. 10 to (Equation 2). The matrix in FIG. 12 is a single sentence identifier, the elements of the matrix are the cosine similarity between single sentences corresponding to the row and column identifiers, and the elements with similarity of 0.2 or more have a gray background. ing. In the present embodiment, since the similarity matrix is a target matrix, the lower triangular component and the similarity between the same single sentences are not displayed. For example, the similarity between simple sentence 1 and simple sentence 3 is 0.63.
The similarity between single sentences in FIG. 12 is also stored in an appropriate format in the document database. Note that the amount of data for the similarity between single sentences increases as the number of documents increases. Therefore, threshold processing is performed, all element values below the threshold are set to 0, and the data volume is reduced by adopting a sparse data structure. Is possible.

As an example of sparse format data, FIG. 13 shows a part of the effective row index list table and the column index-value list table of the similarity between single sentences in FIG.
Each value in the valid row index list table is an index number of a row having one or more elements having a value equal to or larger than the threshold value of the matrix in FIG. Each value in the column index-value list table is a column index number corresponding to a value equal to or greater than the threshold value of the row entered in the valid row index list table.
The correspondence between the row index of the effective index list table and the corresponding column index-value list table is not explicitly shown here, but if the column index-value list table itself is listed, what is an effective index list table? One-to-one correspondence can be easily made, and reference information to the column index-value list table corresponding to each element of the effective index list table may be provided.
In the present embodiment, it is assumed that the calculation result of the similarity between all single sentences is recorded in the document information database in the table format shown in FIG.

<Similar simple sentence connected set group extraction processing>
In the similar single sentence concatenated set extraction process shown in step S5, based on the extracted single sentence inter-sentence similarity and the appearance position in the document, the single sentence set that is adjacent in the document and the similarity between the single sentences is equal to or greater than a certain value. Are all extracted. In the present embodiment, an operation example up to the processing for calculating the similarity between single sentences is inherited, and an operation for extracting a group of similar single sentence connected sets based on the similarity matrix between single sentences shown in FIG. 12 is shown.
In the inter-sentence similarity matrix of FIG. 12, FIG. 14 shows that the similarity is 1 or more when the similarity is 0.2 or more, and 0 when the similarity is 0.2 or less. In FIG. 14, when the element value is 1, the background is gray, and when the element value is 0, the color is white, and a line is drawn for each document boundary.

In the present embodiment, a single sentence is extracted by extracting a connected component of a graph generated by regarding a set having a single sentence pair in an adjacent document as one node and a similarity between the single sentence pairs as an edge. A pair-similar graph is generated, and a similar single sentence concatenated set group is generated by fusing nodes and combining connected components based on the adjacent relationship in the document of the node pair of each connected component. The processing flow is shown in FIG.
In this case, first, in step S21, the CPU 4 generates a set including two adjacent short sentences in the same document as elements. Next, the set generated in step S22 is regarded as a node, and if one or more similar relations exist in all the simple sentences constituting two nodes included in different documents, etching is performed between the nodes to generate a graph. To do. In subsequent step S23, it is determined whether or not a graph is generated. If an affirmative result is obtained in step S23 ("Yes" in S23), the process proceeds to step S24, and after extracting the connected components of the generated graph, in any two node pairs in different connected components in the subsequent step S25 If none of the product sets of the corresponding nodes are empty, the graphs are connected using the ring set of the corresponding nodes as a new node. Finally, each connected component generated in step S26 is extracted as a similar short sentence concatenation set to finish the process. If a negative result is obtained in step S23 ("No" in S23), the process is finished as it is.

More specifically, for example, {1, 2} is one node in document 1, and {3, 4}, {4, 5}, etc. are nodes in document 2.
Next, an edge is drawn between each node from FIG. The condition for drawing an edge is that at least one simple sentence between the single sentences constituting the node has a similarity equal to or higher than a threshold (in this embodiment, 0 and 2; in FIG. 14, the element value 1 is 1). Yes) For example, edges can be drawn on the nodes {1, 2} and {3, 4}, the nodes {1, 2} and the nodes {7, 8}.
As a result, three connected components (graphs) can be extracted from FIG. 14, and the results are shown in FIG.
Next, node fusion and connection component combination are performed based on the adjacent relationship in the document of the extracted connected component node pair.

In the present embodiment, the condition of the fusion of nodes and the combination of connected components is as follows: “If any two node pairs in different connected components are not empty, the union of the corresponding nodes Let's connect the graphs with the new node as "."
In the graph of FIG. 16, since the {7, 8}-{15, 16} component of the graph 1 and the {8, 9}-{16, 17} component of the graph 2 are the note pairs that satisfy the condition, {7, 8} and {8, 9}, and the nodes {15, 16} and {16, 17} are merged, respectively, and the new nodes {7, 8, 9} and {15, 16, 17} Combine graph 2.
As a result, the graph 1 and the graph 2 in FIG. 14 are combined (graph 1 ′), and the result is shown in FIG. Each graph of FIG. 17 becomes a similar single sentence connected set.

In the present embodiment, the initial node is a single sentence that is continuous in two documents. However, the initial node is a single sentence set generated from a window function centered on one node, or a combination of extracted connected components. It is also possible to use a more complicated mechanism such as setting a threshold for the node fusion condition and the union size of the node.
The extracted similar single sentence concatenated sets are recorded in a document information database in an appropriate format.
As an example of similar single sentence connected set group data, FIG. 18 shows a similar single sentence connected set group list table in which the information of the graphs 1 ′ and 2 is described.

The node identifier is an identifier to be given to each node of the graph, the single sentence identifier list is a set of identifiers of single sentences constituting the node, and the related node identifier list is another node related to the node (with edges connected). It is a list. For example, the first line is of the node {1, 2}, the identifier is 1, the simple sentences constituting the node are document identifiers 1 and 2, and the nodes related to this node are the nodes of identifiers 2, 3, 4 It is shown that. The single sentence identifier list and the related node identifier list may have a separate list table as shown in FIG. 11 and the like, and this element may take the form of describing reference information to the table.
In the present embodiment, it is assumed that the calculation result of the similar single sentence concatenated set group is recorded in the document information database in the table format shown in FIG.

式３を基に文書１から文書４のスコアを算出すると、夫々０．６６、０．６６、２、２となり、文書３、文書４、文書１、文書２の順にランキングされる。 <Document score calculation processing>
In the document score calculation process shown in step S6 of FIG. 2, the document score is calculated based on the extracted information of the similar single sentence concatenation set. In the present embodiment, when the operation example up to the similar single sentence connected set group is inherited and the similar single sentence connected set group shown in FIG. 17 is given, the importance of the similar single sentence connected set included in the document, the similar single sentence connected set, and The operation of calculating the document score based on the ratio of simple sentences included in the set will be described.
First, as a score criterion, consider that a document having many common topics and detailed information obtains a high score. If one graph in FIG. 17 is regarded as one common topic, a document including as many nodes having a large number of elements as possible should have a good score. For example, the score may be formulated as shown in Equation 3.
(Formula 3)

When the scores of the document 1 to the document 4 are calculated based on the expression 3, they are 0.66, 0.66, 2, and 2, and are ranked in the order of the document 3, the document 4, the document 1, and the document 2.

式４を基に文書１から文書４のスコアを算出すると、夫々１、０．５、０．６６、０．２となり、文書１、文書３、文書２、文書４の順にランキングされる。
なお、本実施形態では上記２つの基準に基づく動作のみを例示しているが、類似単文連接集合群の情報をもとにより複雑な基準をもとにスコアを算出してもよい。 In addition, as a criterion for scores, considering that a document that contains many common topics but not other common topics as much as possible gets a good score, it contains many nodes that belong to different graphs and does not belong to any nodes. What is necessary is just to take a good score for a document without a single sentence. For example, the score may be formulated as shown in Equation 4.
(Formula 4)

When the scores of the document 4 from the document 1 are calculated based on the expression 4, they are 1, 0.5, 0.66, and 0.2, respectively, and are ranked in the order of the document 1, the document 3, the document 2, and the document 4.
In the present embodiment, only the operation based on the above two criteria is illustrated, but the score may be calculated based on a complex criterion based on the information of the similar single sentence connected set group.

The calculated document score is recorded in the document information database.
FIG. 19 shows a document score list table in which document scores calculated based on the two score criteria are shown as an example of document score data.
The document score list table is composed of a document identifier, a score criterion 1, and a score criterion 2. The score criterion 1 is a document score based on the above-mentioned “getting a high score for documents having many common topics and including details”. The value / score criterion 2 is a score value of a document on the basis of “obtaining a good score for a document that includes many common topics but does not include as much as possible other than common topics”.
For example, the first line is data of the document 1, the identification number is 1, the score on the score criterion 1 is 0.66, and the score on the score criterion 2 is 1.
In this embodiment, the ranking based on the score value of the document data is not clearly shown, but it can be easily obtained by sorting the score value.
In the present embodiment, it is assumed that the calculation result of the similar single sentence connected set group is recorded in the document information database in the table format shown in FIG.
Next, CPU4 performs a result presentation process in step S13.

<Document search processing>
In the document search process shown in step S7, any document search process can be used as long as the document search can be appropriately performed. For example, the Google search result described above may be applied.
For example, when a URL of a document is acquired as a search result acquired in the document search process, a known HTML document acquisition tool such as wget (for example, see http://wget.sunsite.dk/) is used. A tool for acquiring HTML documents and converting known HTML documents such as html2text (for example, see http://search.cpan.org/~awrigley/html2text-0.003/html2text.pl) into plain text By using it, the acquired HTML document is converted into plain text. Then, the plain text of the acquired search result is registered in the document database.

<Result presentation process>
For example, FIG. 20 shows a display example of ranking of the documents 1 to 4.
In FIG. 20, ranking (column direction) from document 1 to document 4 (row direction) is shown, and “matching query word” is a query word: “postal privatization and summary” in each document. The ranking based on the matching frequency, “Topic abundance” is the ranking based on the score criterion 1, and “Different contents” is the ranking based on the score criterion 2, and the ranking value increases from the center to the left.
In the present embodiment, the ranking result of “query word match” is calculated by using a full-text search system: Namazu (http://www.namazu.org) not explicitly shown.
For example, “query word match” has the same ranking value from document 1 to document 4, but “topic richness” ranks in the order of document 3, document 4, document 1, document 2 as described above. . Therefore, according to FIG. 20, it can be said that the user can list rankings based on a multifaceted standard and can support browsing of a desired document.

21 to 23 show display examples when the document 3 is selected based on the three ranking criteria in FIG.
FIG. 21 shows the document 3 based on the “matching inquiry” criterion, and a portion matching the query word is highlighted as an important part in this criterion. FIG. 22 shows the document 3 based on the “buzz abundance” criterion. As the important part in this criterion, that is, the common topic portion in the retrieved document group, the nodes constituting the similar single sentence concatenated set group are shown. The included single sentence is highlighted. FIG. 23 shows a document 3 based on the “different contents” criterion. As an important part in this criterion, that is, a part other than the common topic in the retrieved document group, the nodes constituting the similar single sentence connected set group are shown. Single sentences that are not included are highlighted. Thereby, the user can also browse the important part in the document in each standard.

In FIG. 22, the information of the similar single sentence concatenated set group is used, so that the reference information to other documents is displayed in the same manner, thereby enabling more analytical browsing.
As a result, according to the present invention, by providing a ranking method that can rank documents according to criteria related to the amount and density of document topics, a user can browse and analyze a group of documents such as search results from a multifaceted viewpoint. Is possible.
Note that a computer-readable recording medium such as a floppy disk or an optical disk on which a program for causing a computer to execute each function of the information extraction apparatus described above is recorded can be created. By mounting the recording medium on a floppy disk device such as a general-purpose personal computer or an optical disk device such as a CD-ROM reader, reading the program recorded there and installing it in a recording device such as an internal hard disk, It is possible to provide a function as an information extraction device according to the present invention.

It is the figure which showed an example of the result searched by Google. It is the figure which showed the structural example of the computer which implement | achieves the information extraction apparatus which is one Embodiment of this invention. It is the flowchart which showed the document ranking process which the information extraction device of this embodiment performs. It is the flowchart which showed the other process which the information extraction apparatus of this embodiment performs. It is the figure which showed an example of the result of applying a morphological analysis. It is the figure which showed an example of the document information table. It is the figure which showed an example of the morpheme list table of the document identifier 1. It is the figure which showed an example of the morpheme information table. FIG. 10 is a diagram illustrating a simple sentence obtained by applying a rule to a morphological analysis result of document 1. It is the figure which showed the result when extracting a single sentence also in the document 2 to the document 4. FIG. It is the figure which showed the single sentence end position list table of the document identifier. It is the figure which showed the result computed by applying the morpheme frequency vector which does not specify each simple sentence shown in FIG. 10 to (Formula 2). It is the figure which showed the one part effective row index list table and column index-value list table of the similarity between single sentences of FIG. In the inter-sentence similarity matrix of FIG. 12, FIG. 13 is a diagram in which similarity is 0.2 or more and 1 is 0.2 or less. It is the figure which showed the processing flow which produces | generates a similar single sentence connection set group. It is the figure which showed the extraction result of three connected components. FIG. 4 is a diagram showing a result of combining graph 1 and graph 2; It is the figure which showed the similar single sentence connection set group list table which described the information of the graph 1 'and the graph 2. FIG. It is the figure which showed the document score list table. FIG. 6 is a diagram illustrating a display example of rankings of documents 1 to 4; FIG. 10 is a diagram illustrating a display example when a document 3 is selected. FIG. 10 is a diagram illustrating a display example when a document 3 is selected. FIG. 10 is a diagram illustrating a display example when a document 3 is selected.

Explanation of symbols

  2 ... Keyboard, 3 ... Communication I / O interface, 4 ... CPU, 5 ... Memory, 6 ... Hard disk, 7 ... Display, 8 ... Printer, 10 ... Internet, 11 ... Document database

Claims (11)

A document input step for entering a document;
A single sentence extraction step of extracting a single sentence from the document;
A single sentence similarity calculation step for calculating a similarity between single sentences extracted by the single sentence extraction step;
A similar single sentence concatenated set group extracting step for extracting a similar single sentence concatenated set group from the similarity relation of the single sentence and the appearance position information in the document of the single sentence;
A document score calculating step for calculating a score of a document based on the similar single sentence connected set group extracted by the similar single sentence connected set group extracting step;
A document ranking method characterized by comprising: The document ranking method according to claim 1,
Further comprising a morphological analysis step of extracting morphemes from the document;
In the simple sentence extraction step, simple sentences are extracted based on the morpheme information analyzed in the morpheme analysis step,
A document ranking method characterized in that the similarity between single sentences is calculated based on the morpheme information analyzed in the single sentence similarity calculation step. The document ranking method according to claim 2,
The document score calculating step calculates a score based on the importance of a similar single sentence concatenation set included in the document and a ratio including the similar single sentence concatenation set. A document ranking method according to claim 3,
A document search step for searching for similar documents;
A search result presentation step for presenting a search result,
The search result presented in the search result presentation step is ranked according to the document ranking method. A document input means for inputting a document;
Simple sentence extraction means for extracting a simple sentence from the document;
A single sentence similarity calculating means for calculating a similarity between single sentences extracted by the single sentence extracting means;
Similar single sentence concatenated set extraction means for extracting similar single sentence concatenated sets from the single sentence similarity and the appearance position information in the single sentence document;
Document score calculating means for calculating a score of a document based on the similar single sentence connected set group extracted by the similar single sentence connected set group extracting means;
A document ranking apparatus comprising: The document ranking apparatus according to claim 5, wherein
Further comprising morpheme analysis means for extracting morphemes from the document;
The simple sentence extracting means extracts simple sentences based on the morpheme information analyzed by the morpheme analyzing means, and calculates the similarity between simple sentences based on the morpheme information analyzed by the simple sentence similarity calculating means. Feature document ranking device. The document ranking apparatus according to claim 6, wherein
The document ranking calculating device, wherein the document score calculating means calculates a score based on the importance of a similar single sentence concatenation set included in the document and a ratio including the similar single sentence concatenation set. The document ranking apparatus according to claim 7, wherein
It has a document information database,
Document identifier input by the document input unit, morphological analysis result of the document extracted by the morpheme analysis unit, single sentence information of the document extracted by the single sentence extraction unit, calculated by the similarity between single sentences calculation unit Storing the single-sentence similarity between the single sentences, the similar single-sentence connected set group extracted by the similar single-sentence connected set group extracting unit, and the document score calculated by the document score calculating unit in an appropriate format in the document database. Document ranking device characterized by this. A document ranking device according to claim 8,
A document search means for searching for similar documents, and a search result presentation means for presenting the search results, wherein the search results presented by the search result presentation means are ranked by the document ranking device. Feature document retrieval device.   A recording medium in which a program for executing the document ranking method according to any one of claims 1 to 3 is recorded in a computer-readable format.   A recording medium in which a program for executing the document search method according to claim 4 is recorded in a computer-readable format.

Images