Graph-based ranking algorithms for text processing

• US 20050278325A1
• Filed: 03/09/2005
• Published: 12/15/2005
• Est. Priority Date: 06/14/2004
• Status: Active Grant

• Current Assignee: University of North Texas
• Original Assignee: University of North Texas
• Inventors: Mihalcea, Rada, Tarau, Paul
• Granted Patent: US 7,809,548 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

The present invention provides a method of processing at least one natural language text using a graph. The method includes determining a plurality of text units based upon the natural language text, associating the plurality of text units with a plurality of graph nodes, and determining at least one connecting relation between at least two of the plurality of text units. The method also includes associating the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes and determining a plurality of rankings associated with the plurality of graph nodes based upon the at least one graph edge. The method can also include a graphical visualization of at least one important text unit in a natural language text or collection of texts. Methods for word sense disambiguation, keyword extraction, and sentence extraction are also provided.

Claims

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

determining a plurality of text units based upon the natural language text;

associating the plurality of text units with a plurality of graph nodes;

determining at least one connecting relation between at least two of the plurality of text units;

associating the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes; and

determining at least one ranking based on at least one of the plurality of graph nodes and the at least one graph edge.

2. The method of claim 1, wherein determining the at least one ranking comprises determining a plurality of rankings associated with the plurality of graph nodes based upon the at least one graph edge.

3. The method of claim 2, wherein determining the plurality of rankings associated with the plurality of graph nodes based upon the at least one graph edge comprises:

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

determining a second plurality of scores associated with the plurality of graph nodes by applying an iterative recursive algorithm to the first plurality of scores based upon the at least one graph edge.

4. The method of claim 3, wherein determining the plurality of rankings comprises sorting the second plurality of scores to produce a plurality of rankings associated with the plurality of graph nodes.

5. The method of claim 1, wherein determining the at least one ranking comprises determining at least one ranking associated with the at least one graph edge based upon the plurality of graph nodes.

6. The method of claim 5, wherein determining the at least one ranking associated with the at least one graph edge based upon the plurality of graph nodes comprises:

assigning at least one score to the at least one graph edge; and

determining at least one second score associated with the at least one graph edge by applying an iterative recursive algorithm to the at least one first score based upon the plurality of graph nodes.

7. The method of claim 6, wherein determining the at least one ranking comprises sorting the at least one second score to produce at least one ranking associated with the at least one graph edge.

8. The method of claim 1, further comprising selecting at least one word sense associated with at least one of the plurality of text units based upon the at least one ranking.

9. The method of claim 1, further comprising selecting at least one keyword from the plurality of text units based upon the at least one ranking.

10. The method of claim 1, wherein the plurality of text units comprises a plurality of sentences, and comprising selecting at least one of the plurality of sentences based upon the at least one ranking.

11. The method of claim 10, further comprising forming a summary of the natural language text using the at least one selected sentence.

12. The method of claim 10, further comprising forming at least one summary of a plurality of natural language texts based upon a plurality of rankings associated with the plurality of sentences in the plurality of texts.

13. A method of disambiguating word senses in at least one natural language text using a graph, comprising:

determining a plurality of text units based upon the natural language text;

associating at least one word sense with each text unit;

associating the plurality of word senses with a plurality of graph nodes;

determining at least one connecting relation between at least two of the plurality of word senses;

associating the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes;

determining a plurality of rankings associated with the plurality of graph nodes based upon the at least one graph edge; and

selecting one word sense for each text unit based on the plurality of rankings.

14. The method of claim 13, wherein determining the plurality of text units based upon the natural language text comprises selecting a plurality of open-class words from the natural language text.

15. The method of claim 13, wherein associating at least one word sense with each text unit comprises determining at least one of a synonym word, word phrase, concept, and a definition associated with each text unit.

16. The method of claim 15, wherein determining the at least one synonym word, word phrase, concept, or definition comprises determining the at least one synonym word, word phrase, concept, or definition based upon a lexical knowledge base.

17. The method of claim 13, wherein determining the at least one connecting relation between at least two of the plurality of word senses comprises determining the at least one connecting relation between at least two of the plurality of word senses based upon a semantic, lexical, or syntactic relation.

18. The method of claim 17, wherein determining the at least one connecting relation between at least two of the plurality of word senses based upon the semantic, lexical, or syntactic relation comprises determining the at least one connecting relation between at least two of the plurality of word senses based on hypernymy, hyponomy, meronomy, holonomy, entailment, causality, attribute, and pertainimy, or based on co-occurrence information from a raw or annotated corpus.

19. The method of claim 18, wherein determining the at least one connecting relation between at least two of the plurality of word senses comprises forming a coordinate connecting relation based on a plurality of semantic relations.

20. The method of claim 13, wherein determining the at least one connecting relation between at least two of the plurality of word senses comprises forming a connecting relation between co-occurring text units.

21. The method of claim 13, wherein determining the plurality of rankings associated with the plurality of graph nodes based upon the at least one graph edge comprises:

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

determining a second plurality of scores associated with the plurality of graph nodes by applying an iterative recursive algorithm to the first plurality of scores based upon the at least one graph edge.

22. The method of claim 13, wherein selecting one word sense for each text unit based on the plurality of rankings comprises selecting the word sense having the highest ranking associated with each text unit.

