US 6,721,728 B2 · System, method and apparatus for discovering phrases in a database · patentgrep

Loading patent…

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.

Claims50

Dependent claims

A method of discovering phrases from a database comprising:

providing a selection of text;
extracting a plurality of phrases from the provided text, by a proces comprising:
determining a plurality of phrase processing positions within the selection of text, by a process comprising;
determining a plurality of phase processing starting positions within the selection of text, by a process comprising:
identifying a phrase starting position (T1);
initializing values for an iterative process by a process comprising setting an interior stopterm counter to zero and setting a tuple size to two;
determining a plurality of phrase processing ending positions within the selection of relevant text, by a process comprising:
identifying a phrase ending position (T2);
identifying a position immediately subsequent to the phrase ending position T2 as the phrase ending position T2;
extracting a plurality of phrases, wherein the first position of each of the plurality of phrases is one of the plurality of phrase processing starting positions (T1) and the last position of each of the plurality of phrases is a one of the plurality of phrase processing ending positions (T2), by a process comprising:
identifying an indicated phrase, wherein an indicated phrase is a sequence of positions staffing at T1 and ending at T2;
determining a tuple size, wherein tuple size is a count of positions within the indicated phrase;
determining if the tuple size is greater than a maximum phrase length, and when the tuple size is not greater than the maximum phrase length, outputting the indicated phrase as an extracted phrase;
culling the extracted plurality of phrases;
gathering a plurality of phrases, wherein the gathered plurality of phrases are related by relevance to a plurality of contextual patterns included within and among the culled and extracted plurality of phrases;
and
outputting the plurality of gathered phrases.

14 more elements

A method of discovering phrases from a database comprising:

(A) providing a set of text;
(B) extracting a plurality of phrases from the provided text by a process comprising determining a plurality of phrase processing starting positions within a selection of text, and extracting the plurality of phrases wherein, each of the plurality of extracted phrases begins at one of the plurality of starting positions by a process comprising:
(B-1) identifying a first term in the text as a term T1 and a term T2;
(B-2) determining if at least one term subsequent to T1 exists in the text;
(B-3) when at least one term subsequent to T1 exists in the text, determining if T1 is a stopterm;
(B-4) when T1 is a stopterm, identifying the at least one subsequent term as a term T1 and term T2;
and returning to step (B-2);
(B-5) when T1, is not a stopterm, (a) saving T1 as a single term phrase in a phrase list, (b) extracting a plurality of multi-term phrases wherein, each of the plurality of extracted multi-term phrases begins at starting position T1, (c) identifying the at least one term subsequent to T1 as term T1 and term T2, and (d) returning to step (B-2);
(B-6) when at least one term subsequent to T1 does not exist in the text, determining if T1 is a stopterm;
(B-7) when T1 is a stopterm, continuing to step (B-9);
(B-8) when T1 is not a stopterm, saving T1 as a single term phrase in the phrase list, and continuing to step (B-9);
and
(B-9) outputting the phrase list containing the extracted plurality of phrases;
(C) cuffing the extracted plurality of phrases;
(D) gathering a plurality of phrases, wherein the gathered plurality of phrases are related to the culled and extracted plurality of phrases;
and
(E) outputting the plurality of gathered phrases.

14 more elements

A method of discovering phrases from a database comprising:

(A) providing a set of text;
(B) extracting a plurality of phrases from the provided text by a process comprising determining a plurality of phrase processing starting positions within a selection of text, and extracting the plurality of phrases wherein, each of the plurality of extracted phrases begins at one of the plurality of starting positions by a process comprising:
(B-1) identifying a first term in the text as a term T1 and a term T2;
(B-2) determining if at least one term subsequent to T1 exists in the text;
(B-3) when at least one term subsequent to T1 exists in the text, determining if T1 is a stopterm by a process comprising;
(B-3-a) when T1 is a starting stopterm, identifying the at least one subsequent term as a term T1 and term T2;
and returning to step (B-2);
and
(B-3-b) when T1 is not a starting stopterm, (a) saving T1 as a single term phrase in a phrase list, (b) extracting a plurality of multi-term phrases wherein, each of the plurality of extracted multi-term phrases begins at starting position T1, (c) identifying the at least one term subsequent to T1 as term T1 and term T2, and (d) returning to step (B-2);
(B-4) when T1 is a stopterm, identifying the at least one subsequent term as a term T1 and term T2;
and returning to step (B-2);
(B-5) when T1 is not a stopterm, (a) saving T1 as a single term phrase in a phrase list, (b) extracting a plurality of multi-term phrases wherein, each of the plurality of extracted multi-term phrases begins at starting position T1, (c) identifying the at least one term subsequent to T1 as term T1 and term T2, and (d) returning to step (B-2);
(B-6) when at least one term subsequent to T1 does not exist in the text, determining if T1 is a stopterm;
(B-7) when T1 is a stopterm, continuing to step (B-9);
(B-8) when T1 is not a stopterm, saving T1 as a single term phrase in the phrase list, and continuing to step (B-9);
and
(B-9) outputting the phrase list containing the extracted plurality of phrases;
(C) culling the extracted plurality of phrases;
(D) gathering a plurality of phrases, wherein the gathered plurality of phrases are related to the culled and extracted plurality of phrases;
and
(B) outputting the plurality of gathered phrases.

