JP2000235574A - Document processing device - Google Patents

Abstract

(57) [Summary] [Problem] A document is divided for each topic from an electronic document such as a newspaper article in which topics are mixed. SOLUTION: The digitized document is divided into paragraphs, the relevance between paragraphs is obtained, and the relevance is displayed in, for example, a matrix, and a triangle surrounded by an arbitrary row, an arbitrary column, and a diagonal component is displayed. As a region, a total value of the degree of relevance in this triangular region is obtained, and a division point is obtained from the total value. For example, a total value of relevance in a triangular area and a total value of relevance in a rectangular area having a column of this triangle as one side and an arbitrary row as one side are obtained. Is calculated, and the document is divided based on the value of the ratio.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a document processing apparatus, and more particularly, to a document processing apparatus for dividing a document for each semantic block. The present invention relates to a suitable document division to be applied to the case.

[0002]

2. Description of the Related Art In recent years, the number of opportunities for creating documents using personal computers and the rapid spread of the Internet have caused a flood of electronic documents around the user. It is almost impossible to browse all such electronic documents and search for a document that provides valid information due to time limitations.

[0003] In order to solve such a problem, there is a method of searching for a necessary document by a full-text search or the like. However, if the searched document is not read to some extent, the searched document does not have the intended information. It is difficult to judge whether or not to offer.

On the other hand, as a means for solving such a situation, there is a technique for summarizing documents. If the summary of the document is displayed as a search result of the full-text search, it is not necessary to open the searched document and examine the contents thereof, so that the efficiency of the search is dramatically improved.

However, in order to present an abstract from a newspaper article or the like in which various topics are mixed on one page, it is necessary to provide an abstract for each topic.

[0006]

SUMMARY OF THE INVENTION The present invention has been made in view of the above situation, and has as its object to divide an electronic document into meaning blocks.

[0007]

According to the first aspect of the present invention, an electronic document is divided into paragraphs, and the degree of relevance between paragraphs is calculated based on keywords extracted from the paragraphs, and the number of paragraphs is calculated. In the square matrix to be a dimension, the above-described degree of relevance is put into each component of the one-sided area with the diagonal component of the square matrix as a boundary,
In the one-sided area containing the relevance, a total value of relevance in a triangular area surrounded by an arbitrary row (or column), an arbitrary column (or row), and a diagonal component is calculated. ,
The document dividing point is obtained based on the total value of the relevance.

According to a second aspect of the present invention, in the first aspect of the present invention, a total value in the triangular area and a rectangular area corresponding to a column (or row) of the triangular area and excluding the triangular area are included. The document division point is obtained from the relationship between the total values of the degrees of relevance.

According to a third aspect of the present invention, in the invention described in the second aspect, an extreme value is obtained from a ratio of a total value in the triangular area to a total value of relevance in the rectangular area. This is to obtain a document division point.

According to a fourth aspect of the present invention, in the invention described in any one of the first to third aspects, a total of the relevance of a row (or a column) in an adjacent paragraph is obtained, and each total is compared. It is designed to find a turning point.

According to a fifth aspect of the present invention, in the invention according to any one of the first to third aspects, when a total value of relevance of a row (or column) at the division point is equal to or less than a predetermined value, the row (or Or column) as an isolated paragraph.

[0012]

DESCRIPTION OF THE PREFERRED EMBODIMENTS As described above, the present invention makes it possible to provide a summary for each topic even in a document in which a plurality of topics are mixed, such as a newspaper article. Hereinafter, an example in which a document having the text shown in Table 1 is divided into a plurality of semantic blocks in a document processing apparatus having a document summarizing function will be described.

The present invention divides a document into a group of related meanings (semantic block extraction). Extraction of a semantic block described below is a pre-process of extracting an important sentence of a document. This means that the text is divided at the breaks in the topic. For example, this process is effective when extracting important sentences from one page of a newspaper, which is a collection of sentences of various contents. Extract the meaning block
It is better to extract one sentence from the surface and extract the important sentence therefrom than to extract the important sentence directly from a plurality of articles. For example, a digitized document input as a text example is divided into paragraphs as shown in Table 1.

[0014]

[Table 1]

A semantic block is extracted according to the following procedure. 1. Creation of paragraph relevance matrix (1.1). The input document is analyzed for each paragraph, and keywords are extracted. Keywords are basically nouns, and the higher the frequency of appearance, the higher the keyword characteristics. Also, the appearance frequency is calculated in consideration of the matching of the partial character strings between the keywords.

