System and method of generating string-based search expressions using templates

• US 20060195421A1
• Filed: 02/25/2005
• Published: 08/31/2006
• Est. Priority Date: 02/25/2005
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Kilroy, John F.
• Granted Patent: US 7,505,985 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Described are a system and method for generating a search expression for use in searching heterogeneous repositories. An application program receives user-supplied input. A template is selected based on a structure of the input. The input is scanned and tokenized. Each token is substituted into one or more locations within the template designated for that token to produce a string-based search expression. The search expression can have logical OR and logical AND operations, parentheses to specify precedence of evaluation, and an infix notation. Templates are modifiable for changing the content of search expressions constructed for a given user input. User-specifiable and user-modifiable aspects include the selecting of particular attributes, operators, and evaluation precedence of template expressions, the tokenizing of user input, the mapping of token sequences to particular templates, and the designation of locations within a selected token expression in which to substitute tokens derived from the user input.

Claims

1. A method for generating a search expression for use in searching heterogeneous repositories, the method comprising:

receiving user-supplied input including one or more search terms;

selecting a template based on a structure of the user-supplied input; and

generating from the user-supplied input a string-based search expression constructed according to the selected template.

2. The method of claim 1, wherein the step of generating the search expression includes scanning the user-supplied input to identify at least one token, and substituting each token into one or more designated locations for that token in an template expression of the selected template.

3. The method of claim 1, wherein the string-based search expression can include logical OR and logical AND Boolean operators.

4. The method of claim 1, wherein the string-based search expression can include parenthetical expressions to indicate precedence of operation.

5. The method of claim 1, wherein the string-based search expression has an infix notation.

6. The method of claim 1, wherein the string-based search expression includes an LDAP (Lightweight Directory Access Protocol) filter expression.

7. The method of claim 1, further comprising specifying, by a user, how to tokenize the user input.

8. The method of claim 7, wherein the step of specifying includes defining one or more special delimiters that can appear in the user input.

9. The method of claim 1, further comprising specifying, by a user, a mapping of particular token sequences to particular templates.

10. The method of claim 1, further comprising specifying, by a user, a manner in which each token that is derived from the user input is applied to a template expression of the selected template.

11. The method of claim 1, further comprising specifying, by a user, at least one of a particular attribute, operator, and evaluation precedence in a template expression of the selected template.

12. A computing system, comprising:

a scanner for receiving user-supplied input having one or more search terms;

at least one template each for defining a search expression; and

an expression generator for selecting a template based on a structure of the user-supplied input and generating from the user-supplied input a string-based search expression constructed according to the selected template.

13. The computing system of claim 12, wherein the scanner identifies at least one token in the user-supplied string and the expression generator substitutes each token into one or more designated locations for that token in the selected template.

14. The computing system of claim 12, wherein each template includes a template expression that is based on a number of tokens and position of zero or more special delimiters in the user input, and wherein the scanner counts tokens in the user-supplied input and the expression generator selects the template with a template expression that is associated with the number of counted tokens and position of zero or more special delimiters in the user input.

15. The computing system of claim 12, wherein the template can be modified to change the string-based search expression that is generated for a given user-supplied input.

16. A computer program product for use with a computer system, the computer program product comprising a computer useable medium having embodied therein program code comprising:

program code for receiving user-supplied input having one or more search terms;

program code for selecting a template based on a structure of the user-supplied input; and

program code for generating from the user-supplied input a string-based search expression constructed according to the selected template.

17. The computer program product of claim 16, further comprising program code for modifying the template to change the string-based search expression that is generated for a given user-supplied input.

18. The computer program product of claim 16, further comprising program code for generating different templates based on a number of tokens and position of zero or more special delimiters in the user input and means for tokenizing the user-supplied input, wherein the program code for selecting selects the template with a template expression that is associated with the number of counted tokens and position of zero or more special delimiters in the user input.

19. A computer data signal embodied in a carrier wave for use with a computer system having a display and capable of generating a user interface through which a user may interact with the computer system, the computer data signal comprising:

program code for receiving user-supplied input having one or more search terms;

program code for selecting a template based on a structure of the user-supplied input; and

program code for generating from the user-supplied input a string-based search expression constructed according to the selected template.

20. The computer data signal of claim 19, wherein the program code for generating includes program code for scanning the user-supplied input to identify at least one token and program code for substituting each token into one or more designated locations for that token in a template expression of the selected template.

21. The computer data signal of claim 19, further comprising program code for modifying the template to change the string-based search expression that is generated for a given user-supplied input.

22. The computer data signal of claim 19, further comprising program code for generating different templates based on a number of tokens and position of zero or more special delimiters in the user input and means for tokenizing the user-supplied input, wherein the program code for selecting selects the template having a template expression associated with the number of counted tokens and position of zero or more special delimiters in the user input.