System, method and apparatus for discovering phrases in a database

• US 20020188599A1
• Filed: 03/02/2001
• Published: 12/12/2002
• Est. Priority Date: 03/02/2001
• Status: Active Grant

• Current Assignee: U.S.A. as represented by the Administrator of the National Aeronautics and Space Administration
• Original Assignee: U.S.A. as represented by the Administrator of the National Aeronautics and Space Administration
• Inventors: McGreevy, Michael W.
• Granted Patent: US 6,721,728 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/3337 Translation of the query language, e.g. Chinese to English
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A phrase discovery is a method of identifying sequences of terms in a database. First, a selection of one or more relevant sequences of terms, such as relevant text, is provided. Next, several shorter sequences of terms, such as phrases, are extracted from the provided relevant sequences of terms. The extracted sequences of terms are then reduced through a culling process. A gathering process then emphasizes the more relevant of the extracted and culled sequences of terms and de-emphasizes the more generic of the extracted and culled sequences of terms. The gathering process can also include iteratively retrieving additional selections of relevant sequences (e.g., text), extracting and culling additional sequences of terms (e.g., phrases), emphasizing and de-emphasizing extracted and culled sequences of terms and accumulating all gathered sequences of terms. The resulting gathered sequences of terms are then output.

Claims

1. A method of discovering phrases from a database comprising:

providing a set of relevant text;

extracting a plurality of phrases from the provided text;

culling the extracted plurality of phrases;

gathering a plurality of phrases, wherein the gathered plurality of phrases are related to the culled and extracted plurality of phrases; and

outputting the plurality of gathered phrases.

2. The method as recited in claim 1 wherein, extracting phrases includes:

determining a plurality of phrase processing starting positions within a selection of relevant text;

extracting a plurality of phrases wherein, each one of the plurality of extracted phrases start at one of the plurality of starting positions; and

outputting a phrase list.

3. The method as recited in claim 2 wherein, determining a plurality of phrase processing starting positions within the selection of relevant text includes:

selecting a first term in the relevant text; and

identifying the selected term as T1 and T2.

4. The method as recited in claim 3 wherein, determining a plurality of phrase processing starting positions within the selection of relevant text includes determining if there is a term subsequent to T1.

5. The method as recited in claim 4 wherein, if there is a term subsequent to T1, then determining if T1 is a stopterm.

6. The method as recited in claim 5 wherein, if T1 is a stopterm, then identifying the subsequent term as T1 and T2 and repeating the process beginning at claim 4.

7. The method as recited in claim 5 wherein, a stopterm includes at least one of a group consisting of a starting stopterm, an interior stopterm, and an ending stopterm.

8. The method as recited in claim 4 wherein, if there is not a term subsequent to T1, then determining if T1 is a stopterm.

9. The method as recited in claim 8 wherein, a stopterm includes at least one of a group consisting of a starting stopterm, an interior stopterm, and an ending stopterm.

10. The method as recited in claim 8 wherein, if T1 is not a stopterm, then determining if a single term phrase is acceptable.

11. The method as recited in claim 10 wherein, if a single term phrase is acceptable, then determining if a current phrase is included in a phrase list (PL), wherein the current phrase begins at term T1 and ends at term T2.

12. The method as recited in claim 11 wherein, if the current phrase is included in a phrase list (PL), then incrementing a corresponding frequency counter.

13. The method as recited in claim 11 wherein, if the current phrase is not included in a phrase list (PL), then including the current phrase in the PL and setting a corresponding frequency counter to 1.

14. The method as recited in claim 5 wherein, if T1 is not a stopterm then, determining if a single term phrase is acceptable.

15. The method as recited in claim 14 wherein, if a single term phrase is acceptable, then determining if a current phrase is included in a phrase list (PL), wherein the current phrase begins at term T1 and ends at term T2.

16. The method as recited in claim 15 wherein, if the current phrase is included in a phrase list (PL), then incrementing a corresponding frequency counter.

17. The method as recited in claim 15 wherein, if the current phrase is not included in a phrase list (PL), then including the current phrase in the PL and setting a corresponding frequency counter to 1.

18. The method as recited in claim 4 wherein, if there is not a term subsequent to T1, then outputting the phrase list.

19. The method as recited in claim 2 wherein, extracting a plurality of phrases includes:

setting an interior stopterm counter to zero; and

setting a tuple size to two.

20. The method as recited in claim 19 wherein, extracting a plurality of phrases further includes:

identifying the term subsequent to T2 as T2; and

determining if the tuple size is greater than a maximum phrase length.

21. The method as recited in claim 20 wherein, if the tuple size is greater than a maximum phrase length, then:

identifying the term subsequent to T1 as T1 and T2; and

repeating the process beginning at claim 4.

22. The method as recited in claim 20 wherein, if the tuple size is not greater than a maximum phrase length, then determining if T2 is a stopterm.

23. The method as recited in claim 22 wherein, a stopterm includes at least one of a group consisting of a starting stopterm, an interior stopterm, and an ending stopterm.

24. The method as recited in claim 22 wherein, if T2 is a stopterm, then:

incrementing the interior stopterm counter; and

determining if the stopterm counter is greater than a pre-selected number of stopterms.

25. The method as recited in claim 24 wherein, if an interior stopterm counter is greater than a pre-selected number of interior stopterms, then:

identifying the term subsequent to T1 as T1 and T2; and

repeating the process beginning at claim 4.

26. The method as recited in claim 24 wherein, if an interior stopterm counter is not greater than a pre-selected number of interior stopterms, then:

incrementing the tuple size; and

determining if there is a term subsequent to T2 in the relevant text.

27. The method as recited in claim 26 wherein, if there is a term subsequent to T2 in the relevant text, then repeat the process beginning at claim 18.

28. The method as recited in claim 26 wherein, if there is not a term subsequent to T2 in the relevant text, then:

identifying the term subsequent to T1 as T1 and T2; and

repeating the process beginning at claim 4.

29. The method as recited in claim 22 wherein, if T2 is not a stopterm, then:

determining if a current phrase is included in a phrase list (PL), wherein the current phrase begins at term T1 and ends at term T2;

if the current phrase is included in a phrase list (PL), then incrementing a corresponding frequency counter; and

if the current phrase is not included in a phrase list (PL), then including the current phrase in the PL and setting a corresponding frequency counter to 1; and

repeating the process beginning at claim 23.

30. The method as recited in claim 23 wherein, if T2 is not an interior stopterm, then determining if T2 is an ending stopterm.

31. The method as recited in claim 30 wherein, if T2 is not an ending stop term, then:

determining if the current phrase is included in a phrase list (PL) wherein the current phrase begins at term T1 and ends at term T2;

if the current phrase is included in the PL, then incrementing a corresponding frequency counter; and

if the current phrase is not included in the PL, then including the current phrase in the PL and setting the corresponding frequency counter to 1; and

repeating the process beginning at claim 26.

32. The method as recited in claim 30 wherein, if T2 is an ending stopterm, then:

determining if T2 is an interior-only term;

if T2 is an interior-only term, then, repeating the process beginning at claim 23; and

if T2 is not an interior-only term, then identifying the term subsequent to T1 and T1 and T2, and repeating the process beginning at 4.

33. The method as recited in claim 1 wherein, culling the extracted plurality of phrases includes identifying a first phrase from a candidate phrase list (CPL) as P1.

34. The method as recited in claim 33 further including:

identifying a plurality of phrases from the CPL, wherein P1 is a proper subset of each one of the plurality of phrases;

identifying a first phrase from the plurality of phrases having P1 as a proper subset, as P2.

35. The method as recited in claim 34 further including, comparing the frequency of P1 and P2.

36. The method as recited in claim 35 wherein, if the frequency of P1 is not equal to the frequency of P2, then determining if there is a subsequent phrase to P2 in the plurality of phrases having P1 as a proper subset.

37. The method as recited in claim 36 wherein, if there is a subsequent phrase to P2 in the plurality of phrases having P1 as a proper subset, then:

identifying the subsequent phrase as P2; and

repeating the process beginning at claim 35.

38. The method as recited in claim 36 wherein, if there is not a subsequent phrase to P2 in the plurality of phrases having P1 as a proper subset, then determining if there is a phrase subsequent to P1 in the CPL.

39. The method as recited in claim 38 Wherein, if there is a phrase subsequent to P1 in the CPL, then identifying the subsequent phrase as P1 and repeating the process beginning at claim 34.

40. The method as recited in claim 38 wherein, if there is not a phrase subsequent to P1 in the CPL, then outputting the plurality of phrases in the CPL.

41. The method as recited in claim 35 wherein, if the frequency of P1 is equal to the frequency of P2, then:

eliminating P1 from the CPL; and

determining if there is a phrase subsequent to P2 in the CPL.

42. The method as recited in claim 41 wherein, if there is a phrase subsequent to P1 in the CPL, then identifying the subsequent phrase as P1 and repeating the process beginning at claim 34.

43. The method as recited in claim 41 wherein, if there is not a phrase subsequent to P1 in the CPL, then outputting the plurality of phrases in the CPL.

44. The method as recited in claim 1 wherein, gathering a plurality of phrases includes:

initiating a gathered phrase list (GPL), wherein the GPL is empty upon initiation; and

ranking the plurality of phrases output from the extracting and culling processes.

45. The method as recited in claim 44 further including:

creating a combined plurality of phrases including the ranked plurality of phrases from the extracting and culling processes and any phrases contained in the GPL;

storing the combined plurality of phrases in the GPL;

incrementing a phrase search counter; and

determining if the phrase search counter is greater than a pre-selected number of phrase searches.

46. The method as recited in claim 45 wherein, if the phrase search counter is greater than a pre-selected number of phrase searches, then the GPL is output.

47. The method as recited in claim 45 wherein, if the phrase search counter is not greater than a pre-selected number of phrase searches, then:

performing a phrase search on a database, wherein the GPL is input as a single query having a plurality of phrases and wherein the database includes relevant data;

outputting a ranked list of subsets of the database;

extracting a plurality of phrases from the ranked list of subsets; and

culling the extracted plurality of phrases.

48. The method as recited in claim 47 further including:

ranking the plurality of phrases output from the extracting and culling processes; and

repeating the process beginning at claim 45.