(1.2). A two-dimensional array (square matrix) using a paragraph number as an index is prepared, the degree of overlap between the paragraph and the keyword of the paragraph is calculated, and the calculated degree is substituted into an array element (component). For example, a paragraph relevance matrix for the text example in Table 1 is as shown in Table 2.

[0017]

[Table 2]

FIG. 1 is a schematic diagram for explaining a paragraph-related matrix according to the present invention. A triangular area in the upper half of a two-dimensional array (square matrix) is used for semantic block extraction, and no diagonal components are used. In other words, the calculation of the relevance R (n, m) between the paragraph number (n) and the paragraph number (m) does not consider the arrangement of the paragraph numbers. That is, for the following reasons (a) and (b), the values of R (n, m) and R (m, n) are considered to be the same. (A) Do not perform unnecessary calculations. R (n, m) and R (m,
If the value of n) is different, the lower half of the paragraph relevance matrix must be newly calculated. (B) In extracting a semantic block, R (n, m) and R (n, m)
There is no rationale to separate the value of (m, n). R (n,
m) is, from another perspective, a paragraph n in the semantic space.
And a kind of distance of paragraph m. Therefore, the distance measured from the paragraph n to the paragraph m should be the same as the distance measured from the paragraph m to the paragraph n, and if not defined, a problem occurs in the semantic block extraction process.

2. Triangles (excluding diagonal components) are extracted from the paragraph relevance matrix. Triangles represent semantic blocks. In other words, cutting out a triangle means extracting a meaning block. In the paragraph relevance matrix of Table 2, it seems that there is no triangle which is a semantic block due to the presence of keyword noise. However, according to the method described below, a triangle can be cut out.

(2.1). Calculation of area ratio In the paragraph relevance matrix (n × n), as described above, in one side region (triangular region), the first row, the arbitrary column (i column), and the triangle within the diagonal line The sum of the relevance is D _i (the sum of the relevance in the area of the triangle), and the sum of the relevance in the rectangular area corresponding to the row of the triangle and excluding the triangle is R _i (the sum of the relevance in the area of the rectangle). ). For all paragraph numbers i on the matrix, _Di
And R _i . As a result, D ₁ , D ₂ ,..., D _n ,
R ₁ , R ₂ ,..., R _n are obtained.

(2.2). Finding the minimum point R _i / D _i is calculated for all D _i and R _i , and equation (1)
Find points that satisfy. R _i / D _i ≧ R _{i + 1} / D _{i + 1} <R _{i + 2} / D _{i + 2} (1) At this time, the ( _{i +} 1) th paragraph is a division candidate point. In addition,
If the ratio is reversed, the extremum which is a division candidate point becomes the maximum point.

(2.3). Topic conversion coefficient Equation (2) is calculated for paragraph i obtained by equation (1). (R _{i + 2} / D _{i + 2} ) / (R _{i + 1} / D _{i + 1} ) Expression (2) This value represents the degree of the change of the topic of the semantic block. This value will be referred to as a topic conversion coefficient.
If the topic conversion coefficient is sufficiently close to 1, it means that the two semantic blocks formed by the division points obtained by the equation (1) are based on topics similar to each other.

As the topic conversion coefficient becomes farther from 1, the two semantic blocks are based on different topics. Thus, if the topic conversion factor is clearly greater than 1, paragraph i + 1 is a break in meaning. That is, the semantic block whose paragraph number is 1 to i + 1 and the paragraph number is i + 2
It is divided into n meaning blocks.

(2.4). The topic conversion coefficient means the slope (differential coefficient) of the curve at the minimum point of the curves in FIGS. The value of R _i is suddenly increased, the slope of the curve of the minimum point when the value is suddenly decreased in D _i is increased conversely. In other words, it means that the content of the topic is greatly different from the minimum point P. If the change of the topic is ambiguous (a sentence or a novel whose amendment is ambiguous), the topic conversion coefficient becomes close to 1 even if there is a minimum point, so that a triangle as a semantic block cannot be cut out.

In such a case, an appropriate meaning block can be extracted by appropriately determining the value of the topic conversion coefficient. As a result of the experiment, good results could be obtained even if the topic conversion coefficient was set to 1.1. By introducing the topic conversion coefficient, it is possible to prevent the extraction of an incorrect semantic block.

