×

Graph-based ranking algorithms for text processing

  • US 7,809,548 B2
  • Filed: 03/09/2005
  • Issued: 10/05/2010
  • Est. Priority Date: 06/14/2004
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method of processing at least one natural language text using a graph, comprising:

  • selecting, using a processing unit, a plurality of text units from said at least one natural language text;

    associating, using the processing, unit, the plurality of text units with a plurality of graph nodes such that each graph node corresponds to one of the text units selected from said at least one natural language text;

    determining, using the processing unit, at least one connecting relation between at least two of the plurality of text units;

    associating, using the processing unit, the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes;

    constructing, using the processing unit, a graph using only the plurality of graph nodes that correspond to one of the text units selected from said at least one natural language text and said at least one graph edge; and

    determining, using the processing unit, at least one ranking by applying a graph-based ranking algorithm to the graph, wherein determining the at least one ranking comprises ranking the plurality of graph nodes based upon the at least one graph edge so that the ranking represents the relative importance, within the natural language text, of the text units associated with the graph nodes, and wherein ranking the plurality of graph nodes based upon the at least one graph edge comprises;

    assigning a plurality of first scores to the plurality of graph nodes;

    defining a relationship between a second score of each graph node and second scores, of graph nodes coupled to each graph node by a graph edge; and

    determining a plurality of second scores associated with the plurality of graph nodes by applying an iterative recursive algorithm starting with the first plurality of scores and iterating until the relationship is satisfied.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×