Header-token driven automatic text segmentation

• US 9,053,091 B2
• Filed: 12/09/2013
• Issued: 06/09/2015
• Est. Priority Date: 12/28/2006
• Status: Active Grant

• Current Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Original Assignee: eBay Inc.
• Inventors: Sarwar, Badrul M., Mount, John A.
• Primary Examiner(s): Ly, Anh
• Application Number:
  US14/100,990
• Publication Number:
  US 20140172858A1
• Time in Patent Office: 547 Days
• Field of Search: 707/741, 707/797, 707/798, 707/739, 707/738, 707/728, 707/796, 707/706, 707/740, 707/760, 707/765, 707/766, 707/768, 707/769, 707/759, 707/E17.089, 707/E17.108, 707/737, 707/722, 706/46, 706/45, 704/9, 704/1, 704/8, 704/270, 704/257
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

A method and a system to automatically segment text based on header tokens is described. A relevance value and an irrelevance value are determined for each token in a description, assuming no tokens are left out of computations. The irrelevance value is based on occurrences of a token in a sample set of descriptions. The relevance value is an estimated probability of relevance based on the header of the description being segmented.

Claims

1. A method comprising:

assigning a value to a first token in a description, the value indicating either;

that the first token also occurs in a header of the description,

that a lexical association exists between the first token and a second token in the header, or

that the lexical association does not exist and the first token is absent from the header;

computing a relevance value of a group of tokens that occur in the description and include the first token with the assigned value, the relevance value of the group being computed by a processor of a machine based on the value assigned to the first token;

indicating that the group of tokens is a most relevant group of tokens in the description;

wherein;

the assigning of the value to the first token includes initially assigning a default value that indicates the lexical association does not exist and the first token is absent from the header; and

the assigning of the value to the first token includes overwriting the initially assigned default value based on the first token occurring in the header.

2. The method of claim 1, wherein:

the header of the description is a body of text shorter than the description and provides information about the description.

3. The method of claim 1, wherein:

the header of the description includes at least one of a title of the description, an abstract of the description, a summary of description, or a synopsis of the description.

4. The method of claim 1, wherein:

the computing of the relevance value of the group of tokens computes the relevance value of a segment of the description; and

the indicating indicates that the segment is a most relevant segment of the description.

5. The method of claim 1, wherein:

the computing of the relevance value of the group of tokens computes the relevance value of a sequence of tokens; and

the indicating indicates that the sequence is a most relevant sequence of tokens in the description.

6. The method of claim 1 further comprising:

determining that the lexical association exists between the first token and the second token by accessing a table that lexically associates the first token with the second token.

7. The method of claim 1, wherein:

the assigned value represents a relevance probability of the first token; and

the computing of the relevance value of the group of tokens is based on the relevance probability of the first token and further based on an irrelevance probability of the first token.

8. The method of claim 7 further comprising:

determining the irrelevance probability based on a proportion of descriptions that contain the first token within a set of descriptions.

9. The method of claim 1, wherein:

the indicating that the group of tokens is the most relevant group of tokens in the description includes modifying a font of the most relevant group of tokens in the description.

10. The method of claim 1, wherein:

the indicating that the group of tokens is the most relevant group of tokens in the description includes presenting the most relevant group of tokens with the header of the description.

11. A non-transitory machine-readable storage medium comprising instructions that, when executed by one or more processors of a machine, cause the machine to perform operations comprising:

assigning a value to a first token in a description, the value indicating either;

that the first token also occurs in a header of the description,

that a lexical association exists between the first token and a second token in the header, or

that the lexical association does not exist and the first token is absent from the header;

computing a relevance value of a group of tokens that occur in the description and include the first token with the assigned value, the relevance value of the group being computed based on the value assigned to the first token;

indicating that the group of tokens is a most relevant group of tokens in the description;

wherein;

the assigning of the value to the first token includes initially assigning a default value that indicates the lexical association does not exist and the first token is absent from the header; and

the assigning of the value to the first token includes overwriting the initially assigned default value based on the lexical association existing between the first token and the second token in the header.

12. The non-transitory machine-readable storage medium of claim 11, wherein the operations further comprise:

the assigned value represents a relevance probability of the first token; and

the computing of the relevance value of the group of tokens is based on the relevance probability of the first token and further based on an irrelevance probability of the first token.

13. The non-transitory machine-readable storage medium of claim 12, wherein the operations further comprise:

determining the irrelevance probability based on a proportion of descriptions that contain the first token within a set of descriptions.

14. A system comprising:

at least one processor; and

a segmentation module that configures the at least one processor to;

assign a value to a first token in a description, the value indicating either;

that the first token also occurs in a header of the description,

that a lexical association exists between the first token and a second token in the header, or

that the lexical association does not exist and the first token is absent from the header;

compute a relevance value of a group of tokens that occur in the description and include the first token with the assigned value, the relevance value of the group being computed based on the value assigned to the first token;

indicate that the group of tokens is a most relevant group of tokens in the description;

wherein;

the segmentation module configures the at least one processor to initially assign a default value that indicates the lexical association does not exist and the first token is absent from the header; and

the segmentation module configures the at least one processor to overwrite the initially assigned default value based on the first token occurring in the header.

15. The system of claim 14, wherein:

the assigned value represents a relevance probability of the first token; and

the segmentation module configures the at least one processor to compute the relevance value of the group of tokens based on the relevance probability of the first token and further based on an irrelevance probability of the first token.