Loading patent…
AssigneeMicrosoft Corporation
InventorAmit Finkelstein
Estimating the term…
Given a language with all words in a fixed length, and a set of regular expressions composed only from characters in the alphabet of the language or the “?” sign (any single character), the method of the invention defines a data structure that is used to efficiently find the set of matching regular expressions for a given query word. The method may be adjusted by appropriate selection of a control variable to vary the storage space required and the search time necessary to complete the query. Specifically, the method of the present invention provides a space versus time trade-off between the storage space required for the data structures of the present invention and the amount of time to search those data structures to determine the matching set of regular expressions.
In a language using an alphabet having a first number of characters L forming words of a fixed length W, and a second number N of regular expressions composed only from the characters in the alphabet and the ‘?’ sign, a method of finding a set of matching regular expressions associated with a given query word, comprising the steps of:
A computer-readable medium having computer-executable instructions for performing steps, comprising:
A computer-readable medium having stored thereon a first number J of data structures, the first number J corresponding to a division of a fixed word length W required by a language by a selected base B, each data structure having a second number of data fields K, the second number K corresponding to a third number L of different characters in the language raised to the power of the selected base B, each data field containing a bitmap of length N, where N is equal to a fourth number of regular expressions.
Dependencies are inferred from the claim text.