Method of extracting important terms, phrases, and sentences

• US 20030028558A1
• Filed: 05/30/2002
• Published: 02/06/2003
• Est. Priority Date: 05/30/2001
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Kawatani, Takahiko
• Granted Patent: US 7,225,120 B2
• Time in Patent Office: Days
• US Class Current: 715/500
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/345 Summarisation for human users

Abstract

A computer extracts important terms, phrases or sentences from a document that it segments. The computer generates a square sum matrix from the document segments. The computer determines the importance of a given term, phrase or sentence on the basis of eigenvectors and eigenvalues of the matrix. The computer thereby selects the important terms, phrases or sentences related to the central concepts of the document.

Claims

1. A method of extracting an important item from an input document including at least one document segment, comprising the steps of:

(a) generating, for the respective at least one document segment, document segment vectors having values relating to occurrence frequencies of terms occurring in the respective at least one document segment as component values;

(b) generating a square sum matrix from the document segment vectors;

(c) calculating eigenvectors and eigenvalues of the square sum matrix; and

(d) selecting the important item of the input document from the calculated eigenvectors and eigenvalues of the square sum matrix.

2. The method of claim 1 wherein the item is a term.

3. The method of claim 1 wherein the item is a phrase.

4. The method of claim 1 wherein the item is a sentence.

5. The method of claim 1 wherein step (d) includes selecting a definite number of eigenvectors and eigenvalues from the eigenvectors and the eigenvectors;

generating, with respect to the items in the input document, item vectors in which only components corresponding to the terms included in the items have a first binary value and the other components have a second binary value; and

obtaining a measure of the importance of the items by using the definite number of eigenvectors, the definite number of eigenvalues, and the item vectors.

6. The method according to claim 5, wherein the square sum matrix is calculated as:

7. The method of claim 5 wherein the importance measure of the item with respect to the eigenvector of each order is obtained by obtaining a product of a squared inner product between the eigenvector of the order and the item vector, and the eigenvalue of the order.

8. The method of claim 7 wherein the item is a term, and the importance measure of the item is obtained by normalizing with a value of a diagonal component corresponding to each term in the square sum matrix or a value relating thereto.

9. The method of claim 7 wherein the item is a phrase or a sentence and the importance measure of the item is obtained by normalizing with a value of the squared norm of the item vector or a value of a squared sum of inner products between the all document segment vectors and the item vector or a value relating thereto.

10. The method of claim 5 wherein the importance measure of the item with respect to the input document is obtained by using weights calculated from the eigenvalues of respective orders and by a weighted sum of products of a squared inner product between the eigenvector of each order and the item vector, and the eigenvalue of the order over the definite number of orders.

11. The method of claim 10 wherein the item is a term and the importance measure of the item is obtained by normalizing with a value of a diagonal component corresponding to each term in the square sum matrix or a value relating thereto.

12. The method of claim 10 wherein the item is a phrase or a sentence and the importance measure of the item is obtained by normalizing with a value of the squared norm of the item vector or a value of a squared sum of inner products between the all document segment vectors and the item vector or a value relating thereto.

13. A method of extracting an important item from an input document including at least one document segment, comprising the steps of:

(a) generating document segment vectors having, as components, values relating to occurrence frequencies of terms occurring in the document segments;

(b) generating, with respect to an item in the input document, an item vector in which occurrence numbers of terms contained in the item are assigned to components corresponding to the terms in the item, and the other components are assigned a zero value;

(c) obtaining a measure of the importance of the item by using a sum of squared inner products between the item vector and all the document segment vectors; and

(d) selecting the important item of the input document by using the importance measure.

14. The method of claim 13 wherein the item is a phrase.

15. The method of claim 13 wherein the item is a sentence.

16. The method of claim 13 further including determining the importance measure of the item by normalizing with the squared norm of the item vector.

17. Apparatus for extracting an important item from an input document including at least one document segment, the apparatus comprising:

(a) a data processor arrangement,

(b) an input device for supplying the document to the data processor arrangement,

(c) the data processor arrangement being arranged to be responsive to the document supplied to it by the input device for;

(i) generating, for the respective at least one document segment, document segment vectors having values relating to occurrence frequencies of terms occurring in the respective at least one document segment as component values;

(ii) generating a square sum matrix from the document segment vectors;

(iii) calculating eigenvectors and eigenvalues of the square sum matrix; and

(iv) selecting the important item of the input document from the calculated eigenvectors and eigenvalues of the square sum matrix.

18. The apparatus of claim 17 wherein the processor is further arranged for performing step (d) by:

(i) selecting a definite number of eigenvectors and eigenvalues from the eigenvectors and the eigenvectors;

(ii) generating, with respect to the items in the input document, item vectors in which only components corresponding to the terms included in the items have a first binary value and the other components have as second binary value; and

(iii) obtaining a measure of the importance of the items by using the definite number of eigenvectors, the definite number of eigenvalues, and the item vectors.

19. The apparatus of claim 18 wherein the square sum matrix is calculated as:

20. The apparatus of claim 18 wherein the processor arrangement is arranged for obtaining the importance measure of the item with respect to the eigenvector of each order by calculating a product of a square inner product between the eigenvector of the order and the item vector, and the eigenvalue of the order.

21. The apparatus of claim 20 wherein the item is a term, and the processor arrangement is arranged for obtaining the importance measure of the item by normalizing with a value of a diagonal component corresponding to each term in the square sum matrix or a value relating thereto.

22. The apparatus of claim 20 wherein the item is a phrase or a sentence and the processor arrangement is arranged for obtaining the importance measure of the item by normalizing with a value of the squared norm of the item vector or a value of a squared sum of inner products between the all document segment vectors and the item vector or a value relating thereto.

23. The apparatus of claim 18 wherein the processor arrangement is arranged for obtaining the importance measure of the item with respect to the input document by using weights calculated from the eigenvalues of respective orders and by a weighted sum of products of a squared inner product between the eigenvector of each order and the item vector, and the eigenvalue of the order over the definite number of orders.

24. The apparatus of claim 23 wherein the processor arrangement is arranged for obtaining the importance measure of the item by normalizing with a value of a diagonal component corresponding to each term in the square sum matrix or a value relating thereto.

25. The apparatus of claim 23 wherein the item is a phrase or a sentence and the processor arrangement is arranged for obtaining the importance measure of the item by normalizing with a value of the squared norm of the item vector or a value of a squared sum of inner products between the all document segment vectors and the item vector or a value relating thereto.

26. The apparatus of claim 17 wherein the items are terms.

27. The apparatus of claim 17 wherein the items are phrases.

28. The apparatus of claim 17 wherein the items are sentences.

29. Apparatus for extracting an important item from an input document including at least one document segment, the apparatus comprising:

(a) a data processor arrangement,

(b) an input device for supplying the document to the data processor arrangement,

(c) the data processor arrangement arranged to be responsive to the document supplied to it by the input device for;

(i) generating document segment vectors having, as components, values relating to occurrence frequencies of terms occurring in the document segments;

(ii) generating, with respect to an item in the input document, an item vector in which occurrence numbers of terms contained in the item are assigned to components corresponding to the terms in the item, and the other components are assigned a zero value;

(iii) obtaining a measure of the importance of the item by using a sum of squared inner products between the item vector and all the document segment vectors; and

(iv) selecting the important item of the input document by using the importance measure.