Method of summarizing text by sentence extraction

• US 6,990,634 B2
• Filed: 04/26/2002
• Issued: 01/24/2006
• Est. Priority Date: 04/27/2001
• Status: Active Grant

• Current Assignee: National Security Agency
• Original Assignee: The United States of America As Represented By The Director National Security Agency
• Inventors: Conroy, John M., O'Leary, Dianne P.
• Primary Examiner(s): Hong, Stephen
• Assistant Examiner(s): Huynh, Thu V.
• Application Number:
  US10/135,100
• Publication Number:
  US 20020174149A1
• Time in Patent Office: 1,369 Days
• Field of Search: 715/531, 704/1, 704/9
• US Class Current: 715/227
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation

Abstract

A method of summarizing text. The sentences in the text are identified first. Then, the terms in each sentence are identified. A matrix is then generated, where the columns represent the sentences and the rows represent the terms. The entries in the matrix are weighted with an exponentially decaying function or a Hidden Markov Model. The Euclidean length of each column is determined. The sentence corresponding to the column having the maximum Euclidean length is selected as a summary sentence. The columns corresponding to the remaining sentences have their matrix entries reduced. If additional summary sentences are desired then return to the step of determining Euclidean length of the columns.

Claims

1. A method of summarizing text on a computer, where the text consists of a number of sentences, and where each sentence includes a number of terms, comprising the steps of:

(a) identifying each sentence in the text;

(b) identifying each term in each sentence;

(c) generating a matrix on the computer, where each column in the matrix represents a sentence in the text, and where each row in the matrix represents a term in the text;

(d) replacing each entry in the matrix by a product of the matrix entry and a user-definable function that decays exponentially;

(e) determining the Euclidean length of each column by squaring the entries in the corresponding column, summing the squares, and taking the square root of the sum;

(f) selecting the column with a maximum Euclidean length as a summary sentence;

(g) reducing the Euclidean lengths of the columns not selected in step (f); and

(h) returning to step(e) if another summary sentence is desired, otherwise returning the selected summary sentences as the summary of the text.

2. The method of claim 1, wherein said step of identifying each term in each sentence is comprised of the step of identifying each term in each sentence after stop-words are eliminated and any term ambiguity is resolved.

3. The method of claim 1, wherein said step of generating a matrix on the computer is comprised of the step of generating a matrix on the computer where each entry in the matrix is selected from the group of matrix entries comprising one and the frequency of occurrence of a particular term in a particular sentence.

4. The method of claim 1, wherein said step of replacing each entry in the matrix by a product of the matrix entry and a user-definable function that decays exponentially is comprised of the step of replacing each entry in the matrix by a product of the matrix entry and ge⁽⁻

8j/n)+t, where g is a user-definable constant, where e~2.718, where j is the column number of the column in question, where n is the number of sentences in the text, and where t is a user-definable constant that makes the decaying function'"'"'s length approximately equal to the decaying function'"'"'s height.

5. The method of claim 1, wherein said step of reducing the Euclidean lengths of the columns not selected in step (f) is comprised of the step of subtracting r_jiq_i, from each entry in the columns not selected in step (f), where r_ji=a_j^Tq_i, where a_j^T the transpose of the column in question prior to reducing the entries therein, where q_i=a_s/∥

a_s∥

, where a_s, is the column selected in step (f), and where ∥

a_s∥

is the Eucidean length of column a_s.

6. A method of summarizing text on a computer, where the text consists of a number of sentences, and where each sentence includes a number of terms, comprising the steps of:

(a) identifying each sentence in the text;

(b) identifying each term in each sentence;

(c) generating a matrix on the computer, where each column in the matrix represents a sentence in the text, and where each row in the matrix represents a term in the text;

(d) replacing each entry in the matrix by a product of the matrix entry and a Hidden Markov Model probability that the sentence corresponding to the matrix entry is a summary sentence;

(e) determining the Eudidean length of each column by squaring the entries in the column in question, summing the squares, and taking the square root of the sum;

(f) selecting the column with the maximum Euclidean length as a summary sentence;

(g) reducing the Eucidean lengths of the columns not selected in step (f); and

(h) returning to step(e) if another summery sentence is desired, otherwise returning the selected summary sentences as the summary of the text.

7. A method of summarizing a plurality of documents on a computer, where each document consists of a number of sentences, and where each sentence includes a number of terms, comprising the steps of:

(a) identifying each sentence in each document from the plurality of documents;

(b) identifying each term in said each sentence;

(c) generating a matrix on the computer, where each column in the matrix represents a sentence in the plurality of text, and where each row in the matrix represents a term in the plurality of text;

(d) replacing each entry in the matrix by a product of the matrix entry and a Hidden Markov Model probability that the sentence corresponding to the matrix entry is a summary sentence;

(e) determining the Euclidean length of each column by squaring the entries in the corresponding column, summing the squares, and taking the square root of the sum;

(f) selecting the column with a maximum Euclidean length as a summary sentence;

(g) reducing the Euclidean lengths of the columns not selected in step (f); and

(h) returning to step(e) if another summary sentence is desired, otherwise returning the selected summary sentences as the summary of the text.