18 more elements

A method of discovering phrases from a database comprising:

(A) providing a set of text;
(B) extracting a plurality of phrases from the provided text by a process comprising determining a plurality of phrase processing starting positions within a selection of text, and extracting the plurality of phrases wherein, each of the plurality of extracted phrases begins at one of the plurality of starting positions by a process comprising;
(B-1) identifying a first term in the relevant text as a term T1 and a term T2;
(B-2) determining if at least one term subsequent to T1 exists in the relevant text;
(B-3) when at least one term subsequent to T1 exists in the relevant text, determining if T1 is a stopterm;
(B-4) when T1 is a stopterm, identifying the at least one subsequent term as a term T1 and term T2;
and returning to step (B-2);
(B-5) when T1 is not a stopterm, (a) saving T1 as a single term phrase in a phrase list, (b) extracting a plurality of multi-term phrases wherein, each of the plurality of extracted multi-term phrases begins at starting position, (c) identifying the at least one term subsequent to T1 as term T1 and term T2, and (d) returning to step (B-2), wherein the process of extracting the plurality of multi-term phrases comprises:
(B-5-b-i) initializing a counter of interior stopterms to 0, and setting a tuple size equal to 2;
(B-5-b-ii) identifying the term subsequent to said T2 as T2;
(B-5-b-iii) determining if the tuple size is greater than a selected maximum phrase length;
(B-5-b-iv) when the tuple size is not greater than the selected maximum phrase length, determining if said 172 is a stopterm;
(B-5-b-v) when the tuple size is not greater than the selected maximum phrase length, and said T2 is not a stopterm, saving said phrase and continuing to step (B-5-b-x);
(B-5-b-vi) when the tuple size is not greater than the selected maximum phrase length, and said T2 is a stopterm, incrementing by 1 the counter of interior stopterms and determining if the interior stopterm counter value is greater than a selected number of interior stopterms;
(B-5-b-vii) when the tuple size is not greater than the selected maximum phrase length, and said T2 is a stopterm and the interior stopterm counter value is not greater than a selected number of stopterms, continuing to step (B-5-b-x);
(B-5-b-viii) when the tuple size is not greater than the selected maximum phrase length, and said T2 is a stopterm and the interior stopterm counter value is greater than a selected number of stopterms, ending said sub-process of said step (B-5-b);
(B-5-b-ix) when the tuple size is greater than the selected maximum phrase length, ending said sub-process of said step (B-5-b);
(B-5-b-x) incrementing by 1 the tuple size, and determining if there is a term subsequent to T2 in said text;
(B-5-b-xi) when there is no term subsequent to T2 in said relevant text, ending the sub-process of said step (B-5-b);
and
(B-5-b-xii) when there is a term subsequent to T2 in said relevant text, returning to step (B-5-b-ii);
(B-6) when at least one term subsequent to T1 does not exist in the text, determining if T1 is a stopterm;
(B-7) when T1 is a stopterm, continuing to step (B-9);
(B-8) when T1 is not a stopterm, saving T1 as a single term phrase in the phrase list, and continuing to step (B-9);
and
(B-9) outputting the phrase list containing the extracted plurality of phrases;
(C) culling the extracted plurality of phrases;
(D) gathering a plurality of phrases, wherein the gathered plurality of phrases are related to the culled and extracted plurality of phrases;
and
(E) outputting the plurality of gathered phrases.

27 more elements

A method of discovering phrases from a database comprising:

