JP2000148752A - Document structure recognition method and apparatus, and storage medium storing document structure recognition program - Google Patents

Abstract

(57) [Summary] [Problem] To focus on a specific character string pattern in a document and the length from the beginning to the end of a line including the pattern, and to determine the relationship between the length of the entire line and the length of the specific character string pattern. A document structure recognizing method and apparatus capable of analyzing the structure of a sentence including an optional bullet point that does not depend on the field, and a storage medium storing a document structure recognizing program are provided. An object of the present invention is to input a document to be recognized, perform pattern matching between the document and a previously stored bullet pattern on a line-by-line basis, and select bullet candidates that match the bullet pattern. For each line of the document, measure the length of the character string from the beginning of the line where the character is present to the end of the line where the character is present, and if the generated bullet points include blanks, calculate the length of the character string. And determining one bullet point candidate from the obtained bullet point candidates,
Blanks are removed from the determined bullet points to obtain bullet label and content information, and the determined bullet points are added with the label content information as tags and output.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and apparatus for recognizing a document structure and a storage medium storing a document structure recognizing program, and more particularly to a document of an electronic document transmitted via a network or read by an OCR. The present invention relates to a document structure recognition method and apparatus for recognizing a structure and a storage medium storing a document structure recognition program.

[0002]

2. Description of the Related Art In a conventional method of analyzing a document structure, when specifying a bullet point, a word or a symbol capable of representing a predetermined labeled bullet point is prepared and a search is performed on the document. Is determined as a bulleted list.

[0003]

However, in the above-described conventional method of searching for a document using words or symbols representing predetermined bullet points, it is necessary to prepare keywords depending on the field, There is a problem that it is not possible to determine that the item is a bullet when it does not match or when a space is included between characters.

The present invention has been made in view of the above points, and focuses on a specific character string pattern in a document and the length of a line including the pattern from the beginning to the end of the line. By considering the relationship between the lengths of the column patterns, a document structure recognition method and apparatus capable of analyzing the structure of a sentence including an arbitrary bullet point independent of a field, and a storage medium storing a document structure recognition program are provided. The purpose is to provide.

[0005]

FIG. 1 is a diagram for explaining the principle of the present invention. According to the present invention (claim 1), in a document structure recognition method for analyzing the structure of a document including an arbitrary bullet point, a document to be recognized is input (step 1), and the document and the document are stored in advance. Pattern matching is performed for each line with the bullet pattern, and a bullet candidate that matches the bullet pattern is generated (step 2), and the characters from the beginning of the line where the character exists to the end of the line where the character exists in one line of the document The length of the column is measured (step 3), and if the generated bullet points include spaces, one bullet point is obtained from the obtained bullet points using the length of the character string. A candidate is determined (step 4), blanks are removed from the determined list item, and information on the item label and content is obtained (step 5). The information on the label content is added to the determined list item. tag Granted and outputs to (Step 6).

According to the present invention (claim 2), as a pre-stored bullet pattern, a pattern matching a bullet containing or not including a blank is retained using the type of character. According to the present invention (claim 3), when generating an itemized list, a plurality of candidates are generated by performing pattern matching as much as possible on a character string pattern in which an input document is divided and written including spaces.

According to the present invention (claim 4), when measuring the length of a character string, the length of a character string including a blank from the beginning to the end of the line excluding the blank at the beginning of a line is measured for one line of the document. Measure in bytes. According to the present invention (claim 5), when there are a plurality of obtained bullet candidates, the line that matches the bullet pattern is equal to or indented at the beginning of the line that does not match the bullet pattern. Compare the length of the next line, and the line that matches the bullet pattern is longer,
Alternatively, if the next line is blank, half the length of the matched line is taken as the upper limit of the itemized list, and if the line that matches the itemized pattern is shorter, the matched line Is the upper limit of the list item, and the maximum list item candidate is determined.

