Automatic linear text segmentation

• US 20060224584A1
• Filed: 12/27/2005
• Published: 10/05/2006
• Est. Priority Date: 03/31/2005
• Status: Abandoned Application

• Current Assignee: Content Analyst Company, LLC (Relativity ODA LLC)
• Original Assignee: Content Analyst Company, LLC (Relativity ODA LLC)
• Inventors: Price, Robert Jenson
• Application Number:
  US11/316,837
• Publication Number:
  US 20060224584A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing

Abstract

An embodiment of the present invention provides a method for automatically subdividing a document into conceptually cohesive segments. The method includes the following steps: subdividing the document into contiguous blocks of text; generating an abstract mathematical space based on the blocks of text, wherein each block of text has a representation in the abstract mathematical space; computing similarity scores for adjacent blocks of text based on the similarity scores; and aggregating similar adjacent blocks of text based on the similarity scores.

Claims

1. A method for automatically organizing a document into conceptually cohesive segments, comprising:

(a) subdividing the document into contiguous blocks of text;

(b) generating an abstract mathematical space based on the blocks of text, wherein each block of text has a representation in the abstract mathematical space;

(c) computing similarity scores for adjacent blocks of text based on the representations of the adjacent blocks of text; and

(d) aggregating similar adjacent blocks of text based on the similarity scores.

2. The method of claim 1, wherein step (b) comprises:

(b) generating a Latent Semantic Indexing (LSI) space based on the blocks of text, wherein each block of text has a representation in the LSI space.

3. The method of claim 2, wherein step (c) comprises:

(c) computing cosine similarities for adjacent blocks of text based on the representations of the adjacent blocks of text.

4. The method of claim 2, wherein step (c) comprises:

(c) computing similarity scores for adjacent blocks of text based on the representations of the adjacent blocks of text, wherein computing a similarity score comprises computing at least of one a dot product, a scaled dot product, a scaled cosine, an inner product, or a Euclidean distance.

5. The method of claim 1, wherein step (c) comprises:

(c) computing a similarity between the representation of a first block of text and the representation of at least one other block of text that is within a proximity threshold of the first block of text.

6. The method of claim 1, wherein step (c) comprises:

(c) computing a similarity between a first plurality of representations of blocks of text and a second plurality of representations of blocks of text, wherein the second plurality of blocks of text are within a proximity threshold of the first plurality of blocks of text.

7. The method of claim 1, further comprising:

(e) computing a similarity between the representation of a first block of text and the representation of respective blocks of text in an aggregated segment of text, wherein each block of text in the aggregated segment of text is within a proximity threshold of the first block of text.

8. The method of claim 7, further comprising:

(f) aggregating the first block of text and the aggregated segment of text based on a maximum similarity computed in step (e).

9. The method of claim 7, further comprising:

(f) aggregating the first block of text and the aggregated segment of text based on a composite similarity computed in step (e).

10. The method of claim 1, wherein steps (c) and (d) comprise:

(c1) computing a similarity between the representation of a first block of text and a composite representation of a plurality of blocks of text, wherein each block of text in the plurality of blocks of text is within a proximity threshold of the first block of text; and

(d1) aggregating the first block of text and the plurality of blocks of text based on the similarity computed in step (c1).

11. The method of claim 1, wherein steps (c) and (d) further comprise:

(c1) computing a first similarity of the representation of a first block of text with respect to the representation of a second block of text that is to the right of and within a proximity threshold of the first block of text;

(c2) computing a second similarity of the representation of the second block of text with respect to the representation of a block of text that is to the left of and within a proximity threshold of the second block of text; and

(d) aggregating the first block of text and the second block of text based on a comparison of the first and second similarities.

12. The method of claim 1, further comprising:

(e) computing a similarity between the representation of a last block of text in an aggregated segment of text and the representation of a second plurality of blocks of text, wherein each block of text in the second plurality of blocks of text is within a proximity threshold of the last block of text in the aggregated segment of text; and

(f) aggregating the first aggregated segment of text and the second plurality of blocks of text into a second aggregated segment of text based on the similarity computed in step (e).

13. A computer program product for automatically organizing a document into conceptually cohesive segments, comprising:

a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on an operating system of a computer, said computer readable program code means comprising;

a computer readable first program code means for subdividing the document into contiguous blocks of text;

a computer readable second program code means for generating an abstract mathematical space based on the blocks of text, wherein each block of text has a representation in the abstract mathematical space;

a computer readable third program code means for computing similarity scores for adjacent blocks of text based on the representations of the adjacent blocks of text; and

a computer readable fourth program code means for aggregating similar adjacent blocks of text based on the similarity scores.

14. The computer program product of claim 13, wherein the second computer readable program code means comprises:

means for generating a Latent Semantic Indexing (LSI) space based on the blocks of text, wherein each block of text has a representation in the LSI space.

15. The computer program product of claim 14, wherein the third computer readable program code means comprises:

means for computing cosine similarities for adjacent blocks of text based on the representations of the adjacent blocks of text.

16. The computer program product of claim 14, wherein the third computer readable program code means comprises:

means for computing similarity scores for adjacent blocks of text based on the representations of the adjacent blocks of text, wherein computing a similarity score comprises computing at least one of a dot product, a scaled dot product, a scaled cosine, an inner product, or a Euclidean distance.

17. The computer program product of claim 13, wherein the third computer readable program code means comprises:

means for computing a similarity between the representation of a first block of text and the representation of at least one other block of text that is within a proximity threshold of the first block of text.

18. The computer program product of claim 13, wherein the third computer readable program code means comprises:

means for computing a similarity between a first plurality of representations of blocks of text and a second plurality of representations of blocks of text, wherein the second plurality of blocks of text are within a proximity threshold of the first plurality of blocks of text.

19. The computer program product of claim 13, further comprising:

a computer readable fifth program code means for computing a similarity between the representation of a first block of text and the representation of respective blocks of text in an aggregated segment of text, wherein each block of text in the aggregated segment of text is within a proximity threshold of the first block of text.

20. The computer program product of claim 19, further comprising:

a computer readable sixth program code means for aggregating the first block of text and the aggregated segment of text based on a maximum similarity computed by the fifth computer readable program code means.

21. The computer program product of claim 19, further comprising:

a computer readable sixth program code means for aggregating the first block of text and the aggregated segment of text based on a composite similarity computed by the fifth computer readable program code means.

22. The computer program product of claim 13, wherein:

the third computer readable program code means comprises means for computing a similarity between the representation of a first block of text and a composite representation of a plurality of blocks of text, wherein each block of text in the plurality of blocks of text is within a proximity threshold of the first block of text; and

the fourth computer readable program code means comprises means for aggregating the first block of text and the plurality of blocks of text based on the similarity computed by the third computer readable program code means.

23. The computer program product of claim 13, wherein:

the third computer readable program code means comprises means for (i) computing a first similarity of the representation of a first block of text with respect to the representation of a second block of text that is to the right of and within a proximity threshold of the first block of text, and (ii) computing a second similarity of the representation of the second block of text with respect to the representation of a block of text that is to the left of and within a proximity threshold of the second block of text; and

the fourth computer readable program code means comprises means for aggregating the first block of text and the second block of text based on a comparison of the first and second similarities.

24. The computer program product of claim 13, further comprising:

a computer readable fifth program code means for computing a similarity between the representation of a last block of text in an aggregated segment of text and the representation of a second plurality of sentences, wherein each sentence in the second plurality of sentences is within a proximity threshold of the last block of text in the aggregated segment of text; and

a computer readable sixth program code means for aggregating the first segment and the second plurality of sentences into a second segment based on the similarity computation.