(2.5). Determination of Isolated Paragraph in Semantic Block Extraction When the paragraph i is at the head of the semantic block and the total value of the components of the rectangular area (R _i ) is equal to or less than a predetermined value, for example, 0,
It becomes an isolated paragraph. As can be seen from the paragraph association matrix shown in Table 2, this paragraph is not associated with any paragraph. Due to the nature of this semantic block extraction logic, isolated paragraphs (paragraphs that are isolated without being related to any paragraph)
It always comes at the beginning of the semantic block (see "Theoretical background to semantic block extraction method" described later and "Algorithm implementation" in Table 3). In such a case, assuming that the starting paragraph number of the semantic block is S and the ending paragraph number is E, [S, E] → [S, S] + [S + 1, E]... Is divided and processed.

This isolated paragraph has a meaning block [S + 1,
E], but it may be related to the previous paragraph, so if you want an exact result, you need to check its connectivity. However, since an isolated paragraph is unlikely to include an important sentence, it can be ignored when extracting a semantic block as preprocessing of the important sentence extraction processing.

3. Theoretical background to the method of extracting a triangle that is a semantic block (3.1). Grounds for Triangulating Triangles Based on the Area Ratio of Triangles and Rectangles In the paragraph relevance matrix of Table 2, it is clear that a group of paragraphs having a high degree of relevance constitutes a triangle on the paragraph relevance matrix. However, in practice, even paragraphs that are not related to each other may have similar keywords, and thus appear as noise on the paragraph relevance matrix.

Such noise appears on a rectangle. Table 1
In the text example, paragraphs 1 to 5 form one semantic block, and paragraphs 6 to 10 form another semantic block. However, in paragraphs 1 and 6, keywords such as "Washington", "US government", and "Federal government" appear in common and seem to be related to each other. In this case, such keywords are noise and appear in rectangles that are off-diagonal components. That is the value of 9 which is the element (component) of (1, 6) in Table 2. In order to remove such noise and cut out a triangle, attention should be paid to the area ratio between the triangle and the rectangle.

Assuming that there is no noise, the value of (area of the rectangle) 三角形 (area of the triangle) becomes infinite at the beginning of the paragraph, as can be easily understood from the paragraph relevance matrix shown in FIG. (D area is 0), 0 at the end of the paragraph
(R area is 0).

FIG. 2 shows the value of (the area of a rectangle) ÷ (the area of a triangle) as a conceptual curve (of course, actually becomes a discrete curve). Is divided into two semantic blocks). In FIG. 2, the value of the minimum point P is 0 (the value of R is 0).
And the value in paragraph number 1 is infinite, and the value in paragraph number n is 0.

FIG. 3 shows the case where there is noise. In this case, the value of the minimum point P at the division point of the meaning block increases in the Y-axis direction by the amount of the noise. However, the value in paragraph number 1 is infinite, and the value in paragraph n remains 0. It should be noted that the shape of the curve is similar to FIGS. 2 and 3 regardless of whether there is noise. That is, the value of the area ratio starts from infinity,
It gradually decreases to 0 while having the minimum point and the maximum point alternately.

(3.2). Reason why the minimum point becomes a division point From the paragraph relation matrix of Table 2, the following relation is established in the semantic block (triangle). R ₁ ≤R ₂ ≤ ... <R _k-1 <R _k > R _{k + 1} >...> R _m (R _m → 0) Equation (4) D ₁ ≦ D ₂ ≦ ... <D _m Equation (5) It is assumed that there is no division point between paragraph numbers 1 to m. At this time, in the semantic block, R _i / D _i ≧ R _{i + 1} / D _{i + 1} ... Equation (7) holds under the fixed condition of {i} [l, m]... (This explanation is not a mathematical proof, so it lacks rigor).

[0034]

(Equation 1)

## EQU1 ## In the paragraph relevance matrix, X and Y indicate a component in the Y direction with a column of i and a component in the X direction with a row i, respectively, as shown in FIG. (Y-
When X) is 0 or more, the sign of Expression (8) is positive.
When (Y−X) is negative, D _i > (R _i · Y) / (X−Y)... Indicates the state of the elements (components) of the paragraph relevance matrix that satisfies Expression (9). When Expression (9) is satisfied, the sign of Expression (8) becomes negative, and i becomes the minimum point. That is, when there is an element (component) of the paragraph relevance matrix that satisfies Expression (9),
The division point exists in the semantic block assuming that there is no division point. In such cases, the following (a),
Let's consider the two parts (b).