According to the present invention (claim 6), when the position of the next line that does not match the itemized pattern is the same as that of the line that matches the itemized pattern or the item is indented, To be included in the content of the bulleted list. FIG. 2 is a diagram illustrating the principle of the present invention. The present invention (claim 7) is a document structure recognizing device for analyzing the structure of a document including an arbitrary list, which stores a document input unit 1 for inputting a document to be recognized and a list pattern. The pattern storage unit 2 performs pattern matching for each line between a document input by the document input unit 1 and an itemized pattern stored in the pattern storage unit 2 in advance, and an itemized list that matches the itemized pattern. Candidate generating means 3 for generating a candidate, and length measuring means 4 for measuring the length of a character string from the beginning of the line where the character is present to the end of the line where the character is present for one line of the candidate generated by the candidate generating means 3 In the case where a blank is included in the itemized candidate generated by the candidate generating means 3, one itemized candidate is determined from the obtained itemized candidate using the length of the character string. That the candidate determining unit 5, a bullet extraction means 6 for acquiring information bullet label and content from a determined bullet candidate blanks removed by the candidate determination unit 5,
An output unit 7 is provided which adds information on the contents of the label acquired by the item extraction means 6 as a tag to the itemized candidate determined by the item candidate determination means 5 and outputs the result.

According to the present invention (claim 8), in the pattern storage means 2, a pattern matching a bullet containing or not including a blank is held by utilizing the type of character. According to the present invention (claim 9), in the candidate generation means 3,
It includes a pattern matching unit that performs pattern matching as much as possible on a character string pattern in which an input document is divided and written including a blank, and generates a plurality of candidates.

According to the present invention (claim 10), the length measuring means 4 is provided.
Means for measuring the length of a character string including a blank from the beginning of the line to the end of the line excluding the space at the beginning of the line, in bytes, for one line of the document. The present invention (claim 11) provides
In the candidate determination means 5, when there are a plurality of obtained bullet points, the line matching the bullet pattern in the pattern storage means is equal to or indented at the beginning of the line without matching the bullet pattern. Compare the length of the next line, and if the line that matches the bulleted pattern is longer, or if the next line is blank, halve the length of the matched line If the line that matches the pattern is shorter, the length of the matched line is taken as the upper limit of the itemization, and means for determining the maximum itemization candidate is included.

According to the present invention (claim 12), in the bullet extraction means 6, the position of the next line that does not match the bullet pattern is the same as that of the line that matches the bullet pattern, or is indented. If so, the scope of the list includes the means to be included in the content of the list. The present invention (claim 13) is a storage medium storing a document structure recognition program for analyzing a structure of a document including an arbitrary itemized list, the document input process for inputting a document to be recognized, and a document input process. A candidate generation process of performing pattern matching for each line between the document input by the input process and the bullet pattern stored in the pattern storage unit for each line, and generating bullet candidates that match the bullet pattern; A length measurement process that measures the length of a character string from the beginning of a line where a character is present to the end of a line where a character is present in one line of a candidate generated by the candidate generation process, and a blank in the bullet point candidate generated by the candidate generation process Is included, using the length of the character string to determine one bullet candidate from the obtained bullet candidates, Process, the bullet extraction process that removes blanks from the bullet candidates determined by the candidate decision process to obtain bullet label and content information, and the bullet extraction that is determined by the bullet candidate that was determined by the candidate decision process. And an output process for adding information on the contents of the label acquired in the process as a tag and outputting the tag.

According to the present invention (claim 14), in the candidate generation process, a pattern of a character string in which an input document is divided and written including a space is subjected to pattern matching as much as possible, and a plurality of candidates are generated. including. The present invention (claim 15) includes, in the length measuring process, a process of measuring, for each line of a document, a length of a character string including a blank from the head of the line to the end of the line excluding the space at the head of the line in bytes. .

According to the present invention (claim 16), in the candidate determination process, when there are a plurality of obtained bullet candidates,
Compare the line that matches the bulleted pattern in the pattern storage process with the length of the next line that does not match the bulleted pattern and has the same head position or is indented,
If the line that matches the bullet pattern is longer or the next line is blank, half the length of the matched line is shorter and the line that matches the bullet pattern is shorter. Includes the process of determining the length of the matched line as the upper limit of the list item and determining the maximum list item candidate.