(A) providing a set of text;
(B) extracting a plurality of phases from the provided text by a process comprising determining a plurality of phrase processing starting positions within a selection of text, and extracting the plurality of phrases wherein, each of the plurality of extracted phrases begins at one of the plurality of starting positions by a process comprising:
(B-1) identifying a first term in the text as a term T1 and a term T2;
(B-2) determining if at least one term subsequent to T1 exists in the text;
(B-3) when at least one term subsequent to T1 exists in the text, determining if T1 is a stopterm;
(B-4) when T1 is a stopterm, identifying the at least one subsequent term as a term T1 and term T2;
and returning to step (B-2);
(B-5) when T1 is not a stopterm, (a) saving T1 as a single term phrase in a phrase list, (b) extracting a plurality of multi-term phrases wherein, each of the plurality of extracted multi-term phrases begins at starting position T1, (c) identifying the at least one term subsequent to T1 as term T1 and term T2, and (d) returning to step (B-2), wherein the process of extracting the plurality of multi-term phrases at the phrase starting position comprises:
(B-5-b-i) initializing a counter of interior stopterms to 0, and setting a tuple size equal to 2;
(B-5-b-ii) identifying the term subsequent to the T2 as T2;
(B-5-b-iii) determining if the tuple size is greater than a selected maximum phrase length;
(B-5-b-iv) when the tuple size is greater than the selected maximum phrase length, ending the sub-process of step (B-5-b-i);
(B-5-b-v) when the tuple size is not greater than the selected maximum phrase length, determining if the T2 is an interior stopterm;
(B-5-b-vi) when the tuple size is not greater than the selected maximum phrase length, and T2 is not an interior stopterm, determining if T2 is an ending stopterm;
(B-5-b-vii) when the tuple size is not greater than the selected maximum phrase length, and the T2 is not an interior stopterm, and T2 is not an ending stopterm, saving the phrase and continuing to step (B-5-b-xiv);
(B-5-b-vii) when the tuple size is not greater than the selected maximum phrase length and T2 is not an interior stopterm and T2 is an ending stopterm, determining if T2 is an interior-only term;
(B-b-5-ix) when the tuple size is not greater than the selected maximum phrase length and T2 is not an interior stopterm and T2 is an ending stopterm and T2 is an interior-only term, continuing to step (B-5-b-xiv);
(B-5-b-x) when the tuple size is not greater than the selected maximum phrase length and T2 is not an interior stopterm and T2 is an ending stopterm and T2 is not an interior-only term, ending the sub-process of step (B-5);
(B-5-b-xi) when the tuple size is not greater than the selected maximum phrase length and T2 is an interior stopterm, incrementing by 1 the interior stopterm counter and determining if the interior stopterm count is greater than a selected number of interior stopterms;
(B-5-b-xii) when the tuple size is not greater than the selected maximum phrase length and T2 is an interior stopterm and the interior stopterm count is greater than the selected number of interior stopterms, ending the sub-process of step (B-5);
(B-5-b-xiii) when the tuple size is not greater than the selected maximum phrase length and T2 is an interior stopterm and the interior stopterm count is not greater than the selected number of interior stopterms, continuing to step (B-5-b-xiv);
(B-5-b-xiv) incrementing by 1 the tuple size, and determining if there is a term subsequent to T2 in the text;
(B-5-b-xv) when there is no term subsequent to T2 in the text, ending the sub-process of step (B-5);
and
(B-5-b-xvi) when there is a term subsequent to T2 in the text, returning to step (B-5-b-ii);
(B-6) when at least one term subsequent to T1 does not exist in the text, determining if T1 is a stopterm;
(B-7) when T1 is a stopterm, continuing to step (B-9);
(B-8) when T1 is not a stopterm, saving T1 as a single term phrase in the phrase list, and continuing to step (B-9);
and
(B-9) outputting the phrase list containing the extracted plurality of phrases;
(C) culling the extracted plurality of phrases;
(D) gathering a plurality of phrases, wherein the gathered plurality of phrases are related to the culled and extracted plurality of phrases;
and
(E) outputting the plurality of gathered phrases.

31 more elements

Dependencies are inferred from the claim text.

Facts

Application: 09/800,310Filed 2 Mar 2001
Published: US 2002/0188599 A112 Dec 2002
Granted: 13 Apr 2004
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 16/2465
Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries: query processing support for facilitating data mining…
G06F 16/3337
Query translation: translation of the query language, e.g. Chinese to English
Y10S 707/99933
Database or file accessing: query processing, i.e. searching
Y10S 707/99936
Query processing, i.e. searching: pattern matching access

Family

US 2002/0188599 A1Pre-grant publication · published 12 Dec 2002
US 6,721,728 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere