System and method for facts extraction and domain knowledge repository creation from unstructured and semi-structured documents

• US 7,756,807 B1
• Filed: 09/24/2008
• Issued: 07/13/2010
• Est. Priority Date: 06/18/2004
• Status: Active Grant

• Current Assignee: Glenbrook Networks
• Original Assignee: Glenbrook Networks
• Inventors: Komissarchik, Julia, Komissarchik, Edward
• Primary Examiner(s): HOLMES, MICHAEL B
• Application Number:
  US12/237,059
• Time in Patent Office: 657 Days
• Field of Search: 706/46
• US Class Current: 706/46
• CPC Class Codes: G06F 16/345 Summarisation for human users

Abstract

Provided are methods and systems that extract facts of unstructured documents and build an oracle for various domains. The present invention addresses the problem of efficient finding and extraction of facts about a particular subject domain from semi-structured and unstructured documents, makes inferences of new facts from the extracted facts and the ways of verification of the facts, thus becoming a source of knowledge about the domain to be effectively queried. The methods and systems can also extract temporal information from unstructured and semi-structured documents, and can find and extract dynamically generated documents from Deep or Dynamic Web.

Claims

1. A method for automatic article and title extraction without templates, comprising:

building a paragraph tree from a page;

building paragraphs from tree nodes that include a table depth determination for each node;

determining the paragraphs that contain a href, url reference;

grouping contiguous href and non-href paragraphs into blocks and categorizing them by size as small, medium and large; and

declaring the largest medium block as large, if there are no large blocks.

2. The method of claim 1, wherein large blocks separated by one href block with less than a predefined number of paragraphs are merged together.

3. The method of claim 2, wherein large blocks of the same table depth that are separated by no more than a predefined number of paragraphs are merged together.

4. The method of claim 3, wherein medium and small blocks with the same table depth and separated from the large blocks by no more than MAXJUMP paragraphs are added to the large blocks.

5. The method of claim 1, wherein adjacent large blocks are merged together.

6. The method of claim 5, wherein the largest of the large blocks is chosen as article body.

7. The method of claim 1, wherein the paragraphs are marked as candidates for article title based on b, i, u, h, and title tags.

8. The method of claim 7, wherein the title candidates which are situated below a predefined percent of article body are eliminated.

9. The method of claim 8, wherein the title candidate within the article body with the highest similarity score to the article body is declared article title.

10. The method of claim 8, wherein if there is no candidate title within article body, the one with the highest similarity score to the article body is declared article title.

11. The method of claim 1, wherein the paragraphs from article body that are above article title are eliminated.

12. The method of claim 1, wherein the histogram of paragraph left and right coordinates on the page is calculated.

13. The method of claim 12, wherein the two-peak distribution from the histogram is determined.

14. The method of claim 13, wherein the paragraphs from article body and article title that start or end further away than a predetermined percentage from these two peaks are eliminated.

15. A method for extraction of people names, positions they have with companies, companies names and their quotes from an article comprising:

building a list of paragraphs; and

applying island grammar to extract quadruples that include at last one of, person, position, company and quote.

16. The method of claim 15, wherein company instances are built based on the third coordinate of the quadruples.

17. The method of claim 16, wherein company objects corresponding to company instances are defined.

18. The method of claim 17, wherein company instances that correspond to more than one company object are eliminated.

19. The method of claim 18, wherein person instances are built based on the first coordinate of the quadruples.

20. The method of claim 19, wherein person objects corresponding to person instances are defined.

21. The method of claim 20, wherein incomplete quadruples are merged in accordance with matching elements.

22. The method of claim 21, wherein for each person object the best position out of all second coordinate of corresponding quadruplets is chosen.

23. The method of claim 22, wherein all incomplete quadruplets are eliminated.