According to the present invention (claim 17), in the bullet extraction process, the position of the next line that does not match the bullet pattern is the same or indented as compared with the line that matches the bullet pattern. In some cases, the scope of the list includes the process of including it in the content of the list. As described above, according to the present invention, in the case of recognizing the structure of an e-mail notifying of event guidance, when a received e-mail document is input,
A pattern that matches the itemized list consisting of character types is stored, and pattern matching is performed on the input document using the stored itemized pattern to generate a list item candidate that matches the pattern. And
Measure the length from the beginning to the end of the next line that has the same or indented line instead of a blank line and the line that matches the pattern, and derives it based on the measured line and the length of the next line. One of the items is determined as an itemized list, information on the determined itemized label and content is extracted, the itemized label and information on the content are added as tags to the document, and output.

[0015] With this, attention is paid to the specific character string pattern in the document and the length from the beginning to the end of the line including the pattern, and the relationship between the length of the entire line and the length of the specific character string pattern is considered. Thus, it is possible to analyze the structure of a sentence including an optional bullet point that does not depend on the field.

[0016]

FIG. 3 shows the configuration of a document structure recognition apparatus according to the present invention. The document structure recognizing device shown in FIG. 1 includes a document input unit 1 for inputting a document to be subjected to structure recognition, a pattern matching a list of character types (matching a list including a blank or a list including no blank). pattern)
Storage unit 2 for storing a list, an itemized candidate generation unit 3 that performs pattern matching on an input document using the itemized pattern of the pattern storage unit 2 to generate itemized candidates that match the pattern, The line length measuring unit 4 for measuring the length of one line from to the end of the line. The line length measuring unit 4 measures the length of the bulleted label from the line length matching the pattern, and calculates the obtained length. A bullet determination unit 5 that determines one of the candidates obtained from the criteria as a bullet, a bullet extraction unit 6 that extracts label and label information of the determined bullet, and a bullet label and content. It comprises a tagged document output unit 7 for adding and outputting information to a document as a tag, and a control unit 8 for controlling the above components.

Next, the operation of the above configuration will be described.
FIG. 4 is a flowchart for explaining the operation of the document structure recognition device of the present invention. Step 101) The document input unit 1 according to an instruction from the control unit 8
, Input a document for which the document structure is to be recognized.

Step 102) It is determined whether the input document is not at the end of the line.
The process proceeds to step 109 if the end of the line has been reached. Step 103) Under the control of the control unit 8, the bullet candidate generation unit 3 reads the bullet pattern from the pattern storage unit 2. Step 104) The bullet candidate generation unit 3 performs pattern matching, and generates as many bullet candidates as possible for the line that matches the bullet pattern.

Step 105) Bulleted line candidate generating unit 3
It is determined whether or not there are a plurality of bullet candidates generated in step. If there are a plurality of bullet candidates, the process proceeds to step 106; otherwise, the process proceeds to step 107. Step 106) When there are a plurality of bullet candidates, the one-line length measuring unit 4 measures the length of one line from the beginning of the line to the end of the line, and sends the measured length to the bullet determining unit 5. hand over. When measuring the length of one line, measure the length of a character string including blanks from the beginning of the line to the end of the line excluding the leading blanks in bytes. Then, the bullet determination unit 5 determines one bullet based on the length, and proceeds to step 108.

Step 107) If it is determined in step 105 that there is only one candidate for the itemized list, the candidate is determined as an itemized list, and the process proceeds to step 108. Step 108) The item extraction unit 6 adds the item to be itemized and the additional information to the itemized item, and extracts the itemized information.

Step 109) Tagged Document Output Unit 7
Repeats the above processing until the end of the line, and finally inserts the itemized label and the information of the content as tags into the input document, and outputs a tagged document indicating the document structure. Next, the operation of the itemized list determination unit 5 in step 106 will be described.

FIG. 5 is a flow chart for explaining the operation of the itemized decision section of the present invention. Step 201) The bullet determination unit 5 acquires the length of one line from the beginning to the end of the matched line measured by the one-line length measuring unit 4. Step 202) If the next line is not a blank line and does not match the itemized pattern, the process proceeds to step 203; otherwise, the process proceeds to step 206.

Step 203) If the position of the beginning of the next line is the same or indented, the process proceeds to step 204; otherwise, the process proceeds to step 2
Shift to 06. Step 204) If the condition of step 203 is satisfied, the length of the next line is measured.

Step 205) The length of the line matched with the pattern is compared with the length of the next line, and if the matched line is longer than the next line, or if the next line matches the blank line or the bulleted pattern If not, proceed to step 206; otherwise, proceed to step 207. Step 206) Determine an itemized label with an upper limit of half the length of the matched line, and end the process.

Step 207) If the line matching the pattern is short, the length of the line is used as the length of the itemized label to determine the itemized label, and the process is terminated.
Next, the operation of the item extraction unit 6 will be described. FIG. 6 is a flowchart for explaining the operation of the bullet extraction unit of the present invention.

Step 301) It is determined whether or not the itemized label includes a blank. If it does, the process proceeds to step 302; otherwise, the process proceeds to step 305. Step 302) Delete blanks in the label. Step 303) The itemized list determination unit 5 determines whether the length of the itemized label is set to 1 of the two sentences in the line. If so, the process proceeds to step 304; otherwise, the process proceeds to step 305. I do.

Step 304) Delete blanks in the contents of the bulleted list. Step 305) Finally, information on the itemized label and its contents is extracted.

[0028]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 7 is an example of an itemized pattern stored in the pattern storage unit according to one embodiment of the present invention. [CJ shown in FIG.
KAS] are Kanji (C), Hiragana (J),
Indicates the character type of katakana (K), alphabet (A), and space (S). {1, n} indicates n repetitions. In the example shown in the figure, "<prefix pattern>, <label pattern>, <postfix pattern>, <content pattern>", "<label turn>, <postfix pattern>, <<Contentpattern> ”“ <prefix pattern>, <label pattern>, <postfix pattern> ”“ <label pattern>, <postfix pattern> ”“ <prefix pattern>, <label pattern> ”“ <label pattern ” >> are stored as a set.

FIG. 8 is an example of an input e-mail document according to an embodiment of the present invention. It is assumed that a blank line is inserted every other line from the title “Ceremonial Festival” to the line preceding “Remarks”. For example, assuming that the electronic mail document shown in FIG. 8 is an input document from the document input unit 1, the third line matches the segmented bullet pattern by the processing of the bullet candidate generation unit 3, and the bullet candidate is Are generated. Further, one line length measuring unit 4
Indicates that the line length is 30 bytes. The bullet determination unit 5 recognizes that the next line is a blank line,
The length of the bulleted label is one half of the line length1
Since it is determined to be a candidate having an upper limit of 5 bytes, the item extraction unit 6 uses “type” as the item label.
Here, since the itemized label “type” includes two blanks, the blank of the label is deleted to obtain “type”. Further, since the bullet length is determined by the bullet determination unit 5 up to a half of the line length, blanks in the content of the bullet are deleted, and the content of the bullet is defined as:
Get "marriage". The obtained information is added to the document as a tag in the tagged document output unit 7 and output.

In the same manner, since the candidate for the itemized list in the fifth line matches only "belonging", this item is used as the itemized item. The seventh and eleventh rows are the same as the third row. The ninth and thirteenth rows are the same as the fifth row. Thus, when the electronic mail shown in FIG. 8 is used as the input document, the document shown in FIG. 9 is output.

Although the above embodiment has been described based on the configuration shown in FIG. 3, each component of the document structure recognition apparatus shown in FIG. 3 is constructed as a program and used as the document structure recognition apparatus. Disk devices connected to computers, floppy disks (registered trademark), CD-
The present invention can be easily realized by storing it in a portable storage medium such as a ROM and installing the same when implementing the present invention.

