Complex queries for corpus indexing and search

• US 8,266,169 B2
• Filed: 12/18/2008
• Issued: 09/11/2012
• Est. Priority Date: 12/18/2008
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Bobrow, Daniel G, Cheslow, Robert D
• Primary Examiner(s): Vu, Bai D.
• Application Number:
  US12/338,029
• Publication Number:
  US 20100161639A1
• Time in Patent Office: 1,363 Days
• Field of Search: None
• US Class Current: 707/759
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

Computer methods, apparatus and articles of manufacture therefor, are disclosed for developing a complex-query pattern that is transformed into a region-matching transducer. A corpus-level transducer and the region matching transducer are combined. The combined transducer is applied to a corpus to identify strings therein that satisfy patterns defined in the corpus-level transducer, including the complex-query pattern, with each identified pattern being recorded in a corpus index. The corpus and the corpus index are made available for receiving a query with the query tag for querying the corpus and applying the query using the corpus index to identify locations in the corpus that satisfy the query.

Claims

1. A computer implemented method, comprising:

receiving in a memory a complex-query pattern, wherein the complex-query pattern identifies a relationship between a plurality of words using a query language;

receiving a corpus;

transforming with a processor the complex-query pattern into a region matching transducer, wherein the transducer is a form of a finite state network;

determining whether a corpus index exists;

in response to determining the corpus index does not exist;

combining a corpus-level transducer and the region matching transducer; and

applying the combined transducer to the corpus to identify strings therein that satisfy patterns defined in the corpus-level transducer, including the complex-query pattern, with each identified pattern being recorded in the corpus index;

in response to determining the corpus index exists;

applying the region matching transducer to the corpus to identify strings therein that satisfy the complex-query pattern, with each identified pattern being recorded in an augmented index; and

merging the corpus index with the augmented index specifying locations in the corpus satisfying the complex-query pattern;

storing in the memory the corpus index that records a query tag for indexing locations in the corpus satisfying the complex-query pattern.

2. The method according to claim 1, further comprising developing the complex-query pattern using a reduced corpus that contains a portion of the corpus.

3. The method according to claim 2, wherein said developing the complex-query pattern is performed by iteratively refining the complex-query pattern until search results are produced with a predefined level of recall and precision.

4. The method according to claim 1, wherein said applying the region matching transducer identifies at least one of one or more sequences of delimited strings in the corpus that satisfies at least one pattern defined in the region matching transducer.

5. The method according to claim 4, further including:

developing the corpus index by applying the corpus-level transducer to the corpus for indexing one or more strings identified in the corpus;

the corpus-level transducer following a longest match principle when identifying the one or more strings in the corpus data; and

at least one of the patterns in the corpus-level transducer having an arc that leads from a penultimate state with a transition label that identifies a query tag.

6. The method according to claim 5, wherein the corpus-level transducer shares states between patterns leading to a penultimate state when segments of delimited strings making up two or more patterns overlap.

7. The method according to claim 1, further comprising:

receiving a query with the query tag for querying the corpus; and

applying the query using the corpus index to identify locations in the corpus that satisfy the query.

8. A computer apparatus, comprising:

a memory for storing processing instructions of the apparatus; and

a processor coupled to the memory for executing the processing instructions of the apparatus;

the processor in executing the processing instructions;

receiving in the memory a complex-query pattern, wherein the complex-query pattern identifies a relationship between a plurality of words using a query language;

receiving a corpus;

transforming the complex-query pattern into a region matching transducer, wherein the transducer is a form of a finite state network;

determining whether a corpus index exists;

in response to determining the corpus index does not exist;

combining a corpus-level transducer and the region matching transducer; and

applying the combined transducer to the corpus to identify strings therein that satisfy patterns defined in the corpus-level transducer, including the complex-query pattern, with each identified pattern being recorded in the corpus index;

in response to determining the corpus index exists;

applying the region matching transducer to the corpus to identify strings therein that satisfy the complex-query pattern, with each identified pattern being recorded in an augmented index; and

merging the corpus index with the augmented index specifying locations in the corpus satisfying the complex-query pattern;

storing in the memory the corpus index that records a query tag for indexing locations in the corpus satisfying the complex-query pattern.

9. The apparatus according to claim 8, wherein the processor in executing the processing instructions develops the complex-query pattern using a reduced corpus that contains a portion of the corpus.

10. The apparatus according to claim 8, wherein said applying the region matching transducer identifies at least one of one or more sequences of delimited strings in the corpus that satisfies at least one pattern defined in the region matching transducer.

11. The apparatus according to claim 8, wherein the processor in executing the processing instructions:

receives a query with the query tag for querying the corpus; and

applies the query using the corpus index to identify locations in the corpus that satisfy the query.

12. A computer apparatus, comprising:

a means for storing in a memory a complex-query pattern, wherein the complex-query pattern identifies a relationship between a plurality of words using a query language;

means for receiving a corpus;

means for transforming the complex-query pattern into a region matching transducer, wherein the transducer is a form of a finite state network;

means for determining whether a corpus index exists;

in response to determining the corpus index does not exist;

a means for combining a corpus-level transducer and the region matching transducer; and

a means for applying the combined transducer to a corpus to identify strings therein that satisfy patterns defined in the corpus-level transducer, including the complex-query pattern, with each identified pattern being recorded in a corpus index;

in response to determining the corpus index exists;

a means for applying the region matching transducer to the corpus to identify strings therein that satisfy the complex-query pattern, with each identified pattern being recorded in an augmented index; and

a means for merging the corpus index with the augmented index specifying locations in the corpus satisfying the complex-query pattern;

a means for storing in the memory the corpus index that records a query taq for indexing locations in the corpus satisfying the complex query pattern.

13. The apparatus according to claim 12, further comprising means for developing the complex-query pattern using a reduced corpus that contains a portion of the corpus.

14. The apparatus according to claim 12, wherein said means for applying the region matching transducer identifies at least one of one or more sequences of delimited strings in the corpus that satisfies at least one pattern defined in the region matching transducer.

15. The apparatus according to claim 12, further comprising:

means for receiving a query with the query tag for querying the corpus; and

means for applying the query using the corpus index to identify locations in the corpus that satisfy the query.

16. An article of manufacture comprising a non-transitory media including computer readable instructions embedded therein that causes a computer to perform a method, wherein the method comprises:

receiving in a memory a complex-query pattern, wherein the complex-query pattern identifies a relationship between a plurality of words using a query language;

transforming the complex-query pattern into a region matching transducer, wherein the transducer is a form of a finite state network;

combining a corpus-level transducer and the region matching transducer;

applying the combined transducer to a corpus to identify strings therein that satisfy patterns defined in the corpus-level transducer, including the complex-query pattern, with each identified pattern being recorded in a corpus index;

applying the region matching transducer to the corpus to identify strings therein that satisfy the complex-query pattern, with each identified pattern being recorded in an augmented index;

merging the corpus index with the augmented index specifying locations in the corpus satisfying the complex-query pattern; and

storing in the memory the corpus index that records a query tag for indexing locations in the corpus satisfying the complex-query pattern.

17. The article of manufacture according to claim 16, wherein the method further comprises developing the complex-query pattern using a reduced corpus that contains a portion of the corpus.

18. The article of manufacture according to claim 16, wherein said applying the region matching transducer identifies at least one of one or more sequences of delimited strings in the corpus that satisfies at least one pattern defined in the region matching transducer.

19. The article of manufacture according to claim 16, wherein the method further comprises:

receiving a query with the query tag for querying the corpus; and

applying the query using the corpus index to identify locations in the corpus that satisfy the query.