23. The method of claim 13, wherein selecting one word sense for each text unit based on the plurality of rankings comprises selecting one word sense for each text unit based on the plurality of rankings and at least one of a Lesk algorithm and a sense frequency.

24. The method of claim 13, wherein selecting one word sense for each text unit based on the plurality of rankings comprises selecting one word sense for each text unit using at least one of an uninformed and an informed algorithm.

25. A method of keyword extraction from at least one natural language text using a graph, comprising:

determining a plurality of text units based upon the natural language text;

associating the plurality of text units with a plurality of graph nodes;

determining at least one connecting relation between at least two of the plurality of text units;

associating the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes;

determining a plurality of rankings associated with the plurality of graph nodes based upon the at least one graph edge; and

determine at least one keyword based on the plurality of text units and the plurality of rankings.

26. The method of claim 25, wherein determining the plurality of text units based upon the natural language text comprises determining at least one sequence of at least one lexical unit extracted from the natural language text.

27. The method of claim 25, wherein associating the plurality of text units with the plurality of graph nodes comprises associating the plurality of text units with the plurality of graph nodes based upon at least one syntactic or lexical filter.

28. The method of claim 25, wherein determining at least one connecting relation between at least two of the plurality of text units comprises determining at least one connecting relation based on a co-occurrence relation.

29. The method of claim 25, wherein determining at least one connecting relation based on the co-occurrence relation comprises determining the at least one connecting relation based on a co-occurrence relation controlled by a distance between word occurrences.

30. The method of claim 25, wherein determining the plurality of rankings associated with the plurality of graph nodes based upon the at least one graph edge comprises:

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

determining a second plurality of scores associated with the plurality of graph nodes by applying an iterative recursive algorithm to the first plurality of scores based upon the at least one graph edge.

31. The method of claim 25, wherein determining at least one keyword based on the plurality of text units and the plurality of rankings comprises sorting the graph nodes based upon the plurality of rankings.

32. The method of claim 31, wherein determining the at least one keyword comprises selecting at least one keyword based upon the ranking of the graph nodes.

33. The method of claim 32, wherein determining the at least one keyword comprises forming at least one multi-word key word from the selected keywords.

34. The method of claim 33, wherein forming at least one multi-word keyword comprises combining a plurality of adjacent selected keywords.

35. A method of sentence extraction from at least one natural language text using a graph, comprising:

determining a plurality of sentences based upon the natural language text;

associating the plurality of sentences with a plurality of graph nodes;

determining at least one connecting relation between at least two of the plurality of sentences;

associating the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes;

determining a plurality of rankings associated with the plurality of graph nodes based upon the at least one graph edge; and

selecting at least one of the plurality of sentences based on the plurality of text units and the plurality of rankings.

36. The method of claim 35, wherein determining at least one connecting relation between at least two of the plurality of sentences comprises determining at least one connecting relation based upon a similarity relation between the at least two of the plurality of sentences.

37. The method of claim 36, wherein determining at least one connecting relation based upon the similarity relation comprises determining at least one connecting relation as a function of contents overlap between at least two of the plurality of sentences.

38. The method of claim 36, wherein determining at least one connecting relation based upon the similarity relation comprises determining a number of common tokens in the at least two of the plurality of sentences.

39. The method of claim 36, wherein determining at least one connecting relation based upon the similarity relation comprises applying a syntactic or lexical filter to the plurality of sentences.

40. The method of claim 35, wherein associating the at least one connecting relation with at least one graph edge comprises associating a weight with each graph edge.

41. The method of claim 40, wherein associating the weight with each graph edge comprises determining the weight based upon the at least one connecting relation.

42. The method of claim 35, further comprising representing the graph as at least one of an undirected graph, a forward directed graph, and a backward directed graph.

43. The method of claim 35, wherein determining the plurality of rankings associated with the plurality of graph nodes based upon the at least one graph edge comprises:

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

determining a second plurality of scores associated with the plurality of graph nodes by applying an iterative recursive algorithm to the first plurality of scores based upon the at least one graph edge.

44. The method of claim 43, wherein determining the plurality of rankings comprises sorting the sentences in reverse order based upon the second plurality of scores.

45. The method of claim 44, wherein selecting at least one of the plurality of sentences comprises selecting a selected number of sentences having the highest rankings.

46. A method for graphical visualization of a natural language text, comprising:

determining a plurality of text units based upon the natural language text;

associating the plurality of text units with a plurality of graph nodes;

determining at least one connecting relation between at least two of the plurality of text units;

associating the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes;

determining a plurality of rankings associated with the plurality of graph nodes based upon the at least one graph edge; and

providing a visual indication for each text unit based on the plurality of rankings.

47. The method of claim 46, wherein providing the visual indication comprises displaying at least one text unit using at least one color.

48. The method of claim 47, wherein displaying the at least one text unit using at least one color comprises displaying the at least one text unit using a plurality of colors representing the plurality of rankings.

49. The method of claim 46, comprising:

determining at least one keyword based on the plurality of text units and the plurality of rankings; and

providing at least one visual indication associated with the at least one keyword.

50. The method of claim 46, comprising:

selecting at least one sentence based on the plurality of text units and the plurality of rankings; and

providing at least one visual indication associated with the at least one sentence.