The present invention is not limited to the above embodiment, but can be variously modified and applied within the scope of the claims.

[0033]

As described above, according to the present invention, by using the length of a character string and the position of the head of a line written in a bulleted list, it is possible to prepare blanks without preparing keywords depending on the field. It is possible to recognize a document structure including an optional bulleted list in which characters are separated by sandwiching.

[Brief description of the drawings]

FIG. 1 is a diagram for explaining the principle of the present invention.

FIG. 2 is a principle configuration diagram of the present invention.

FIG. 3 is a configuration diagram of a document structure recognition device of the present invention.

FIG. 4 is a flowchart for explaining the operation of the document structure recognition device of the present invention.

FIG. 5 is a flowchart for explaining the operation of an itemized decision unit according to the present invention;

FIG. 6 is a flowchart for explaining the operation of a bullet extraction unit of the present invention.

FIG. 7 is an example of an itemized pattern stored in a pattern storage unit according to an embodiment of the present invention.

FIG. 8 is an example of an input e-mail document according to an embodiment of the present invention.

FIG. 9 is an example of an output document according to an embodiment of the present invention.

[Explanation of symbols]

 REFERENCE SIGNS LIST 1 document input unit, document input unit 2 pattern storage unit, pattern storage unit 3 candidate generation unit, bullet candidate generation unit 4 length measurement unit, one line length measurement unit 5 candidate determination unit, bullet determination unit 6 bullet extraction Means, bullet extraction section 7 Output means, Tagged document output section

Claims (17)

