System, method and apparatus for generating phrases from a database

• US 20020188587A1
• 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,697,793 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/3335 Syntactic pre-processing, e.g. stopword elimination, stemming
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A phrase generation is a method of generating sequences of terms, such as phrases, that may occur within a database of subsets containing sequences of terms, such as text. A database is provided and a relational model of the database is created. A query is then input. The query includes a term or a sequence of terms or multiple individual terms or multiple sequences of terms or combinations thereof. Next, several sequences of terms that are contextually related to the query are assembled from contextual relations in the model of the database. The sequences of terms are then sorted and output. Phrase generation can also be an iterative process used to produce sequences of terms from a relational model of a database.

Claims

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

providing a database;

creating a relational model of the database;

inputting a query;

determining a plurality of phrases from the relational model of the database wherein each one of the plurality of phrases is contextually related to the query;

sorting the plurality of phrases; and

outputting the sorted plurality of phrases.

2. The method as recited in claim 1 further comprising, providing a plurality of stopterms.

3. The method as recited in claim 1 wherein, the query includes at least one of a group consisting of:

a plurality of terms; and

a plurality of phrases.

4. The method as recited in claim 1 wherein, inputting the query includes setting an initial threshold weight.

5. The method as recited in claim 1 wherein, inputting the query includes setting an initial weight for each term and phrase of the input query.

6. The method as recited in claim 1 wherein, inputting the query includes setting a pre-selected number of phrases to be output.

7. The method as recited in claim 1 wherein, determining a plurality of phrases from the relational model of the database wherein each one of the plurality of phrases is contextually related to the query includes setting a weight of the input query to an initial threshold level.

8. The method as recited in claim 7 further comprising, replacing a phrase list (PL) with the query.

9. The method as recited in claim 8 further comprising:

selecting a first one of the plurality of relations from the model of the database.

10. The method as recited in claim 9 further comprising:

selecting a first term from the selected relation;

identifying the selected term as a contained term; and

identifying the second term of the selected relation as an appended term.

11. The method as recited in claim 10 further comprising, determining if contained term is included in the plurality of base phrases in the PL.

12. The method as recited in claim 11 wherein, if the selected term is included in PL, then selecting a base phrase from the PL, wherein the selected base phrase includes the contained term.

13. The method as recited in claim 12 wherein, if the selected term is not included in PL, then determining if the second term in the selected relation has been processed as a contained term.

14. The method as recited in claim 12 further comprising, concatenating the selected base phrase and the appended term into two candidate phrases, wherein a first candidate phrase includes the selected base phrase followed by the appended term and a second candidate phrase includes the appended term followed by the selected base phrase.

15. The method as recited in claim 14 further comprising:

updating a conditional phrase list (CPL); and

selecting the first candidate phrase.

16. The method as recited in claim 15 further comprising, determining if a number of links in the selected phrase is equal to the number of terms in the base phrase.

17. The method as recited in claim 16 wherein, determining if a number of links in the selected phrase is equal to the number of terms in the base phrase includes:

if a number of links is not equal to the number of terms in the base phrase, then determining if the second candidate phrase has been selected for processing;

if a number of links is equal to the number of terms in the base phrase, then determining if the all link weights in the selected candidate phrase are greater than zero;

if the all link weights in the selected candidate phrase are greater than zero then including the selected candidate phrase in an interim phrase list (IPL) and then determining if the second candidate phrase has been selected for processing; and

if the all link weights in the selected candidate phrase are not greater than zero then deleting the selected phrase and determining if the second candidate phrase has been selected for processing.

18. The method as recited in claim 17 wherein, determining if the second candidate phrase has been selected for processing includes:

if the second candidate phrase has not been selected for processing, then select the second candidate phrase and repeat the process starting with claim 16.

if the second candidate phrase has been selected for processing, then determining if there is a subsequent phrase in the PL that contains the contained term.

19. The method as recited in claim 18 wherein, selecting the first candidate phrase includes:

determining if the number of stopterms in the selected candidate phrase is greater than a pre-selected number;

if the number of stopterms in the selected candidate phrase is greater than a pre-selected number, then;

deleting the selected candidate phrase; and

determining if the second candidate phrase has been selected for processing

if the number of stopterms in the selected candidate phrase is not greater than a pre-selected number, then continue the process at claim 16.

20. The method as recited in claim 18 wherein, determining if there is a subsequent phrase in the PL that contains the contained term includes:

if there is a subsequent phrase in the PL that contains the contained term, then;

selecting the subsequent phrase; and

repeating the process beginning at claim 14.

if there is not a subsequent phrase in the PL that contains the contained term, then determining if the second term in the selected relation has been processed as a contained term.

21. The method as recited in claim 20 wherein, if the second term in the selected relation has not been processed as a contained term, then:

identifying the second term of the selected relation as the contained term;

identifying the first term of the relation as the appended term; and

repeating the process beginning with claim 11.

22. The method as recited in claim 21 wherein, if the second term in the selected relation has been processed as a contained term, then:

determining if there is a subsequent relation in the model of the database;

if there is a subsequent relation, then;

selecting the subsequent relation; and

repeating the process beginning with claim 10; and

23. The method as recited in claim 22 wherein, if there is not a subsequent relation in the model of the database then:

eliminating any duplicate phrases in an interim phrase list (IPL); and

determining if a number of phrases in IPL is greater than zero.

24. The method as recited in claim 23 further including:

filtering each one of the phrases in the IPL based on the weight of the phrase.

25. The method as recited in claim 24 wherein, if a number of phrases in IPL is greater than zero, then:

adding phrases in IPL to interim buffer (IB);

replacing the phrases in the PL with the phrases in the IPL; and

repeating the process beginning at claim 9.

26. The method as recited in claim 24 wherein, if a number of phrases in IPL is not greater than zero, then

determining if a number of phrases in interim buffer is greater than or equal to a pre-selected number.

27. The method as recited in claim 26 wherein, if the number of phrases in interim buffer is less than the pre-selected number, then:

reducing the threshold weight; and

repeating the process beginning at claim 8.

28. The method as recited in claim 26 wherein, if the number of phrases in interim buffer is greater than or equal to the pre-selected number, then outputting the phrases in the interim buffer.

29. The method as recited in claim 28 wherein, outputting the phrases in the interim buffer includes sorting the phrases in the interim buffer.

30. The method as recited in claim 15 wherein, updating a conditional phrase list includes:

processing a first one of the two candidate phrases having the steps of;

selecting the first candidate phrase;

determining if the selected candidate phrase is included in the CLP;

setting a corresponding count of known relations; and

determining a weight of the candidate phrase in the CLP; and

processing the second candidate phrase.

31. The method as recited in claim 30 wherein, if the selected candidate phrase is included in the CLP then increment the corresponding count of known relations.

32. The method as recited in claim 31 further including, assigning a weight of the candidate phrase equal to the lesser of a current weight of the candidate phrase or a weight of a corresponding directional metric of the selected relation.

33. The method as recited in claim 30 further including, if the selected candidate phrase is not included in the CLP, then including the selected candidate phrase in the CLP and setting the corresponding count of known relations to one.

34. The method as recited in claim 33 further including, assigning a weight of the candidate phrase equal to the lesser of a weight of the base phrase or a weight of a corresponding directional metric of the selected relation.