(A). Y / (XY)> 1 That is,
X>Y> X / 2 if the above formula (9), when the coefficient is greater than 1 the R _i, since equation (9) is satisfied, the area of the D _i (weight: total value of relevance), the Area of R _i (weight: total value of relevance)
It can be said that it is larger. That is, the area (weight) of the triangle
Therefore, when the area (weight) of the rectangle is larger, Expression (9) holds.

If the value of Y is close to the value of X and the weight of the triangle is heavier than the surroundings, it is considered that the topic is unclearly developed in one semantic block that handles the same topic. In such a case, equation (8) becomes negative and i becomes the minimum point. The semantic blocks before and after the division at the minimum point are semantic blocks describing the same topic, and the topic conversion coefficient at this minimum point has a value quite close to 1.

(B). Y / (XY) ≦ 1 That is,
When 0 ≦ Y ≦ X / 2 When Y is 0, the paragraph i is an isolated paragraph. At this time, the sign of equation (8) becomes negative, and there is a minimum point. Further, as Y approaches X / 2, the situation approaches a. In summary, even in a semantic block that is assumed to have no division point, a division point occurs when an isolated paragraph exists or a topic unambiguously develops. However, as described above, such a situation can be remedied by introducing a topic conversion coefficient and processing an isolated paragraph.

4. Algorithm Implementation The implementation of the semantic block extraction algorithm is extremely simple, and the actual code is very short. An example is shown in Table 3 in pseudo code (however, the integration of semantic blocks and the isolated paragraph processing are omitted. ing). However, to speed up the calculation of D _i and R _i , the paragraph relevance matrix is not a two-dimensional array but has a completely separate data structure. In this pseudo code, one break in meaning is found from a given paragraph group, and the paragraph is divided into two meaning paragraph groups.
If no meaning break is found, the meaning block extraction process ends. If there is a meaning break, recursively call itself to search for a meaning break in the first paragraph group divided. Similarly, it is called recursively to search for a break in the meaning of a group of paragraphs after division.
Judgment condition of the break of the meaning is "triangulation method"
As described in the above.

[0040]

[Table 3]

[0041]

According to the present invention, it is possible to provide a summary for each topic even in a document including a plurality of topics such as newspaper articles. When extracting an important sentence from an article having a plurality of articles such as a newspaper article, the extraction of the relevant article after performing the semantic block extraction according to the present invention, and extracting the important sentence therefrom, Is better than extracting important sentences directly from Further, according to the present invention, even when two or more languages such as Japanese and English are mixed in the same document, it is possible to divide the document into portions described in Japanese. By introducing the topic conversion coefficient, it is possible to prevent erroneous semantic blocks from being extracted.

[Brief description of the drawings]

FIG. 1 is a schematic diagram for explaining a paragraph relevance matrix.

FIG. 2 is a diagram for explaining a relationship between a triangular area and a rectangular area.

FIG. 3 is a diagram illustrating a relationship between a triangular area and a rectangular area (when there is noise).

FIG. 4 is a diagram illustrating a paragraph relevance matrix.

Claims (5)

[Claims] An electronic document is divided into paragraphs, a relevancy between paragraphs is calculated based on keywords extracted from the paragraphs, and a square matrix having the paragraphs as a dimension is a diagonal of the square matrix. The relevance is put into each component of the one-sided area with the component as a boundary, and in the one-sided area where the relevance is put, an arbitrary row (or column), an arbitrary column (or row), and a diagonal A document processing apparatus comprising: obtaining a total value of relevance in a triangular region surrounded by components; and obtaining a document division point based on the total value of the relevance. 2. The document processing apparatus according to claim 1, wherein a total value in the triangular area and a degree of association in a rectangular area corresponding to a column (or row) of the triangular area and excluding the triangular area. A document division point obtained from a relationship with a total value of the document. 3. The document processing apparatus according to claim 2, wherein an extremum is obtained from a ratio of a total value in the triangular area to a total value of the relevance in the rectangular area. A document processing device for obtaining points. 4. The document processing apparatus according to claim 1, wherein a sum of relevance of a row (or a column) in an adjacent paragraph is obtained, and the sum is compared to obtain a topic turning point. A document processing apparatus characterized by determining 5. The document processing apparatus according to claim 1, wherein when the total value of the relevance of a row (or a column) at the division point is equal to or less than a predetermined value, the row (or the column). A document processing apparatus, wherein the document is an isolated paragraph.