[Claims] 1. A document structure recognizing method for analyzing a structure of a document including an arbitrary bullet point, a document to be recognized is input, and the document and a bullet pattern stored in advance are line-by-line. To generate a bullet candidate that matches the bullet pattern, measure the length of the character string from the beginning of the line where the characters are present to the end of the line where the characters are present for one line of the document, and generate In the case where the itemized candidate includes a blank, one itemized item candidate is determined from the obtained itemized candidate using the length of the character string, and the determined itemized candidate is determined. A document structure recognition method characterized in that information on itemized labels and contents is obtained by removing blanks from the list, and information on the contents of the label is added as a tag to the determined itemized bullet candidates and output. Law. 2. The document structure recognizing method according to claim 1, wherein a pattern matching a bullet containing or not including a blank is stored as the previously stored bullet pattern by using a character type. . 3. The method according to claim 1, wherein, when generating the candidate for the itemized list, a plurality of candidates are generated by performing a pattern matching of a character string pattern in which the input document is divided and written including a blank space as much as possible. Document structure recognition method described. 4. When measuring the length of the character string, the length of a character string including a blank from the head of the line to the end of the line excluding the space at the beginning of the line is measured in bytes for one line of the document. The method according to claim 1. 5. When there are a plurality of obtained bullet points, a line that matches the bullet pattern and a next line that does not match the bullet pattern and has the same head position or is indented If the line that matches the bulleted pattern is longer, or if the next line is blank, one-half the length of the matched line is replaced by the maximum length of the bulleted list. 2. The document structure recognition according to claim 1, wherein when the line matching the bullet pattern is shorter, the length of the matched line is set as the upper limit length of the bullet, and the maximum bullet candidate is determined. Method. 6. If the position of the next line that does not match the itemized pattern is the same or indented as compared with the line that matches the itemized pattern, the itemized list is included in the itemized range. 2. The document structure recognition method according to claim 1, wherein the document structure is included in the content of the document structure. 7. A document structure recognizing device for analyzing a structure of a document including an arbitrary bullet point, a document input means for inputting a document to be recognized, a pattern storage means for holding a bullet pattern, Pattern matching is performed for each line between the document input by the document input unit and the bullet pattern stored in the pattern storage unit, and a bullet candidate that matches the bullet pattern is generated. Candidate generating means; length measuring means for measuring the length of a character string from the beginning of a line where a character is present to the end of a line where a character is present in one line of the candidate generated by the candidate generating means; If a blank is included in the list item candidate, the length of the character string is used,
Candidate determining means for determining one bullet point candidate from the obtained bullet points; obtaining blank label and content information by deleting blanks from the bullet point candidates determined by the candidate determining means; Item extraction means, and output means for adding the information of the content of the label obtained by the item extraction means as a tag to the item candidate determined by the candidate determination means and outputting the result. Document structure recognition device. 8. The document structure recognition apparatus according to claim 7, wherein said pattern storage means stores a pattern matching a bullet point including or not including a blank, using a character type. 9. The method according to claim 7, wherein the candidate generating unit includes a pattern matching unit that generates a plurality of candidates by performing pattern matching as much as possible on a character string pattern in which the input document is divided and written including a blank. Document structure recognition device as described. 10. The apparatus according to claim 1, wherein said length measuring means includes means for measuring, for each line of said document, a length of a character string including a space from the head of the line to the end of the line excluding a space at the head of the line in bytes. 7. The document structure recognition device according to 7. 11. The candidate deciding means, when there are a plurality of obtained bullet points, a line matching the bullet pattern of the pattern storage means and a position of the head of the line which is not matched with the bullet pattern is equal. Or compare the length of the next indented line, and if the line that matches the bulleted pattern is longer or the next line is blank, 8. The method according to claim 7, further comprising the step of: determining a maximum number of candidate bullets by setting the length of the matched line as an upper limit length of the bullet when the line matching the bullet pattern is shorter. Document structure recognition device. 12. The method according to claim 12, wherein: the list extracting unit determines whether a position of a next line that does not match the list pattern is the same as a position of a line that matches the list pattern.
8. The document structure recognition apparatus according to claim 7, further comprising means for including, when indented, the content of the list as a range of the list. 13. A storage medium storing a document structure recognition program for analyzing a structure of a document including an arbitrary itemized list, wherein the document input process inputs a document to be recognized. A candidate generation process for performing line-by-line pattern matching between the input document and a bullet pattern stored in a pattern storage unit in order to generate bullet candidates that match the bullet pattern; A length measurement process that measures the length of a character string from the beginning of a line where a character is present to the end of a line where a character is present for one line of the candidate generated by the generation process, and the list item candidate generated by the candidate generation process When a blank is included, one bullet point candidate is obtained from the obtained bullet points using the length of the character string. A candidate determination process to be determined, a bullet extraction process for removing information from the bullet candidates determined by the candidate determination process and obtaining bullet label and content information, and a bullet extraction process determined in the candidate determination process. A storage medium storing a document structure recognizing program, comprising: an output process of adding, as a tag, information on the contents of a label acquired in the bullet extraction process to a bullet candidate and outputting the tag. 14. The candidate generating process includes a pattern matching process of generating a plurality of candidates by pattern-matching as much as possible a character string pattern in which the input document is divided and written including a blank. A storage medium that stores the described document structure recognition program. 15. The method according to claim 15, wherein the length measuring process includes a process of measuring a length of a character string including a blank from a head of the line excluding a space at the beginning of the line to an end of the line for each line of the document in bytes. A storage medium storing the document structure recognition program according to claim 13. 16. The candidate determination process, in the case where there are a plurality of obtained bullet candidates, a line that matches the bullet pattern of the pattern storing process is equal to the head of the line that does not match the bullet pattern. Or
Compare the length of the next indented line, and if the line that matches the bulleted pattern is longer, or if the next line is blank, reduce the length of the matched line by half. , If the line that matches the bullet pattern is shorter,
2. The method according to claim 1, further comprising a step of determining a maximum list item candidate by setting a length of the matched line as an upper limit of the list item.
A storage medium storing the document structure recognition program according to Item 3. 17. The list extraction process according to claim 1, wherein a position of a next line that does not match the list pattern is the same as a position of a line that matches the list pattern.
Claim 13 including, if indented, the process of including in the content of the list as the scope of the list.
A storage medium that stores the described document structure recognition program.